ZB<sup>+</sup>-tree: A Novel ZNS SSD-Aware Index Structure

Liu Yang; Jin Peiquan

doi:10.7544/issn1000-1239.202220502

Journal of Computer Research and Development > 2023 > 60(3): 509-524. > DOI: 10.7544/issn1000-1239.202220502

Liu Yang, Jin Peiquan. ZB⁺-tree: A Novel ZNS SSD-Aware Index Structure[J]. Journal of Computer Research and Development, 2023, 60(3): 509-524. DOI: 10.7544/issn1000-1239.202220502

Citation:

Liu Yang, Jin Peiquan. ZB⁺-tree: A Novel ZNS SSD-Aware Index Structure[J]. Journal of Computer Research and Development, 2023, 60(3): 509-524. DOI: 10.7544/issn1000-1239.202220502

Citation:

Liu Yang, Jin Peiquan. ZB⁺-tree: A Novel ZNS SSD-Aware Index Structure[J]. Journal of Computer Research and Development, 2023, 60(3): 509-524. DOI: 10.7544/issn1000-1239.202220502

PDF (2296 KB)

ZB⁺-tree: A Novel ZNS SSD-Aware Index Structure

Liu Yang,
Jin Peiquan^,

School of Computer Science and Technology , University of Science and Technology of China , Hefei 230026
Key Laboratory of Electromagnetic Space Information , Chinese Academy of Sciences , Hefei 230026

Funds: This work was supported by the National Natural Science Foundation of China (62072419).

More Information

Received Date: June 10, 2022
Revised Date: November 03, 2022
Available Online: February 26, 2023

Graphical Abstract

Abstract

Abstract

ZNS SSD is a newly emerging solid state drive (SSD). It supports zone-based storage and access of data in SSD. Compared with traditional SSDs, ZNS SSD can effectively improve the read-write throughput of SSD, reduce write amplification and over-provisioning in SSD. However, ZNS SSD requires that data must be written to zones sequentially, and tasks such as space allocation and garbage collection need to be controlled by users. These characteristics of ZNS SSD pose new challenges to many components in traditional database systems, such as storage management, indexing, and buffer management. This paper mainly studies how to adapt the traditional B⁺-tree index structure to ZNS SSD. We propose a new ZNS SSD-aware index structure called ZB⁺-tree (ZNS-aware B⁺-tree), which is the first ZNS SSD-aware index so far. ZB⁺-tree takes B⁺-tree as the base structure, and utilizes the two kinds of zones inside ZNS SSD, namely conventional zones supporting a few random writes and sequential zones only supporting sequential writes. In particular, it uses conventional zones to absorb random writes to ZNS SSD and stores the index nodes in conventional and sequential zones separately. We design different node structures for the nodes in the two zones. By using different types of nodes on the two zones, ZB⁺-tree can absorb random writes on the index and ensure the sequential write requirements on sequential zones. We conduct experiments by simulating ZNS SSD using null_blk and libzbd. Also, we modify the existing copy-on-write (CoW) B⁺-tree as the competitor. The results show that ZB⁺-tree outperforms CoW B⁺-tree in various metrics including running time and space efficiency.
- ZNS SSD,
- B⁺-tree,
- database index,
- CoW B⁺-tree,
- zoned storage

FullText(HTML)

References (29)

References

