一種wandering B+tree 問題解決方法

楊勇鵬 蔣德鈞

（中國(guó)科學(xué)院計(jì)算技術(shù)研究所 北京 100190）

（中國(guó)科學(xué)院大學(xué) 北京 100049）

隨著大數(shù)據(jù)時(shí)代的到來和發(fā)展，數(shù)據(jù)量呈現(xiàn)爆炸式增長(zhǎng).根據(jù)IDC（International Data Corporation）的預(yù)測(cè)，全球數(shù)據(jù)領(lǐng)域?qū)?018 年的33ZB 增長(zhǎng)到2025 年的175ZB[1].為了滿足數(shù)據(jù)存儲(chǔ)的需求，數(shù)據(jù)存儲(chǔ)系統(tǒng)的規(guī)模和存儲(chǔ)介質(zhì)的容量都在不斷地增長(zhǎng).各大存儲(chǔ)設(shè)備廠商紛紛推出大容量存儲(chǔ)設(shè)備來滿足大量數(shù)據(jù)存儲(chǔ)的需求.例如，西部數(shù)據(jù)已經(jīng)推出單盤容量達(dá)18TB 的機(jī)械硬盤（hard disk drive，HDD）[2]，和單盤容量達(dá)20TB 的瓦記錄磁盤（shingled write disk，SWD）[3].存儲(chǔ)廠商N(yùn)imbus Data 推出單盤最大容量高達(dá)100TB 的固態(tài)硬盤（solid state disk，SSD）[4].

對(duì)于HDD，文獻(xiàn)[5]提到，Unix 文件系統(tǒng)只能利用5%～10%的磁盤寫帶寬，其他時(shí)間都消耗在磁盤尋道上.Sprite LFS[5]（log-structured file system）采用日志結(jié)構(gòu)（log-structured）技術(shù)，該系統(tǒng)假設(shè)：文件都緩存在內(nèi)存中，容量逐漸增大的內(nèi)存可以很有效地滿足讀請(qǐng)求的處理需求.基于該假設(shè)，Sprite LFS 著重優(yōu)化寫性能.Sprite LFS 的物理地址分配方式為寫時(shí)分配，文件系統(tǒng)的元數(shù)據(jù)和數(shù)據(jù)的更新方式均為異地寫（out-of-place write）.Sprite LFS 將所有的寫請(qǐng)求轉(zhuǎn)換為順序?qū)懞?，幾乎可以消除所有的磁盤尋道開銷.基于Sprite LFS，NILFS[6]在Linux 系統(tǒng)上實(shí)現(xiàn)了日志結(jié)構(gòu)文件系統(tǒng).

對(duì)于SSD，文獻(xiàn)[7-8]的研究表明：頻繁地隨機(jī)寫請(qǐng)求處理，會(huì)導(dǎo)致嚴(yán)重的內(nèi)部碎片，影響SSD 的持續(xù)性能表現(xiàn).SFS[9]研究發(fā)現(xiàn)：SSD 的隨機(jī)寫帶寬和順序?qū)憥挼牟町惓^10 倍；隨機(jī)寫會(huì)增加單位寫請(qǐng)求的閃存塊平均擦除次數(shù)，從而減少SSD 的使用壽命.為解決上述問題，SFS 以NILFS 為基礎(chǔ)針對(duì)閃存介質(zhì)特性，實(shí)現(xiàn)新的文件系統(tǒng)，提升系統(tǒng)吞吐率，降低閃存塊平均擦除次數(shù)，減少SSD 元數(shù)據(jù)管理開銷，從而提升SSD 壽命.

近年來，業(yè)界又先后推出了JFFS[10]，F(xiàn)2FS[11-14]等日志結(jié)構(gòu)文件系統(tǒng).除了文件系統(tǒng)外，日志結(jié)構(gòu)技術(shù)還被應(yīng)用于塊存儲(chǔ)系統(tǒng)，例如BW-RAID[15]存儲(chǔ)系統(tǒng)的ASD 子系統(tǒng)[16-17]，ASD 系統(tǒng)向上提供標(biāo)準(zhǔn)塊設(shè)備接口，將上層寫請(qǐng)求轉(zhuǎn)換為本地磁盤RAID 的順序?qū)?，以提升BW-RAID 系統(tǒng)的吞吐率.本文把這類系統(tǒng)統(tǒng)稱為日志結(jié)構(gòu)存儲(chǔ)系統(tǒng).

雖然日志結(jié)構(gòu)存儲(chǔ)系統(tǒng)可以將所有的寫請(qǐng)求轉(zhuǎn)換為順序?qū)懀且驗(yàn)槿罩窘Y(jié)構(gòu)存儲(chǔ)系統(tǒng)要求數(shù)據(jù)和元數(shù)據(jù)的修改都采用異地更新的方式，它面臨元數(shù)據(jù)異地更新帶來的連鎖更新問題.樹狀結(jié)構(gòu)通常被用于保存元數(shù)據(jù)，例如B+tree，RB-tree（red-black tree），而一旦樹狀結(jié)構(gòu)的某個(gè)結(jié)點(diǎn)執(zhí)行了異地更新，就會(huì)觸發(fā)遞歸更新樹狀結(jié)構(gòu)，這一問題通常被稱作wandering tree 問 題[18].因 為B+tree 被廣泛 應(yīng)用于 存儲(chǔ)系統(tǒng)中，所以本文主要關(guān)注wandering B+tree 問題.

針對(duì)wandering tree 問題，現(xiàn)有日志結(jié)構(gòu)存儲(chǔ)系統(tǒng)均提出了各自的解決方法：例如，NILFS2[19]使用B+tree 管理所有元數(shù)據(jù)，引入特殊的內(nèi)部文件DAT（data address translation file）管理所有B+tree 樹結(jié)點(diǎn)；DAT 文件的每個(gè)數(shù)據(jù)塊為B+tree 的樹結(jié)點(diǎn)，在文件內(nèi)的偏移作為B+tree 樹結(jié)點(diǎn)的邏輯索引（用于索引在內(nèi)存中的樹結(jié)點(diǎn)）.但是，DAT 文件的地址映射關(guān)系仍然使用B+tree 維護(hù)，以此保存邏輯索引和物理地址的映射（元數(shù)據(jù)塊和數(shù)據(jù)塊在物理設(shè)備上的地址），因此當(dāng)DAT 文件更新時(shí)，DAT 文件的映射管理仍然面臨wandering B+tree 的問題.

F2FS 采用多級(jí)間接索引管理文件映射，同樣面臨元數(shù)據(jù)結(jié)構(gòu)遞歸更新問題.為了緩解這一問題帶來的性能影響，F(xiàn)2FS 使用物理設(shè)備上固定的NAT（node address table）[11]區(qū)域存放元數(shù)據(jù)塊邏輯索引和物理地址的映射關(guān)系.1 個(gè)設(shè)備上共有2 個(gè)交替使用的NAT 區(qū)域，目的是為了確保每次下刷NAT 塊均為原子操作.此外，對(duì)于采用日志結(jié)構(gòu)技術(shù)的塊存儲(chǔ)系統(tǒng)ASD 而言，它采用2 層RB-tree 管理地址映射，通過固定區(qū)域存放地址映射的反向映射來解決wandering RB-tree 問題.

綜上，上述系統(tǒng)均使用額外的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間管理樹結(jié)點(diǎn)邏輯索引和物理地址的映射，以此解決元數(shù)據(jù)管理的wandering tree 問題.但引入額外的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間，會(huì)增加系統(tǒng)設(shè)計(jì)的復(fù)雜度、降低寫物理設(shè)備的連續(xù)度.

采用日志結(jié)構(gòu)設(shè)計(jì)的文件系統(tǒng)和塊設(shè)備系統(tǒng)在業(yè)界均有廣泛的應(yīng)用，然而針對(duì)大容量塊存儲(chǔ)系統(tǒng)，若采用高扇出、樹操作效率高的B+tree 管理塊設(shè)備邏輯地址和物理地址的映射關(guān)系，則需要解決wandering B+tree 問題，現(xiàn)有的塊設(shè)備解決方法及日志結(jié)構(gòu)文件系統(tǒng)的解決方法均需要引入額外的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間.為解決wandering B+tree 問題，本文提出IBT（internal node based translation）B+tree.本文的主要貢獻(xiàn)有3 個(gè)方面：

1）提出IBT B+tree 樹結(jié)構(gòu).中間結(jié)點(diǎn)記錄孩子結(jié)點(diǎn)的邏輯索引和物理地址，避免引入額外數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間.

