ZB^(+)-tree:一种ZNS SSD感知的新型索引结构  

ZB^(+)-tree:A Novel ZNS SSD-Aware Index Structure

作　　者：刘扬[1] 金培权[2] 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)

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230026 [2]中国科学院电磁空间信息重点实验室,合肥230026

出　　处：《计算机研究与发展》2023年第3期509-524,共16页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(62072419)。

摘　　要：ZNS SSD是近年来提出的一种新型固态硬盘(solid state drive,SSD),它以分区(Zone)的方式管理和存取SSD内的数据.相比于传统SSD,ZNS SSD可以有效提升SSD的读写吞吐,降低写放大,减少SSD的预留空间.但是,ZNS SSD要求Zone内必须采用顺序写模式,并且Zone上的空间分配、垃圾回收等任务都需要用户自行控制.ZNS SSD的这些特性对于传统数据库系统的存储管理、索引、缓存等技术均提出了新的挑战.针对如何使传统的B^(+)-tree索引结构适配ZNS SSD的问题,提出了一种ZNS SSD感知的新型索引结构——ZB^(+)-tree(ZNS-aware B^(+)-tree).ZB^(+)-tree是目前已知的首个ZNS SSD感知的索引,它以B^(+)-tree为基础,利用ZNS SSD内部支持少量随机写的常规Zone(conventional zone,Cov-Zone)和只支持顺序写的顺序Zone(sequential zone,Seq-Zone),通过常规Zone来吸收对ZNS SSD的随机写操作.ZB^(+)-tree将索引节点分散存储在常规Zone和顺序Zone中,并为2种Zone内的节点分别设计了节点结构,使ZB^(+)-tree不仅能够吸收对索引的随机写操作,而且又可以保证顺序Zone内的顺序写要求.在实验中利用null_blk和libzbd模拟ZNS SSD设备,并将现有的CoW B^(+)-tree修改后作为对比索引.结果表明,ZB^(+)-tree在运行时间、空间利用率等多个指标上均优于CoW B^(+)-tree.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^(+)树 数据库索引 CoW B^(+)-tree 分区存储 

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