(西安交通大学计算机科学与技术学院 西安 710049) (yanweiwei.002@stu.xjtu.edu.cn)
出版日期: 2021-02-01基金资助:国家重点研发计划项目(2016YFB1000303)One-Direction Shift B+-Tree Based on Persistent Memory
Yan Wei, Zhang Xingjun, Ji Zeyu, Dong Xiaoshe, Ji Chenzhao(School of Computer Science and Technology, Xi’an Jiaotong University, Xi’an 710049)
Online: 2021-02-01Supported by:This work was supported by the National Key Research and Development Program of China (2016YFB1000303).摘要/Abstract
摘要： 由新型非易失存储介质构成的持久性内存(persistent memory, PM)具有扩展性强、按字节访问与静态能耗低等特性，为未来主存与辅存融合提供了强大的契机.然而由于LLC(last level cache)具有易失性且与主存交互粒度通常为64B，而PM的原子持久化操作粒度为8B.因此，数据从LLC更新到PM的过程中，若发生故障，则可能破坏更新操作的失败原子性,进而影响原始数据的完整性.为了保证更新操作的失败原子性，目前研究主要采用显式调用持久化指令与内存屏障指令，将数据有序地持久化到PM上，但该操作会造成显著的开销，在索引更新中尤为明显.在对索引进行更新时，往往会涉及到索引结构的变化，该变化需要大量的有序持久化开销.研究旨在减少基于PM的B\++树在更新过程中为保证失败原子性而引入的持久化开销.通过分析B\++树节点利用率、不同更新模式下持久化开销以及更新操作之间的关系，提出了一种基于节点内数据真实分布的数据单向移动算法.通过原地删除的方式，减少删除带来的持久化开销.利用删除操作在节点内留下的空位，减少后续插入操作造成的数据移动，进而减少数据持久化开销.基于上述算法，对B\++树的重均衡操作进行优化.最后通过实验证明，相较于最新基于PM的B\++树，提出的单向移动B\++树能够显著提高单一负载与混合负载性能.
参考文献
相关文章 15
| [1] | 陈茂棠, 郑圣安, 游理通, 王晶钰, 闫田, 屠要峰, 韩银俊, 黄林鹏. 一种基于RDMA多播机制的分布式持久性内存文件系统[J]. 计算机研究与发展, 2021, 58(2): 384-396. |
| [2] | 汪庆, 朱博弘, 舒继武. 一种多核友好的持久性内存键值系统[J]. 计算机研究与发展, 2021, 58(2): 397-405. |
| [3] | 屠要峰, 陈正华, 韩银俊, 陈兵, 关东海. 基于持久性内存和SSD的后端存储MixStore[J]. 计算机研究与发展, 2021, 58(2): 406-417. |
| [4] | 刘润涛, 梁建创. 基于新型索引结构的反最近邻查询[J]. 计算机研究与发展, 2020, 57(6): 1335-1346. |
| [5] | 杨帆, 李飞, 舒继武. 安全持久性内存存储研究综述[J]. 计算机研究与发展, 2020, 57(5): 912-927. |
| [6] | 陈波, 陆游游, 蔡涛, 陈游旻, 屠要峰, 舒继武. 一种分布式持久性内存文件系统的一致性机制[J]. 计算机研究与发展, 2020, 57(3): 660-667. |
| [7] | 何柯文, 张佳辰, 刘晓光, 王刚. 新型存储设备上重复数据删除指纹查找优化[J]. 计算机研究与发展, 2020, 57(2): 269-280. |
| [8] | 陈游旻, 朱博弘, 韩银俊, 屠要峰, 舒继武. 一种持久性内存文件系统数据页的混合管理机制[J]. 计算机研究与发展, 2020, 57(2): 281-290. |
| [9] | 陈娟,胡庆达,陈游旻,陆游游,舒继武,杨晓辉. 一种基于微日志的持久性事务内存系统[J]. 计算机研究与发展, 2018, 55(9): 2029-2037. |
| [10] | 李玮,张大方,谢鲲,黎文伟,何杰. 一种面向闪存键值存储的矩阵索引布鲁姆过滤器[J]. 计算机研究与发展, 2015, 52(5): 1210-1222. |
| [11] | 冷芳玲, 刘金鹏, 王志刚, 陈昌宁, 鲍玉斌, 于戈, 邓超. BSP模型下基于边聚簇的大图划分与迭代处理[J]. 计算机研究与发展, 2015, 52(4): 960-971. |
| [12] | 秦志光,王士雨,赵洋,熊虎,吴松洋. 云存储服务的动态数据完整性审计方案[J]. 计算机研究与发展, 2015, 52(10): 2192-2199. |
| [13] | 罗 杨,夏春和,李亚卓,魏 昭,梁晓艳. 一种基于双模式虚拟机的多态Shellcode检测方法[J]. 计算机研究与发展, 2014, 51(8): 1704-1714. |
| [14] | HF-Tree:一种闪存数据库的高更新性能索引结构. 通信作者：孟小峰(xfmeng@ruc.edu.cn)[J]. , 2010, 47(5): 832-840. |
| [15] | 刘润涛, 郝忠孝,. 基于多序的空间数据索引结构——MOIS-树[J]. , 2010, 47(5): 849-857. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4351