[1]	Bjørling M, Aghayev A, Holmberg H, et al. ZNS: Avoiding the block interface tax for flash-based SSDs [C] //Proc of 2021 USENIX Annual Technical Conf (USENIX ATC 21). Berkeley, CA: USENIX Association, 2021: 689−703
[2]	Han K, Gwak H, Shin D, et al. ZNS+: Advanced zoned namespace interface for supporting in-storage zone compaction [C] //Proc of the 15th USENIX Symp on Operating Systems Design and Implementation (OSDI 21). Berkeley, CA: USENIX Association, 2021: 147−162
[3]	Stavrinos T, Berger D S, Katz-Bassett E, et al. Don't be a blockhead: Zoned namespaces make work on conventional SSDs obsolete[C] //Proc of the Workshop on Hot Topics in Operating Systems. New York: ACM, 2021: 144−151
[4]	Maheshwari U. From blocks to rocks: A natural extension of zoned namespaces[C] //Proc of the 13th ACM Workshop on Hot Topics in Storage and File Systems. New York: ACM, 2021: 21−27
[5]	Choi G, Lee K, Oh M, et al. A new LSM-style garbage collection scheme for ZNS SSDs [C] //Proc of the 12th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 20). Berkeley, CA: USENIX Association, 2020: Article 1
[6]	Purandare D R, Wilcox P, Litz H, et al. Append is near: Log-based data management on ZNS SSDs[C/OL] //Proc of the 12th Annual Conf on Innovative Data Systems Research (CIDR’22). 2022[2022-08-20].https://www.ssrc.ucsc.edu/media/pubs/8698b15f3152427d1285a995af615fbe7be26c7b.pdf
[7]	Shin H, Oh M, Choi G, et al. Exploring performance characteristics of ZNS SSDs: Observation and implication[C/OL] //Proc of the 9th Non-Volatile Memory Systems and Applications Symp (NVMSA). Piscataway, NJ: IEEE, 2020[2022-08-20].https://ieeexplore.ieee.org/abstract/document/9188086
[8]	Park C, Cheon W, Kang J, et al. A reconfigurable FTL (flash translation layer) architecture for NAND flash-based applications[J/OL]. ACM Transactions on Embedded Computing Systems, 2008[2022-08-20].https://people.eecs.berkeley.edu/~kubitron/courses/cs262a/handouts/papers/a38-park.pdf
[9]	Bux W, Iliadis I. Performance of greedy garbage collection in flash-based solid-state drives[J]. Performance Evaluation, 2010, 67(11): 1172−1186 doi: 10.1016/j.peva.2010.07.003
[10]	Smith K. Understanding SSD over-provisioning [EB/OL]. 2022[2022-08-20].https://www.edn.com/understanding-ssd-over-provisioning
[11]	Hu Xiaoyu, Eleftheriou E, Haas R, et al. Write amplification analysis in flash-based solid state drives[C/OL] //Proc of 2009 Israeli Experimental Systems Conf (SYSTOR). New York: ACM , 2009[2022-08-20]. http://roman.pletka.ch/publications/hu2009write-ampl.pdf
[12]	Bjørling M. ZNS SDDs in Western Digital [EB/OL]. 2020[2022-08-20].https://snia.org/sites/default/files/SDC/2020/075-Bjørling-Zoned-Namespaces-ZNS-SSDs.pdf
[13]	Western Digital. NVMe Zoned Namespaces (ZNS) SSDs [EB/OL]. 2021[2022-08-20].https://zonedstorage.io/docs/introduction/zns
[14]	NVMe. Zoned Namespaces Command Set [EB/OL]. 2022[2022-08-20].https://nvmexpress.org/wp-content/uploads/NVM-Express-Zoned-Namespace-Command-Set-Specification-1.1b-2022.01.05-Ratified.pdf
[15]	Roh H, Park S, Kim S, et al. B⁺-tree index optimization by exploiting internal parallelism of flash-based solid state drives[J]. Proceedings of the VLDB Endowment, 2011, 5(4): 286−297 doi: 10.14778/2095686.2095688
[16]	Na G J, Lee S W, Moon B. Dynamic in-page logging for B⁺-tree index[J]. IEEE Transactions on Knowledge and Data Engineering, 2011, 24(7): 1231−1243
[17]	Agrawal D, Ganesan D, Sitaraman R, et al. Lazy-adaptive tree: An optimized index structure for flash devices[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 361−372 doi: 10.14778/1687627.1687669
[18]	Ahn J S, Kang D, Jung D, et al. μ*-tree: An ordered index structure for NAND flash memory with adaptive page layout scheme[J]. IEEE Transactions on Computers, 2012, 62(4): 784−797
[19]	Fang Huawei, Yeh M, Suei P, et al. An adaptive endurance-aware B⁺-tree for flash memory storage systems[J]. IEEE Transactions on Computers, 2013, 63(11): 2661−2673
[20]	Jin Peiquan, Yang Chengcheng, Jensen C, et al. Read/write-optimized tree indexing for solid-state drives[J]. The VLDB Journal, 2016, 25(5): 695−717 doi: 10.1007/s00778-015-0406-1
[21]	Lv Yanfei, Li Jing, Cui Bin, et al. Log-compact R-tree: An efficient spatial index for SSD[C]//Proc of the Int Conf on Database Systems for Advanced Applications (DASFAA 11). Berlin: Springer, 2011: 202−213
[22]	Jin Peiquan, Yang Chengcheng, Wang Xiaoliang, et al. SAL-Hashing: A self-adaptive linear hashing index for SSDs[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(3): 519−532 doi: 10.1109/TKDE.2018.2884714
[23]	Ho V, Park D. WPCB-tree: A novel flash-aware B-tree index using a write pattern converter [J/OL]. Symmetry, 2018[2022-08-20].https://www.mdpi.com/2073 − 8994/10/1/18/pdf
[24]	Jin R, Cho H, Lee S, et al. Lazy-split B⁺-tree: A novel B⁺-tree index scheme for flash-based database systems[J]. Design Automation for Embedded Systems, 2013, 17(1): 167−191 doi: 10.1007/s10617-013-9123-4
[25]	Twigg A, Byde A, Miłoś G, et al. Stratified B-trees and versioned dictionaries[C] //Proc of the 3rd Workshop on Hot Topics in Storage and File Systems (HotStorage 11). Berkeley, CA: USENIX Association, 2011: Article 3
[26]	闫玮,张兴军,纪泽宇,等. 基于持久性内存的单向移动B⁺树[J]. 计算机研究与发展,2021,58(2):371−383 doi: 10.7544/issn1000-1239.2021.20200403 Yan Wei, Zhang Xingjun, Ji Zeyu, et al. One-direction shift B⁺-tree based on persistent memory[J]. Journal of Computer Research and Development, 2021, 58(2): 371−383 (in Chinese) doi: 10.7544/issn1000-1239.2021.20200403
[27]	Western Digital. null_blk [EB/OL]. 2022[2022-10-15].https://zonedstorage.io/docs/getting-started/zns-device
[28]	Western Digital. libzbd [EB/OL]. 2022[2022-08-20].https://github.com/westerndigitalcorporation/libzbd
[29]	Cooper B F, Silberstein A, Tam E, et al. Benchmarking cloud serving systems with YCSB[C] //Proc of the 1st ACM Symp on Cloud Computing (SoCC 10). New York: ACM, 2010: 143−154

[1]	Zhang Naizhou, Cao Wei, Zhang Xiaojian, Li Shijun. Conversation Generation Based on Variational Attention Knowledge Selection and Pre-trained Language Model[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440551
[2]	Wang Honglin, Yang Dan, Nie Tiezheng, Kou Yue. Attributed Heterogeneous Information Network Embedding with Self-Attention Mechanism for Product Recommendation[J]. Journal of Computer Research and Development, 2022, 59(7): 1509-1521. DOI: 10.7544/issn1000-1239.20210016
[3]	Cheng Yan, Yao Leibo, Zhang Guanghe, Tang Tianwei, Xiang Guoxiong, Chen Haomai, Feng Yue, Cai Zhuang. Text Sentiment Orientation Analysis of Multi-Channels CNN and BiGRU Based on Attention Mechanism[J]. Journal of Computer Research and Development, 2020, 57(12): 2583-2595. DOI: 10.7544/issn1000-1239.2020.20190854
[4]	Wei Zhenkai, Cheng Meng, Zhou Xiabing, Li Zhifeng, Zou Bowei, Hong Yu, Yao Jianmin. Convolutional Interactive Attention Mechanism for Aspect Extraction[J]. Journal of Computer Research and Development, 2020, 57(11): 2456-2466. DOI: 10.7544/issn1000-1239.2020.20190748
[5]	Chen Yanmin, Wang Hao, Ma Jianhui, Du Dongfang, Zhao Hongke. A Hierarchical Attention Mechanism Framework for Internet Credit Evaluation[J]. Journal of Computer Research and Development, 2020, 57(8): 1755-1768. DOI: 10.7544/issn1000-1239.2020.20200217
[6]	Li Mengying, Wang Xiaodong, Ruan Shulan, Zhang Kun, Liu Qi. Student Performance Prediction Model Based on Two-Way Attention Mechanism[J]. Journal of Computer Research and Development, 2020, 57(8): 1729-1740. DOI: 10.7544/issn1000-1239.2020.20200181
[7]	Zhang Yingying, Qian Shengsheng, Fang Quan, Xu Changsheng. Multi-Modal Knowledge-Aware Attention Network for Question Answering[J]. Journal of Computer Research and Development, 2020, 57(5): 1037-1045. DOI: 10.7544/issn1000-1239.2020.20190474
[8]	Zhang Yixuan, Guo Bin, Liu Jiaqi, Ouyang Yi, Yu Zhiwen. app Popularity Prediction with Multi-Level Attention Networks[J]. Journal of Computer Research and Development, 2020, 57(5): 984-995. DOI: 10.7544/issn1000-1239.2020.20190672
[9]	Liu Ye, Huang Jinxiao, Ma Yutao. An Automatic Method Using Hybrid Neural Networks and Attention Mechanism for Software Bug Triaging[J]. Journal of Computer Research and Development, 2020, 57(3): 461-473. DOI: 10.7544/issn1000-1239.2020.20190606
[10]	Zhang Zhichang, Zhang Zhenwen, Zhang Zhiman. User Intent Classification Based on IndRNN-Attention[J]. Journal of Computer Research and Development, 2019, 56(7): 1517-1524. DOI: 10.7544/issn1000-1239.2019.20180648