Heterogeneous Index for Non-volatile Memory
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [31]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Non-volatile memory (NVM) introduces new opportunities to data storage and management, but it also requires existing indices to be revisited according to the properties of NVM. This study, based on the access characteristics of NVM, focuses on the performance optimization of the access, persistence, range query, and other operations of tree indexes on NVM. A two-layer heterogeneous index called HART is presented. HART takes advantage of the high range query performance of the B+-tree and the fast node search speed of the Radix tree. The index structure is redesigned and the strategy of path compression for the Radix tree is improved. Moreover, a write-efficient node is proposed for NVM and the Radix leaf nodes together with a link are stored. The experiments are conducted on both simulated NVM and real Intel Optane persistent memory modules and different variants of HART are compared to several existing NVM indices. The results show that HART achieves better performance for point queries and writes than existing B+tree-like indices. In addition, it outperforms the existing Radix-tree-based WOART index in range query performance. As a result, HART can deliver high overall performance.

    Reference
    [1] Kultursay E, Kandemir M, Sivasubramaniam A, et al. Evaluating STT-RAM as an energy-efficient main memory alternative. In: Proc. of the ISPASS. 2013. 256-267.
    [2] Mao M, Cao Y, Yu S, et al. Optimizing latency, energy, and relia-bility of 1T1R ReRAM through cross-layer techniques. IEEE Journal of Emerging and Selected Topics in Circuits and Systems, 2016, 6(3):352-363.
    [3] Yang J, Williams R. Memristive devices in computing system:Promises and challenges. ACM Journal on Emerging Technologies in Computing Systems, 2013, 9(2):Article No.11.
    [4] Raoux S, Burr G, Breitwisch M, et al. Phase-change random access memory:A scalable technology. IBM Journal of Research and Development, 2008, 52(4-5):465-480.
    [5] Song S, Das A, Mutlu O, et al. Improving phase change memory performance with data content aware access, In:Proc. of the ISMM. 2020. 30-47.
    [6] Izraelevitz J, Yang J, Zhang L, et al. Basic performance measurements of the Intel Optane DC persistent memory module. CoRR abs/1903.05714, 2019.
    [7] Chen S, Jin Q. Persistent B+-trees in non-volatile main memory. Proc. of the VLDB Endowment, 2015, 8(7):786-797.
    [8] Kim W, Seo J, Kim J, et al. clfB-tree:Cacheline friendly persistent B-tree for NVRAM. ACM Trans. on Storage, 2018, 14(1): Article No.5.
    [9] Chi P, Lee W, Xie Y. Adapting B+-tree for emerging nonvolatile memory-based main memory. IEEE Trans. on Computer-aided Design of Integrated Circuits and Systems, 2016, 35(9):1461-1474.
    [10] Chen Q, Yeom H. Design of skiplist based key-value store on non-volatile memory. In:Proc. of the ICAC. 2018. 44-50.
    [11] Lee S, Lim K, Song H, et al. WOART:Write optimal radix tree for persistent memory storage systems. In:Proc. of the FAST. 2017. 257-270.
    [12] Ma S, Chen K, Chen S, et al. ROART:Range-query optimized persistent ART. In:Proc. of the FAST. 2021. 1-16.
    [13] Ying Y, Huang K, Zheng S, et al. CANRT:A client-active NVM-based radix tree for fast remote access. In:Proc. of the ICA3PP. 2020. 433-447.
    [14] Leis V, Kemper A, Neumann T. The adaptive radix tree:Artful indexing for main-memory databases. In:Proc. of the ICDE. 2013. 38-49.
    [15] Liu R, Jin P, Wang X, et al. NVlevel:A high performance key-value store for non-volatile memory. In:Proc. of the HPCC/SmartCity/DSS. 2019. 1020-1027.
    [16] Zhang X, Feng D, Hua Y, et al. A write-efficient and consistent hashing scheme for non-volatile memory. In:Proc. of the ICPP. 2018.
    [17] Zuo P, Hua Y, Wu J. Write-optimized and high-performance hashing index scheme for persistent memory. In:Proc. of the OSDI. 2018. 461-476.
    [18] Wan H, Li F, Zhou Z, et al. NVLH:Crash-consistent linear hashing for non-volatile memory. In:Proc. of the NVMSA. 2018. 117-118.
    [19] Xia F, Jiang D, Xiong J, et al. HiKV:A hybrid index key-value store for DRAM-NVM memory systems. In:Proc. of the ATC. 2017. 349-362.
    [20] Venkataraman S, Tolia N, Ranganathan P, et al. Consistent and durable data structures for non-volatile byte-addressable memory. In:Proc. of the FAST. 2011. 61-75.
    [21] Hwang D, Kim W, Won Y, et al. Endurable transient inconsistency in byte-addressable persistent B+-tree. In:Proc. of the FAST. 2018. 187-200.
    [22] Yang J, Wei Q, Wang C, et al. NV-tree:A consistent and workload-adaptive tree structure for non-volatile memory. IEEE Trans. on Computers, 2016, 65(7):2169-2183.
    [23] Oukid I, Lasperas J, Nica A, et al. FPtree:A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In: Proc. of the SIGMOD. 2016. 371-386.
    [24] Jeong J, Hong J, Maeng S, et al. Unbounded hardware transactional memory for a hybrid DRAM/NVM memory system. In:Proc. of the MICRO. 2020. 525-538.
    [25] Zhou X, Shou L, Chen K, et al. DPtree:Differential indexing for persistent memory. Proc. of the VLDB Endowment, 2019, 13(4): 421-434.
    [26] O'Neil P, Cheng E, Gawlick D, et al. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33(4):351-385.
    [27] Han S, Jiang D, Xiong J. LightKV:A cross media key value store with persistent memory to cut long tail latency. In:Proc. of the MSST. 2020.
    [28] Liu J, Chen S, Wang L. LB+-trees:Optimizing persistent index performance on 3DXPoint memory. Proc. of the VLDB Endowment, 2020, 13(7):1078-1090.
    [29] van Renen A, Vogel L, Leis V, et al. Building blocks for persistent memory. The VLDB Journal, 2020, 29(6):1223-1241.
    [30] Hirofuchi T, Takano R. A prompt report on the performance of Intel Optane DC persistent memory module. IEICE Trans. on Information & Systems, 2020, 103-D(5):1168-1172.
    [31] Schwalb D, Berning T, Faust M, et al. nvm_malloc:Memory allocation for NVRAM. In:Proc. of the ADMS@VLDB. 2015. 61-72.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

刘睿诚,张俊晨,罗永平,金培权.面向非易失内存的异构索引.软件学报,2022,33(3):832-848

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:June 30,2021
  • Revised:July 31,2021
  • Online: October 21,2021
  • Published: March 06,2022
You are the first2032502Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063