ZB-+-tree：一种Z..._SSD感知的新型索引结构_刘扬.pdf

ZB+-tree：一种 ZNS SSD 感知的新型索引结构刘扬金培权（中国科学技术大学计算机科学与技术学院合肥230026）（中国科学院电磁空间信息重点实验室合肥230026）（）ZB+-tree:A Novel ZNS SSD-Aware Index StructureLiuYangandJinPeiquan（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）AbstractZNSSSDisanewlyemergingsolidstatedrive(SSD).Itsupportszone-basedstorageandaccessofdatainSSD.ComparedwithtraditionalSSDs,ZNSSSDcaneffectivelyimprovetheread-writethroughputofSSD,reducewriteamplificationandover-provisioninginSSD.However,ZNSSSDrequiresthatdatamustbewrittentozonessequentially,and tasks such as space allocation and garbage collection need to be controlled by users.ThesecharacteristicsofZNSSSDposenewchallengestomanycomponentsintraditionaldatabasesystems,suchasstoragemanagement,indexing,andbuffermanagement.ThispapermainlystudieshowtoadaptthetraditionalB+-treeindexstructuretoZNSSSD.WeproposeanewZNSSSD-awareindexstructurecalledZB+-tree(ZNS-awareB+-tree),whichisthefirstZNSSSD-awareindexsofar.ZB+-treetakesB+-treeasthebasestructure,andutilizesthetwokindsofzonesinsideZNSSSD,namelyconventionalzonessupportingafewrandomwritesandsequentialzonesonlysupportingsequentialwrites.Inparticular,itusesconventionalzonestoabsorbrandomwritestoZNSSSDandstorestheindexnodesinconventionalandsequentialzonesseparately.Wedesigndifferentnodestructuresforthenodesinthetwozones.Byusingdifferenttypesofnodesonthetwozones,ZB+-treecanabsorbrandomwritesontheindexandensurethesequentialwriterequirementsonsequentialzones.WeconductexperimentsbysimulatingZNSSSDusingnull_blkandlibzbd.Also,wemodifytheexistingcopy-on-write(CoW)B+-treeasthecompetitor.TheresultsshowthatZB+-treeoutperformsCoWB+-treeinvariousmetricsincludingrunningtimeandspaceefficiency.Key wordsZNSSSD；B+-tree；databaseindex；CoWB+-tree；zonedstorage摘要ZNSSSD 是近年来提出的一种新型固态硬盘（solidstatedrive，SSD），它以分区（Zone）的方式管理和存取 SSD 内的数据.相比于传统 SSD，ZNSSSD 可以有效提升 SSD 的读写吞吐，降低写放大，减少SSD 的预留空间.但是，ZNSSSD 要求 Zone 内必须采用顺序写模式，并且 Zone 上的空间分配、垃圾回收等任务都需要用户自行控制.ZNSSSD 的这些特性对于传统数据库系统的存储管理、索引、缓存等技术均提出了新的挑战.针对如何使传统的 B+-tree 索引结构适配 ZNSSSD 的问题，提出了一种 ZNSSSD 感知的新型索引结构ZB+-tree（ZNS-awareB+-tree）.ZB+-tree 是目前已知的首个 ZNSSSD 感知的索引，它以 B+-tree 为基础，利用 ZNSSSD 内部支持少量随机写的常规 Zone（conventionalzone，Cov-Zone）和只支持顺序写的顺序 Zone（sequentialzone，Seq-Zone），通过常规 Zone 来吸收对 ZNSSSD 的随机写操作.ZB+-tree 将索收稿日期：2022-06-11；修回日期：2022-11-04基金项目：国家自然科学基金项目（62072419）ThisworkwassupportedbytheNationalNaturalScienceFoundationofChina(62072419).通信作者：金培权()计 算 机 研 究 与 发 展DOI：10.7544/issn1000-1239.202220502JournalofComputerResearchandDevelopment60（3）：509524，2023引节点分散存储在常规 Zone 和顺序 Zone 中，并为 2 种 Zone 内的节点分别设计了节点结构，使 ZB+-tree 不仅能够吸收对索引的随机写操作，而且又可以保证顺序 Zone 内的顺序写要求.在实验中利用 null_blk 和libzbd 模拟 ZNSSSD 设备，并将现有的 CoWB+-tree 修改后作为对比索引.结果表明，ZB+-tree 在运行时间、空间利用率等多个指标上均优于 CoWB+-tree.关键词ZNSSSD；B+树；数据库索引；CoWB+-tree；分区存储中图法分类号TP311.13ZNSSSD（ZonedNamespacesSSD）1-7是 2019 年由西部数据公司和三星公司推出的新一代固态硬盘（solidstatedrive，SSD），目前受到了工业界和学术界的广泛关注.由于基于闪存的 SSD只有在块被完全擦除以后才能重写，传统的SSD通过使用闪存转换层（flashtranslationlayer，FTL）8来适应这一特性，但由于闪存块存在物理限制（擦除操作以块大小进行，而读写操作以页大小进行），因此经常需要进行垃圾回收（garbagecollection，GC）5,9，同时也带来了预留空间（overprovisioning，OP）10和写放大（writeamplification，WA）11等问题，ZNSSSD 可以有效提升 SSD 的读写吞吐，降低写入时的写放大，减少 SSD 本身的预留空间，并且还能解决传统 SSD 在空间占用达到一定程度时由于内部垃圾回收导致的性能不稳定的问题12-13，因此利用 ZNSSSD 来构建数据库系统是一个趋势3.图 1 展示了 ZNSSSD和传统SSD数据放置对比，在 ZNSSSD 上数据由主机程序显式地控制放置.虽然 ZNSSSD 具有如此多优点，但它同样带来了一些挑战3,7.与传统基于闪存的 SSD 相比，ZNSSSD 移除了 FTL，将分区（Zone）的空间直接交由主机程序控制管理，由主机程序来处理垃圾回收、磨损均衡、数据放置等，这扩大了用户数据布局的设计空间.由用户程序来决定数据的放置、生命周期和垃圾回收时机，通过有效合理地组织数据，可以提高系统的性能.但ZNSSSD同样给主机程序的设计带来了新的要求，比如一个 Zone 内有一个写指针只能进行顺序写、不同 Zone 性能有差异、何时进行 Zone-Reset 操作等7,14.应用程序1应用程序2应用程序3应用程序3应用程序2应用程序1传统SSD控制器传统SSD:设备控制数据放置ZNS SSD:应用程序控制Zone内的数据放置ZNS SSD控制器闪存闪存Fig.1ComparisonofZNSSSDandconventionalSSDdataplacement图1ZNSSSD 和传统 SSD 数据放置对比B+-tree 是数据库中经典的索引结构，以往研究者已经提出了多种针对 SSD、持久性内存等新型存储的 B+-tree 优化方法15-26.但是，已有的 SSD 索引设计重点在于减少对 SSD 的随机写操作.虽然 ZNSSSD的底层介质仍是闪存，但由于 Zone 内只能顺序写，因此随机写的问题不再是 ZNSSSD 上 B+-tree 索引优化的第一目标.B+-tree 如何在没有 FTL 的情况下适应 ZNSSSD 的分区特性以及 Zone 内顺序写要求，是ZNSSSD 感知的 B+-tree 索引需要解决的关键问题.针对传统 SSD 设计的索引由于没有考虑 ZNSSSD 的特性，所以都无法直接运行在 ZNSSSD 上.此外，根据我们的调研，目前也还没有提出 ZNSSSD 感知的索引结构.本文提出了一种ZNSSSD 感知的新型索引结构ZB+-tree（ZNS-awareB+-tree）.我们发现，虽然 ZNSSSD上要求 Zone 内顺序写，但是实际的分区块设备（zonedblockdevice，ZBD）中除了只允许顺序写的顺序 Zone（sequentialzone，Seq-Zone），还存在着少量允许随机写的常规 Zone（conventionalzone，Cov-Zone）.因此，我们结合了 ZNSSSD 内部这 2 类 Zone 的特性设计了 ZB+-tree 的结构来适配 ZNSSSD.具体而言，本文的主要工作和贡献可总结为 3 个方面：510计算机研究与发展2023，60（3）1）提出了一种 ZNSSSD 感知的新型索引结构ZB+-tree.ZB+-tree 利 用 了 ZNSSSD 内 部 的 Cov-Zone来吸收对 Zone 的随机写操作，并将索引节点分散存储在 Cov-Zone 和 Seq-Zone 中，通过设计不同的节点结构来管理不同 Zone 上的节点，在保证 Zone 内顺序写要求的同时提高空间效率.2）设 计 了 ZB+-tree 上 的 相 关 操 作，包 括 Sync，Search，Insert，Delete 等，在保证索引性能的同时减少操作过程中的读写次数.3）利用 null_blk27和 libzbd28模拟 ZNSSSD 设备开展实验，并将传统的 CoWB+-tree 修改后作为对比索引.结果表明，ZB+-tree 能有效阻断级联更新，减少读写次数，在运行时间、空间利用率上均优于 CoWB+-tree.1背景与相关工作本节主要介绍目前业界对于 ZNSSSD 的相关研究和 SSD感知的 B+-tree 索引的相关工作，同时也介绍本文用于对比实验的 CoWB+-tree.1.1ZNS SSD 相关工作ZNSSSD 将其空间划分为许多的 Zones，在一个Zone 内可以随机读，但是只能顺序写，当一个 Zone写满时会触发 Zone-Reset