2）提 出IBT B+tree 下刷算 法.引入每 層dirty 鏈表按層次管理所有dirty 樹結(jié)點(diǎn)，自底向上按層次下刷IBT B+tree，避免遞歸更新樹結(jié)構(gòu).

3）設(shè)計(jì)實(shí)現(xiàn)Monty-Dev 塊存儲(chǔ)系統(tǒng)，評(píng)價(jià)IBT B+tree 在寫放大和下刷效率方面的優(yōu)化效果.

1 相關(guān)工作

對(duì)于樹狀數(shù)據(jù)結(jié)構(gòu)，父親結(jié)點(diǎn)需要記錄孩子結(jié)點(diǎn)的地址信息.對(duì)于需要持久化到物理設(shè)備的樹結(jié)構(gòu)，則需要通過在中間結(jié)點(diǎn)中記錄的孩子結(jié)點(diǎn)信息，確定孩子結(jié)點(diǎn)的物理地址.本文將樹結(jié)點(diǎn)在內(nèi)存中的唯一標(biāo)識(shí)稱作樹結(jié)點(diǎn)邏輯索引，將樹結(jié)點(diǎn)在物理設(shè)備上的地址稱作樹結(jié)點(diǎn)物理地址.Linux 內(nèi)核中的ext4，dm-btree 等模塊的樹狀數(shù)據(jù)結(jié)構(gòu)，通過中間結(jié)點(diǎn)記錄孩子結(jié)點(diǎn)的物理地址訪問孩子結(jié)點(diǎn)，因此樹結(jié)點(diǎn)邏輯索引和物理地址相同.其中，dm-btree 使用RBtree 組織緩存在內(nèi)存中的樹結(jié)點(diǎn)，訪問孩子結(jié)點(diǎn)時(shí)首先檢查孩子結(jié)點(diǎn)是否在RB-tree 中，如果在則直接訪問樹結(jié)點(diǎn)，否則需要從物理設(shè)備加載.

日志結(jié)構(gòu)存儲(chǔ)系統(tǒng)要求樹結(jié)點(diǎn)的更新方式為異地寫，且為寫時(shí)分配物理地址.如果樹結(jié)點(diǎn)邏輯索引和物理地址相同，則在樹結(jié)點(diǎn)下刷時(shí)需要遞歸更新祖先結(jié)點(diǎn)中記錄的孩子結(jié)點(diǎn)物理地址，因此存在wandering tree 問題.本節(jié)分別介紹NILFS2，F(xiàn)2FS，ASD系統(tǒng)針對(duì)wandering tree 問題的解決方法.

1.1 NILFS2

NILFS2 使用B+tree 管理文件映射和inode.對(duì)于wandering B+tree 問題，NILFS2 的解決方法是：普通文件映射及管理inode 的B+tree 樹結(jié)點(diǎn)，由一個(gè)文件名為DAT 的特殊文件管理；所有管理用戶文件映射的B+tree 樹結(jié)點(diǎn)是DAT 文件的一個(gè)數(shù)據(jù)塊；DAT文件的地址映射也由B+tree 管理，該B+tree 的樹結(jié)點(diǎn)邏輯索引與物理地址相同.

Fig.1 The case of NILFS2 user file and DAT file mapping [19]圖1 NILFS2 的用戶文件和DAT 文件映射案例[19]

圖1 介紹NILFS2 的解決方法.圖1（a）為管理普通用戶文件映射的B+tree 示意圖，樹結(jié)點(diǎn)邏輯索引為vblocknr，即樹結(jié)點(diǎn)在DAT 文件中的偏移；圖1（b）為管理DAT 文件映射的B+tree 示意圖，樹結(jié)點(diǎn)邏輯索引和物理地址為blocknr.

若要讀取用戶文件邏輯地址為0 的塊，則需要查找圖1（a）所示的B+tree，訪問結(jié)點(diǎn)Rf確定下一個(gè)要訪問的孩子結(jié)點(diǎn)vblocknr=1；若DAT 文件的第1 號(hào)塊不在內(nèi)存，則通過圖1（b）中所示的B+tree 查找映射，自上至下訪問結(jié)點(diǎn)Ad，確定DAT 文件第1 號(hào)塊的物理地址為4，即為結(jié)點(diǎn)Af的物理地址；通過查找結(jié)點(diǎn)Af，可確定用戶文件第0 號(hào)邏輯塊的物理地址為0.

圖1（a）中樹結(jié)點(diǎn)修改下刷只需要修改DAT 文件，無需遞歸更新圖1（a）；而圖1（b）中樹結(jié)點(diǎn)修改下刷時(shí)，仍然需要遞歸更新.

綜上，NILFS2 可以解決除管理DAT 文件映射的B+tree 之外所有元數(shù)據(jù)面臨的wandering B+tree 問題.因此，NILFS2 的方法可以部分解決wandering B+tree問題，但仍然存在遞歸更新B+tree 樹結(jié)點(diǎn)的問題.

1.2 F2FS

F2FS 將底層設(shè)備劃分為多個(gè)segment，segment是F2FS 管理的最小單元.除物理設(shè)備頭部固定空間占用外，剩余每個(gè)segment 用來存放數(shù)據(jù)或者元數(shù)據(jù)，F(xiàn)2FS 的元數(shù)據(jù)主要包括2 類：inode 塊和間接索引塊.F2FS 通過inode 塊存放文件信息，使用多級(jí)間接索引管理文件的地址映射.多級(jí)間接索引有著索引管理簡(jiǎn)單的優(yōu)點(diǎn)，但是不抗稀疏，不能支持Extent.由于使用了多級(jí)間接索引，F(xiàn)2FS 也存在wandering tree 問題.

F2FS 的解決方法是：引入NAT 的設(shè)計(jì)，將文件系統(tǒng)元數(shù)據(jù)塊的邏輯索引和物理地址分離；使用固定的NAT 區(qū)域存放NAT ID 和物理地址的映射關(guān)系，避免修改一個(gè)元數(shù)據(jù)塊就需要遞歸更新上級(jí)元數(shù)據(jù)塊中記錄的下級(jí)元數(shù)據(jù)塊物理地址；F2FS 在格式化時(shí)，按照設(shè)備大小計(jì)算出管理既定物理設(shè)備空間所需的NAT 塊個(gè)數(shù)上限，NAT 區(qū)域中塊數(shù)量為上限的2 倍，2 個(gè)空間存放NAT 塊的不同版本，交替使用.

NAT 塊管理示意圖如圖2 所示，圖中有4 個(gè)segment，每個(gè)segment 包括512 個(gè)塊，每個(gè)塊大小均為4KB；每個(gè)塊包括455 個(gè)NAT entry，即455 個(gè)NAT ID 到物理地址的轉(zhuǎn)換；由于使用固定物理空間存放NAT，因此可通過每個(gè)NAT entry 相對(duì)于NAT 區(qū)域起始地址的差值計(jì)算得到NAT ID；每2 個(gè)連續(xù)的segment存放512 個(gè)有效NAT 塊，NAT 塊更新時(shí)寫不同的segment，由version bitmap 標(biāo)識(shí)某一個(gè)NAT 塊的最新版本在哪個(gè)segment 中.因此，通過2 個(gè)segment 和bitmap 的設(shè)計(jì)，可確保NAT 塊每次更新均為異地寫.

Fig.2 NAT block and version bitmap[11]圖2 NAT 塊和version bitmap[11]

隨著設(shè)備的增大，文件系統(tǒng)的元數(shù)據(jù)量也在增大，因此NAT 區(qū)域就需要管理更多的NAT 塊.但NAT 的隨機(jī)修改會(huì)導(dǎo)致嚴(yán)重的寫放大，為解決該問題，引入了journal 的設(shè)計(jì)，將最近對(duì)NAT 的修改記錄在CP 區(qū)域中，journal 無可用空間時(shí)再更新NAT 并下刷.

綜上，F(xiàn)2FS 采用NAT 和journal 的設(shè)計(jì)解決了wandering tree 問題.但NAT 設(shè)計(jì)無法利用負(fù)載的空間局部性，隨著NAT 空間的增大，寫放大問題會(huì)更嚴(yán)重，且物理設(shè)備的訪問模式不是順序?qū)?

1.3 ASD

