ZB+-tree：一種ZNS SSD 感知的新型索引結(jié)構(gòu)

劉揚 金培權(quán)

（中國科學技術(shù)大學計算機科學與技術(shù)學院 合肥 230026）

（中國科學院電磁空間信息重點實驗室 合肥 230026）

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

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

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

B+-tree 是數(shù)據(jù)庫中經(jīng)典的索引結(jié)構(gòu)，以往研究者已經(jīng)提出了多種針對SSD、持久性內(nèi)存等新型存儲的B+-tree 優(yōu)化方法[15-26].但是，已有的SSD 索引設計重點在于減少對SSD 的隨機寫操作.雖然ZNS SSD的底層介質(zhì)仍是閃存，但由于Zone 內(nèi)只能順序?qū)?，因此隨機寫的問題不再是ZNS SSD 上B+-tree 索引優(yōu)化的第一目標.B+-tree 如何在沒有FTL 的情況下適應ZNS SSD 的分區(qū)特性以及Zone 內(nèi)順序?qū)懸螅荶NS SSD 感知的B+-tree 索引需要解決的關鍵問題.針對傳統(tǒng)SSD 設計的索引由于沒有考慮ZNS SSD 的特性，所以都無法直接運行在ZNS SSD 上.此外，根據(jù)我們的調(diào)研，目前也還沒有提出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ū)?，但是實際的分區(qū)塊設備（zoned block device，ZBD）中除了只允許順序?qū)懙捻樞騔one（sequential zone，Seq-Zone），還存在著少量允許隨機寫的常規(guī)Zone（conventional zone，Cov-Zone）.因此，我們結(jié)合了ZNS SSD 內(nèi)部這2 類Zone 的特性設計了ZB+-tree 的結(jié)構(gòu)來適配ZNS SSD.具體而言，本文的主要工作和貢獻可總結(jié)為3 個方面：

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

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

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

1 背景與相關工作

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

1.1 ZNS SSD 相關工作

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

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

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

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

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

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

1.2 SSD 感知的B+-tree 相關工作

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

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

1.3 CoW B+-tree

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

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

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

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

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

2.1 設計思路

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

針對上述目標，ZB+-tree 進行了全新設計，主要設計思路總結(jié)為5 個方面：

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

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

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

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

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

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

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

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

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

圖5 顯示了ZB+-tree 節(jié)點在ZNS SSD 上的具體分布情況，其中IH 和LH 層都位于Cov-Zone 中，而interior 節(jié)點和leaf 節(jié)點則分布在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é)點在ZNS SSD 上的分布

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

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

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

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

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

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

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

1）Sync 操作.將節(jié)點與對應的log 節(jié)點進行合并，Sync 操作完成之后節(jié)點還是處于steady_state.

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

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

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

2.3 ZB+-tree 節(jié)點結(jié)構(gòu)設計

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

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

Fig.7 An example of leaf and corresponding leaf-log圖7 leaf 和對應的leaf-log 示例

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

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

3）log_addr.表示子節(jié)點對應的日志節(jié)點所處的位置.

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

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

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

3 ZB+-tree 索引操作

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

3.1 Sync

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

1）Normal_apply.圖9 給出了Normal_apply 的 過程.當節(jié)點對應的log 節(jié)點還未滿時，如果節(jié)點處于steady_state，表示節(jié)點還未進行過刪除操作，log 節(jié)點中無刪除記錄，因此根據(jù)log 節(jié)點進行更新后的節(jié)點仍然處于steady_state，此時將新的節(jié)點寫回Seq-Zone并釋放Cov-Zone 上log 節(jié)點的空間.如果節(jié)點處于after_state，則表示節(jié)點經(jīng)過了刪除操作，log 節(jié)點中一定有刪除記錄，根據(jù)log 節(jié)點進行更新后的節(jié)點轉(zhuǎn)換成change_state并寫到Cov-Zone 中原log 節(jié)點的位置.算法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 的 過程.當節(jié)點對應的log 節(jié)點已經(jīng)寫滿時，將發(fā)生Switch_apply，與Normal_apply 不同的是，Switch_apply 不需要讀原節(jié)點，而只需要讀其log 節(jié)點，因為日志已滿說明原節(jié)點中所有鍵值對都已經(jīng)經(jīng)過了更新或者刪除.如果原節(jié)點處于steady_state，說明對節(jié)點的所有鍵值對都進行過更新操作，因此直接將log 節(jié)點作為新的節(jié)點寫入Seq-Zone 中，并釋放在Cov-Zone 中l(wèi)og節(jié)點的空間.如果原節(jié)點處于after_state，說明其除了進行過更新操作之外還有刪除操作，因此把log 節(jié)點中有刪除標記（delete_key）的鍵值對去除后，轉(zhuǎn)化為change_state的節(jié)點，直接寫回Cov-Zone 中原log 節(jié)點位置.算法2 給出了Switch_apply.

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

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

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

3.2 Search

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

算法4.Search（key）.

算法5.Search_leaf_head（leaf_head,key）.

3.3 Insert

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

算法6.Insert（key,value）.

3.4 Delete

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

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

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

算法7.Delete（key）.

3.5 理論代價分析

3.5.1 時間性能

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

3.5.2 空間代價

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

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

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

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

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

4 實驗與分析

4.1 實驗設置

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

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

Table 1 Experimental Configuration表1 實驗配置

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

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

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

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

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

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

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

4.2 實驗結(jié)果分析

4.2.1 運行時間比較

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

Fig.11 Running time comparison under the Zipfian distribution圖11 Zipfian 分布下運行時間對比

Fig.12 Running time comparison under the uniform distribution圖12 uniform 分布下運行時間對比

Fig.13 Running time comparison under the latest distribution圖13 latest 分布下運行時間對比

4.2.2 讀寫次數(shù)比較

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

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

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

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

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

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

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

4.2.3 空間占用率比較

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

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

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

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

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

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

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

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

由于當前還沒有ZNS SSD 的真實設備，因此Cov-Zone 和Seq-Zone 的比例可能會發(fā)生變化，因此，我們改變Cov-Zone 和Seq-Zone 的比例來測試ZB+-tree的效果.

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

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

由表7 和表8 可知，在不同比例下，ZB+-tree 對Seq-Zone 的占用率都遠小于CoW B+-tree.同時，我們發(fā)現(xiàn)更改Seq-Zone 和Cov-Zone 的比例對ZB+-tree 的空間效率影響不大，表明ZB+-tree 能夠適應不同的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 不同比例下運行時間對比

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

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

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

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

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

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

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

4.2.6 對Cov-Zone 的占用分析

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

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

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

5 結(jié)束語

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

未來的工作將主要集中在3 個方向：1）為ZB+-tree增加合理的GC 機制；2）在選擇節(jié)點放置時設置更加合理的Zone 選擇方案；3）在真實的ZNS SSD 設備上進行實驗.

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