Write-Optimized B^(+) Tree Index Technology for Persistent Memory  

作　　者：Rui-Xiang Ma Fei Wu Bu-Rong Dong Meng Zhang Wei-Jun Li Chang-Sheng Xie 

机构地区：[1]Wuhan National Laboratory for Optoelectronics,Huazhong University of Science and Technology,Wuhan 430070,China [2]Key Laboratory of Information Storage System,Ministry of Education of China,Wuhan 430070,China [3]Engineering Research Center of Data Storage Systems and Technology,Huazhong University of Science and Technology Wuhan 430070,China [4]School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430070,China [5]Shenzhen DAPU Microelectronics Co.,Ltd,Shenzhen 518116,China

出　　处：《Journal of Computer Science & Technology》2021年第5期1037-1050,共14页计算机科学技术学报（英文版）

基　　金：supported in part by the National Natural Science Foundation of China under Grant Nos.U1709220,U2001203,61821003,61872413,and 61902137;in part by the National Key Research and Development Program of China under Grant No.2018YFB1003305;in part by the Key-Area Research and Development Program of Guangdong Province of China under Grant No.2019B010107001.

摘　　要：Due to its low latency,byte-addressable,non-volatile,and high density,persistent memory(PM)is expected to be used to design a high-performance storage system.However,PM also has disadvantages such as limited endurance,thereby proposing challenges to traditional index technologies such as B(+)tree.B(+)tree is originally designed for dynamic random access memory(DRAM)-based or disk-based systems and has a large write amplification problem.The high write amplification is detrimental to a PM-based system.This paper proposes WO-tree,a write-optimized B(+)tree for PM.WO-tree adopts an unordered write mechanism for the leaf nodes,and the unordered write mechanism can reduce a large number of write operations caused by maintaining the entry order in the leaf nodes.When the leaf node is split,WO-tree performs the cache line flushing operation after all write operations are completed,which can reduce frequent data flushing operations.WO-tree adopts a partial logging mechanism and it only writes the log for the leaf node.The inner node recognizes the data inconsistency by the read operation and the data can be recovered using the leaf node information,thereby significantly reducing the logging overhead.Furthermore,WO-tree adopts a lock-free search for inner nodes,which reduces the locking overhead for concurrency operation.We evaluate WO-tree using the Yahoo!Cloud Serving Benchmark(YCSB)workloads.Compared with traditional B(+)tree,wB-tree,and Fast-Fair,the number of cache line flushes caused by WO-tree insertion operations is reduced by 84.7%,22.2%,and 30.8%,respectively,and the execution time is reduced by 84.3%,27.3%,and 44.7%,respectively.

关 键 词：persist memory B^(+)tree write amplication CONSISTENCY YCSB(Yahoo!Cloud Serving Benchmark) 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]