research-article

A highly write-optimized concurrent B+-tree for persistent memory

Authors:

Zhang XingjunAuthors Info & Claims

Volume 155, Issue C

Pages 219 - 230

https://doi.org/10.1016/j.future.2024.02.008

Published: 18 July 2024 Publication History

Abstract

Writes to persistent memory are considered expensive for the limited naive write performance of the device and the implementation of persist primitives. Write-optimized strategies are widely adopted in designing B+-Trees for persistent memory. In this paper, we concluded two major issues, including successive writes and recovery efficiency, on existing write-optimizing strategies. A highly write-optimized B+-Tree, HW-tree, is proposed to address these issues. HW-tree is constructed with three novel designs including distributed validation, log-free split, and concurrent recovery. Experimental results show that HW-tree can outperform its counterparts by large margins in almost all test workloads. The recovery time for reconstructing the tree can also be reduced by 88%.

Highlights

•

We conducted an in-depth analysis of the existing designs of the B⁺-Tree for PM and identify the potential for improving the write performance of the B⁺-Tree and the endurance of PM.

•

We propose HW-tree customized for PM with several designs to improve the performance of the tree and the endurance of PM.

•

We conducted experiments using state-of-the-art indices, and the results demonstrate that our design can provide significant performance improvements.

References

[1]

Raoux Simone, Burr Geoffrey W., Breitwisch Matthew J., Rettner Charles T., Chen Y.-C., Shelby Robert M., Salinga Martin, Krebs Daniel, Chen S.-H., Lung H.-L., et al., Phase-change random access memory: A scalable technology, IBM J. Res. Dev. 52 (4.5) (2008) 465–479.

Digital Library

[2]

Apalkov Dmytro, Khvalkovskiy Alexey, Watts Steven, Nikitin Vladimir, Tang Xueti, Lottis Daniel, Moon Kiseok, Luo Xiao, Chen Eugene, Ong Adrian, et al., Spin-transfer torque magnetic random access memory (STT-MRAM), ACM J. Emerg. Technol. Comput. Syst. (JETC) 9 (2) (2013) 1–35.

[3]

Baek I.G., Lee M.S., Seo S., Lee M.J., Seo D.H., Suh D.-S., Park J.C., Park S.O., Kim H.S., Yoo I.K., et al., Highly scalable nonvolatile resistive memory using simple binary oxide driven by asymmetric unipolar voltage pulses, in: IEDM Technical Digest. IEEE International Electron Devices Meeting, 2004, IEEE, 2004, pp. 587–590.

[4]

Ismail Oukid, Johan Lasperas, Anisoara Nica, Thomas Willhalm, Wolfgang Lehner, FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory, in: Proceedings of the 2016 International Conference on Management of Data, 2016, pp. 371–386.

[5]

Chen Shimin, Jin Qin, Persistent b+-trees in non-volatile main memory, Proc. VLDB Endow. 8 (7) (2015) 786–797.

Digital Library

[6]

Jun Yang, Qingsong Wei, Cheng Chen, Chundong Wang, Khai Leong Yong, Bingsheng He, NV-Tree: Reducing Consistency Cost for NVM-based Single Level Systems., in: FAST, Vol. v, 2015, pp. 167–181.

[7]

Zhou Xinjing, Shou Lidan, Chen Ke, Hu Wei, Chen Gang, DPTree: differential indexing for persistent memory, Proc. VLDB Endow. 13 (4) (2019) 421–434.

[8]

Wook-Hee Kim, R. Madhava Krishnan, Xinwei Fu, Sanidhya Kashyap, Changwoo Min, PACTree: A high performance persistent range index using PAC guidelines, in: Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles, 2021, pp. 424–439.

[9]

Guide Part, Intel® 64 and ia-32 architectures software developer’s manual, Volume 3B: System programming Guide, Part, vol. 2, 2011.

[10]

Jeremy Condit, Edmund B. Nightingale, Christopher Frost, Engin Ipek, Benjamin Lee, Doug Burger, Derrick Coetzee, Better I/O through byte-addressable, persistent memory, in: Proceedings of the ACM SIGOPS 22nd Symposium on Operating Systems Principles, 2009, pp. 133–146.

[11]

Pelley Steven, Chen Peter M., Wenisch Thomas F., Memory persistency, ACM SIGARCH Comput. Archit. News 42 (3) (2014) 265–276.

[12]

Beeler Brian, Intel optane DC persistent memory module (PMM), Retrieved March 11 (2019) 2021.

[13]

Izraelevitz Joseph, Yang Jian, Zhang Lu, Kim Juno, Liu Xiao, Memaripour Amirsaman, Soh Yun Joon, Wang Zixuan, Xu Yi, Dulloor Subramanya R., et al., Basic performance measurements of the intel optane DC persistent memory module, 2019, arXiv preprint arXiv:1903.05714.

[14]

Ivy B. Peng, Maya B. Gokhale, Eric W. Green, System evaluation of the intel optane byte-addressable nvm, in: Proceedings of the International Symposium on Memory Systems, 2019, pp. 304–315.

[15]

Jian Yang, Juno Kim, Morteza Hoseinzadeh, Joseph Izraelevitz, Steve Swanson, An empirical guide to the behavior and use of scalable persistent memory, in: 18th USENIX Conference on File and Storage Technologies, FAST 20, 2020, pp. 169–182.

