WOBTree:a write-optimized B+-tree for non-volatile memory

作     者：Haitao WANG Zhanhuai LI Xiao ZHANG Xiaonan ZHAO Song JIANG Haitao WANG;Zhanhuai LI;Xiao ZHANG;Xiaonan ZHAO;Song JIANG

作者机构：School of Computer Science and EngineeringNorthwestern Polytechnical UniversityXi'An 710072China Key Laboratory of Big Data Storage and ManagementNorthwestern Polytechnical UniversityMinistry of Industry and Information TechnologyXi'An 710072China National Engineering Laboratory for Integrated Aero-Space-Ground-Ocean Big Data Application TechnologyXi’An 710072China Department of Computer Science and EngineeringUniversity of Texas at ArlingtonArlingtonTX 76010USA 

出 版 物：《Frontiers of Computer Science》 (中国计算机科学前沿（英文版）)

年 卷 期：2021年第15卷第5期

页      面：37-51页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：the National Key Research and Development Program of China(2018YFB1004401) the National Natural Science Foundation of China for Young Scientists(Grant No.61502392) the General Program of the National Natural Science Foundation of China(61472323) 

主　　题：non-volatile memory B+-tree atomic granularity mismatch write amplification performance optimization 

摘      要：The emergence of non-volatile memory(NVM)has introduced new opportunities for performance optimizations in existing storage *** better utilize its byte-addressability and near-DRAM performance,NVM can be attached on the memory bus and accessed via load/store memory instructions rather than the conventional block *** this scenario,a cache line(usually 64 bytes)becomes the data transfer unit between volatile and non-volatile ***,the failure-atomicity of write on NVM is the memory bit width(usually 8 bytes).This mismatch between the data transfer unit and the atomicity unit may introduce write amplification and compromise data consistency of node-based data structures such as B+-*** this paper,we propose WOBTree,a Write-Optimized B+-Tree for NVM to address the mismatch problem without expensive *** minimizes the update granularity from a tree node to a much smaller subnode and carefully arranges the write operations in it to ensure crash consistency and reduce write *** results show that compared with previous persistent B+-tree solutions,WOBTree reduces the write amplification by up to 86× and improves write performance by up to 61× while maintaining similar search performance.