PLTree: 一个高性能持久化内存学习索引
作者:
中图分类号:

TP311

基金项目:

浙江省尖兵研发攻关计划(2024C01021); 浙江省科技创新领军人才计划(2023R5214)


PLTree: High-performance Learning Index for Persistent Memory
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [44]
  • | |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    持久化内存(persistent memory, PM)作为主存的补充和替代, 为数据存储提供了相对较低的价格成本, 并且保证了数据的持久化. 为PM设计的传统结构索引(如B+树等)未能充分利用数据分布特点来发挥索引在PM上的读写性能. 最近的研究尝试利用学习索引的数据分布感知能力提升索引在PM上的读写性能并实现持久化. 但在面对真实世界的数据时, 现有基于PM的持久化学习索引的数据结构设计会导致额外的内存访问, 从而影响读写性能. 针对PM学习索引在面对真实数据时读写性能下降的问题, 提出一种DRAM/PM混合架构的学习索引PLTree. 它通过以下方法提升在PM上的读写性能并减轻数据分布颠簸对性能的影响: (1)使用两阶段方法构建索引消除内部节点的局部搜索, 减少PM的访问. (2)利用模型搜索来优化PM上的查找性能并通过在DRAM存储元数据加速查找. (3)根据PM的特性设计了日志式分层溢出缓存结构, 优化写入性能. 实验结果表明, 在不同数据集上, 与现有的持久化内存索引(APEX, FPTree, uTree, NBTree和DPTree)相比, PLTree在索引构建性能上平均提升了约1.9–34倍; 单线程查询/插入性能平均提升了约1.26–4.45倍和2.63–6.83倍; 在多线程场景, 查询/插入性能最高提升了约10.2倍和23.7倍.

    Abstract:

    Persistent memory (PM), serving as a supplement and potential replacement for main memory, offers a lower cost for data storage while ensuring data persistence. However, traditional index structures tailored for PM like B+ trees fail to fully exploit the distribution characteristics of data for optimizing reading and writing performance on PM. Recent research endeavors have sought to enhance indexes’ reading and writing performance on PM and support index persistence through the data distribution awareness of learning indexes. Nonetheless, existing designs of persistent learning index structures suffer from additional PM accesses and poor performance when confronted with real-world data. To address the performance degradation of persistent learning indexes in the face of real data distributions, this study proposes a learning index PLTree, a DRAM/PM hybrid architecture. PLTree optimizes reading and writing performance under real data distributions through the following approaches: (1) a two-stage approach to construct the index, eliminating last-mile search in internal nodes and reducing the access of PM, (2) model-based search for efficient query performance on PM and accelerated query by leveraging metadata in DRAM, and (3) a log-based hierarchical overflow buffer structure tailored to PM characteristics to optimize writing performance. The results show that, compared with the existing persistent memory indexes (APEX, FPTree, uTree, NBTree, and DPTree), PLTree achieves significantly better performance in index construction 1.9× to 34× across various datasets. In single-threaded scenarios, PLTree exhibits an average query and insertion performance improvement of 1.26× to 4.45× and 2.63× to 6.83×, respectively. In multi-threaded scenarios, PLTree surpasses the baseline by up to 10.2× and 23.7× in query and insertion performance, respectively.

    参考文献
    [1] Lu BT, Ding JL, Lo E, Minhas UF, Wang TZ. APEX: A high-performance learned index on persistent memory. Proc. of the VLDB Endowment, 2021, 15(3): 597–610.
    [2] 3D XPointTM: A breakthrough in non-volatile memory technology. https://www.intel.com/content/www/us/en/architecture-and-technology/intel-micron-3d-xpoint-webcast.html
    [3] Lersch L, Hao XP, Oukid I, Wang TZ, Willhalm T. Evaluating persistent memory range indexes. Proc. of the VLDB Endowment, 2019, 13(4): 574–587.
    [4] Hwang D, Kim WH, Won Y, Nam B. Endurable transient inconsistency in Byte-Addressable persistent B+-Tree. In: Proc. of the 16th USENIX Conf. on File and Storage Technologies. Oakland: USENIX Association, 2018. 187–200.
    [5] Yang J, Wei QS, Chen C, Wang CD, Yong KL, He BS. NV-Tree: Reducing consistency cost for NVM-based single level systems. In: Proc. of the 13th USENIX Conf. on File and Storage Technologies. Santa Clara: USENIX Association, 2015. 167–181.
    [6] Oukid I, Lasperas J, Nica A, Willhalm T, Lehner W. FPTree: A hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In: Proc. of the 2016 Int’l Conf. on Management of Data. San Francisco: ACM, 2016. 371–386.
    [7] Liu JH, Chen SN, Wang LJ. LB+trees: Optimizing persistent index performance on 3DXPoint memory. Proc. of the VLDB Endowment, 2020, 13(7): 1078–1090.
    [8] Zhang BW, Zheng S, Qi ZL, Huang LP. NBTree: A lock-free pm-friendly persistent B+-tree for eADR-enabled PM systems. Proc. of the VLDB Endowment, 2022, 15(6): 1187–1200.
    [9] Lee SK, Lim KH, Song H, Nam B, Noh SH. WORT: Write optimal radix tree for persistent memory storage systems. In: Proc. of the 15th USENIX Conf. on File and Storage Technologies. Santa Clara: USENIX Association, 2017. 257–270.
    [10] Ma SN, Chen K, Chen SM, Liu MX, Zhu JL, Kang HB, Wu YW. ROART: Range-query optimized persistent art. In: Proc. of the 19th USENIX Conf. on File and Storage Technologies. USENIX Association, 2021. 1–16.
    [11] Kim WH, Krishnan RM, Fu XW, Kashyap S, Min C. PACTree: A high performance persistent range index using pac guidelines. In: Proc. of the 28th ACM SIGOPS ACM Symp. on Operating Systems Principles. Virtual Event: ACM, 2021. 424–439.
    [12] Zhou XJ, Shou LD, Chen K, Hu W, Chen G. DPTree: Differential indexing for persistent memory. Proc. of the VLDB Endowment, 2019, 13(4): 421–434.
    [13] Chen YM, Lu YY, Fang KD, Wang Q, Shu JW. uTree: A persistent B+-tree with low tail latency. Proc. of the VLDB Endowment, 2020, 13(12): 2634–2648.
    [14] Arulraj J, Levandoski J, Minhas UF, Larson PA. BzTree: A high-performance latch-free range index for non-volatile memory. Proc. of the VLDB Endowment, 2018, 11(5): 553–565.
    [15] Debnath B, Haghdoost A, Kadav A, Khatib MG, Ungureanu C. Revisiting hash table design for phase change memory. ACM SIGOPS Operating Systems Review, 2016, 49(2): 18–26.
    [16] Zuo PF, Hua Y, Wu J. Level hashing: A high-performance and flexible-resizing persistent hashing index structure. ACM Trans. on Storage, 2019, 15(2): 13.
    [17] Nam M, Cha H, Choi YR, Noh SH, Nam B. Write-optimized dynamic hashing for persistent memory. In: Proc. of the 17th USENIX Conf. on File and Storage Technologies. Boston: USENIX Association, 2019. 31–44.
    [18] Lu BT, Hao XP, Wang TZ, Lo E. Dash: Scalable hashing on persistent memory. Proc. of the VLDB Endowment, 2020, 13(8): 1147–1161.
    [19] Hu DK, Chen ZW, Che WK, Sun JH, Chen H. Halo: A hybrid PMEM-DRAM persistent hash index with fast recovery. In: Proc. of the 2022 Int’l Conf. on Management of Data. Philadelphia: ACM, 2022. 1049–1063. [doi: 10.1145/3514221.3517884]
    [20] Vogel L, van Renen A, Imamura S, Giceva J, Neumann T, Kemper A. Plush: A write-optimized persistent log-structured hash-table. Proc. of the VLDB Endowment, 2022, 15(11): 2895–2907.
    [21] Kraska T, Beutel A, Chi EH, Dean J, Polyzotis N. The case for learned index structures. In: Proc. of the 2018 Int’l Conf. on Management of Data. Houston: ACM, 2018. 489–504. [doi: 10.1145/3183713.3196909]
    [22] 张洲, 金培权, 谢希科. 学习索引: 现状与研究展望. 软件学报, 2021, 32(4): 1129–1150. http://www.jos.org.cn/1000-9825/6168.htm
    Zhang Z, Jin PQ, Xie XK. Learned indexes: Current situations and research prospects. Ruan Jian Xue Bao/Journal of Software, 2021, 32(4): 1129–1150 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6168.htm
    [23] Chen LY, Chen SM. How does updatable learned index perform on non-volatile main memory? In: Proc. of the 37th IEEE Int’l Conf. on Data Engineering Workshops. Chania: IEEE, 2021. 66–71. [doi: 10.1109/ICDEW53142.2021.00019]
    [24] Zhang Z, Chu ZL, Jin PQ, Luo YP, Xie XK, Wan SH, Luo Y, Wu XF, Zou P, Zheng CY, Wu GA, Rudoff A. PLIN: A persistent learned index for non-volatile memory with high performance and instant recovery. Proc. of the VLDB Endowment, 2022, 16(2): 243–255.
    [25] 王中华, 赖必梁, 赵泽阳, 鲁凯, 万继光. APLI: 一种基于持久化内存的高性能学习索引. 小型微型计算机系统, 2023 (在线出版). https://kns.cnki.net/kcms2/detail/21.1106.TP.20230606.1807.020.html
    Wang ZH, Lai BL, Zhao ZY, et al. APLI: A high-performance learned index for persistent memory. Journal of Chinese Computer Systems, 2023 (in Chinese) (published online). https://kns.cnki.net/kcms2/detail/21.1106.TP.20230606.1807.020.html
    [26] Kipf A, Marcus R, Van Renen A, Stoian M, Kemper A, Kraska T, Neumann T. SOSD: A benchmark for learned indexes. arXiv:1911.13014, 2019.
    [27] Xie Q, Pang CY, Zhou XF, Zhang XL, Deng K. Maximum error-bounded piecewise linear representation for online stream approximation. The VLDB Journal, 2014, 23(6): 915–937.
    [28] Ding JL, Minhas UF, Yu J, Wang C, Do J, Li YN, Zhang HT, Chandramouli B, Gehrke J, Kossmann D, Lomet D, Kraska T. ALEX: An updatable adaptive learned index. In: Proc. of the 2020 ACM SIGMOD Int’l Conf. on Management of Data. Portland: ACM, 2020. 969–984. [doi: 10.1145/3318464.3389711]
    [29] Ferragina P, Vinciguerra G. The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds. Proc. of the VLDB Endowment, 2020, 13(8): 1162–1175.
    [30] Galakatos A, Markovitch M, Binnig C, Fonseca R, Kraska T. FITing-tree: A data-aware index structure. In: Proc. of the 2019 Int’l Conf. on Management of Data. Amsterdam: ACM, 2019. 1189–1206. [doi: 10.1145/3299869.3319860]
    [31] 陈井爽, 陈珂, 寿黎但, 江大伟, 陈刚. ALERT: 基于Radix Tree的工作负载自适应学习型索引. 软件学报, 2022, 33(12): 4688–4703. http://www.jos.org.cn/1000-9825/6354.htm
    Chen JS, Chen K, Shou LD, Jiang DW, Chen G. ALERT: Workload-adaptive learned index based on radix tree. Ruan Jian Xue Bao/Journal of Software, 2022, 33(12): 4688–4703 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6354.htm
    [32] Tang CZ, Wang YY, Dong ZY, Hu GS, Wang ZG, Wang MJ, Chen HB. XIndex: A scalable learned index for multicore data storage. In: Proc. of the 25th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming. San Diego: ACM, 2020. 308–320.
    [33] Li PF, Hua Y, Jia JN, Zuo PF. FINEdex: A fine-grained learned index scheme for scalable and concurrent memory systems. Proc. of the VLDB Endowment, 2021, 15(2): 321–334.
    [34] Wu JC, Zhang Y, Chen SM, Wang J, Chen Y, Xing CX. Updatable learned index with precise positions. Proc. of the VLDB Endowment, 2021, 14(8): 1276–1288.
    [35] Li PF, Lu H, Zhu R, Ding BL, Yang L, Pan G. DILI: A distribution-driven learned index (Extended version). arXiv:2304.08817, 2023.
    [36] O’Neil P, Cheng E, Gawlick D, O’Neil E. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33(4): 351–385.
    [37] Yang J, Kim J, Hoseinzadeh M, Izraelevitz J, Swanson S. An empirical guide to the behavior and use of scalable persistent memory. In: Proc. of the 18th USENIX Conf. on File and Storage Technologies. Santa Clara: USENIX Association, 2020. 169–182.
    [38] Liu XY, Lin ZJ, Wang HQ. Novel online methods for time series segmentation. IEEE Trans. on Knowledge and Data Engineering, 2008, 20(12): 1616–1626.
    [39] Intel Corporation. Intel? 64 and IA-32 architectures software developer’s manual. https://www.intel.cn/content/www/cn/zh/developer/articles/technical/intel-sdm.html
    [40] Intel Corporation. Deprecating the PCOMMIT Instruction. https://www.intel.cn/content/www/cn/zh/developer/articles/technical/deprecate-pcommit-instruction.html
    [41] Wongkham C, Lu BT, Liu C, Zhong ZC, Lo E, Wang TZ. Are updatable learned indexes ready? Proc. of the VLDB Endowment, 2022, 15(11): 3004–3017.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

张志国,谢钟乐,陈珂,寿黎但. PLTree: 一个高性能持久化内存学习索引.软件学报,,():1-21

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-12-11
  • 最后修改日期:2024-01-21
  • 在线发布日期: 2024-06-14
文章二维码
您是第19799526位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号