[16]

Samsung Corporation, Samsung electronics unveils far-reaching, next-generation memory solutions at flash memory summit 2022, 2022, https://bit.ly/3SbMDvU.

[17]

Samsung Corporation, Samsung electronics introduces industry’s first 512GB CXL memory module, 2022, https://bit.ly/3P66knr.

[18]

Liu Jihang, Chen Shimin, Wang Lujun, Lb+ trees: Optimizing persistent index performance on 3DXPoint memory, Proc. VLDB Endow. 13 (7) (2020) 1078–1090.

[19]

Deukyeon Hwang, Wook-Hee Kim, Youjip Won, Beomseok Nam, Endurable Transient Inconsistency in {Byte-Addressable} Persistent {B+-Tree}, in: 16th USENIX Conference on File and Storage Technologies, FAST 18, 2018, pp. 187–200.

[20]

Moinuddin K. Qureshi, John Karidis, Michele Franceschini, Vijayalakshmi Srinivasan, Luis Lastras, Bulent Abali, Enhancing lifetime and security of PCM-based main memory with start-gap wear leveling, in: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture, 2009, pp. 14–23.

[21]

Wilcox Matthew, Add support for NV-DIMMs to ext4, 2014, URL https://lwn.net/Articles/613384.

[22]

Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, Russell Sears, Benchmarking cloud serving systems with YCSB, in: Proceedings of the 1st ACM Symposium on Cloud Computing, 2010, pp. 143–154.

[23]

Lersch Lucas, Hao Xiangpeng, Oukid Ismail, Wang Tianzheng, Willhalm Thomas, Evaluating persistent memory range indexes, Proc. VLDB Endow. 13 (4) (2019) 574–587.

[24]

Shaonan Ma, Kang Chen, Shimin Chen, Mengxing Liu, Jianglang Zhu, Hongbo Kang, Yongwei Wu, {ROART}: Range-query Optimized Persistent {ART}, in: 19th USENIX Conference on File and Storage Technologies, FAST 21, 2021, pp. 1–16.

[25]

Chen Youmin, Lu Youyou, Fang Kedong, Wang Qing, Shu Jiwu, uTree: a persistent B+-tree with low tail latency, Proc. VLDB Endow. 13 (12) (2020) 2634–2648.

[26]

Shivaram Venkataraman, Niraj Tolia, Parthasarathy Ranganathan, Roy H. Campbell, Consistent and Durable Data Structures for {Non-Volatile}{Byte-Addressable} Memory, in: 9th USENIX Conference on File and Storage Technologies, 2011, FAST 11.

[27]

Se Kwon Lee, K. Hyun Lim, Hyunsub Song, Beomseok Nam, Sam H. Noh, {WORT}: Write optimal radix tree for persistent memory storage systems, in: 15th USENIX Conference on File and Storage Technologies, FAST 17, 2017, pp. 257–270.

[28]

Zhangyu Chen, Yu Hua, Bo Ding, Pengfei Zuo, Lock-free concurrent level hashing for persistent memory, in: 2020 USENIX Annual Technical Conference, USENIX ATC 20, 2020, pp. 799–812.

[29]

Moohyeon Nam, Hokeun Cha, Young-ri Choi, Sam H. Noh, Beomseok Nam, {Write-Optimized} Dynamic Hashing for Persistent Memory, in: 17th USENIX Conference on File and Storage Technologies, FAST 19, 2019, pp. 31–44.

[30]

Lu Baotong, Hao Xiangpeng, Wang Tianzheng, Lo Eric, Dash: Scalable hashing on persistent memory, 2020, arXiv preprint arXiv:2003.07302.

[31]

Zuriel Yoav, Friedman Michal, Sheffi Gali, Cohen Nachshon, Petrank Erez, Efficient lock-free durable sets, Proc. ACM Program. Lang. 3 (OOPSLA) (2019) 1–26.

[32]

Benson Lawrence, Makait Hendrik, Rabl Tilmann, Viper: An efficient hybrid pmem-dram key-value store, Proc. VLDB Endow. 14 (9) (2021) 1544–1556.

[33]

Daokun Hu, Zhiwen Chen, Wenkui Che, Jianhua Sun, Hao Chen, Halo: A hybrid PMem-DRAM persistent hash index with fast recovery, in: Proceedings of the 2022 International Conference on Management of Data, 2022, pp. 1049–1063.

Recommendations

Flash-optimized B+-tree

With the rapid increasing capacity of flash memory, flash-aware indexing techniques are highly desirable for flash devices. The unique features of flash memory, such as the erase-before-write constraint and the asymmetric read/write cost, severely ...
Crash recoverable ARMv8-oriented B+-tree for byte-addressable persistent memory
LCTES 2019: Proceedings of the 20th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems

The byte-addressable non-volatile memory (NVM) promises persistent memory. Concretely, ARM processors have incorporated architectural supports to utilize NVM. In this paper, we consider tailoring the important B+-tree for NVM operated by a 64-bit ARMv8 ...
WOBTree: a write-optimized B+-tree for non-volatile memory
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Future Generation Computer Systems

Future Generation Computer Systems Volume 155, Issue C

Jun 2024

486 pages

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 18 July 2024

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents