劉揚(yáng) 金培權(quán)

（中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 合肥 230026）

（中國(guó)科學(xué)院電磁空間信息重點(diǎn)實(shí)驗(yàn)室 合肥 230026）

ZNS SSD（Zoned Namespaces SSD）[1-7]是2019 年由西部數(shù)據(jù)公司和三星公司推出的新一代固態(tài)硬盤（solid state drive，SSD），目前受到了工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注.由于基于閃存的SSD只有在塊被完全擦除以后才能重寫，傳統(tǒng)的 SSD 通過(guò)使用閃存轉(zhuǎn)換層（flash translation layer，F(xiàn)TL）[8]來(lái)適應(yīng)這一特性，但由于閃存塊存在物理限制（擦除操作以塊大小進(jìn)行，而讀寫操作以頁(yè)大小進(jìn)行），因此經(jīng)常需要進(jìn)行垃圾回收（garbage collection，GC）[5,9]，同時(shí)也帶來(lái)了預(yù)留空間（over provisioning，OP）[10]和寫放大（write amplification，WA）[11]等問(wèn)題，ZNS SSD 可以有效提升SSD 的讀寫吞吐，降低寫入時(shí)的寫放大，減少SSD 本身的預(yù)留空間，并且還能解決傳統(tǒng)SSD 在空間占用達(dá)到一定程度時(shí)由于內(nèi)部垃圾回收導(dǎo)致的性能不穩(wěn)定的問(wèn)題[12-13]，因此利用ZNS SSD 來(lái)構(gòu)建數(shù)據(jù)庫(kù)系統(tǒng)是一個(gè)趨勢(shì)[3].

圖1 展示了ZNS SSD 和傳統(tǒng) SSD 數(shù)據(jù)放置對(duì)比，在ZNS SSD 上數(shù)據(jù)由主機(jī)程序顯式地控制放置.雖然ZNS SSD 具有如此多優(yōu)點(diǎn)，但它同樣帶來(lái)了一些挑戰(zhàn)[3,7].與傳統(tǒng)基于閃存的SSD 相比，ZNS SSD 移除了FTL，將分區(qū)（Zone）的空間直接交由主機(jī)程序控制管理，由主機(jī)程序來(lái)處理垃圾回收、磨損均衡、數(shù)據(jù)放置等，這擴(kuò)大了用戶數(shù)據(jù)布局的設(shè)計(jì)空間.由用戶程序來(lái)決定數(shù)據(jù)的放置、生命周期和垃圾回收時(shí)機(jī)，通過(guò)有效合理地組織數(shù)據(jù)，可以提高系統(tǒng)的性能.但ZNS SSD 同樣給主機(jī)程序的設(shè)計(jì)帶來(lái)了新的要求，比如一個(gè)Zone 內(nèi)有一個(gè)寫指針只能進(jìn)行順序?qū)?、不同Zone 性能有差異、何時(shí)進(jìn)行Zone-Reset 操作等[7,14].

Fig.1 Comparison of ZNS SSD and conventional SSD data placement圖1 ZNS SSD 和傳統(tǒng)SSD 數(shù)據(jù)放置對(duì)比

B+-tree 是數(shù)據(jù)庫(kù)中經(jīng)典的索引結(jié)構(gòu)，以往研究者已經(jīng)提出了多種針對(duì)SSD、持久性內(nèi)存等新型存儲(chǔ)的B+-tree 優(yōu)化方法[15-26].但是，已有的SSD 索引設(shè)計(jì)重點(diǎn)在于減少對(duì)SSD 的隨機(jī)寫操作.雖然ZNS SSD的底層介質(zhì)仍是閃存，但由于Zone 內(nèi)只能順序?qū)?，因此隨機(jī)寫的問(wèn)題不再是ZNS SSD 上B+-tree 索引優(yōu)化的第一目標(biāo).B+-tree 如何在沒(méi)有FTL 的情況下適應(yīng)ZNS SSD 的分區(qū)特性以及Zone 內(nèi)順序?qū)懸?，是ZNS SSD 感知的B+-tree 索引需要解決的關(guān)鍵問(wèn)題.針對(duì)傳統(tǒng)SSD 設(shè)計(jì)的索引由于沒(méi)有考慮ZNS SSD 的特性，所以都無(wú)法直接運(yùn)行在ZNS SSD 上.此外，根據(jù)我們的調(diào)研，目前也還沒(méi)有提出ZNS SSD 感知的索引結(jié)構(gòu).

本文提出了一種ZNS SSD 感知的新型索引結(jié)構(gòu)——ZB+-tree（ZNS-aware B+-tree）.我們發(fā)現(xiàn)，雖然ZNS SSD上要求Zone 內(nèi)順序?qū)懀菍?shí)際的分區(qū)塊設(shè)備（zoned block device，ZBD）中除了只允許順序?qū)懙捻樞騔one（sequential zone，Seq-Zone），還存在著少量允許隨機(jī)寫的常規(guī)Zone（conventional zone，Cov-Zone）.因此，我們結(jié)合了ZNS SSD 內(nèi)部這2 類Zone 的特性設(shè)計(jì)了ZB+-tree 的結(jié)構(gòu)來(lái)適配ZNS SSD.具體而言，本文的主要工作和貢獻(xiàn)可總結(jié)為3 個(gè)方面：

1）提出了一種ZNS SSD 感知的新型索引結(jié)構(gòu)ZB+-tree.ZB+-tree 利用了ZNS SSD 內(nèi)部的Cov-Zone來(lái)吸收對(duì)Zone 的隨機(jī)寫操作，并將索引節(jié)點(diǎn)分散存儲(chǔ)在Cov-Zone 和Seq-Zone 中，通過(guò)設(shè)計(jì)不同的節(jié)點(diǎn)結(jié)構(gòu)來(lái)管理不同Zone 上的節(jié)點(diǎn)，在保證Zone 內(nèi)順序?qū)懸蟮耐瑫r(shí)提高空間效率.

2）設(shè)計(jì)了ZB+-tree 上的相 關(guān)操作，包括Sync，Search，Insert，Delete 等，在保證索引性能的同時(shí)減少操作過(guò)程中的讀寫次數(shù).

3）利用null_blk[27]和libzbd[28]模擬ZNS SSD 設(shè)備開展實(shí)驗(yàn)，并將傳統(tǒng)的CoW B+-tree 修改后作為對(duì)比索引.結(jié)果表明，ZB+-tree 能有效阻斷級(jí)聯(lián)更新，減少讀寫次數(shù)，在運(yùn)行時(shí)間、空間利用率上均優(yōu)于CoW B+-tree.

1 背景與相關(guān)工作

本節(jié)主要介紹目前業(yè)界對(duì)于ZNS SSD 的相關(guān)研究和SSD 感知的B+-tree 索引的相關(guān)工作，同時(shí)也介紹本文用于對(duì)比實(shí)驗(yàn)的CoW B+-tree.

1.1 ZNS SSD 相關(guān)工作

ZNS SSD 將其空間劃分為許多的Zones，在一個(gè)Zone 內(nèi)可以隨機(jī)讀，但是只能順序?qū)?，?dāng)一個(gè)Zone寫滿時(shí)會(huì)觸發(fā)Zone-Reset 和GC 操作.圖2 顯示了Zone 的大致結(jié)構(gòu)，每個(gè)Zone 內(nèi)有一個(gè)寫指針，Zone內(nèi)有嚴(yán)格的順序?qū)懴拗?

Fig.2 The structure of Zone圖2 Zone 的結(jié)構(gòu)

傳統(tǒng)SSD 由于FTL 的存在，會(huì)給主機(jī)程序提供塊接口[1]，各類任務(wù)都交由FTL 來(lái)處理，SSD 通過(guò)FTL提供給上層應(yīng)用的接口是支持隨機(jī)讀寫的，在程序設(shè)計(jì)時(shí)可以視為硬盤.FTL 的存在使得之前為硬盤設(shè)計(jì)的各類應(yīng)用程序可以幾乎不用修改而直接遷移到SSD 上，但同時(shí)也導(dǎo)致了SSD 需要預(yù)留空間、需要進(jìn)行內(nèi)部的垃圾回收、在空間占比達(dá)到一定程度時(shí)會(huì)發(fā)生性能抖動(dòng)等問(wèn)題[1,12].

ZNS SSD 相比于傳統(tǒng)塊接口的SSD 有以下優(yōu)點(diǎn)：首先在ZNS SSD 上減少甚至移除了FTL，將映射表的管理、垃圾回收和順序?qū)懙南拗贫冀唤o主機(jī)端進(jìn)行控制，節(jié)約了成本，同時(shí)解決了預(yù)留空間的問(wèn)題.其次由于主機(jī)程序能控制ZNS SSD 上數(shù)據(jù)的放置、垃圾回收時(shí)機(jī)，通過(guò)將不同特性的數(shù)據(jù)放置在不同的Zone，選擇合理的垃圾回收時(shí)機(jī)等策略將有助于提高系統(tǒng)性能、延長(zhǎng)SSD 使用壽命.

由于在Zone 內(nèi)只能順序?qū)懀虼撕芏嗷趥鹘y(tǒng)SSD 抽象接口開發(fā)的應(yīng)用和系統(tǒng)不能直接應(yīng)用在ZNS SSD 上[1-6].此外，由于ZNS SSD 移除了設(shè)備內(nèi)的垃圾回收，因此需要用戶自行設(shè)計(jì)垃圾回收機(jī)制，帶來(lái)了額外的復(fù)雜性.Stavrinos 等人[3]分析了ZNS SSD的各項(xiàng)優(yōu)勢(shì)，并通過(guò)調(diào)研發(fā)現(xiàn)一旦行業(yè)因?yàn)閆NS SSD的成本和性能優(yōu)勢(shì)開始轉(zhuǎn)向ZNS SSD，則之前大多數(shù)SSD 上的工作都需要重新審視，因此呼吁研究者轉(zhuǎn)向ZNS SSD 的研究.Shin 等人[7]通過(guò)在ZNS SSD原型硬件上進(jìn)行各種性能測(cè)試，為ZNS SSD 上的軟件設(shè)計(jì)提供了有效思路.Choi 等人[5]提出了一種在ZNS SSD 上的LSM（log-structured merge）風(fēng)格的垃圾回收機(jī)制，他們建議針對(duì)ZNS SSD 進(jìn)行細(xì)粒度的垃圾回收，并根據(jù)數(shù)據(jù)熱度將細(xì)粒度數(shù)據(jù)存儲(chǔ)在不同的分區(qū)內(nèi).西部數(shù)據(jù)的Bj?rling 等人[1]基于ZNS SSD 開發(fā)出了ZenFS 文件系統(tǒng)來(lái)適配 RocksDB 的文件接口，目前已經(jīng)成功提交到 RocksDB 的社區(qū).Han 等人[2]在ZNS 接口的基礎(chǔ)上更進(jìn)一步，提出了ZNS+接口.ZNS+是一種對(duì)日志結(jié)構(gòu)文件系統(tǒng)（log-structured file system，LFS）感知的ZNS 接口，將用戶定義的垃圾回收產(chǎn)生的有效數(shù)據(jù)拷貝放到設(shè)備內(nèi)部進(jìn)行，從而減少I/O 操作，提升文件系統(tǒng)垃圾回收的效率.

雖然ZNS SSD 具有如此多優(yōu)點(diǎn)，但它同樣帶來(lái)了一些挑戰(zhàn).與傳統(tǒng)SSD 相比，ZNS SSD 移除了FTL，將Zone 的空間直接交由主機(jī)程序控制管理，由主機(jī)程序來(lái)處理垃圾回收、磨損均衡、數(shù)據(jù)放置等，這擴(kuò)大了用戶數(shù)據(jù)存儲(chǔ)管理的設(shè)計(jì)空間，也帶來(lái)了設(shè)計(jì)上的困難.總體而言，ZNS SSD 的順序?qū)懞蚙one 劃分等限制對(duì)現(xiàn)有的數(shù)據(jù)存儲(chǔ)管理機(jī)制提出了諸多新的挑戰(zhàn)，包括存儲(chǔ)分配、垃圾回收、索引結(jié)構(gòu)等.

1.2 SSD 感知的B+-tree 相關(guān)工作

在過(guò)去的10 多年里，由于閃存技術(shù)的快速發(fā)展，學(xué)術(shù)界針對(duì)閃存感知的B+-tree 優(yōu)化方法開展了廣泛的研究.Roh 等人[15]利用SSD 內(nèi)部的并行性來(lái)優(yōu)化B+-tree 索引.Na 等人[16]提出了一種動(dòng)態(tài)頁(yè)內(nèi)日志風(fēng)格的B+-tree 索引.Agrawal 等人[17]設(shè)計(jì)了一種惰性更新的機(jī)制來(lái)使B+-tree 更適合SSD 特性.Ahn 等人[18]利用CoW B+-tree 的性質(zhì)對(duì)SSD 上的B+-tree 進(jìn)行了優(yōu)化.Fang 等人[19]提出一種感知SSD 持久度的B+-tree方案.Jin 等人[20]則利用布隆過(guò)濾器（Bloom filter）和節(jié)點(diǎn)的更新緩存實(shí)現(xiàn)了不降低讀性能的同時(shí)減少SSD寫操作.Lv 等人[21]通過(guò)日志的方式將隨機(jī)寫轉(zhuǎn)為順序?qū)憗?lái)優(yōu)化SSD 上的R-tree 的讀寫操作.Jin 等人[22]通過(guò)利用SSD 內(nèi)部的并行來(lái)批量處理小的寫入，提出了一種flash 感知的線性散列索引.Ho 和Park[23]通過(guò)在內(nèi)存中設(shè)計(jì)一個(gè)寫模式轉(zhuǎn)換器，將隨機(jī)寫轉(zhuǎn)換為順序?qū)?，以此?lái)充分利用SSD 的特性.文獻(xiàn)[24]使用IPL（in-page logging）和寫緩存等技術(shù)設(shè)計(jì)符合SSD 特性的LSB+-tree，同時(shí)提高了索引的時(shí)間和空間效率.

總體而言，SSD 感知的B+-tree 索引的設(shè)計(jì)重點(diǎn)在于減少對(duì)SSD 的隨機(jī)寫操作.這是因?yàn)锽+-tree 本身是一種寫不友好的索引，因此對(duì)于SSD 上的寫密集應(yīng)用性能較差.ZNS SSD 的介質(zhì)仍是閃存，因此同樣需要考慮減少隨機(jī)寫操作.但由于Zone 內(nèi)只能順序?qū)?，隨機(jī)寫的問(wèn)題不再是ZNS SSD 上B+-tree 索引優(yōu)化的第一目標(biāo).如何適應(yīng)數(shù)據(jù)的分區(qū)存儲(chǔ)和順序?qū)懱匦裕窃O(shè)計(jì)ZNS SSD 感知的B+-tree 索引需要重點(diǎn)考慮的問(wèn)題.就目前的研究進(jìn)展，還沒(méi)有一種已有的SSD 索引能夠直接運(yùn)行在ZNS SSD 上.

1.3 CoW B+-tree

目前學(xué)術(shù)界還沒(méi)有提出針對(duì)ZNS SSD 的索引結(jié)構(gòu).與本文工作較相關(guān)的已有工作主要是CoW B+-tree.CoW B+-tree 是一種追加寫（append-only write）的B+樹結(jié)構(gòu)[25].這剛好適應(yīng)了ZNS SSD 的Zone 內(nèi)順序?qū)懸螅虼巳绻豢紤]Zone 內(nèi)數(shù)據(jù)存儲(chǔ)分配的話，可以將CoW B+-tree 修改后運(yùn)行在ZNS SSD 上.圖3 給出了CoW B+-tree 的數(shù)據(jù)更新過(guò)程.

Fig.3 An example of CoW B+-tree update圖3 CoW B+-tree 更新過(guò)程示例

文獻(xiàn)[18]對(duì)Cow B+-tree 針對(duì)SSD 特性做了一些優(yōu)化以減少寫放大，但是卻無(wú)法保證B+-tree 節(jié)點(diǎn)大小相同，因此本文還是選擇傳統(tǒng)CoW B+-tree[25]進(jìn)行對(duì)比，CoW B+-tree 算法流程和傳統(tǒng)的B+-tree 基本一樣，只是修改葉節(jié)點(diǎn)時(shí)由于不能原地更新，因此需要把修改后的節(jié)點(diǎn)直接附加在寫指針處，由于葉節(jié)點(diǎn)的地址發(fā)生了改變，因此還需要修改其父節(jié)點(diǎn)中指向葉節(jié)點(diǎn)的指針.這一修改會(huì)級(jí)聯(lián)往上傳遞，直到根節(jié)點(diǎn).

但是，直接將CoW B+-tree 的所有節(jié)點(diǎn)都寫在一個(gè)Zone 中將會(huì)很快耗盡Zone 的空間，從而頻繁觸發(fā)Zone-Reset 操作.因此，在本文后續(xù)的對(duì)比實(shí)驗(yàn)中，我們對(duì)CoW B+-tree 進(jìn)行了修改使其能夠利用所有的Zone，并減少頻繁的Zone-Reset 操作.由于主機(jī)程序可以得知Zone 的使用情況，我們總是將CoW B+-tree節(jié)點(diǎn)寫入剩余空間最多的Zone，并根據(jù)當(dāng)前Zone 的使用情況動(dòng)態(tài)選擇Zone 而不是固定寫入一個(gè)Zone.這樣可以在使用該索引時(shí)盡量減少Zone-Reset，同時(shí)充分利用ZNS SSD 的空間.

2 ZB+-tree 索引結(jié)構(gòu)

2.1 設(shè)計(jì)思路

由于ZNS SSD 具有多分區(qū)特性，不同的Zone 性能有所差異，在頻繁訪問(wèn)的磨損較多的Zone 會(huì)有更高的訪問(wèn)延遲[7]，且在Seq-Zone 中有嚴(yán)格的順序?qū)懸?當(dāng)Zone 寫滿時(shí)會(huì)觸發(fā)Zone-Reset 操作和垃圾回收，這2 個(gè)操作非常耗時(shí)，會(huì)帶來(lái)性能的抖動(dòng).因此ZB+-tree 主要針對(duì)4 個(gè)目標(biāo)進(jìn)行設(shè)計(jì)：1）索引要能充分利用ZNS SSD 的多分區(qū)特性；2）要滿足在Seq-Zone 中的嚴(yán)格順序?qū)懴拗疲?）將頻繁訪問(wèn)的數(shù)據(jù)盡量放置在磨損較少的Zone 以降低訪問(wèn)延遲；4）盡量減少在運(yùn)行過(guò)程中的GC 和Zone-Reset 操作，以避免性能抖動(dòng).

針對(duì)上述目標(biāo)，ZB+-tree 進(jìn)行了全新設(shè)計(jì)，主要設(shè)計(jì)思路總結(jié)為5 個(gè)方面：

1）將索引節(jié)點(diǎn)分散在多個(gè)Zone 中，允許節(jié)點(diǎn)在不同Zone 之間進(jìn)行移動(dòng).由于Cov-Zone 中允許進(jìn)行原地更新，如果能充分利用這一特性，就能將對(duì)索引的原地更新吸收在Cov-Zone 中.當(dāng)節(jié)點(diǎn)寫滿時(shí)則整體移動(dòng)到Seq-Zone 中，既保證不會(huì)有太大的寫放大，而同時(shí)也能保證在Seq-Zone 中的順序?qū)懸?

2）將對(duì)Seq-Zone 中節(jié)點(diǎn)的更新也吸收在Cov-Zone 中，為Seq-Zone 中不可原地更新的節(jié)點(diǎn)設(shè)計(jì)了日志節(jié)點(diǎn)結(jié)構(gòu)，日志節(jié)點(diǎn)放置在Cov-Zone 中以進(jìn)行原地更新，減少寫放大.同時(shí)為避免日志節(jié)點(diǎn)過(guò)多而影響整體的讀寫性能，需要將日志與節(jié)點(diǎn)合并，可通過(guò)設(shè)計(jì)新的Sync 操作來(lái)實(shí)現(xiàn).

3）為不同類型的節(jié)點(diǎn)動(dòng)態(tài)選擇不同的Zone 進(jìn)行放置，由于葉節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)更新頻率不同，葉節(jié)點(diǎn)頻繁更新而內(nèi)部節(jié)點(diǎn)相對(duì)更新較少，因此我們提出一種動(dòng)態(tài)選擇Zone 的策略，將頻繁更新的葉節(jié)點(diǎn)放置在空間占用較少、磨損較少的Zone 中，而將內(nèi)部節(jié)點(diǎn)放置于空間占用和磨損相對(duì)較多的Zone 中，以充分利用ZNS SSD 的多分區(qū)特性，并降低訪問(wèn)延遲.

4）為管理分散在不同Zone 的節(jié)點(diǎn)和對(duì)應(yīng)的日志節(jié)點(diǎn)，我們?yōu)槿~節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)都設(shè)計(jì)相應(yīng)的head節(jié)點(diǎn)，以記錄節(jié)點(diǎn)的狀態(tài)、地址、日志情況，并將head 節(jié)點(diǎn)存儲(chǔ)于Cov-Zone 中，以阻斷級(jí)聯(lián)更新.

5）由于不同分層的節(jié)點(diǎn)處于不同類型的Zone 中，對(duì)節(jié)點(diǎn)的合并控制也將采用不同的策略，對(duì)于都在Cov-Zone 中的節(jié)點(diǎn)，采用嚴(yán)格控制合并策略；對(duì)于節(jié)點(diǎn)分散在Cov-Zone 和Seq-Zone 中的節(jié)點(diǎn)，則采用機(jī)會(huì)主義合并策略.通過(guò)不同的控制合并策略，在保證索引性能的同時(shí)盡量減少級(jí)聯(lián)更新和寫放大.

2.2 ZB+-tree 總體結(jié)構(gòu)

在本文的設(shè)計(jì)中，ZB+-tree 總共分為4 層，從上到下分別是IH 層、Interior 層、LH 層、Leaf 層，其中IH層由interior-head 節(jié)點(diǎn)組成，LH 層由leaf-head 節(jié)點(diǎn)組成，Interior 層由interior 節(jié)點(diǎn)和interior-log 節(jié)點(diǎn)組成，Leaf 層由leaf 節(jié)點(diǎn)和leaf-log 節(jié)點(diǎn)組成.由于通常來(lái)說(shuō)B+-tree 為3～4 層，我們?cè)O(shè)計(jì)的IH 可以視為B+-tree的根節(jié)點(diǎn).IH 層和LH 層的節(jié)點(diǎn)既可以作為B+-tree的內(nèi)部節(jié)點(diǎn)（里面存著key 值和子節(jié)點(diǎn)地址），同時(shí)又記錄著下一層的節(jié)點(diǎn)狀態(tài)和日志情況.圖4 展示了ZB+-tree 的邏輯結(jié)構(gòu)，其中F 代表key 值為First（key無(wú)法取到的最小值），K 代表普通key 值.

Fig.4 ZB+-tree logical structure圖4 ZB+-tree 邏輯結(jié)構(gòu)

由于主機(jī)程序可以隨時(shí)知道ZNS SSD 上各個(gè)Zone 的使用情況，這里提出一種動(dòng)態(tài)選擇Zone 的方法，即當(dāng)有節(jié)點(diǎn)需要從Cov-Zone 移入到Seq-Zone 中時(shí)，如果是leaf 節(jié)點(diǎn)，則動(dòng)態(tài)選擇當(dāng)前剩余容量最多的Zone（稱為Hot-Seq-Zone）放置，如果是interior 節(jié)點(diǎn)，則動(dòng)態(tài)選擇當(dāng)前剩余容量最少的Zone（稱為Cold-Seq-Zone）放置.之所以這么區(qū)分，是因?yàn)槿~節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)的更新頻率不同，把更新頻率高的葉節(jié)點(diǎn)往剩余空間最大的Zone 內(nèi)放置可以避免由于Zone 空間被迅速占滿而導(dǎo)致的Zone-Reset 操作.同時(shí)剩余容量多、磨損較少的Zone 的讀寫性能也更好，可以便于leaf 的頻繁讀寫.

圖5 顯示了ZB+-tree 節(jié)點(diǎn)在ZNS SSD 上的具體分布情況，其中IH 和LH 層都位于Cov-Zone 中，而interior 節(jié)點(diǎn)和leaf 節(jié)點(diǎn)則分布在Cov-Zone 和Seq-Zone中.在本文中，我們約定：白色代表Cov-Zone，深灰色代表Hot-Seq-Zone，淺灰色代表Cold-Seq-Zone，灰色漸變代表處于Seq-Zone 中可能是Hot 狀態(tài)也可能是Cold 狀態(tài).

Fig.5 Distribution of ZB+-tree nodes on ZNS SSD圖5 ZB+-tree 節(jié)點(diǎn)在ZNS SSD 上的分布

對(duì)于interior 節(jié)點(diǎn)和leaf 節(jié)點(diǎn)，設(shè)計(jì)了相應(yīng)的狀態(tài)轉(zhuǎn)換機(jī)制，如圖6 所示.ZB+-tree 的interior 節(jié)點(diǎn)和leaf 節(jié)點(diǎn)有4 種可能的狀態(tài).

Fig.6 ZB+-tree node state transition圖6 ZB+-tree 節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換

1）change_state.處 于change_state的節(jié)點(diǎn) 都位于Cov-Zone 中，并且節(jié)點(diǎn)未滿，可以就地插入、刪除、更新.處于change_state的節(jié)點(diǎn)一旦滿了，如果是葉節(jié)點(diǎn)，則整體移動(dòng)到Hot-Seq-Zone 中；如果是內(nèi)部節(jié)點(diǎn)，則整體移動(dòng)到Cold-Seq-Zone 中，這剛好符合ZNS SSD 的順序?qū)懴拗?

2）steady_state_hot.節(jié)點(diǎn)位于Hot-Seq-Zone 中，且為葉節(jié)點(diǎn)，節(jié)點(diǎn)一定是滿的，并且不可就地更改.對(duì)此狀態(tài)的節(jié)點(diǎn)進(jìn)行插入將導(dǎo)致其分裂成2 個(gè)change_state的葉節(jié)點(diǎn)，對(duì)此狀態(tài)節(jié)點(diǎn)的更新和刪除將記錄在leaf-log 節(jié)點(diǎn)中.

3）steady_state_cold.節(jié)點(diǎn)位 于Cold-Seq-Zone 中，且是內(nèi)部節(jié)點(diǎn)，節(jié)點(diǎn)一定是滿的，并且不可就地更改.對(duì)此狀態(tài)的節(jié)點(diǎn)進(jìn)行插入將導(dǎo)致其分裂成2 個(gè)change_state的內(nèi)部節(jié)點(diǎn)，對(duì)此狀態(tài)節(jié)點(diǎn)的更新和刪除將記錄在interior-log 節(jié)點(diǎn)中.

4）after_state.處于該狀態(tài)的節(jié)點(diǎn)一定帶有l(wèi)og 節(jié)點(diǎn)，并且log 節(jié)點(diǎn)中有刪除記錄，表示該節(jié)點(diǎn)在steady_state經(jīng)過(guò)了刪除.對(duì)此狀態(tài)的節(jié)點(diǎn)進(jìn)行插入會(huì)首先觸發(fā)Sync 操作，將節(jié)點(diǎn)和對(duì)應(yīng)的log 節(jié)點(diǎn)合并之后再進(jìn)行插入，對(duì)此狀態(tài)節(jié)點(diǎn)的更新和刪除將記錄在log 節(jié)點(diǎn)中.

處于steady_state的節(jié)點(diǎn)可能帶log 節(jié)點(diǎn)也可能不帶log 節(jié)點(diǎn)，log 節(jié)點(diǎn)都位于Cov-Zone 中以吸收對(duì)Seq-Zone 中節(jié)點(diǎn)的原地更新，對(duì)steady_state的節(jié)點(diǎn)進(jìn)行的更新和刪除操作會(huì)直接寫到對(duì)應(yīng)的log 節(jié)點(diǎn)里（如果該節(jié)點(diǎn)原本不帶log 節(jié)點(diǎn)則為其分配一個(gè)log節(jié)點(diǎn)）.處于steady_state的節(jié)點(diǎn)可以進(jìn)行3 種操作：

1）Sync 操作.將節(jié)點(diǎn)與對(duì)應(yīng)的log 節(jié)點(diǎn)進(jìn)行合并，Sync 操作完成之后節(jié)點(diǎn)還是處于steady_state.

2）Delete 操作.在log 節(jié)點(diǎn)中增加刪除記錄，Delete操作完成之后節(jié)點(diǎn)轉(zhuǎn)換為after_state表示節(jié)點(diǎn)已經(jīng)經(jīng)過(guò)了刪除.

3）Split 操作.節(jié)點(diǎn)分裂成2 個(gè)，Split 操作完成之后節(jié)點(diǎn)轉(zhuǎn)化為2 個(gè)change_state的節(jié)點(diǎn)并移動(dòng)到Cov-Zone 中.

處于after_state的節(jié)點(diǎn)可以進(jìn)行Sync 操作，將節(jié)點(diǎn)與對(duì)應(yīng)的log 節(jié)點(diǎn)進(jìn)行合并.由于必然經(jīng)過(guò)了刪除操作，實(shí)際上after_state的節(jié)點(diǎn)在邏輯上代表一個(gè)未滿的節(jié)點(diǎn)，因此合并后節(jié)點(diǎn)狀態(tài)轉(zhuǎn)換為change_state.

2.3 ZB+-tree 節(jié)點(diǎn)結(jié)構(gòu)設(shè)計(jì)

leaf 節(jié)點(diǎn)設(shè)置為n個(gè)key 值和n個(gè)value 值，leaflog 節(jié)點(diǎn)的結(jié)構(gòu)與leaf 節(jié)點(diǎn)的結(jié)構(gòu)完全相同，之所以設(shè)置為結(jié)構(gòu)相同，是因?yàn)樵赟ync 操作中需要將leaflog 節(jié)點(diǎn)直接轉(zhuǎn)化為leaf 節(jié)點(diǎn)（具體細(xì)節(jié)見(jiàn)3.1 節(jié)Sync操作），在leaf-log 節(jié)點(diǎn)中通過(guò)位置與leaf 節(jié)點(diǎn)中的鍵值對(duì)應(yīng)，如圖7 所示.

對(duì)于leaf-head 節(jié)點(diǎn)，結(jié)構(gòu)為n+1 個(gè)key 值和n+1個(gè)ptr 結(jié)構(gòu)，如圖8 所示.ptr 結(jié)構(gòu)中包括3 個(gè)值：

Fig.7 An example of leaf and corresponding leaf-log圖7 leaf 和對(duì)應(yīng)的leaf-log 示例

1）state.表示子節(jié)點(diǎn)所處的狀態(tài).

2）addr.表示子節(jié)點(diǎn)所在的位置.

3）log_addr.表示子節(jié)點(diǎn)對(duì)應(yīng)的日志節(jié)點(diǎn)所處的位置.

leaf-head 節(jié)點(diǎn)的第1 個(gè)key 值一定是First（key 無(wú)法取到的最小值）.

interior 節(jié)點(diǎn)的 結(jié)構(gòu)為n+1 個(gè)key 和n+1 個(gè)addr（子節(jié)點(diǎn)的地址），interior-log 和interior 結(jié)構(gòu)完全相同（同樣是因?yàn)镾ync 操作的要求），interior-head 的結(jié)構(gòu)和leaf-head 的結(jié)構(gòu)相同.在interior 和interior-head 節(jié)點(diǎn)中，第1 個(gè)key 值同樣設(shè)置為First.之所以在interior節(jié)點(diǎn)中引入First 值是因?yàn)樵赯B+-tree 中的Sync 操作需要讓日志節(jié)點(diǎn)和interior 節(jié)點(diǎn)保持相同結(jié)構(gòu)以便于log 節(jié)點(diǎn)與正常的內(nèi)部節(jié)點(diǎn)之間直接進(jìn)行轉(zhuǎn)化，而日志節(jié)點(diǎn)又是通過(guò)位置與原內(nèi)部節(jié)點(diǎn)進(jìn)行對(duì)應(yīng)，所以需要給第1 個(gè)位置一個(gè)key 值，代表這是第1 個(gè)子節(jié)點(diǎn).之所以在leaf-head 和interior-head 中引入First 值，是因?yàn)閷?duì)于每一個(gè)leaf 節(jié)點(diǎn)或者是interior 節(jié)點(diǎn)，都需要相應(yīng)的ptr 結(jié)構(gòu)來(lái)指示其狀態(tài)、位置和日志情況.即使樹中只有一個(gè)leaf 節(jié)點(diǎn)或只有一個(gè)interior節(jié)點(diǎn)也要有對(duì)應(yīng)的ptr 結(jié)構(gòu)，因此，需要為第1 個(gè)ptr結(jié)構(gòu)設(shè)置key 值為First，表示這是子樹中第1 個(gè)interior 節(jié)點(diǎn)或者第1 個(gè)leaf 節(jié)點(diǎn)，而其他的key 值則與正常B+-tree 中的key 值含義相同，代表對(duì)應(yīng)子樹中的最小key 值.

Fig.8 The structure of leaf-head圖8 leaf-head 的結(jié)構(gòu)

3 ZB+-tree 索引操作

本節(jié)主要介紹ZB+-tree 的Sync，Search，Insert，Delete等操作，并給出了時(shí)間性能和空間代價(jià)分析.

3.1 Sync

在ZB+-tree 中無(wú)論是interior-log 節(jié)點(diǎn)還是leaflog 節(jié)點(diǎn)都只記錄更新和刪除操作，其結(jié)構(gòu)和對(duì)應(yīng)的interior 節(jié)點(diǎn)或leaf 節(jié)點(diǎn)相同，當(dāng)樹中存在的日志節(jié)點(diǎn)過(guò)多時(shí)會(huì)對(duì)Cov-Zone 有較大的占用而且會(huì)影響整體的查找性能，因?yàn)樽x一個(gè)節(jié)點(diǎn)之后還需要再讀一次日志節(jié)點(diǎn)來(lái)重建最新的節(jié)點(diǎn).因此需要將日志節(jié)點(diǎn)和對(duì)應(yīng)的節(jié)點(diǎn)進(jìn)行合并，構(gòu)建最新的節(jié)點(diǎn)并釋放日志節(jié)點(diǎn)空間，我們稱之為Sync 操作.在日志節(jié)點(diǎn)寫滿時(shí)同樣需要將日志與節(jié)點(diǎn)進(jìn)行合并.在ZB+-tree 中，我們?cè)O(shè)計(jì)了2 種方式的合并，當(dāng)日志節(jié)點(diǎn)未滿時(shí)的合并稱之為Normal_apply，當(dāng)日志節(jié)點(diǎn)滿了時(shí)的合并稱之為Switch_apply.

1）Normal_apply.圖9 給出了Normal_apply 的 過(guò)程.當(dāng)節(jié)點(diǎn)對(duì)應(yīng)的log 節(jié)點(diǎn)還未滿時(shí)，如果節(jié)點(diǎn)處于steady_state，表示節(jié)點(diǎn)還未進(jìn)行過(guò)刪除操作，log 節(jié)點(diǎn)中無(wú)刪除記錄，因此根據(jù)log 節(jié)點(diǎn)進(jìn)行更新后的節(jié)點(diǎn)仍然處于steady_state，此時(shí)將新的節(jié)點(diǎn)寫回Seq-Zone并釋放Cov-Zone 上log 節(jié)點(diǎn)的空間.如果節(jié)點(diǎn)處于after_state，則表示節(jié)點(diǎn)經(jīng)過(guò)了刪除操作，log 節(jié)點(diǎn)中一定有刪除記錄，根據(jù)log 節(jié)點(diǎn)進(jìn)行更新后的節(jié)點(diǎn)轉(zhuǎn)換成change_state并寫到Cov-Zone 中原log 節(jié)點(diǎn)的位置.算法1 給出了Normal_apply 操作流程.

Fig.9 Normal_apply schematic圖9 Normal_apply 示意圖

算法1.Normal_apply_leaf（&leaf,&leaf_log,&leaf_ptr）.

Fig.10 Switch_apply schematic圖10 Switch_apply 示意圖

2）Switch_apply.圖10 給出了Switch_apply 的 過(guò)程.當(dāng)節(jié)點(diǎn)對(duì)應(yīng)的log 節(jié)點(diǎn)已經(jīng)寫滿時(shí)，將發(fā)生Switch_apply，與Normal_apply 不同的是，Switch_apply 不需要讀原節(jié)點(diǎn)，而只需要讀其log 節(jié)點(diǎn)，因?yàn)槿罩疽褲M說(shuō)明原節(jié)點(diǎn)中所有鍵值對(duì)都已經(jīng)經(jīng)過(guò)了更新或者刪除.如果原節(jié)點(diǎn)處于steady_state，說(shuō)明對(duì)節(jié)點(diǎn)的所有鍵值對(duì)都進(jìn)行過(guò)更新操作，因此直接將log 節(jié)點(diǎn)作為新的節(jié)點(diǎn)寫入Seq-Zone 中，并釋放在Cov-Zone 中l(wèi)og節(jié)點(diǎn)的空間.如果原節(jié)點(diǎn)處于after_state，說(shuō)明其除了進(jìn)行過(guò)更新操作之外還有刪除操作，因此把log 節(jié)點(diǎn)中有刪除標(biāo)記（delete_key）的鍵值對(duì)去除后，轉(zhuǎn)化為change_state的節(jié)點(diǎn)，直接寫回Cov-Zone 中原log 節(jié)點(diǎn)位置.算法2 給出了Switch_apply.

算法2.Switch_apply_leaf（&leaf_log,&leaf_ptr）.

Sync 操作（見(jiàn)算法3）對(duì)于interior 節(jié)點(diǎn)和leaf 節(jié)點(diǎn)都類似，唯一區(qū)別在于interior 節(jié)點(diǎn)中為n+1 個(gè)鍵值對(duì)而leaf 節(jié)點(diǎn)中為n個(gè)鍵值對(duì).對(duì)leaf 節(jié)點(diǎn)的操作為Sync，對(duì)于interior 節(jié)點(diǎn)也有相應(yīng)的in_Sync 操作.

算法3.Sync（&leaf,&leaf_log,&leaf_ptr）.

3.2 Search

在ZB+-tree 上的Search 過(guò)程如算法4 所示，如果ZB+-tree 中還沒(méi)有IH 層，也就是整棵樹只有2 層（LH層和Leaf 層）時(shí)，只有一個(gè)leaf-head 節(jié)點(diǎn)，此時(shí)直接從leaf-head 開始進(jìn)行搜索.如果樹中存在IH 層，則根據(jù)要搜索的key 值，先從IH 中得到interior 節(jié)點(diǎn)對(duì)應(yīng)的ptr 結(jié)構(gòu)，如果interior 節(jié)點(diǎn)沒(méi)有l(wèi)og 節(jié)點(diǎn)，則直接讀出interior 節(jié)點(diǎn)；如果interior 節(jié)點(diǎn)有l(wèi)og 節(jié)點(diǎn)，則會(huì)觸發(fā)apply_innner_log（）操作，這個(gè)操作只是在內(nèi)存中重建最新的interior 節(jié)點(diǎn)，并不會(huì)對(duì)ZNS SSD 上的interior節(jié)點(diǎn)和日志節(jié)點(diǎn)進(jìn)行修改.這樣做的目的是避免在Search 過(guò)程中觸發(fā)寫操作.得到了最新的interior 節(jié)點(diǎn)之后，在其中根據(jù)key 值搜索得到leaf-head 節(jié)點(diǎn)的地址，并讀出leaf-head 節(jié)點(diǎn)，再?gòu)膌eaf-head 開始搜索，即觸發(fā)Search_leaf_head（）操作，具體見(jiàn)算法5.其過(guò)程與從IH 搜索interior 節(jié)點(diǎn)的過(guò)程類似，其中apply_leaf_log（）也只是在內(nèi)存中建立最新的leaf 節(jié)點(diǎn)，并不修改ZNS SSD 上的leaf 節(jié)點(diǎn)和log 節(jié)點(diǎn).得到最新的leaf 節(jié)點(diǎn)之后，再根據(jù)key 值進(jìn)行搜索，如果搜到則返回value 值，否則返回Null，表示沒(méi)有搜到.

算法4.Search（key）.

算法5.Search_leaf_head（leaf_head,key）.

3.3 Insert

在ZB+-tree 上的Insert 操作會(huì)先根據(jù)要插入的key 值從根節(jié)點(diǎn)一路搜索到葉節(jié)點(diǎn)對(duì)應(yīng)的leaf-head節(jié)點(diǎn)，搜索過(guò)程與Search 相同，從leaf-head 節(jié)點(diǎn)中得到對(duì)應(yīng)的ptr 結(jié)構(gòu)，如果葉節(jié)點(diǎn)處于change_state，則直接往葉節(jié)點(diǎn)中插入鍵值對(duì)，如果滿了則移動(dòng)到Seq-Zone 中.而對(duì)于steady_state的葉節(jié)點(diǎn)，如果不帶log節(jié)點(diǎn)，則直接進(jìn)行Split 操作，分裂成2 個(gè)Cov-Zone 上的change_state的節(jié)點(diǎn)，如果帶log 節(jié)點(diǎn)，則先進(jìn)行Sync 操作，合并leaf 節(jié)點(diǎn)和log 節(jié)點(diǎn)之后再插入鍵值對(duì)，Insert 具體細(xì)節(jié)見(jiàn)算法6，ZB+-tree 上的Split 操作和正常B+-tree 的操作類似，唯一需要注意的是對(duì)樹中First 值的維護(hù).

算法6.Insert（key,value）.

3.4 Delete

ZB+-tree 上的刪除操作與經(jīng)典B+-tree 算法有許多不同之處，由于不同層的節(jié)點(diǎn)所處的Zone 性質(zhì)是不同的，對(duì)于不同層的節(jié)點(diǎn)在進(jìn)行Delete 操作時(shí)，也將采用不同的控制合并的策略.

對(duì)于IH 層，由于所有的leaf-head 節(jié)點(diǎn)都處于Cov-Zone 中，可以發(fā)生原地更新，因此在刪除時(shí)當(dāng)節(jié)點(diǎn)容量達(dá)到下限（lower_bound），我們采取嚴(yán)格控制合并的策略，即leaf-head 節(jié)點(diǎn)的容量嚴(yán)格控制在lower_bound 和full 之間（整棵樹只有一個(gè)leaf-head 節(jié)點(diǎn)時(shí)例外）.而對(duì)于Leaf 層，在進(jìn)行刪除時(shí)我們采取的是機(jī)會(huì)主義策略控制合并，即查看鄰居節(jié)點(diǎn)，能合并就合并（二者容量之和小于n），不能合并就不作處理，能滿足合并條件則意味著二者必然都處于change_state，即都在Cov-Zone 中.之所以采取不同策略，是因?yàn)長(zhǎng)eaf 層的節(jié)點(diǎn)分散在Seq-Zone 和Cov-Zone 中，且節(jié)點(diǎn)可能帶log 節(jié)點(diǎn)也可能不帶log 節(jié)點(diǎn).如果不能發(fā)生合并，從steady_state的鄰居借一個(gè)鍵值對(duì)，并不會(huì)減少空間的占用，反而將引發(fā)級(jí)聯(lián)的修改，還要處理log 節(jié)點(diǎn).在機(jī)會(huì)主義策略控制下，leaf 節(jié)點(diǎn)的容量范圍為1～n.

對(duì)于Interior 層的節(jié)點(diǎn)我們同樣采取機(jī)會(huì)主義控制合并的策略，理由和Leaf 層相同，interior 節(jié)點(diǎn)的容量范圍為1～n+1，當(dāng)節(jié)點(diǎn)只有一個(gè)key 值時(shí)必然是First，算法7 展示了對(duì)Leaf 層的Delete 操作.

算法7.Delete（key）.

3.5 理論代價(jià)分析

3.5.1 時(shí)間性能

4 層的ZB+-tree 在查詢時(shí)最壞情況下需要讀6 次，即讀interior-head 節(jié)點(diǎn)、讀interior 節(jié)點(diǎn)和interior-log節(jié)點(diǎn)、讀leaf-head 節(jié)點(diǎn)、再讀leaf 節(jié)點(diǎn)和leaf-log 節(jié)點(diǎn)，如果Interior 層和Leaf 層沒(méi)有l(wèi)og 節(jié)點(diǎn)，則與4 層的CoW B+-tree 一樣，需要讀4 次.在進(jìn)行插入操作時(shí)，CoW B+-tree 需要先4 次讀出根到葉節(jié)點(diǎn)的路徑，如果不發(fā)生分裂需要4 次寫操作，在最壞情況下除了根節(jié)點(diǎn)外每層節(jié)點(diǎn)都分裂，則需要7 次寫操作.而ZB+-tree 插入時(shí)同樣需要先進(jìn)行4～6 次讀，如果不發(fā)生分裂則只需要1 次寫操作（即直接往Cov-Zone 中就地插入），如果發(fā)生分裂，最壞情況下需要7 次寫操作，但大多數(shù)情況下不會(huì)出現(xiàn)每一層都恰好分裂，因此往往只需要1～2 次寫操作即可，即將級(jí)聯(lián)的更新阻斷在Cov-Zone 中.對(duì)CoW B+-tree 的刪除操作，同樣需要先進(jìn)行4 次讀，隨后如果沒(méi)發(fā)生合并，最好情況下需要4 次寫操作，如果發(fā)生合并或者向鄰居借鍵值對(duì)則需要更多的讀寫.而ZB+-tree 在進(jìn)行4～6 次讀操作之后，如果沒(méi)發(fā)生合并，則只需要1 次寫操作（change_state的節(jié)點(diǎn)就地刪除后只需要1 次寫；steady_state的節(jié)點(diǎn)則往log 節(jié)點(diǎn)中插入刪除記錄，也只需要1 次寫），如果發(fā)生合并，則在機(jī)會(huì)主義策略控制合并的2 層進(jìn)行的合并操作會(huì)更少，并且在這2層不會(huì)發(fā)生向鄰居借鍵值對(duì)的操作，而在LH 層和IH 層與CoW B+-tree 一樣都采用了嚴(yán)格控制合并的策略，因此總體上的讀寫次數(shù)也會(huì)少于CoW B+-tree.結(jié)合上述分析，可知ZB+-tree 在查詢性能上與CoW B+-tree 接近，在插入時(shí)會(huì)減少寫操作，而在刪除時(shí)會(huì)同時(shí)減少讀寫操作.

3.5.2 空間代價(jià)

CoW B+-tree 的每次更新都至少需要將從根到葉節(jié)點(diǎn)的路徑重新寫回到ZNS SSD 中；而ZB+-tree 則將更新吸收在Cov-Zone 中，往往只需要在Cov-Zone 中進(jìn)行一次原地更新.因此，相比于CoW B+-tree，ZB+-tree 會(huì)大大減少對(duì)Seq-Zone 的占用.

假設(shè)一個(gè)節(jié)點(diǎn)大小為m，一個(gè)4 層的ZB+-tree，階數(shù)為n，最壞情況下，每個(gè)leaf 節(jié)點(diǎn)都帶有l(wèi)eaf-log 節(jié)點(diǎn)，且每個(gè)interior 節(jié)點(diǎn)都帶有interior-log 節(jié)點(diǎn)，此時(shí)有效節(jié)點(diǎn)總大小可估計(jì)為

1 棵4 層的CoW B+-tree 有效節(jié)點(diǎn)所占空間大小即正常B+-tree 所占空間大小，總空間大小可估計(jì)為

隨著對(duì)索引的修改，CoW B+-tree 會(huì)不斷將修改過(guò)的節(jié)點(diǎn)以及到根節(jié)點(diǎn)的路徑上的節(jié)點(diǎn)寫入SSD 中.上述分析僅僅針對(duì)其有效節(jié)點(diǎn)部分，實(shí)際運(yùn)行中CoW B+-tree 還會(huì)產(chǎn)生大量無(wú)效節(jié)點(diǎn)，進(jìn)一步增加空間占用率.而ZB+-tree 將原地更新吸收在Cov-Zone 中，實(shí)際運(yùn)行時(shí)雖然也會(huì)在Seq-Zone 中產(chǎn)生無(wú)效節(jié)點(diǎn)，但數(shù)量會(huì)遠(yuǎn)遠(yuǎn)少于CoW B+-tree，且其有效節(jié)點(diǎn)部分在最壞情況下也和CoW B+-tree 處于同一個(gè)量級(jí).因此，總體上，ZB+-tree 的空間代價(jià)低于CoW B+-tree.

ZB+-tree 相比于CoW B+-tree 在LH 層和IH 層增加了一些數(shù)據(jù)結(jié)構(gòu)用于管理下一層的節(jié)點(diǎn)，由于IH 層和LH 層都是內(nèi)部節(jié)點(diǎn)，相對(duì)較少，因此額外的空間代價(jià)并不會(huì)特別高.ZB+-tree 對(duì)Cov-Zone 的占用情況則主要和工作負(fù)載有關(guān)，需要通過(guò)實(shí)驗(yàn)來(lái)進(jìn)行驗(yàn)證.

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)設(shè)置

服務(wù)器操作系統(tǒng)為Ubuntu20.04.1LTS，內(nèi)核版本5.4.0，gcc 版本為 9.4.0 .由于目前還沒(méi)有商用ZNS SSD，因此我們使用了null_blk 來(lái)模擬ZNS SSD設(shè)備，并使用西部數(shù)據(jù)的ZBD 操作庫(kù)libzbd 進(jìn)行實(shí)驗(yàn).具體的實(shí)驗(yàn)配置如表1 所示.

由于目前還沒(méi)有提出ZNS SSD 感知的索引，因此我們將CoW B+-tree 進(jìn)行了修改使其能夠運(yùn)行在ZNS SSD 上.具體而言，總是將CoW B+-tree 節(jié)點(diǎn)寫入剩余空間最多的Zone，并根據(jù)當(dāng)前Zone 的使用情況動(dòng)態(tài)選擇要寫入的Zone，以盡量減少Zone-Reset 操作，同時(shí)充分利用ZNS SSD 的空間.

Table 1 Experimental Configuration表1 實(shí)驗(yàn)配置

實(shí)驗(yàn)使用YCSB[29]作為測(cè)試負(fù)載.YCSB 是目前在存儲(chǔ)和數(shù)據(jù)庫(kù)領(lǐng)域廣泛使用的測(cè)試負(fù)載，它也允許用戶自行配置讀寫比例和訪問(wèn)傾斜性.在實(shí)驗(yàn)中我們利用YCSB 生成了5 個(gè)測(cè)試負(fù)載，說(shuō)明如下：

1）Workload1 是寫密集的負(fù)載，包含插入、刪除、查找操作，并且3 類操作的占比分別為插入40%、刪除30%、查找30%.

2）Workload2 是讀密集的負(fù)載，包含插入、刪除、查找操作，并且3 類操作的占比分別為插入10%、刪除10%、查找80%.

3）Workload3 是讀寫均衡的負(fù)載，包含插入、刪除、查找操作，并且3 類操作的占比分別為插入25%、刪除25%、查找50%.

4）Workload4 是純寫負(fù)載，包含插入、刪除操作，并且2 類操作的占比分別為插入50%、刪除50%.

5）Workload5 是純讀負(fù)載，只包含查找操作.

我們?cè)? 種負(fù)載上分別測(cè)試不同數(shù)據(jù)量和不同數(shù)據(jù)分布下的性能.數(shù)據(jù)量分別設(shè)置為50 萬(wàn)、150 萬(wàn)、250 萬(wàn)鍵值記錄對(duì)，數(shù)據(jù)分布采用了文獻(xiàn)[29]中的3類分布，包括Zipfian 分布、uniform 分布、latest 分布.在YCSB 中執(zhí)行測(cè)試前會(huì)先加載數(shù)據(jù)，以下的實(shí)驗(yàn)數(shù)據(jù)都是指在數(shù)據(jù)加載完成之后再進(jìn)行各種操作時(shí)統(tǒng)計(jì)的數(shù)據(jù).CoW B+-tree 實(shí)驗(yàn)中模擬的ZBD 設(shè)備為40個(gè)Seq-Zone 以及1 個(gè)Cov-Zone（為保證實(shí)驗(yàn)對(duì)比公平，我們把Cov-Zone 按照Seq-Zone 的順序?qū)懩Ｊ絹?lái)使用），每個(gè)Zone 大小為2 GB；ZB+-tree 實(shí)驗(yàn)中模擬的ZBD 設(shè)備為40 個(gè)Seq-Zone 以及1 個(gè)Cov-Zone，大小都為2GB.在模擬器中塊大小統(tǒng)一設(shè)置為4 KB.

4.2 實(shí)驗(yàn)結(jié)果分析

4.2.1 運(yùn)行時(shí)間比較

圖11～13 給出了ZB+-tree 和CoW B+-tree 的運(yùn)行時(shí)間對(duì)比.可以看到，在不同數(shù)據(jù)規(guī)模和不同工作負(fù)載下，ZB+-tree 運(yùn)行時(shí)間都要小于CoW B+-tree.雖然ZB+-tree 相對(duì)于CoW B+-tree 在查詢時(shí)可能要多讀1～2 次log 節(jié)點(diǎn)，但由于在插入和刪除操作中減少了讀寫次數(shù)，且SSD 讀操作比寫操作要快[7]，因此ZB+-tree 總體性能要好于CoW B+-tree，與理論分析相符.

Fig.11 Running time comparison under the Zipfian distribution圖11 Zipfian 分布下運(yùn)行時(shí)間對(duì)比

Fig.12 Running time comparison under the uniform distribution圖12 uniform 分布下運(yùn)行時(shí)間對(duì)比

Fig.13 Running time comparison under the latest distribution圖13 latest 分布下運(yùn)行時(shí)間對(duì)比

4.2.2 讀寫次數(shù)比較

圖14～16 和圖17～19 分別顯示了ZB+-tree 和CoW B+-tree 的讀操作次數(shù)和寫操作次數(shù)對(duì)比.ZB+-tree 比CoW B+-tree 在讀操作次數(shù)上減少了25%左右，這是因?yàn)樵趧h除操作時(shí)，相比于CoW B+-tree 需要級(jí)聯(lián)的讀寫，ZB+-tree 在機(jī)會(huì)主義策略控制的2 層減少了合并操作并去除了從鄰居借鍵值對(duì)的操作.在寫操作次數(shù)方面，ZB+-tree 在不同數(shù)據(jù)規(guī)模時(shí)平均節(jié)約了75%的寫，這主要是因?yàn)閆B+-tree 通過(guò)LH 層和IH 層的獨(dú)特設(shè)計(jì)將級(jí)聯(lián)的更新進(jìn)行了2 次阻斷.由于LH和IH 都位于Cov-Zone 中，允許進(jìn)行原地更新，因此節(jié)點(diǎn)修改后的地址不發(fā)生改變，所以級(jí)聯(lián)的更新被阻斷在了Cov-Zone 中.相比于CoW B+-tree 每次更新至少需要4 次寫操作，ZB+-tree 只需要1～2 次寫操作即可.

Fig.14 Read counts comparison under the Zipfian distribution圖14 Zipfian 分布下讀次數(shù)對(duì)比

Fig.15 Read counts comparison under the uniform distribution圖15 uniform 分布下讀次數(shù)對(duì)比

Fig.16 Read counts comparison under the latest distribution圖16 latest 分布下讀次數(shù)對(duì)比

Fig.17 Write counts comparison under the Zipfian distribution圖17 Zipfian 分布下寫次數(shù)對(duì)比

Fig.18 Write counts comparison under the uniform distribution圖18 uniform 分布下寫次數(shù)對(duì)比

Fig.19 Write counts comparison under the latest distribution圖19 latest 分布下寫次數(shù)對(duì)比

4.2.3 空間占用率比較

表2～6 分別顯示了在Zipfian 分布下，5 種工作負(fù)載和3 種數(shù)據(jù)規(guī)模下ZB+-tree 和CoW B+-tree 對(duì)于所有Seq-Zone 的平均占用情況，其他數(shù)據(jù)分布下實(shí)驗(yàn)結(jié)果類似.可以看出，隨著數(shù)據(jù)規(guī)模的增加，CoW B+-tree 將快速占用Seq-Zone 的空間.在當(dāng)數(shù)據(jù)規(guī)模為250萬(wàn)時(shí)，CoW B+-tree 對(duì)Seq-Zone 的占用率最大達(dá)到了0.739 822（Workload4），最小也有0.450 943（Workload5）.因此，在大規(guī)模寫入負(fù)載下，CoW B+-tree 的Seq-Zone將被快速寫滿，從而觸發(fā)耗時(shí)的Zone 垃圾回收和Zone-Reset 操作，導(dǎo)致系統(tǒng)性能出現(xiàn)急劇下降.

Table 2 Occupancy Rate of Seq-Zone Under Workload1 at Different Data Scales表2 不同數(shù)據(jù)規(guī)模下Workload1 下對(duì)Seq-Zone 的占用率

Table 3 Occupancy Rate of Seq-Zone Under Workload2 at Different Data Scales表3 不同數(shù)據(jù)規(guī)模下Workload2 下對(duì)Seq-Zone 的占用率

Table 4 Occupancy Rate of Seq-Zone Under Workload3 at Different Data Scales表4 不同數(shù)據(jù)規(guī)模下Workload3 下對(duì)Seq-Zone 的占用率

Table 5 Occupancy Rate of Seq-Zone Under Workload4 at Different Data Scales表5 不同數(shù)據(jù)規(guī)模下Workload4 下對(duì)Seq-Zone 的占用率

Table 6 Occupancy Rate of Seq-Zone Under Workload5 at Different Data Scales表6 不同數(shù)據(jù)規(guī)模下Workload5 下對(duì)Seq-Zone 的占用率

此外，ZB+-tree 對(duì)于所有Seq-Zone 的平均占用率在5 種不同負(fù)載下均低于0.002 7，遠(yuǎn)遠(yuǎn)低于CoW B+-tree.而且ZB+-tree 的Seq-Zone 占用率不會(huì)因?yàn)閿?shù)據(jù)規(guī)模的增大而出現(xiàn)Seq-Zone 被快速寫滿的情況.因此，在系統(tǒng)運(yùn)行過(guò)程中，ZB+-tree 一般不會(huì)頻繁觸發(fā)Zone 垃圾回收和Zone-Reset 操作，從而可以在保證系統(tǒng)性能和穩(wěn)定性的同時(shí)節(jié)省較多的Seq-Zone 空間，提升空間效率.

4.2.4 Cov-Zone 和Seq-Zone 的不同比例

由于當(dāng)前還沒(méi)有ZNS SSD 的真實(shí)設(shè)備，因此Cov-Zone 和Seq-Zone 的比例可能會(huì)發(fā)生變化，因此，我們改變Cov-Zone 和Seq-Zone 的比例來(lái)測(cè)試ZB+-tree的效果.

在本節(jié)實(shí)驗(yàn)中，我們測(cè)試了3 種不同的Cov-Zone和Seq-Zone 的比例，分別是1∶32，1∶48，1∶64，數(shù)據(jù)分布為Zipfian 分布，數(shù)據(jù)量設(shè)置為100 萬(wàn)鍵值對(duì)，測(cè)試的負(fù)載為Workload1 和Workload2，如圖20 所示.

從圖20 可以看出，在不同比例下，ZB+-tree 的運(yùn)行時(shí)間 都要少于CoW B+-tree，更 改Cov-Zone 與Seq-Zone 的比例并不影響讀寫次數(shù)，只會(huì)影響對(duì)Seq-Zone 的占用率大小，具體結(jié)果如表7 和表8 所示.

由表7 和表8 可知，在不同比例下，ZB+-tree 對(duì)Seq-Zone 的占用率都遠(yuǎn)小于CoW B+-tree.同時(shí)，我們發(fā)現(xiàn)更改Seq-Zone 和Cov-Zone 的比例對(duì)ZB+-tree 的空間效率影響不大，表明ZB+-tree 能夠適應(yīng)不同的Zone 配置.

4.2.5 Zone-Reset 次數(shù)比較

Fig.20 Comparison of running time under different ratios of Cov-Zone and Seq-Zone圖20 Cov-Zone 和Seq-Zone 不同比例下運(yùn)行時(shí)間對(duì)比

Table 7 Occupancy Rate of Seq-Zone Under Workload1 at Different Ratios表7 不同比例下Workload1 下對(duì)Seq-Zone 的占用率

Table 8 Occupancy Rate of Seq-Zone Under Workload2 at Different Ratios表8 不同比例下Workload2 下對(duì)Seq-Zone 的占用率

在4.2.1～4.2.4 節(jié)的實(shí)驗(yàn)中，ZB+-tree 和CoW B+-tree都采用了動(dòng)態(tài)選擇Zone 的策略.該策略將葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)分開存放以充分利用ZNS SSD 內(nèi)部各個(gè)Zone 的空間，并且盡量減少Zone-Reset 操作，同時(shí)將不同特性的節(jié)點(diǎn)放在不同的Zone 來(lái)降低訪問(wèn)延遲.

本節(jié)的實(shí)驗(yàn)旨在進(jìn)一步驗(yàn)證ZB+-tree 在不采用動(dòng)態(tài)選擇Zone 策略時(shí)的性能.為了保證實(shí)驗(yàn)的公平性，CoW B+-tree 同樣不采用動(dòng)態(tài)選擇Zone 的策略.此外，為了體現(xiàn)實(shí)驗(yàn)完整性，本實(shí)驗(yàn)中我們通過(guò)統(tǒng)計(jì)Zone-Reset 的次數(shù)來(lái)對(duì)比ZB+-tree 和CoW B+-tree.

對(duì)于ZB+-tree，設(shè) 置1 個(gè)Seq-Zone 和1 個(gè)Cov-Zone，大小都為2 GB，然后統(tǒng)計(jì)Zone-Reset 次數(shù).對(duì)于CoW B+-tree，設(shè) 置1 個(gè)Seq-Zone 和1 個(gè)Cov-Zone（按順序?qū)懩Ｊ绞褂茫?，大小都? GB，當(dāng)某一個(gè)Zone 寫滿時(shí)，讀出有效節(jié)點(diǎn)寫到另一個(gè)Zone，然后進(jìn)行Zone-Reset 操作并統(tǒng)計(jì)次數(shù).實(shí)驗(yàn)數(shù)據(jù)量分別為250 萬(wàn)、500 萬(wàn)、750 萬(wàn)鍵值 對(duì)，數(shù)據(jù)分 布設(shè)置 為Zipfian，測(cè)試負(fù)載為Workload1 和Workload2.

實(shí)驗(yàn)結(jié)果表明，在Workload1 下，在數(shù)據(jù)量分別為250 萬(wàn)、500 萬(wàn)、750 萬(wàn)鍵值對(duì)時(shí)，ZB+-tree 均沒(méi)有觸發(fā)Zone-Reset 操作；而CoW B+-tree 則分別觸發(fā)了10，22，37 次Zone-Reset 操 作.在Workload2 下，ZB+-tree 在數(shù)據(jù)量為250 萬(wàn)、500 萬(wàn)、750 萬(wàn)鍵值對(duì)時(shí)依然沒(méi)有觸發(fā)Zone-Reset 操作；而CoW B+-tree 則分別觸發(fā)了2，6，9 次Zone-Reset 操作.

因此，CoW B+-tree 比ZB+-tree 會(huì)更容易觸發(fā)Zone-Reset 操作，而ZB+-tree 即使不進(jìn)行動(dòng)態(tài)選擇優(yōu)化，也能夠在插入大量鍵值時(shí)不觸發(fā)Zone-Reset 操作.由于Zone-Reset 和Zone 垃圾回收操作的時(shí)間延遲高，因此ZB+-tree 相對(duì)于CoW B+-tree 具有更好的時(shí)間性能，尤其是在寫密集型負(fù)載下，這種優(yōu)勢(shì)更加明顯.

4.2.6 對(duì)Cov-Zone 的占用分析

在本節(jié)實(shí)驗(yàn)中，我們創(chuàng)建了40 個(gè)Seq-Zone 和1個(gè)Cov-Zone（每個(gè)Zone 大小都為2 GB），并分別在100萬(wàn)、250 萬(wàn)、500 萬(wàn)、750 萬(wàn)、1 000 萬(wàn)鍵值對(duì)的數(shù)據(jù)集上運(yùn)行在Zipfian 分布下的Workload1 和Workload2，然后統(tǒng)計(jì)ZB+-tree 對(duì)Cov-Zone 的空間占用率.

實(shí)驗(yàn)結(jié)果如圖21 所示.隨著數(shù)據(jù)規(guī)模的增大，ZB+-tree 對(duì)Cov-Zone 的空間占用率呈線性增長(zhǎng)趨勢(shì)，這是因?yàn)閿?shù)據(jù)規(guī)模越大，負(fù)載中涉及更新的鍵值越多，因此對(duì)Cov-Zone 的使用量也增大.但是，即使數(shù)據(jù)規(guī)模達(dá)到了1 000 萬(wàn)，對(duì)Cov-Zone 的占用率也沒(méi)有超過(guò)0.50，這表明Cov-Zone 的空間不會(huì)用滿，因此可以滿足絕大部分應(yīng)用的需要.

Fig.21 Changes in the occupancy rate of Cov-Zone by ZB+-tree圖21 ZB+-tree 對(duì)Cov-Zone 的占用率變化

5 結(jié)束語(yǔ)

本文提出了一種ZNS SSD 感知的新型索引結(jié)構(gòu)ZB+-tree，通過(guò)合理利用ZNS SSD 中的常規(guī)Zone 和順序Zone 的特性來(lái)吸收對(duì)Zone 的隨機(jī)寫操作、阻斷級(jí)聯(lián)更新、減少讀寫次數(shù).我們?yōu)? 種Zone 內(nèi)的節(jié)點(diǎn)設(shè)計(jì)了不同的節(jié)點(diǎn)結(jié)構(gòu)，并通過(guò)將不同訪問(wèn)頻率的節(jié)點(diǎn)分散在不同Zone 中以降低訪問(wèn)延遲，并且滿足ZNS SSD 順序?qū)懙南拗?我們利用ZNS SSD 模擬器展開了實(shí)驗(yàn)，并對(duì)比了ZB+-tree 和傳統(tǒng)CoW B+-tree，結(jié)果表明ZB+-tree 在運(yùn)行時(shí)間和讀寫次數(shù)上均優(yōu)于CoW B+-tree.同時(shí)，ZB+-tree 具有更低的Seq-Zone 空間占用率，可以有效減少系統(tǒng)運(yùn)行過(guò)程中進(jìn)行的垃圾回收和Zone-Reset 操作，提高系統(tǒng)性能，并且對(duì)Cov-Zone 的占用率也能夠在數(shù)據(jù)規(guī)模增大時(shí)始終保持在0.50 以下，可以滿足大多數(shù)應(yīng)用的需要.

未來(lái)的工作將主要集中在3 個(gè)方向：1）為ZB+-tree增加合理的GC 機(jī)制；2）在選擇節(jié)點(diǎn)放置時(shí)設(shè)置更加合理的Zone 選擇方案；3）在真實(shí)的ZNS SSD 設(shè)備上進(jìn)行實(shí)驗(yàn).

作者貢獻(xiàn)聲明：劉揚(yáng)提出算法思路，完成實(shí)驗(yàn)并撰寫論文初稿；金培權(quán)提出指導(dǎo)意見(jiàn)并修改論文.