We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 36 Issue 1
January  2021
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Supplements
Heng Bu, Ming-Kai Dong, Ji-Fei Yi, Bin-Yu Zang, Hai-Bo Chen. Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory[J]. Journal of Computer Science and Technology, 2021, 36(1): 140-157. DOI: 10.1007/s11390-020-9871-0
Citation: Heng Bu, Ming-Kai Dong, Ji-Fei Yi, Bin-Yu Zang, Hai-Bo Chen. Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory[J]. Journal of Computer Science and Technology, 2021, 36(1): 140-157. DOI: 10.1007/s11390-020-9871-0
shu

Revisiting Persistent Indexing Structures on Intel Optane DC Persistent Memory

  • Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai 200240, China

Funds: This work is supported in part by the National Key Research and Development Program under Grant No. 2016YFB1000104, the National Natural Science Foundation of China under Grant No. 61672345, and the HighTech Support Program from Shanghai Committee of Science and Technology under Grant No. 19511121100.
More Information
  • Author Bio:

    Heng Bu received his B.S. degree in software engineering from Nanjing University, Nanjing, in 2017. He is a Master student of the Institute of Parallel and Distributed Systems, Shanghai Jiao Tong University, Shanghai. His research interests include non-volatile memory, file systems and concurrent data structures.

  • Corresponding author:

    Hai-Bo Chen E-mail: haibocheng@sjtu.edu.cn

  • Received Date: July 20, 2019
  • Revised Date: February 14, 2020
  • Published Date: January 04, 2021
    Abstract
  • Persistent indexing structures are proposed in response to emerging non-volatile memory (NVM) to provide high performance yet durable indexes. However, due to the lack of real NVM hardware, many prior persistent indexing structures were evaluated via emulation, which varies a lot across different setups and differs from the real deployment. Recently, Intel has released its Optane DC Persistent Memory Module (PMM), which is the first production-ready NVM. In this paper, we revisit popular persistent indexing structures on PMM and conduct comprehensive evaluations to study the performance differences among persistent indexing structures, including persistent hash tables and persistent trees. According to the evaluation results, we find that Cacheline-Conscious Extendible Hashing (CCEH) achieves the best performance among all evaluated persistent hash tables, and Failure-Atomic ShifT B+-Tree (FAST) and Write Optimal Radix Tree (WORT) perform better than other trees. Besides, we find that the insertion performance of hash tables is heavily influenced by data locality, while the insertion latency of trees is dominated by the flush instructions. We also uncover that no existing emulation methods accurately simulate PMM for all the studied data structures. Finally, we provide three suggestions on how to fully utilize PMM for better performance, including using clflushopt/clwb with sfence instead of clflush, flushing continuous data in a batch, and avoiding data access immediately after it is flushed to PMM.
    • FullText(HTML)
    • References (33)
  • [1]
    Kannan S, Bhat N, Gavrilovska A, Arpaci-Dusseau A, Arpaci-Dusseau R. Redesigning LSMs for nonvolatile memory with NoveLSM. In Proc. the 2018 USENIX Annual Technical Conference, July 2018, pp.993-1005.
    [2]
    Liu S, Wei Y, Zhao J, Kolli A, Khan S. PMTest:A fast and flexible testing framework for persistent memory programs. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.411-425. DOI: 10.1145/3297858.3304015.
    [3]
    Xu J, Kim J, Memaripour A, Swanson S. Finding and fixing performance pathologies in persistent memory software stacks. In Proc. the 24th International Conference on Architectural Support for Programming Languages and Operating Systems, Apr. 2019, pp.427-439. DOI: 10.1145/3297858.3304077.
    [4]
    Xia F, Jiang D J, Xiong J, Sun N H. A survey of phase change memory systems. Journal of Computer Science and Technology, 2015, 30(1):121-144. DOI:10.1007/s11390- 015-1509-2.
    [5]
    Zuo P, Hua Y. A write-friendly hashing scheme for nonvolatile memory systems. In Proc. the 33rd International Conference on Massive Storage Systems and Technology, May 2017.
    [6]
    Zuo P, Hua Y, Wu J. Write-optimized and highperformance hashing index scheme for persistent memory. In Proc. the 13th USENIX Symposium on Operating Systems Design and Implementation, Oct. 2018, pp.461-476.
    [7]
    Nam M, Cha H, Choi Y R, Noh S H, Nam B. Write-optimized dynamic hashing for persistent memory. In Proc. the 17th USENIX Conference on File and Storage Technologies, Feb. 2019, pp.31-44. DOI: 10.5555/3323298.3323302.
    [8]
    Yang J, Wei Q, Chen C, Wang C, Yong K L, He B. NV-Tree:Reducing consistency cost for NVM-based single level systems. In Proc. the 13th USENIX Conference on File and Storage Technologies, Feb. 2015, pp.167-181. DOI: 10.5555/2750482.2750495.
    [9]
    Chen S Jin Q. Persistent B+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 2015, 8(7):786-797. DOI: 10.14778/2752939.2752947.
    [10]
    Lee S K, Lim K H, Song H, Nam B, Noh S H. WORT:Write optimal radix tree for persistent memory storage systems. In Proc. the 15th USENIX Conference on File and Storage Technologies, Feb. 2017, pp.257-270.
    [11]
    Hwang D, Kim W H, Won Y, Nam B. Endurable transient inconsistency in byte-addressable persistent B+-tree. In Proc. the 16th USENIX Conference on File and Storage Technologies, Feb. 2018, pp.187-200.
    [12]
    Burr G W, Breitwisch M J, Franceschini M et al. Phase change memory technology. Journal of Vacuum Science & Technology B, 2010, 28(2):223-262. DOI: 10.1116/1.3301579.
    [13]
    Apalkov D, Khvalkovskiy A, Watts S et al. Spintransfer torque magnetic random access memory (STTMRAM). ACM Journal on Emerging Technologies in Computing Systems, 2013, 9(2):Article No. 13. DOI: 10.1145/2463585.2463589.
    [14]
    Yang J J, Williams R S. Memristive devices in computing system:Promises and challenges. ACM Journal on Emerging Technologies in Computing Systems, 2013, 9(2):Article No. 11. DOI: 10.1145/2463585.2463587.
    [15]
    Zuo P, Hua Y, Zhao M, Zhou W, Guo Y. Improving the performance and endurance of encrypted non-volatile main memory through deduplicating writes. In Proc. the 51st Annual IEEE/ACM International Symposium on Microarchitecture, Oct. 2018, pp.442-454. DOI: 10.1109/MICRO.2018.00043.
    [16]
    Rudoff A. Persistent memory programming. Login, 2017, 42(2):34-40.
    [17]
    Xu J, Swanson S. NOVA:A log-structured file system for hybrid volatile/non-volatile main memories. In Proc. the 14th USENIX Conference on File and Storage Technologies, Feb. 2016, pp.323-338.
    [18]
    Rao D S, Kumar S, Keshavamurthy A, Lantz P, Reddy D, Sankaran R, Jackson J. System software for persistent memory. In Proc. the 9th European Conference on Computer Systems, Apr. 2014, Article No. 15. DOI: 10.1145/2592798.2592814.
    [19]
    Dong M, Chen H. Soft updates made simple and fast on non-volatile memory. In Proc. the 2017 USENIX Annual Technical Conference, Jul. 2017, pp.719-731.
    [20]
    Kwon Y, Fingler H, Hunt T, Peter S, Witchel E, Anderson T. Strata:A cross media file system. In Proc. the 26th Symposium on Operating Systems Principles, Oct. 2017, pp.460-477. DOI: 10.1145/3132747.3132770.
    [21]
    Volos H, Nalli S, Panneerselvam S, Varadarajan V, Saxena P, Swift M M. Aerie:Flexible file-system interfaces to storage-class memory. In Proc. the 9th European Conference on Computer Systems, Apr. 2014, Article No. 14. DOI: 10.1145/2592798.2592810.
    [22]
    Dong M, Bu H, Yi J, Dong B, Chen H. Performance and protection in the ZoFS user-space NVM file system. In Proc. the 27th ACM Symposium on Operating Systems Principles, Oct. 2019, pp.478-493. DOI: 10.1145/3341301.3359637.
    [23]
    Bhandari K, Chakrabarti D R, Boehm H J. Makalu:Fast recoverable allocation of non-volatile memory. ACM SIGPLAN Notices, 2016, 51(10):677-694. DOI: 10.1145/3022671.2984019.
    [24]
    Flajolet P, Poblete P, Viola A. On the analysis of linear probing hashing. Algorithmica, 1998, 22(4):490-515. DOI: 10.1007/PL00009236.
    [25]
    Pagh R, Rodler F F. Cuckoo hashing. Journal of Algorithms, 2004, 51(2):122-144. DOI:10.1016/j.jalgor.20- 03.12.002.
    [26]
    Ellis C S. Extendible hashing for concurrent operations and distributed data. In Proc. the 2nd ACM SIGACTSIGMOD Symposium on Principles of Database Systems, March 1983, pp.106-116. DOI: 10.1145/588058.588072.
    [27]
    Oukid I, Lasperas J, Nica A, Willhalm T, Lehner W. FPTree:A hybrid SCM-DRAM persistent and concurrent Btree for storage class memory. In Proc. the 2016 International Conference on Management of Data, June 2016, pp.371-386. DOI: 10.1145/2882903.2915251.
    [28]
    Sha E H M, Jiang W, Dong H, Ma Z, Zhang R, Chen X, Zhuge Q. Towards the design of efficient and consistent index structure with minimal write activities for non-volatile memory. IEEE Transactions on Computers, 2017, 67(3):432-448. DOI: 10.1109/TC.2017.2754381.
    [29]
    Volos H, Magalhaes G, Cherkasova L, Li J. Quartz:A lightweight performance emulator for persistent memory software. In Proc. the 16th Annual Middleware Conference, Nov. 2015, pp.37-49. DOI: 10.1145/2814576.2814806.
    [30]
    Leis V, Kemper A, Neumann T. The adaptive radix tree:ARTful indexing for main-memory databases. In Proc. the 29th International Conference on Data Engineering, April 2013, pp.38-49. DOI: 10.1109/ICDE.2013.6544812.
    [31]
    Evans J. A scalable concurrent malloc (3) implementation for FreeBSD. In Proc. the 2006 BSDCan Conference, May 2006.
    [32]
    Viswanathan K. Intel corporation. Intel memory latency checker v3.7. https://software.intel.com/en-us/articles/intelr-memory-latency-checker, Feb. 2020.
    [33]
    Izraelevitz J, Yang J, Zhang L et al. Basic performance measurements of the Intel Optane DC persistent memory module. arXiv:1903.05714, 2019. https://arxiv.org/pdf/1903.05714v3.pdf, Oct. 2020.
    • Relative Articles

  • Related Articles

    [1]Ying Wang, Wen-Qing Jia, De-Jun Jiang, Jin Xiong. A Survey of Non-Volatile Main Memory File Systems[J]. Journal of Computer Science and Technology, 2023, 38(2): 348-372. DOI: 10.1007/s11390-023-1054-3
    [2]Michèle Weiland, Bernhard Homölle. Usage Scenarios for Byte-Addressable Persistent Memory in High-Performance and Data Intensive Computing[J]. Journal of Computer Science and Technology, 2021, 36(1): 110-122. DOI: 10.1007/s11390-020-0776-8
    [3]Kai Wu, Dong Li. Unimem: Runtime Data Management on Non-Volatile Memory-Based Heterogeneous Main Memory for High Performance Computing[J]. Journal of Computer Science and Technology, 2021, 36(1): 90-109. DOI: 10.1007/s11390-020-0942-z
    [4]Hai-Kun Liu, Di Chen, Hai Jin, Xiao-Fei Liao, Binsheng He, Kan Hu, Yu Zhang. A Survey of Non-Volatile Main Memory Technologies: State-of-the-Arts, Practices, and Future Directions[J]. Journal of Computer Science and Technology, 2021, 36(1): 4-32. DOI: 10.1007/s11390-020-0780-z
    [5]Yun Liang, Shuo Wang. Performance-Centric Optimization for Racetrack Memory Based Register File on GPUs[J]. Journal of Computer Science and Technology, 2016, 31(1): 36-49. DOI: 10.1007/s11390-016-1610-1
    [6]Fei Xia, De-Jun Jiang, Jin Xiong, Ning-Hui Sun. A Survey of Phase Change Memory Systems[J]. Journal of Computer Science and Technology, 2015, 30(1): 121-144. DOI: 10.1007/s11390-015-1509-2
    [7]Qi Wang, Jia-Rui Li, Dong-Hui Wang. Improving the Performance and Energy Efficiency of Phase Change Memory Systems[J]. Journal of Computer Science and Technology, 2015, 30(1): 110-120. DOI: 10.1007/s11390-015-1508-3
    [8]Hai-Bo Chen, Feng-Zhe Zhang, Rong Chen, Bin-Yu Zang, Pen-Chung Yew. Mercury: Combining Performance with Dependability Using Self-Virtualization[J]. Journal of Computer Science and Technology, 2012, 27(1): 92-104. DOI: 10.1007/s11390-012-1208-1
    [9]Gang Huang, Li Zhou, Xuan-Zhe Liu, Hong Mei, Shing-Chi Cheung. Performance Aware Service Pool in Dependable Service Oriented Architecture[J]. Journal of Computer Science and Technology, 2006, 21(4): 565-573.
    [10]Ben Leslie, Peter Chubb, Nicholas Fitzroy-Dale, Stefan Gotz, Charles Gray, Luke Macpherson, Daniel Potts, Yue-Ting Shen, Kevin Elphinstone. User-Level Device Drivers: Achieved Performance[J]. Journal of Computer Science and Technology, 2005, 20(5): 654-664.
    • Supplements (2)

  • Others

  • Cited by

    Periodical cited type(5)

    1. Manolis Katsaragakis, Christos Baloukas, Lazaros Papadopoulos, et al. Performance, Energy and NVM Lifetime-Aware Data Structure Refinement and Placement for Heterogeneous Memory Systems. ACM Transactions on Architecture and Code Optimization, 2025. DOI:10.1145/3736174
    2. Xianyu He, Chaoshu Yang, Runyu Zhang, et al. Optimizing both performance and tail latency for B+tree on persistent memory. Journal of Systems Architecture, 2025, 163: 103406. DOI:10.1016/j.sysarc.2025.103406
    3. Xianli Zhao, Zhenlong Hu. Research on an evaluation index system of critical emergency management capability based on machine learning in a complex scientific environment. Frontiers in Ecology and Evolution, 2023, 11 DOI:10.3389/fevo.2023.1176872
    4. Xianyu He, Runyu Zhang, Pengpeng Tian, et al. A Write-Optimized PM-oriented B+-tree with Aligned Flush and Selective Migration. 2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom), DOI:10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00135
    5. Gal Sela, Erez Petrank. Durable Queues. Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, DOI:10.1145/3409964.3461791

    Other cited types(0)

Catalog

    Get Citation
    PDF
    XML
    Read Online
    Article views (85) PDF downloads (0) Cited by(5)
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return