ASD 系統(tǒng)提供Linux 標(biāo)準(zhǔn)塊設(shè)備語義，以虛擬塊設(shè)備（virtual device，VD）的形式提供存儲(chǔ)服務(wù).ASD系統(tǒng)在物理設(shè)備之上創(chuàng)建一個(gè)日志結(jié)構(gòu)存儲(chǔ)池，存儲(chǔ)池之上有多個(gè)邏輯地址空間，每個(gè)邏輯地址空間對(duì)應(yīng)一個(gè)虛擬塊設(shè)備VD，每個(gè)VD 向上提供存儲(chǔ)服務(wù).對(duì)于塊設(shè)備，最重要的元數(shù)據(jù)信息是邏輯地址和物理地址的映射關(guān)系.

ASD 的元數(shù)據(jù)管理結(jié)構(gòu)如圖3 所示.ASD 系統(tǒng)使用Extent 管理一段邏輯地址連續(xù)且物理地址連續(xù)的映射關(guān)系.定長(zhǎng)邏輯空間內(nèi)的多個(gè)Extent 組成一個(gè)Subtree，多個(gè)Subtree 組成一個(gè)Group，多個(gè)Group組成整個(gè)邏輯地址空間.Group 信息常駐內(nèi)存，Subtree和Extent 信息在內(nèi)存中的緩存可在內(nèi)存壓力大的時(shí)候釋放.由于Group 信息與設(shè)備容量相關(guān)，因此隨著設(shè)備容量的增大，內(nèi)存占用也會(huì)增大；另外，由于采用Extent 的方式管理，一個(gè)Extent 作為一個(gè)單獨(dú)的內(nèi)存分配單元，大量分配Extent 后回收、釋放可能存在內(nèi)部碎片問題，釋放了多個(gè)Extent 但是內(nèi)存占用卻沒有減少，且內(nèi)存占用上限越大內(nèi)部碎片越嚴(yán)重.

Fig.3 ASD system metadata structure [16-17]圖3 ASD 系統(tǒng)元數(shù)據(jù)結(jié)構(gòu)[16-17]

上述Extent，Subtree，Group 結(jié)構(gòu)均采用RB-tree進(jìn)行組織，每個(gè)Group 在內(nèi)存中索引多個(gè)Extent.對(duì)于Group 信息的下刷，需要先調(diào)整樹結(jié)構(gòu)，使得一個(gè)Group 索引到的Extent 信息可以記錄到物理設(shè)備上一個(gè)定長(zhǎng)的數(shù)據(jù)塊中，Group 的下刷方式為異地寫.因此，ASD 也存在wandering tree 的問題，ASD 的解決方法是：

1）Group 信息寫到物理設(shè)備上之后，將多個(gè)Group 的邏輯索引和物理地址的映射以異地寫的方式更新到數(shù)據(jù)區(qū)域；

2）將Group 信息的物理地址及其歸屬信息寫入物理設(shè)備頭部固定的反向表區(qū)域；

3）系統(tǒng)重啟時(shí)通過掃描固定區(qū)域重構(gòu)RB-tree.

綜上，ASD 采用2 級(jí)邏輯索引和物理地址的映射解決wandering RB-tree 問題.該方法的優(yōu)點(diǎn)是固定位置寫較少，但管理復(fù)雜度過高.

2 wandering B+tree 問題分析和結(jié)構(gòu)設(shè)計(jì)

本節(jié)首先分析wandering B+tree 問題，提出該問題的解決方法：IBT B+tree.分別通過B+tree 樹結(jié)點(diǎn)布局、鏈表設(shè)計(jì)和樹操作設(shè)計(jì)，以及第3 節(jié)提出的IBT B+tree 下刷算法論述wandering B+tree 的解決方法.

2.1 wandering B+tree 問題分析

首先，通過圖4 介紹wandering B+tree 問題，并明確解決問題的難點(diǎn).圖4 展示了1 棵樹結(jié)點(diǎn)邏輯索引與物理地址相同的3 階B+tree 樹結(jié)點(diǎn)更新過程.圖4 左圖下刷結(jié)點(diǎn)A時(shí)，需要為結(jié)點(diǎn)A分配新的物理地址生成結(jié)點(diǎn)A1；圖4 中間的圖，生成結(jié)點(diǎn)A1后，分配結(jié)點(diǎn)D1使其指向結(jié)點(diǎn)A1；圖4 右圖分配結(jié)點(diǎn)R1同理.因此，非樹根結(jié)點(diǎn)分配物理地址需要遞歸更新父親結(jié)點(diǎn)至樹根結(jié)點(diǎn)，嚴(yán)重影響B(tài)+tree 下刷效率.

Fig.4 Example of wandering B+tree problem圖4 wandering B+tree 問題案例

綜上，要解決wandering B+tree，需要滿足日志結(jié)構(gòu)系統(tǒng)設(shè)計(jì)需求：樹結(jié)點(diǎn)寫時(shí)分配物理地址，且更新方式為異地寫；同時(shí)，避免B+tree 樹結(jié)點(diǎn)下刷時(shí)遞歸更新非葉子結(jié)點(diǎn).

如第1 節(jié)所述，針對(duì)wandering tree 問題，NILFS2,F2FS,ASD 解決方法的共同點(diǎn)是：樹結(jié)點(diǎn)邏輯索引和物理地址不同，即樹結(jié)點(diǎn)的邏輯索引和物理地址分離，額外的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間維護(hù)樹結(jié)點(diǎn)邏輯索引和物理地址的映射關(guān)系.

因此，解決wandering B+tree 問題的難點(diǎn)是：

1）支持樹結(jié)點(diǎn)邏輯索引和物理地址分離，且不引入新的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間，降低復(fù)雜度；

2）避免B+tree 下刷時(shí)遞歸更新樹結(jié)構(gòu).

針對(duì)這2 個(gè)難點(diǎn)，2.2 節(jié)提出第1 個(gè)難點(diǎn)的解決方法，2.3 節(jié)和2.4 節(jié)支撐第3 節(jié)提出的IBT B+tree 下刷算法解決第2 個(gè)難點(diǎn).

2.2 IBT B+tree 樹結(jié)點(diǎn)布局

IBT B+tree 的中間結(jié)點(diǎn)和葉子結(jié)點(diǎn)結(jié)構(gòu)圖如圖5所示，圖5 中各字段的含義如表1 所示.接下來，分別介紹表1 中各字段的用途.

Fig.5 The internal node and leaf node of IBT B+tree圖5 IBT B+tree 中間結(jié)點(diǎn)和葉子結(jié)點(diǎn)

Table 1 The Meaning of the Fields in Fig.5表1 圖5 各字段的含義

1）state字段為孩子結(jié)點(diǎn)的狀態(tài)，dirty 代表孩子結(jié)點(diǎn)需要持久化到物理設(shè)備，clean 代表孩子結(jié)點(diǎn)已經(jīng)持久化且可以在內(nèi)存緊張時(shí)回收.因此，state僅描述內(nèi)存中的樹結(jié)點(diǎn)內(nèi)容是否與設(shè)備上的一致.

2）如圖5 所示，中間結(jié)點(diǎn)記錄孩子結(jié)點(diǎn)的邏輯索引index，隨著樹高的增長(zhǎng)，所有非樹根結(jié)點(diǎn)的index和pbid都會(huì)存放在其父親結(jié)點(diǎn)中，只有樹根結(jié)點(diǎn)的index和pbid不存放在樹結(jié)構(gòu)中.因此，需要額外的數(shù)據(jù)結(jié)構(gòu)和物理設(shè)備空間存放樹根信息，記作Superblock，包括index,pbid,height（見2.4 節(jié)）.由于所有樹結(jié)點(diǎn)的更新方式均為異地寫，因此樹根結(jié)點(diǎn)需要記錄在物理設(shè)備的固定位置上，B+tree 初始化時(shí)才能找到樹根.

3）中間結(jié)點(diǎn)記錄孩子結(jié)點(diǎn)的index和pbid，在內(nèi)存中的B+tree 樹結(jié)點(diǎn)，以index為關(guān)鍵字，使用紅黑樹進(jìn)行組織.各類B+tree 操作執(zhí)行過程中，如果樹結(jié)點(diǎn)不在紅黑樹中，則需要通過pbid從底層設(shè)備讀取樹結(jié)點(diǎn).

2.3 IBT B+tree 鏈表設(shè)計(jì)

2.2 節(jié)提出樹結(jié)點(diǎn)邏輯索引和物理地址分離的方法，通過樹結(jié)點(diǎn)邏輯索引管理內(nèi)存中的樹結(jié)點(diǎn)，通過物理地址加載不在內(nèi)存中的樹結(jié)點(diǎn)，從而支持寫時(shí)分配物理地址.因此，需要在此基礎(chǔ)上解決2.1 節(jié)提出的第2 個(gè)難點(diǎn)：設(shè)計(jì)非遞歸更新的IBT B+tree 下刷算法.主要思路是：按照層次管理B+tree dirty 樹結(jié)點(diǎn)，使得IBT B+tree 能夠按照層次進(jìn)行下刷.本節(jié)主要論述按照層次管理dirty 樹結(jié)點(diǎn)的方法，IBT B+tree下刷算法在第3 節(jié)論述.

擴(kuò)展并修改B+tree 鏈表維護(hù)方法.傳統(tǒng)B+tree只維護(hù)葉子結(jié)點(diǎn)鏈表，用來管理所有葉子結(jié)點(diǎn)，按照關(guān)鍵字升序或降序排列.本文修改并擴(kuò)展樹結(jié)點(diǎn)鏈表：B+tree 的每一層均有一個(gè)dirty 鏈表；引入全局clean 鏈表.2 類鏈表設(shè)計(jì)主要有2 個(gè)特點(diǎn)：

1）B+tree 各層dirty 鏈表管理相應(yīng)層中狀態(tài)為dirty 的樹結(jié)點(diǎn)，dirty 樹結(jié)點(diǎn)按照LRU 的方式管理，而非按照關(guān)鍵字排序；

2）clean 鏈表管理所有狀態(tài)為clean 的樹結(jié)點(diǎn)，clean 鏈表也采用LRU 的方式管理，目的是為了在內(nèi)存緊張時(shí)釋放不經(jīng)常訪問的樹結(jié)點(diǎn).

鏈表的使用，特別是dirty 鏈表，將在2.4 節(jié)介紹.第3 節(jié)將介紹如何通過dirty 鏈表更新樹結(jié)點(diǎn)物理地址.

2.4 IBT B+tree 基本操作設(shè)計(jì)

B+tree 在插入、查找、刪除操作中對(duì)key-value的管理，與采用shadow-clone 設(shè)計(jì)的B+tree[20-21]沒有差異.為使用lock-coupling 細(xì)粒度加鎖協(xié)議支持B+tree 并發(fā)操作[22]，B+tree 采用預(yù)先rebalance、分裂的方式調(diào)整樹結(jié)構(gòu)，避免B+tree 樹操作執(zhí)行過程中對(duì)孩子結(jié)點(diǎn)的修改導(dǎo)致父親結(jié)點(diǎn)rebalance、分裂.

對(duì)于wandering B+tree 問題的解決方法，2.2 節(jié)已經(jīng)給出支持樹結(jié)點(diǎn)邏輯索引和物理地址分離的樹結(jié)構(gòu)設(shè)計(jì).本節(jié)主要從支撐寫時(shí)分配物理地址、更新物理地址的角度進(jìn)行論述.支撐上述特性的主要解決方法是dirty 和clean 鏈表設(shè)計(jì).本節(jié)從B+tree 樹操作的角度介紹2 類鏈表的管理.由于clean 鏈表用來管理clean 樹結(jié)點(diǎn)、支撐內(nèi)存回收，只需要維護(hù)樹結(jié)點(diǎn)的LRU 邏輯即可.因此，本節(jié)主要介紹dirty 鏈表的管理.

dirty 鏈表的變化主要源自插入操作和刪除操作.下面分別通過案例介紹這2 個(gè)操作中dirty 鏈表的管理.本節(jié)所有的案例均圍繞圖4 所示的3 階B+tree進(jìn)行介紹，B+tree 樹結(jié)點(diǎn)的key-value 按照key（邏輯地址）升序排序.

2.4.1 插入操作

圖6 為將〈10,11〉映射插入1 棵3 階B+tree 的主要步驟.下面分步介紹插入操作：

1）初始狀態(tài)如圖6（a）所示，所有樹結(jié)點(diǎn)狀態(tài)均為clean.

2）圖6（b）將結(jié)點(diǎn)R標(biāo)記為dirty，并將結(jié)點(diǎn)R插入list[0]；由于結(jié)點(diǎn)R的key-value 數(shù)量達(dá)到上限，因此需要分裂結(jié)點(diǎn)R，分配D和E這2 個(gè)結(jié)點(diǎn).將結(jié)點(diǎn)R的key-value 平均分配給結(jié)點(diǎn)D和E.將結(jié)點(diǎn)D和E中記錄的最小key 與結(jié)點(diǎn)D和E的邏輯索引分別作為key 和value 插入到結(jié)點(diǎn)R中.此時(shí)不需要為結(jié)點(diǎn)D和E分配物理地址.樹高加1，相應(yīng)地調(diào)整鏈表.

3）圖6（c）和圖6（d），逐層向下訪問到結(jié)點(diǎn)A，將〈10,11〉插入到結(jié)點(diǎn)A中.

如圖6（b）所示，新創(chuàng)建的鏈表為B+tree 的第2 層.因?yàn)槌龢涓Y(jié)點(diǎn)外，B+tree 其他任何層都可能存在兄弟結(jié)點(diǎn)，為降低B+tree 樹操作復(fù)雜度，僅允許樹根結(jié)點(diǎn)分裂出孩子結(jié)點(diǎn).綜上，新插入的dirty 鏈表只發(fā)生在第2 層，這一特性適用于任何高度大于1的B+tree.

圖6 所示的每個(gè)階段操作過程中，都將所有需要訪問的樹結(jié)點(diǎn)狀態(tài)標(biāo)識(shí)為dirty，同時(shí)除樹根結(jié)點(diǎn)外，將所有dirty 樹結(jié)點(diǎn)在其父親結(jié)點(diǎn)中的狀態(tài)標(biāo)識(shí)為dirty.

Fig.6 Insert operation（insert〈10,11〉）圖6 插入操作（插入〈10,11〉）

由于dirty 鏈表的引入，2 個(gè)并發(fā)的插入操作①和②，①先執(zhí)行，②后執(zhí)行；如果插入②導(dǎo)致樹高加1，①獲得的樹高信息不正確，則樹結(jié)點(diǎn)可能插入錯(cuò)誤的鏈表.因此，B+tree 無法支持插入和插入的并發(fā).由于clean 鏈表對(duì)樹高不敏感，B+tree 仍可支持插入和查找操作并發(fā)執(zhí)行.

2.4.2 刪除操作

以圖7（a）所示的3 階B+tree 為例，介紹刪除〈10,11〉映射：

1）訪問樹根結(jié)點(diǎn)R，將結(jié)點(diǎn)R標(biāo)記為dirty，并加入到dirty 鏈表list[0]中.

2）圖7（b），結(jié)點(diǎn)R只有1 個(gè)孩子.因此，將結(jié)點(diǎn)D中記錄的key-value 拷貝到結(jié)點(diǎn)R中，刪除結(jié)點(diǎn)D和相應(yīng)的鏈表.同時(shí)，結(jié)點(diǎn)R繼承結(jié)點(diǎn)D的類型，圖7（b）中D為中間結(jié)點(diǎn)，也存在結(jié)點(diǎn)R只有1 個(gè)孩子且為葉子結(jié)點(diǎn)的情況.因此，結(jié)點(diǎn)R也可能成唯一的葉子結(jié)點(diǎn).

3）圖7（c）和圖7（d），逐級(jí)向下訪問到結(jié)點(diǎn)A，將〈10,11〉從結(jié)點(diǎn)A中刪除.

如圖7（b）所示，被刪除的dirty 鏈表為B+tree 的第2 層.與插入操作同理，dirty 鏈表刪除操作僅刪除第2 層鏈表，這一特性適用于任何高度大于1 的B+tree.

刪除操作可能引起樹高的修改，因此刪除操作與刪除操作、刪除與插入操作均不能并發(fā)執(zhí)行.

Fig.7 Remove operation（remove 〈10,11〉）圖7 刪除操作（刪除〈10,11〉）

3 IBT B+tree 下刷

本節(jié)針對(duì)2.1 節(jié)提到的第2 個(gè)難點(diǎn)，提出非遞歸更新的IBT B+tree 下刷算法，從而解決wandering B+tree 問題.通過第2 節(jié)中IBT B+tree 的相關(guān)介紹可知，IBT B+tree 除樹根結(jié)點(diǎn)外有如下特性：所有狀態(tài)為dirty 的樹結(jié)點(diǎn)的父親結(jié)點(diǎn)狀態(tài)均為dirty；dirty 結(jié)點(diǎn)的狀態(tài)對(duì)父親結(jié)點(diǎn)不透明.利用上述2 個(gè)特性，下面分別通過下刷算法和具體案例介紹IBT B+tree 的下刷.

B+tree 下刷存在2 種情況：下刷所有樹結(jié)點(diǎn)，包括B+tree 創(chuàng)建完成并插入多次關(guān)鍵字之后的狀態(tài)和B+tree 非首次下刷且所有樹結(jié)點(diǎn)狀態(tài)均為dirty；部分下刷，包括部分B+tree 樹結(jié)點(diǎn)為dirty 的情況和經(jīng)過多次刪除后B+tree 為空.

多次插入、刪除操作后，dirty 樹結(jié)點(diǎn)的內(nèi)存占用或下刷時(shí)間間隔達(dá)到一定閾值，需要將B+tree 所有狀態(tài)為dirty 的樹結(jié)點(diǎn)下刷到物理設(shè)備.

為避免遞歸更新B+tree 樹結(jié)構(gòu)，IBT B+tree 下刷采用2 階段提交的方式.

第1 階段，自dirty 鏈表的倒數(shù)第2 層向上下刷所有的dirty 鏈表：

1）根據(jù)該dirty 鏈表上所有樹結(jié)點(diǎn)，下刷該樹結(jié)點(diǎn)所有狀態(tài)為dirty 的孩子；

2）為孩子結(jié)點(diǎn)分配物理地址并下刷，將孩子結(jié)點(diǎn)的物理地址記錄到父結(jié)點(diǎn)中，并更新父結(jié)點(diǎn)中記錄的狀態(tài).

第2 階段，將Superblock 寫到固定的物理設(shè)備空間.

B+tree 下刷算法如算法1 所示：

算法1.IBT B+tree 下刷算法.

圖8 展示了B+tree 下刷的重要階段.接下來，以圖6（d）所示的3 階B+tree 為例，結(jié)合算法1 和圖8介紹B+tree 的下刷.

1）對(duì)于圖6（d）的B+tree，調(diào)用算法1 中的函數(shù)flush_btree下刷整棵B+tree.flush_btree調(diào)用flush_dirty_lists自list[1]開始至樹根鏈表，下刷所有dirty 鏈表.

2）如圖8（a）所示，對(duì)于list[1]的結(jié)點(diǎn)D，調(diào)用函數(shù)flush_dirty_nodes，結(jié)點(diǎn)D只有一個(gè)狀態(tài)為dirty 的孩子結(jié)點(diǎn)A.因此，如圖8（b）所示，為結(jié)點(diǎn)A分配物理地址并記錄在結(jié)點(diǎn)D中，同時(shí)將結(jié)點(diǎn)D中記錄的結(jié)點(diǎn)A狀態(tài)標(biāo)更新為clean.同樣的方式處理list[1]上所有樹結(jié)點(diǎn).

3）圖8（c）下刷list[0]，為結(jié)點(diǎn)D和E分配物理地址并下刷.至此，函數(shù)flush_dirty_lists執(zhí)行完成.

4）圖8（d）為樹根結(jié)點(diǎn)R分配物理地址15，寫樹根結(jié)點(diǎn)R并更新Superblock，完成第1 階段提交.

5）下刷Superblock 完成第2 階段提交.

4 IBT B+tree 評(píng)價(jià)系統(tǒng)設(shè)計(jì)實(shí)現(xiàn)

本文以日志結(jié)構(gòu)塊設(shè)備系統(tǒng)為背景，在第2 節(jié)和第3 節(jié)提出了IBT B+tree，解決了wandering B+tree問題.但是，僅有IBT B+tree 只可進(jìn)行樹操作測(cè)試，難以測(cè)試在不同負(fù)載下的表現(xiàn).

Fig.8 Flush dirty node of IBT B+tree圖8 下刷IBT B+tree 的dirty 結(jié)點(diǎn)

為全面評(píng)價(jià)IBT B+tree 在Fio 和Filebench 場(chǎng)景下的寫放大和下刷效率表現(xiàn)，需要設(shè)計(jì)實(shí)現(xiàn)能夠覆蓋IBT B+tree 支持的各類樹操作和下刷，且避免I/O上下文干擾的日志結(jié)構(gòu)塊存儲(chǔ)系統(tǒng)Monty-Dev.

為對(duì)比評(píng)價(jià)第3 節(jié)所提出解決方法的效果，擬將IBT B+tree 與采用NAT 方案設(shè)計(jì)的B+tree（后文稱作NAT B+tree）進(jìn)行對(duì)比.其中，NAT 方案設(shè)計(jì)參考Linux 內(nèi)核5.14 版本[19]F2FS 的實(shí)現(xiàn).由于NAT 塊通過F2FS 內(nèi)部inode 以文件映射的方式管理，因此這部分不能完全復(fù)用，轉(zhuǎn)而使用radix-tree 管理所有緩存的NAT 塊，基本與F2FS 的實(shí)現(xiàn)方式等價(jià)；其余部分均參考F2FS.另外，對(duì)于NAT 塊的version bitmap需要為每個(gè)樹結(jié)點(diǎn)預(yù)留1 b，計(jì)算方法與f2fs-tools[23]中格式化操作的計(jì)算方法不同.

本文以Linux 系統(tǒng)為平臺(tái)，設(shè)計(jì)實(shí)現(xiàn)Linux 內(nèi)核標(biāo)準(zhǔn)塊設(shè)備Monty-Dev 系統(tǒng).下面分別介紹評(píng)價(jià)系統(tǒng)Monty-Dev 的總體設(shè)計(jì)、元數(shù)據(jù)管理和系統(tǒng)layout.

4.1 Monty-Dev 系統(tǒng)整體架構(gòu)

該設(shè)計(jì)暫不考慮宕機(jī)恢復(fù)和下刷數(shù)據(jù)塊的反向映射信息，B+tree 樹結(jié)點(diǎn)和NAT 塊均緩存在內(nèi)存中，本文聚焦寫放大和固定物理設(shè)備空間非順序?qū)戦_銷的評(píng)價(jià).為評(píng)價(jià)刪除操作的影響，Monty-Dev 系統(tǒng)支持Linux 內(nèi)核中通用塊層的Discard I/O 語義.

Monty-Dev 系統(tǒng)總體架構(gòu)如圖9 所示.使用橫向的虛線標(biāo)識(shí)系統(tǒng)的分層，下面逐層介紹.“用戶接口”用來管理Monty-Dev 系統(tǒng)，比如創(chuàng)建、刪除設(shè)備和修改系統(tǒng)配置等.其他系統(tǒng)可通過“標(biāo)準(zhǔn)塊設(shè)備接口”，直接向Monty-Dev 提交讀寫I/O 請(qǐng)求.ext4/xfs 等文件系統(tǒng)實(shí)例，可向通用塊層提交讀寫I/O、Discard I/O 請(qǐng)求，Discard I/O 用來支持文件系統(tǒng)的trim 操作.

Fig.9 Architecture of Monty-Dev system圖9 Monty-Dev 系統(tǒng)整體架構(gòu)

Monty-Dev 核心模塊實(shí)現(xiàn)了通用塊層的部分接口，處理上層發(fā)往通用塊層的請(qǐng)求.基于Monty-Dev系統(tǒng)可執(zhí)行Fio 測(cè)試，將Monty-Dev 設(shè)備格式化為特定文件系統(tǒng)可支持Filebench 測(cè)試.

因此，通過Monty-Dev 系統(tǒng)測(cè)試Fio 和Filebench負(fù)載，可覆蓋B+tree 的查找、插入、刪除操作及其并發(fā)，以及元數(shù)據(jù)下刷.

4.2 元數(shù)據(jù)管理模塊

Monty-Dev 的元數(shù)據(jù)管理模塊結(jié)構(gòu)圖如圖10 所示，后文稱作Meta tree.

Fig.10 Structure diagram of Meta tree圖10 Meta tree 結(jié)構(gòu)圖

Meta tree 管理塊設(shè)備邏輯地址和物理地址的映射關(guān)系，支持系列元數(shù)據(jù)操作，如查詢、插入、更新、UNMAP.Meta tree 包括2 部分，為方便描述分別稱作Disk tree 和Memory tree，其 中Disk tree 為NAT B+tree 或IBT B+tree，本文評(píng)測(cè)中樹結(jié)點(diǎn)大小和數(shù)據(jù)塊大小均為4KB.

僅通過IBT B+tree 或者NAT B+tree 管理元數(shù)據(jù)，元數(shù)據(jù)下刷會(huì)阻塞I/O 回調(diào)時(shí)對(duì)元數(shù)據(jù)的修改，影響數(shù)據(jù)和元數(shù)據(jù)寫并發(fā)，無法評(píng)價(jià)元數(shù)據(jù)下刷對(duì)用戶I/O 的影響.因此，本文引入Memory tree，包括log0 tree和log1 tree，統(tǒng)稱為log tree.log tree 采用文獻(xiàn)[24]提出的基于lock-coupling 擴(kuò)展協(xié)議的B+tree，2 棵樹常駐內(nèi)存，僅記錄映射關(guān)系修改的log，用來聚合log（映射關(guān)系的修改，包括插入、更新、UNMAP）.2 棵樹交替使用，活躍log tree 處理元數(shù)據(jù)修改，非活躍log tree 進(jìn)行合并.Disk tree 需要下刷到物理設(shè)備，存儲(chǔ)所有映射關(guān)系.

log tree 功能需求有：

1）將上層寫I/O 對(duì)元數(shù)據(jù)的修改以log 的方式記錄下來，記錄的內(nèi)容為邏輯塊號(hào)和對(duì)映射關(guān)系的修改操作.

2）log tree 的內(nèi)存占用達(dá)到一定閾值或其他條件觸發(fā)下刷，如設(shè)備關(guān)閉、下刷超時(shí).Meta tree 下刷時(shí)需要遍歷log tree 中所有l(wèi)og 將映射關(guān)系的修改按照log 類型在Disk tree 上執(zhí)行相應(yīng)的樹操作.合并結(jié)束后，刪除log tree.

3）查詢操作時(shí)，先查詢log tree 再查詢Disk tree，因?yàn)樽钚碌挠成潢P(guān)系修改都記錄在log tree 中.

綜上，log tree 需要提供如下功能：插入、更新、遍歷.這些需求文獻(xiàn)[24]提出的B+tree 都可以滿足，且有著映射關(guān)系插入、查找可并發(fā)的優(yōu)點(diǎn).

通過Meta tree 管理元數(shù)據(jù)，解決B+tree 下刷時(shí)不能更新映射關(guān)系的問題，從而避免元數(shù)據(jù)下刷阻塞用戶I/O 請(qǐng)求，影響系統(tǒng)整體性能表現(xiàn)，同時(shí)也避免了I/O 上下文對(duì)元數(shù)據(jù)下刷的干擾.

4.3 Monty-Dev 系統(tǒng)layout

使用IBT B+tree 管理邏輯地址和物理地址的映射關(guān)系，則需要預(yù)留空間滿足第3 節(jié)中所述的2 階段提交下刷B+tree 的需求，以及存儲(chǔ)塊設(shè)備系統(tǒng)的必要信息.

使用NAT B+tree，則需要NAT 區(qū)域和Checkpoint區(qū)域：NAT 區(qū)域與F2FS 中NAT 區(qū)域的功能相同；Checkpoint 區(qū)域記錄NAT 塊的version bitmap.

5 測(cè)評(píng)與分析

本節(jié)基于第4 節(jié)提出的分別采用NAT B+tree 和IBT B+tree 管理元數(shù)據(jù)的2 個(gè)版本Monty-Dev 系統(tǒng)（為方便描述，后文分別稱作NAT 版本和IBT 版本）進(jìn)行評(píng)測(cè).本節(jié)主要通過Fio[25]和Filebench[26]進(jìn)行測(cè)試，以評(píng)價(jià)在不同負(fù)載下，NAT 版本和IBT 版本在元數(shù)據(jù)寫放大和下刷效率方面的差異.

5.1 測(cè)試環(huán)境

第5 節(jié)的相關(guān)測(cè)試均在表2 所示的測(cè)試環(huán)境上進(jìn)行.5.2 節(jié)和5.3 節(jié)的測(cè)試均分別在SSD 和HDD 上進(jìn)行測(cè)試，以驗(yàn)證IBT B+tree 在2 種介質(zhì)上的優(yōu)化效果.

Table 2 The Hardware Configuration of Testing Server表2 測(cè)試服務(wù)器硬件配置

測(cè)試的軟件環(huán)境如表3 所示.由于NAT 版本和IBT 版本的元數(shù)據(jù)構(gòu)成存在差異：NAT 版本的元數(shù)據(jù)包括NAT 塊和B+tree 樹結(jié)點(diǎn)，而IBT 版本僅包括B+tree 樹結(jié)點(diǎn).因此，NAT 版本和IBT 版本在相同測(cè)試用例下，元數(shù)據(jù)的下刷量可能存在差異.此外，NAT版本存在固定物理設(shè)備空間隨機(jī)寫的問題，而IBT版本不存在.因此，元數(shù)據(jù)下刷效率也可能存在差異.

Table 3 The Software Configuration of Testing Server表3 測(cè)試服務(wù)器軟件配置

5.2 Fio 測(cè)試

2 個(gè)版本的Monty-Dev 系統(tǒng)，采用精簡(jiǎn)配置設(shè)計(jì)，讀測(cè)試和讀寫混合測(cè)試均存在空讀的問題，且B+tree 樹結(jié)點(diǎn)均緩存在內(nèi)存中，IBT B+tree 和NAT B+tree 的查詢效率沒有差異，因此僅測(cè)試Fio 隨機(jī)寫.

Fio 測(cè)試的參數(shù)如表4 所示，以表4 中參數(shù)連續(xù)測(cè)試2 次，分別測(cè)試首次寫和覆蓋寫的吞吐率表現(xiàn)，測(cè)試3 次取平均值.由于Fio 隨機(jī)寫測(cè)試發(fā)送的I/O 請(qǐng)求為偽隨機(jī)請(qǐng)求序列，因此在參數(shù)不變的情況下每次Fio 測(cè)試的I/O 序列均相同.第2 輪測(cè)試即為覆蓋寫，覆蓋寫測(cè)試對(duì)于IBT B+tree 和NAT B+tree 而言均為插入更新操作.因此，該測(cè)試用例可先后評(píng)價(jià)NAT版本和IBT 版本在插入和插入更新場(chǎng)景下的差異.

Table 4 Fio Configuration Parameters表4 Fio 配置參數(shù)

Meta tree 合并下刷頻率受2 個(gè)因素制約：log tree內(nèi)存占用上限；B+tree 的dirty 樹結(jié)點(diǎn)內(nèi)存占用上限.其中，log tree 內(nèi)存占用上限越小，下刷頻率越高；dirty樹結(jié)點(diǎn)內(nèi)存占用上限影響一輪元數(shù)據(jù)下刷量，上限越小，一輪元數(shù)據(jù)下刷量越小，下刷越頻繁.因此，本文分別測(cè)試log tree 內(nèi)存占用上限為10 MB,20 MB,30 MB 的情況下，dirty 樹結(jié)點(diǎn)內(nèi)存占用上限為65 MB,85 MB,105 MB 時(shí)，NAT 版本和IBT 版本首次寫和覆蓋寫的吞吐率表現(xiàn)和元數(shù)據(jù)下刷的寫放大.下面分別在SSD 和HDD 上進(jìn)行測(cè)試分析.

由于NAT 版本和IBT 版本的有效元數(shù)據(jù)量相同，因此本節(jié)通過元數(shù)據(jù)下刷量評(píng)價(jià)元數(shù)據(jù)下刷寫放大.

5.2.1 基于SSD 的Fio 測(cè)試

Fio 測(cè)試中，首次寫和覆蓋寫的吞吐率、元數(shù)據(jù)下刷量對(duì)比如圖11 所示.觀察分析圖11，可得出4 個(gè)結(jié)論：

1）對(duì)于元數(shù)據(jù)下刷量，IBT 版本在大多數(shù)情況下均優(yōu)于NAT 版本，但差異很??；

2）log tree 內(nèi)存占用上限越大，元數(shù)據(jù)下刷量越??；

3）NAT 版本和IBT 版本，在覆蓋寫測(cè)試中l(wèi)og tree 內(nèi)存占用上限越大，吞吐率越大；

4）log tree 大小相同時(shí)，dirty 樹結(jié)點(diǎn)內(nèi)存占用上限對(duì)元數(shù)據(jù)下刷量影響很小.

對(duì)于第4 個(gè)結(jié)論，若在Meta tree 合并過程中，dirty 樹結(jié)點(diǎn)內(nèi)存占用超過上限，需要下刷后再合并剩余映射.由于log tree 將映射關(guān)系按照邏輯地址排序，下刷后再合并剩余映射時(shí)，不會(huì)修改已下刷葉子結(jié)點(diǎn)，但可能會(huì)修改部分已下刷的中間結(jié)點(diǎn).而中間結(jié)點(diǎn)總量較少，因此dirty 樹結(jié)點(diǎn)的內(nèi)存占用上限對(duì)元數(shù)據(jù)下刷量影響很小.

Fig.11 Comparison of throughput and the total amount of flushed metadata based on SSD圖11 基于SSD 的吞吐率、元數(shù)據(jù)下刷量對(duì)比

由于NAT 版本和IBT 版本B+tree 插入更新復(fù)雜度基本相同，因此只需要考慮Meta tree 合并下刷時(shí)的差異.由于吞吐率表現(xiàn)基本相同，因此NAT 版本和IBT 版本的元數(shù)據(jù)下刷效率對(duì)性能的影響基本相同.為此，本節(jié)主要通過分析元數(shù)據(jù)下刷量評(píng)價(jià)NAT版本和IBT 版本的元數(shù)據(jù)寫放大.表5 統(tǒng)計(jì)了圖11（a）中，dirty 樹結(jié)點(diǎn)內(nèi)存占用上限為85 MB 時(shí)，2 輪測(cè)試期間的元數(shù)據(jù)下刷量.

Table 5 Total Amount of 2 Versions Flushed Metadata Under Fio Test Based on SSD表5 基于SSD 的Fio 測(cè)試中2 個(gè)版本元數(shù)據(jù)下刷總量GB

從表5 可以看出，IBT 版本的元數(shù)據(jù)下刷量略低于NAT 版本，但NAT B+tree 下刷時(shí)存在非順序?qū)?NAT 版本的元數(shù)據(jù)包括NAT 塊和B+tree 樹結(jié)點(diǎn)，NAT 塊下刷的物理設(shè)備訪問模式為固定物理設(shè)備空間的非順序?qū)?，而?shù)據(jù)寫為順序?qū)?，NAT 塊和數(shù)據(jù)可并發(fā)寫.2 輪測(cè)試中NAT 塊下刷情況如表6 所示.

Table 6 Statistics of Flushed NAT Block Under Fio Test Based on SSD表6 基于SSD 的Fio 測(cè)試中NAT 塊下刷統(tǒng)計(jì)

覆蓋寫測(cè)試中NAT 塊的寫入量和比例都有所增加.主要原因是B+tree 樹結(jié)點(diǎn)總量增多，導(dǎo)致NAT塊總數(shù)增多，隨機(jī)修改NAT 塊的范圍增大.但由于NAT 塊寫相對(duì)于順序?qū)懙谋壤^小，對(duì)用戶數(shù)據(jù)寫性能影響較小，所以NAT 版本和IBT 版本的吞吐率差異很小.然而，隨機(jī)寫會(huì)導(dǎo)致閃存塊碎片增多，降低閃存性能和壽命，這在短期測(cè)試中不能體現(xiàn)出來.

NAT B+tree 下刷需要下刷葉子結(jié)點(diǎn)和NAT 塊，IBT B+tree 對(duì)于狀態(tài)為dirty 的葉子結(jié)點(diǎn)，其查詢路徑上所有的祖先結(jié)點(diǎn)一定為dirty，而IBT 版本的元數(shù)據(jù)下刷量小于NAT 版本.因此，IBT 版本雖然理論上存在一定的寫放大，但由于NAT 塊的寫開銷，IBT版本實(shí)際表現(xiàn)與NAT 版本相當(dāng)或優(yōu)于NAT 版本.

5.2.2 基于HDD 的Fio 測(cè)試

Fio 測(cè)試經(jīng)過首次寫和覆蓋寫2 輪測(cè)試后，吞吐率、元數(shù)據(jù)下刷量對(duì)比如圖12 所示.觀察分析圖12，可得出5 個(gè)結(jié)論：

1）對(duì)于元數(shù)據(jù)下刷量，IBT 版本在大多數(shù)情況下均優(yōu)于NAT 版本；

2）對(duì)于吞吐率，相對(duì)于NAT 版本，IBT 版本首次寫提升4.7%～13.8%，覆蓋寫提升10.7%～20.3%，內(nèi)存占用越少提升越大；

3）IBT 版本吞吐率表現(xiàn)幾乎不受dirty 樹結(jié)點(diǎn)內(nèi)存占用上限影響，而NAT 版本受影響較大，特別是圖12（b）；

4）log tree 內(nèi)存占用上限越大，吞吐率越大；

5）log tree 內(nèi)存占用上限相同，大多數(shù)情況下，dirty 樹結(jié)點(diǎn)內(nèi)存占用上限越大，元數(shù)據(jù)下刷量越小.

Fig.12 Comparison of throughput and the total amount of flushed metadata based on HDD圖12 基于HDD 的吞吐率、元數(shù)據(jù)下刷量對(duì)比

以圖12（a）dirty 樹結(jié)點(diǎn)內(nèi)存占用上限為85MB 為例，分析元數(shù)據(jù)下刷與吞吐率的關(guān)系.相對(duì)于NAT 版本，IBT 版本2 輪測(cè)試吞吐率提升分別為9.3%和15.3%.相較于5.2.1 節(jié)中基于SSD 的測(cè)試，提升比例更高.同5.2.1 節(jié)，需要關(guān)注Meta tree 合并下刷對(duì)性能造成的影響.2 輪測(cè)試期間元數(shù)據(jù)下刷量如表7 所示.

IBT 版本比NAT 版本元數(shù)據(jù)下刷量略小，但由于NAT 塊下刷不是順序?qū)懀襀DD 的吞吐率受I/O連續(xù)度的影響較SSD 更大，少量的非順序?qū)懸矔?huì)造成磁頭的抖動(dòng)，因此導(dǎo)致吞吐率提升比例更大.表8中展示了2 輪測(cè)試中NAT 塊下刷情況.

Table 7 Total Amount of 2 Versions Flushed Metadata Under Fio Test Based on HDD表7 基于HDD 的Fio 測(cè)試中2 個(gè)版本元數(shù)據(jù)下刷總量GB

Table 8 Statistics of Flushed NAT Block Under Fio Test Based on HDD表8 基于HDD 的Fio 測(cè)試中NAT 塊下刷統(tǒng)計(jì)

如表8 所示，覆蓋寫測(cè)試中NAT 塊的寫入量和比例都增加了，從而導(dǎo)致固定位置非順序?qū)懻?qǐng)求增多.IBT B+tree 葉子結(jié)點(diǎn)需要下刷，其父親結(jié)點(diǎn)必須下刷，對(duì)于局部性比較好的樹操作，多個(gè)被修改的葉子結(jié)點(diǎn)可能有相同的祖先結(jié)點(diǎn).而NAT 塊的設(shè)計(jì)不確保1 個(gè)塊涵蓋的多個(gè)樹結(jié)點(diǎn)在一輪元數(shù)據(jù)下刷時(shí)同時(shí)下刷，所以局部性較好的樹操作不一定能減少NAT 塊的下刷量.

綜上，IBT B+tree 的設(shè)計(jì)能夠更好地利用空間局部性降低元數(shù)據(jù)的下刷量，避免隨機(jī)訪問提升元數(shù)據(jù)的下刷效率.NAT 版本，B+tree 樹結(jié)點(diǎn)總量越多，更新NAT 塊越多，寫放大越嚴(yán)重，增加HDD 尋道時(shí)間從而降低系統(tǒng)吞吐率.因此，IBT 版本在元數(shù)據(jù)寫放大和下刷效率方面的表現(xiàn)均優(yōu)于NAT 版本.

5.3 Filebench 測(cè)試

為避免空讀，測(cè)試查詢、插入、更新、刪除操作的綜合性能，使用Filebench 進(jìn)行測(cè)試，該組測(cè)試主要選取varmail,fileserver 這2 個(gè)負(fù)載.為充分測(cè)試對(duì)比IBT B+tree 和NAT B+tree 的綜合性能，同時(shí)適配當(dāng)前服務(wù)器環(huán)境，對(duì)Filebench 中標(biāo)準(zhǔn)wml 腳本的測(cè)試時(shí)間、線程數(shù)、文件大小、文件數(shù)量均作了修改.這些負(fù)載均首先分配一個(gè)文件集合，2 類負(fù)載的行為如下：

1）varmail，模擬郵件服務(wù)器的I/O 負(fù)載，該負(fù)載多線程執(zhí)行相同任務(wù).順序執(zhí)行刪除、創(chuàng)建—追加—同步、讀—追加—同步、讀操作.

2）fileserver，模擬文件服務(wù)器上的I/O 負(fù)載，該負(fù)載多線程執(zhí)行相同任務(wù).順序創(chuàng)建、寫整個(gè)文件、追加寫、讀整個(gè)文件、刪除文件、查看文件狀態(tài).

測(cè)試方法為：分別基于HDD 和SSD 創(chuàng)建4TB 的Monty-Dev 設(shè)備，格式化為ext4 文件系統(tǒng)，使用discard選項(xiàng)掛載文件系統(tǒng)以測(cè)試B+tree 的刪除操作，每類負(fù)載執(zhí)行1 h，每個(gè)測(cè)試執(zhí)行3 次，結(jié)果取平均值.

5.3.1 基于SSD 的Filebench 測(cè)試

Filebench 測(cè)試結(jié)果，IBT 版本和NAT 版本基 本相同，差異較小.主要原因有：文件系統(tǒng)并不會(huì)將寫請(qǐng)求直接轉(zhuǎn)發(fā)至底層設(shè)備，設(shè)備利用率低；文件系統(tǒng)下發(fā)的寫請(qǐng)求基本為順序?qū)懀? 個(gè)版本差異較小.因此，本節(jié)及5.3.2 節(jié)主要通過元數(shù)據(jù)下刷量評(píng)價(jià)IBT版本和NAT 版本.由于Filebench 測(cè)試按照指定時(shí)長(zhǎng)進(jìn)行測(cè)試，不同測(cè)試中Monty-Dev 設(shè)備收到的I/O 請(qǐng)求數(shù)量存在差異，因此，本節(jié)及5.3.2 節(jié)使用元數(shù)據(jù)下刷比例指標(biāo)評(píng)價(jià)元數(shù)據(jù)的寫放大情況：

通過式（1）的計(jì)算方法，計(jì)算結(jié)果如圖13 所示.

Fig.13 Comparison of Filebench test based on SSD圖13 基于SSD 的Filebench 測(cè)試對(duì)比

相對(duì)于NAT 版本，IBT 版本在varmail 負(fù)載和fileserver 負(fù)載測(cè)試中，元數(shù)據(jù)下刷比例分別減少0.67%和0.69%.經(jīng)統(tǒng)計(jì)，若元數(shù)據(jù)寫比例僅統(tǒng)計(jì)樹結(jié)點(diǎn)下刷量，則2 類負(fù)載測(cè)試中IBT 版本均大于NAT版本，該現(xiàn)象符合IBT 版本和NAT 版本設(shè)計(jì)的差異.因此，導(dǎo)致NAT 版本元數(shù)據(jù)下刷比例高的主要原因是NAT 塊下刷的開銷大.接下來，具體分析NAT 版本元數(shù)據(jù)下刷量的組成.

如表9 所示，NAT 塊下刷量占元數(shù)據(jù)下刷比例較表6 所示的更高.較Fio 負(fù)載，F(xiàn)ilebench 負(fù)載支持discard I/O 請(qǐng)求，系列刪除操作完成后，一些樹結(jié)點(diǎn)需要被釋放，釋放樹結(jié)點(diǎn)需要將NAT 塊中的記錄更新為無效映射.經(jīng)統(tǒng)計(jì)，varmail 和fileserver 負(fù)載測(cè)試中discard I/O 占寫I/O 請(qǐng)求的比例分別為81.5%和76%.因此，刪除操作會(huì)嚴(yán)重影響NAT 版本的NAT塊下刷量，從而影響元數(shù)據(jù)下刷比例，導(dǎo)致NAT 版本寫放大更加嚴(yán)重.

Table 9 Statistics of Flushed NAT Block for Different Loads Under Filebench Test Based on SSD表9 基于SSD 的Filebench 測(cè)試不同負(fù)載NAT 塊下刷統(tǒng)計(jì)

5.3.2 基于HDD 的Filebench 測(cè)試

評(píng)價(jià)方法與SSD 上測(cè)試相同，元數(shù)據(jù)下刷比例對(duì)比結(jié)果如圖14 所示.

Fig.14 Comparison of Filebench test based on HDD圖14 基于HDD 的Filebench 測(cè)試對(duì)比

相對(duì)于NAT 版本，IBT 版本在varmail 負(fù)載和fileserver 負(fù)載測(cè)試中，元數(shù)據(jù)下刷比例分別減少0.11%和0.19%.HDD 上IBT 版本降低比例較SSD 上測(cè)試低的主要原因是：Filebench 測(cè)試預(yù)先寫入的數(shù)據(jù)量相同，HDD 上測(cè)試varmail 負(fù)載和fileserver 負(fù)載分別比SSD 上測(cè)試執(zhí)行的操作數(shù)少約92%和86%.根據(jù)5.3.1 節(jié)分析，刪除操作是造成元數(shù)據(jù)下刷量差異的主要原因.經(jīng)統(tǒng)計(jì)，varmail 和fileserver 負(fù)載測(cè)試中discard I/O 占寫I/O 請(qǐng)求的比例分別為26%和32.2%，均低于SSD 上的測(cè)試結(jié)果.造成discard I/O 比例低的主要原因是：discard I/O 操作元數(shù)據(jù)處理開銷較大，HDD 上處理較SSD 慢，在測(cè)試結(jié)束后，ext4 文件系統(tǒng)仍然在發(fā)送discard I/O.因此，造成HDD 上測(cè)試IBT 版本元數(shù)據(jù)下刷比例降低的主要因素也是刪除操作，造成降低比例較SSD 測(cè)試低的原因是刪除操作比例較低.

NAT 塊下刷量相對(duì)于元數(shù)據(jù)下刷量的比例如表10所示.discard I/O 占比的差異與NAT 塊占比為正相關(guān).綜上，在元數(shù)據(jù)寫放大方面，相對(duì)于NAT 版本，IBT版本在刪除操作中的表現(xiàn)也更優(yōu).

綜上，進(jìn)行了Fio 測(cè)試和Filebench 測(cè)試，IBT 版本相對(duì)于NAT 版本：在HDD 上的吞吐率和元數(shù)據(jù)下刷寫放大方面，較SSD 上的優(yōu)化效果更顯著；在處理大規(guī)模隨機(jī)更新和刪除操作時(shí)，開銷更小.

Table 10 Statistics of Flushed NAT Block for Different Loads Under Filebench Test Based on HDD表10 基于HDD 的Filebench 測(cè)試不同負(fù)載NAT 塊下刷統(tǒng)計(jì)

6 總結(jié)

本文主要研究了使用B+tree 管理日志結(jié)構(gòu)塊存儲(chǔ)系統(tǒng)的地址映射面臨的wandering B+tree 問題.B+tree 具有扇出大、綜合效率高的優(yōu)點(diǎn)，被廣泛應(yīng)用于各類存儲(chǔ)系統(tǒng)中.對(duì)于日志結(jié)構(gòu)塊存儲(chǔ)系統(tǒng)，使用B+tree 管理邏輯地址和物理地址的映射需要解決：支持樹結(jié)點(diǎn)下刷方式為異地寫，并避免遞歸更新B+tree樹結(jié)構(gòu).本文從樹結(jié)構(gòu)和樹操作設(shè)計(jì)的角度出發(fā)，提出了IBT B+tree，將樹結(jié)點(diǎn)物理地址嵌入樹結(jié)構(gòu)的設(shè)計(jì)，引入dirty 鏈表設(shè)計(jì)，定義IBT B+tree 插入、刪除操作，并提出了非遞歸更新算法，既解決了wandering B+tree 問題，又不引入額外的數(shù)據(jù)結(jié)構(gòu)和固定物理設(shè)備空間.設(shè)計(jì)實(shí)現(xiàn)塊設(shè)備存儲(chǔ)系統(tǒng)Monty-Dev，將IBT B+tree 與NAT B+tree 進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明在不同的負(fù)載下IBT B+tree 的寫放大表現(xiàn)與NAT B+tree 相當(dāng)或更優(yōu)，下刷效率更高.IBT B+tree 可應(yīng)用于日志結(jié)構(gòu)塊設(shè)備系統(tǒng)，如ASD 系統(tǒng)；也可應(yīng)用于日志結(jié)構(gòu)文件系統(tǒng)管理文件的地址映射，如NILFS2 文件系統(tǒng).

作者貢獻(xiàn)聲明：楊勇鵬負(fù)責(zé)論文撰寫、部分實(shí)驗(yàn)方案設(shè)計(jì)、實(shí)驗(yàn)執(zhí)行和論文修訂；蔣德鈞負(fù)責(zé)部分實(shí)驗(yàn)方案設(shè)計(jì)和論文修訂.