Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2021, Vol. 15 Issue (5) : 155106    https://doi.org/10.1007/s11704-020-0228-1
RESEARCH ARTICLE
WOBTree: a write-optimized B+-tree for non-volatile memory
Haitao WANG1,2,3, Zhanhuai LI1,2,3(), Xiao ZHANG1,2,3, Xiaonan ZHAO1,2,3, Song JIANG4
1. School of Computer Science and Engineering, Northwestern Polytechnical University, Xi’An 710072, China
2. Key Laboratory of Big Data Storage and Management, Northwestern Polytechnical University, Ministry of Industry and Information Technology, Xi’An 710072, China
3. National Engineering Laboratory for Integrated Aero-Space-Ground-Ocean Big Data Application Technology, Xi’An 710072, China
4. Department of Computer Science and Engineering, University of Texas at Arlington, Arlington, TX 76010, USA
 Download: PDF(1905 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

The emergence of non-volatile memory (NVM) has introduced new opportunities for performance optimizations in existing storage systems. To better utilize its byte-addressability and near-DRAM performance, NVM can be attached on the memory bus and accessed via load/store memory instructions rather than the conventional block interface. In this scenario, a cache line (usually 64 bytes) becomes the data transfer unit between volatile and non-volatile devices. However, the failureatomicity of write on NVM is the memory bit width (usually 8 bytes). This mismatch between the data transfer unit and the atomicity unit may introduce write amplification and compromise data consistency of node-based data structures such as B+-trees. In this paper, we propose WOBTree, a Write-Optimized B+-Tree for NVM to address the mismatch problem without expensive logging. WOBTree minimizes the update granularity from a tree node to a much smaller subnode and carefully arranges the write operations in it to ensure crash consistency and reduce write amplification. Experimental results show that compared with previous persistent B+-tree solutions, WOBTree reduces the write amplification by up to 86× and improves write performance by up to 61× while maintaining similar search performance.

Keywords non-volatile memory      B+-tree      atomic granularity mismatch      write amplification      performance optimization     
Corresponding Author(s): Zhanhuai LI   
Just Accepted Date: 16 March 2021   Issue Date: 30 August 2021
 Cite this article:   
Haitao WANG,Zhanhuai LI,Xiao ZHANG, et al. WOBTree: a write-optimized B+-tree for non-volatile memory[J]. Front. Comput. Sci., 2021, 15(5): 155106.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-020-0228-1
https://academic.hep.com.cn/fcs/EN/Y2021/V15/I5/155106
1 S Mittal, J S Vetter. A survey of software techniques for using non-volatile memories for storage and main memory systems. IEEE Transactions on Parallel and Distributed Systems, 2015, 27(5): 1537–1550
https://doi.org/10.1109/TPDS.2015.2442980
2 D Li, X Liao, H Jin, Y Tang, G Zhao.Writeback throttling in a virtualized system with SCM. Frontiers of Computer Science, 2016, 10(1): 82–95
https://doi.org/10.1007/s11704-015-4217-8
3 R Barber, P Bendel, M Czech, O Draese, F Ho, N Hrle, S Idreos, M Kim, O Koeth, J Lee, T T Li, G M Lohman, K Morfonios, R Müller , K Murthy, I Pandis, L Qiao, V Raman, S Szabo, R Sidle, K Stolze. Blink: not your father’s database! In: Proceedings of the 37th International Conference on Very Large Databases. 2011, 1–22
https://doi.org/10.1007/978-3-642-33500-6_1
4 C Diaconu, C Freedman, E Ismert, P Larson, P Mittal, R Stonecipher, N Verma, M Zwilling. Hekaton: SQL server’s memory-optimized OLTP engine. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013, 1243–1254
https://doi.org/10.1145/2463676.2463710
5 H Plattner. The impact of columnar in-memory databases on enterprise systems. Proceedings of the VLDB Endowment, 2014, 7(13): 1722–1729
https://doi.org/10.14778/2733004.2733074
6 R Nishtala, H Fugal, S Grimm, M Kwiatkowski, H Lee, H C Li, R McElroy, M Paleczny, D Peek, P Saab, D Stafford, T Tung, V Venkataramani. Scaling memcache at facebook. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. 2013, 385–398
7 J K Ousterhout, P Agrawal, D Erickson, C Kozyrakis, J Leverich, D Mazières, S Mitra, A Narayanan, GM Parulkar, M Rosenblum, S M Rumble, E Stratmann, R Stutsman. The case for ramclouds: scalable highperformance storage entirely in dram. ACM SIGOPS Operating Systems Review, 2010, 43(4): 92–105
https://doi.org/10.1145/1713254.1713276
8 M Zaharia, M Chowdhury, T Das, A Dave, J Ma, M McCauly, M J Franklin, S Shenker, I Stoica. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. 2012, 15–28
9 S Chen, Q Jin. Persistent B+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 2015, 8(7): 786–797
https://doi.org/10.14778/2752939.2752947
10 J Condit, E B Nightingale, C Frost, E Ipek, B C Lee, D Burger, D Coetzee. Better I/O through byte-addressable, persistent memory. In: Proceedings of the 22nd ACM Symposium on Operating Systems Principles. 2009, 133–146
https://doi.org/10.1145/1629575.1629589
11 D Hwang, W Kim, Y Won, B Nam. Endurable transient inconsistency in byte-addressable persistent B+-tree. In: Proceedings of the 16th USENIX Conference on File and Storage Technologies. 2018, 187–200
12 P Götze, S Baumann, K Sattler. An NVM-aware storage layout for analytical workloads. In: Proceedings of the 34th IEEE International Conference on Data Engineering Workshops. 2018, 110–115
13 S K Lee, K H Lim, H Song, B Nam, S H Noh. Wort: write optimal radix tree for persistent memory storage systems. In: Proceedings of the 15th USENIX Conference on File and Storage Technologies. 2017, 257–270
14 A Danowitz, K Kelley, J Mao, J P Stevenson, M Horowitz. CPU DB: recording microprocessor history. Communications of the ACM, 2012, 55(4): 55–63
https://doi.org/10.1145/2133806.2133822
15 J Yang, Q Wei, C Chen, C Wang, K L Yong, B He. Nv-tree: reducing consistency cost for nvm-based single level systems. In: Proceedings of the 13th USENIX Conference on File and Storage Technologies. 2015, 167–181
16 I Oukid, J Lasperas, A Nica, T Willhalm, W Lehner . Fptree: a hybrid scmdram persistent and concurrent b-tree for storage class memory. In: Proceedings of the 2016 International Conference on Management of Data. 2016, 371–386
https://doi.org/10.1145/2882903.2915251
17 S Rixner, W J Dally, U J Kapasi, P R Mattson, J D Owens. Memory access scheduling. In: Proceedings of the 27th International Symposium on Computer Architecture. 2000, 128–138
https://doi.org/10.1145/342001.339668
18 Y Wang, M Kapritsos, Z Ren, P Mahajan, J Kirubanandam, L Alvisi, M Dahlin. Robustness in the salus scalable block store. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. 2013, 357–370
19 I Moraru, D G Andersen, M Kaminsky, N Tolia, P Ranganathan, N L Binkert. Consistent, durable, and safe memory management for byteaddressable non volatile main memory. In: Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems. 2013, 1–17
https://doi.org/10.1145/2524211.2524216
20 H Volos, G Magalhaes, L Cherkasova, J Li. Quartz: a lightweight performance emulator for persistent memory software. In: Proceedings of the 16th Annual Middleware Conference. 2015, 37–49
https://doi.org/10.1145/2814576.2814806
21 J Arulraj, A Pavlo, S Dulloor. Let’s talk about storage & recovery methods for non-volatile memory database systems. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015, 707–722
https://doi.org/10.1145/2723372.2749441
22 W Kim, J Kim, W Baek, B Nam, Y Won. NVWAL: exploiting nvram in write-ahead logging. ACM SIGOPS Operating Systems Review, 2016, 50(2): 385–398
https://doi.org/10.1145/2954680.2872392
23 A Chen. A review of emerging non-volatile memory (NVM) technologies and applications. Solid-state Electronics, 2016, 125(Nov): 25–38
https://doi.org/10.1016/j.sse.2016.07.006
[1] Article highlights Download
[1] Xin YOU, Hailong YANG, Zhongzhi LUAN, Depei QIAN. Accelerating the cryo-EM structure determination in RELION on GPU cluster[J]. Front. Comput. Sci., 2022, 16(3): 163102-.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed