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

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

机构地区：[1]School of Computer Science and Engineering,Northwestern Polytechnical University,Xi'An 710072,China [2]Key Laboratory of Big Data Storage and Management,Northwestern Polytechnical University,Ministry of Industry and Information Technology,Xi'An 710072,China [3]National Engineering Laboratory for Integrated Aero-Space-Ground-Ocean Big Data Application Technology,Xi’An 710072,China [4]Department of Computer Science and Engineering,University of Texas at Arlington,Arlington,TX 76010,USA

出　　处：《Frontiers of Computer Science》2021年第5期37-51,共15页中国计算机科学前沿（英文版）

基　　金：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).

摘　　要：The emergence of non-volatile memory(NVM)has introduced new opportunities for performance optimizations in existing storage systems.To 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 interface.In this scenario,a cache line(usually 64 bytes)becomes the data transfer unit between volatile and non-volatile devices.However,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+-trees.In this paper,we propose WOBTree,a Write-Optimized B+-Tree for NVM to address the mismatch problem without expensive logging.WOBTree 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 amplification.Experimental 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.

关 键 词：non-volatile memory B+-tree atomic granularity mismatch write amplification performance optimization 

分 类 号：TP333[自动化与计算机技术—计算机系统结构]