Optimizing B<sup>+</sup>-tree for hybrid memory with in-node hotspot cache and eADR awareness

doi:10.1007/s11704-023-3344-x

Front. Comput. Sci.

2024, Vol. 18

Issue (5) : 185606 https://doi.org/10.1007/s11704-023-3344-x

RESEARCH ARTICLE

Optimizing B⁺-tree for hybrid memory with in-node hotspot cache and eADR awareness

Peiquan JIN(

), Zhaole CHU, Gaocong LIU, Yongping LUO, Shouhong WAN

School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China

Download: PDF(14541 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

The advance in Non-Volatile Memory (NVM) has changed the traditional DRAM-only memory system. Compared to DRAM, NVM has the advantages of non-volatility and large capacity. However, as the read/write speed of NVM is still lower than that of DRAM, building DRAM/NVM-based hybrid memory systems is a feasible way of adding NVM into the current computer architecture. This paper aims to optimize the well-known B⁺-tree for hybrid memory. The novelty of this study is two-fold. First, we observed that the space utilization of internal nodes in B⁺-tree is generally below 70%. Inspired by this observation, we propose to maintain hot keys in the free space within internal nodes, yielding a new index named HATree (Hotness-Aware Tree). The new idea of HATree is to use the unused space of the parent of leaf nodes (PLNs) as the hotspot data cache. Thus, no extra space is needed, and the in-node hotspot cache can efficiently improve query performance. Second, to further improve the update performance of HATree, we propose to utilize the eADR technology supported by the third-generation Intel Xeon Scalable Processors to enhance HATree with instant log persistence, which results in the new HATree-Log structure. We conduct extensive experiments on real hybrid memory architecture involving DRAM and Intel Optane Persistent Memory to evaluate the performance of HATree and HATree-Log. Three state-of-the-art indices for hybrid memory, namely NBTree, LBTree, and FPTree, are included in the experiments, and the results suggest the efficiency of HATree and HATree-Log.

Keywords hybrid memory B⁺-tree hotspot in-node cache eADR

Corresponding Author(s): Peiquan JIN

Just Accepted Date: 22 September 2023 Issue Date: 11 December 2023

Cite this article:

Peiquan JIN,Zhaole CHU,Gaocong LIU, et al. Optimizing B⁺-tree for hybrid memory with in-node hotspot cache and eADR awareness[J]. Front. Comput. Sci., 2024, 18(5): 185606.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-3344-x
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I5/185606

Fig.1 Space utilization of PLNs in an in-memory B⁺-tree

Symbol	Description
$β$	The ratio of the unused PLNs’ space to the dataset
$η$	The space utilization of PLNs
$N P L N$	The number of PLN
$S i n n e r$	The number of entries in an inner node
$S l e a f$	The number of entries in a leaf node

Tab.1 Symbols for analyzing the unused PLNs’ space

Fig.2 The high-level index architecture of HATree

Fig.3 The leaf-node structure of HATree

Fig.4 The inner-node structure of HATree in comparison with the previous design

Fig.5 Process of the search operation

Fig.6 The architecture of HATree-Log

Fig.7 Process of the update operation

Component	Description
CPU	Intel $?$ Xeon $?$ Gold 6242 CPU
CPU	Dual-socket with 40 cores at 3.1 GHz
L1 cache	32 KB iCache & 32 KB dCache (per-core)
L2 cache	1 MB (per core)
L3 cache	36 MB (per socket)
Total DRAM	256 GB (2 (socket) x 4 (channel) x 32 GB)
Total NVM	2,048 GB (2 (socket) x 4 (channel) x 256 GB)

Tab.2 Server configuration

Fig.8 Update performance in the eADR mode when varying skewness

Fig.9 Update performance in the eADR mode with various update proportions

Fig.10 Search/insert/delete performance in the eADR mode

Tab.3 YCSB workloads

Fig.11 Performance on YCSB workloads in the eADR mode

Fig.12 Performance on Bitcask in the eADR mode

1	J, Yang J, Kim M, Hoseinzadeh J, Izraelevitz S Swanson . An empirical guide to the behavior and use of scalable persistent memory. In: Proceedings of the 18th USENIX Conference on File and Storage Technologies. 2020, 169−182
2	S, Raoux G W, Burr M J, Breitwisch C T, Rettner Y C, Chen R M, Shelby M, Salinga D, Krebs S H, Chen H L, Lung C H Lam . Phase-change random access memory: a scalable technology. IBM Journal of Research and Development, 2008, 52(4−5): 465−479
3	D, Apalkov A, Khvalkovskiy S, Watts V, Nikitin X, Tang D, Lottis K, Moon X, Luo E, Chen A, Ong A, Driskill-Smith M Krounbi . Spin-transfer torque magnetic random access memory (STT-MRAM). ACM Journal on Emerging Technologies in Computing Systems, 2013, 9( 2): 13
4	H, Akinaga H Shima . Resistive random access memory (ReRAM) based on metal oxides. Proceedings of the IEEE, 2010, 98( 12): 2237–2251
5	J, Liu S Chen . Initial experience with 3D XPoint main memory. Distributed and Parallel Databases, 2020, 38( 4): 865–880
6	J, Liu S, Chen L Wang . LB+Trees: optimizing persistent index performance on 3DXPoint memory. Proceedings of the VLDB Endowment, 2020, 13( 7): 1078–1090
7	B, Lu X, Hao T, Wang E Lo . Dash: scalable hashing on persistent memory. Proceedings of the VLDB Endowment, 2020, 13( 8): 1147–1161
8	Y, Luo P, Jin Q, Zhang B Cheng . TLBtree: a read/write-optimized tree index for non-volatile memory. In: Proceedings of the 37th International Conference on Data Engineering. 2021, 1889−1894
9	Q, Wang Y, Lu J, Li J Shu . Nap: a black-box approach to NUMA-aware persistent memory indexes. In: Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation. 2021, 93−111
10	B, Zhang S, Zheng Z, Qi L Huang . NBTree: a lock-free PM-friendly persistent B+-tree for eADR-enabled PM systems. Proceedings of the VLDB Endowment, 2022, 15( 6): 1187–1200
11	P, Zuo Y, Hua J Wu . Level hashing: a high-performance and flexible-resizing persistent hashing index structure. ACM Transactions on Storage, 2019, 15( 2): 13
12	B, Lu J, Ding E, Lo U F, Minhas T Wang . APEX: a high-performance learned index on persistent memory. Proceedings of the VLDB Endowment, 2021, 15( 3): 597–610
13	L, Benson H, Makait T Rabl . Viper: an efficient hybrid PMem-DRAM key-value store. Proceedings of the VLDB Endowment, 2021, 14( 9): 1544–1556
14	B, Yan X, Cheng B, Jiang S, Chen C, Shang J, Wang G, Huang X, Yang W Cao . Revisiting the design of LSM-tree based OLTP storage engine with persistent memory. Proceedings of the VLDB Endowment, 2021, 14( 10): 1872–1885
15	W, Zhang X, Zhao S, Jiang H Jiang . ChameleonDB: a key-value store for optane persistent memory. In: Proceedings of the 16th European Conference on Computer Systems. 2021, 194−209
16	S, Gugnani A, Kashyap X Lu . Understanding the idiosyncrasies of real persistent memory. Proceedings of the VLDB Endowment, 2020, 14( 4): 626–639
17	I, Oukid J, Lasperas A, Nica T, Willhalm W Lehner . FPTree: a hybrid SCM-DRAM persistent and concurrent B-tree for storage class memory. In: Proceedings of 2016 International Conference on Management of Data. 2016, 371−386
18	G, Liu Y, Luo P Jin . HATree: a hotness-aware tree index with in-node hotspot cache for NVM/DRAM-based hybrid memory architecture. In: Proceedings of the 27th International Conference on Database Systems for Advanced Applications. 2022, 560−568
19	X, Zhou L, Shou K, Chen W, Hu G Chen . DPTree: differential indexing for persistent memory. Proceedings of the VLDB Endowment, 2019, 13( 4): 421–434
20	D, Hu Z, Chen J, Wu J, Sun H Chen . Persistent memory hash indexes: an experimental evaluation. Proceedings of the VLDB Endowment, 2021, 14( 5): 785–798
21	S, Chen Q Jin . Persistent B+-trees in non-volatile main memory. Proceedings of the VLDB Endowment, 2015, 8( 7): 786–797
22	J, Yang Q, Wei C, Chen C, Wang K L, Yong B He . NV-Tree: reducing consistency cost for NVM-based single level systems. In: Proceedings of the 13th USENIX Conference on File and Storage Technologies. 2015, 167−181
23	J, Yang Q, Wei C, Wang C, Chen K L, Yong B He . NV-Tree: a consistent and workload-adaptive tree structure for non-volatile memory. IEEE Transactions on Computers, 2016, 65( 7): 2169–2183
24	Z, Cao S, Dong S, Vemuri D H C Du . Characterizing, modeling, and benchmarking RocksDB key-value workloads at facebook. In: Proceedings of the 18th USENIX Conference on File and Storage Technologies. 2020, 209−223
25	A, Baldassin J, Barreto D, Castro P Romano . Persistent memory: a survey of programming support and implementations. ACM Computing Surveys, 2022, 54( 7): 152
26	S Scargall . Programming Persistent Memory: A Comprehensive Guide for Developers. Berkeley: Apress, 2020
27	A C C Yao . On random 2–3 trees. Acta Informatica, 1978, 9( 2): 159–170
28	J, Chen L, Chen S, Wang G, Zhu Y, Sun H, Liu F Li . HotRing: a hotspot-aware in-memory key-value store. In: Proceedings of the 18th USENIX Conference on File and Storage Technologies. 2020, 239−252
29	P L, Lehman S B Yao . Efficient locking for concurrent operations on B-trees. ACM Transactions on Database Systems, 1981, 6( 4): 650–670
30	C C, Lo K L Sue . Second chance replacement policy for mobile database overflow. In: Proceedings of the Global Telecommunications Conference. 2002, 1683−1687
31	Y, Luo P, Jin Z, Zhang J, Zhang B, Cheng Q Zhang . Two birds with one stone: boosting both search and write performance for tree indices on persistent memory. ACM Transactions on Embedded Computing Systems, 2021, 20( 5s): 50
32	P, Jin X, Xie N, Wang L Yue . Optimizing R-tree for flash memory. Expert Systems with Applications, 2015, 42( 10): 4676–4686
33	B K, Kim D H Lee . LSB-Tree: a log-structured b-tree index structure for NAND flash SSDs. Design Automation for Embedded Systems, 2015, 19( 1−2): 77–100
34	D R, Purandare P, Wilcox H, Litz S Finkelstein . Append is near: log-based data management on ZNS SSDs. In: Proceedings of the 12th Conference on Innovative Data Systems Research. 2022
35	B F, Cooper A, Silberstein E, Tam R, Ramakrishnan R Sears . Benchmarking cloud serving systems with YCSB. In: Proceedings of the 1st ACM Symposium on Cloud Computing. 2010, 143−154
36	S, Jamil A, Salam A, Khan B, Burgstaller S S, Park Y Kim . Scalable NUMA-aware persistent B+-tree for non-volatile memory devices. Cluster Computing, 2023, 26(5): 2865−2881
37	V, Leis F, Scheibner A, Kemper T Neumann . The ART of practical synchronization. In: Proceedings of the 12th International Workshop on Data Management on New Hardware. 2016

[1]

FCS-23344-OF-PJ_suppl_1

Download

[1]	Ye CHI, Jianhui YUE, Xiaofei LIAO, Haikun LIU, Hai JIN. A hybrid memory architecture supporting fine-grained data migration[J]. Front. Comput. Sci., 2024, 18(2): 182103-.
[2]	Tingting CHEN, Haikun LIU, Xiaofei LIAO, Hai JIN. Resource abstraction and data placement for distributed hybrid memory pool[J]. Front. Comput. Sci., 2021, 15(3): 153103-.
[3]	Wuyang JU,Jianxin LI,Weiren YU,Richong ZHANG. iGraph: an incremental data processing system for dynamic graph[J]. Front. Comput. Sci., 2016, 10(3): 462-476.
[4]	Xiaolong LI, Gang PAN, Zhaohui WU, Guande QI, Shijian LI, Daqing ZHANG, Wangsheng ZHANG, Zonghui WANG. Prediction of urban human mobility using large-scale taxi traces and its applications[J]. Front Comput Sci, 2012, 6(1): 111-121.

Viewed

Full text

Abstract

Cited

Shared

Discussed