LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory

doi:10.14778/3384345.3384355

	LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory
	Liu, Jihang 1,2; Chen, Shimin 1,2; Wang, Lujun 3
	2020-03-01
发表期刊	PROCEEDINGS OF THE VLDB ENDOWMENT
ISSN	2150-8097
卷号	13 期号:7 页码:1078-1090
摘要	3DXPoint memory is the first commercially available NVM solution targeting mainstream computer systems. While 3DXPoint conforms to many assumptions about NVM in previous studies, we observe a number of distinctive features of 3DXPoint. For example, the number of modified words in a cache line does not affect the performance of 3DXPoint writes. This enables a new type of optimization: performing more NVM word writes per line in order to reduce the number of NVM line writes. We propose LB+-Tree, a persistent B+-Tree index optimized for 3DXPoint memory. LB+-Tree nodes are 256B or a multiple of 256B, as 256B is the internal data access size in 3DXPoint memory. We propose three techniques to improve LB+-Tree's insertion performance: (i) Entry moving, which reduces the number of NVM line writes for insertions by creating empty slots in the first line of a leaf node; (ii) Logless node split, which uses NAW (NVM Atomic Write) to reduce logging overhead; and (iii) Distributed headers, which makes (i) and (ii) effective for multi-256B nodes. Theoretical analysis shows that entry moving reduces the number of NVM line writes per insertion of the traditional design by at least 1.35x in a stable tree. Our micro-benchmark experiments on a real machine equipped with 3DXPoint memory shows that LB+-Tree achieves up to 1.12-2.92x speedups over state-of-the-art NVM optimized B+-Trees for insertions while obtaining similar search and deletion performance. Moreover, we study the benefits of LB+-Tree in two real-world systems: X-Engine, a commercial OLTP storage engine, and Memcached, an open source key-value store. X-Engine and Memcached results confirm our findings in the micro-benchmarks.
DOI	10.14778/3384345.3384355
收录类别	SCI
语种	英语
资助项目	National Key R&D Program of China[2018YEB1003303] ; NSFC[61572468] ; Alibaba collaboration project[XT622018000648] ; K.C.Wong Education Foundation
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Theory & Methods
WOS记录号	WOS:000573956000010
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：81[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/15635
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Jihang
作者单位	1.Chinese Acad Sci, ICT, SKL Comp Architecture, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Alibaba Grp, Hangzhou, Zhejiang, Peoples R China
推荐引用方式 GB/T 7714	Liu, Jihang,Chen, Shimin,Wang, Lujun. LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory[J]. PROCEEDINGS OF THE VLDB ENDOWMENT,2020,13(7):1078-1090.
APA	Liu, Jihang,Chen, Shimin,&Wang, Lujun.(2020).LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory.PROCEEDINGS OF THE VLDB ENDOWMENT,13(7),1078-1090.
MLA	Liu, Jihang,et al."LB+-Trees: Optimizing Persistent Index Performance on 3DXPoint Memory".PROCEEDINGS OF THE VLDB ENDOWMENT 13.7(2020):1078-1090.