One-Direction Shift B+-Tree Based on Persistent Memory
-
摘要: 由新型非易失存储介质构成的持久性内存(persistent memory, PM)具有扩展性强、按字节访问与静态能耗低等特性，为未来主存与辅存融合提供了强大的契机.然而由于LLC(last level cache)具有易失性且与主存交互粒度通常为64B，而PM的原子持久化操作粒度为8B.因此，数据从LLC更新到PM的过程中，若发生故障，则可能破坏更新操作的失败原子性,进而影响原始数据的完整性.为了保证更新操作的失败原子性，目前研究主要采用显式调用持久化指令与内存屏障指令，将数据有序地持久化到PM上，但该操作会造成显著的开销，在索引更新中尤为明显.在对索引进行更新时，往往会涉及到索引结构的变化，该变化需要大量的有序持久化开销.研究旨在减少基于PM的B\++树在更新过程中为保证失败原子性而引入的持久化开销.通过分析B\++树节点利用率、不同更新模式下持久化开销以及更新操作之间的关系，提出了一种基于节点内数据真实分布的数据单向移动算法.通过原地删除的方式，减少删除带来的持久化开销.利用删除操作在节点内留下的空位，减少后续插入操作造成的数据移动，进而减少数据持久化开销.基于上述算法，对B\++树的重均衡操作进行优化.最后通过实验证明，相较于最新基于PM的B\++树，提出的单向移动B\++树能够显著提高单一负载与混合负载性能.Abstract: The persistent memory (PM) fascinates many researchers by its high scalability, byte-addressability and low static energy consumption which can contribute to the fusion of main memory and secondary memory. However，the interacting granularity between the volatile last level cache (LLC) and the non-volatile PM is normally 64B which is much larger than 8B, the granularity of the atomic updating operations provided by the main memory. Once an outage takes place during the process of transporting data from LLC to PM, data integration on the PM may be destroyed, which will lead to a breaking down of failure atomicity. Most researches are used to solve this problem by forcing the data persisted following some order implemented with flush and fence instructions which are always accompanied with large overhead. This overhead will be amplified especially in index updating which often leads to some transformation of index structures. In this paper, we focus on reducing the persisting overhead for ensuring the failure atomicity of updating a PM-based B\++-Tree. We propose a one direction shifting (ODS) algorithm based on the real data layout in the tree node as well as the node utility, the persisting overhead of different updating mode and the relation between different operations. This algorithm implements the in-place deletion to reduce the deleting overhead and takes advantage of the pits generated by in-place deletion to further reduce the shifting overhead of insertion. We redesign the rebalancing process of our persistent B\++-Tree according to the ODS algorithm. Experiments show that our proposed ODS tree can outperform the state-of-the-art PM trees on single and synthetic workloads.
-
-
期刊类型引用(20)
1. 肖鸿洲 ，李长云，王志兵 ，甘英华 ，任国鑫 . 一种稀疏体压特征人员识别方法. 现代电子技术. 2025(03): 111-118 . 
百度学术
2. 王莹. 未经授权的人脸识别支付法律责任解释论. 运城学院学报. 2024(02): 70-74+89 . 百度学术
3. 洪延青. 人脸识别技术应用的分层治理理论与制度进路. 法律科学(西北政法大学学报). 2024(01): 89-99 . 百度学术
4. 王勇，熊毅，杨天宇，沈益冉. 一种面向耳戴式设备的用户安全连续认证方法. 计算机研究与发展. 2024(11): 2821-2834 . 本站查看
5. 杨光锴. 基于扩散模型的指纹图像生成方法. 河北省科学院学报. 2023(01): 13-18+66 . 百度学术
6. 徐胜超，熊茂华. 基于子模式的人脸局部遮挡智能识别方法. 信息技术. 2023(03): 35-39 . 百度学术
7. 周宇，向剑文，郑倩荣，赵冬冬. 保护用户数量信息的安全虹膜识别方案. 信息安全学报. 2023(03): 49-64 . 百度学术
8. 张星星，钟陈，王文峰，苏立伟. 生物特征识别标准概述. 信息技术与标准化. 2023(11): 64-68 . 百度学术
9. 张雪锋，常振会，张俊杰，王超飞. 指纹和虹膜特征融合的可撤销模板保护方法. 西安邮电大学学报. 2023(04): 51-60 . 百度学术
10. 钟陈，苏立伟，王文峰. 生物特征识别呈现攻击检测标准化研究. 信息技术与标准化. 2022(Z1): 50-53 . 百度学术
11. 张宗华，王晟贤，高楠，孟召宗. 基于曲面类型与深度学习融合的三维掌纹识别技术. 电子与信息学报. 2022(04): 1469-1475 . 百度学术
12. 胡先智，陈浩，梁艳. 多模态生物特征信息安全防护体系研究. 计算机技术与发展. 2022(04): 86-91 . 百度学术
13. 张波，贺楚博. 基于可撤销人脸的模糊保险箱算法研究与实现. 计算机技术与发展. 2022(06): 126-130 . 百度学术
14. 帕孜来提·努尔买提，古丽娜孜·艾力木江，乎西旦·居马洪，朱双玲. 一种基于深度学习方法的面部微变识别的研究. 伊犁师范大学学报(自然科学版). 2022(02): 41-46+52 . 百度学术
15. 杨丽红，尚泽昊. 基于区块链和模糊提取的多特征融合身份认证模型. 数字技术与应用. 2022(08): 218-220 . 百度学术
16. 董芸嘉，张雪锋，姜文. 基于指纹和手指静脉特征融合的模板保护方法. 传感器与微系统. 2022(11): 9-13 . 百度学术
17. 张波，佟玉强. 基于双随机相位编码的多特征人脸模板保护方法. 激光与光电子学进展. 2022(18): 215-222 . 百度学术
18. 王晟贤，张宗华，高楠，孟召宗. 融合曲面类型与迁移学习的三维掌纹识别方法. 传感器与微系统. 2022(12): 118-121 . 百度学术
19. 丁勇，李佳慧，唐士杰，王会勇. 基于随机映射技术的声纹识别模板保护. 计算机研究与发展. 2020(10): 2201-2208 . 本站查看
20. 张佳，王红. 基于生物特征识别的Android身份认证终端技术研究. 电子测试. 2020(24): 78-79+56 . 百度学术
其他类型引用(28)
计量
- 文章访问数: 597
- HTML全文浏览量: 6
- PDF下载量: 238
- 被引次数: 48
下载:
