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

楊勇鵬 蔣德鈞

（中國科學院計算技術研究所 北京 100190）

（中國科學院大學 北京 100049）

隨著大數據時代的到來和發展，數據量呈現爆炸式增長.根據IDC（International Data Corporation）的預測，全球數據領域將從2018 年的33ZB 增長到2025 年的175ZB[1].為了滿足數據存儲的需求，數據存儲系統的規模和存儲介質的容量都在不斷地增長.各大存儲設備廠商紛紛推出大容量存儲設備來滿足大量數據存儲的需求.例如，西部數據已經推出單盤容量達18TB 的機械硬盤（hard disk drive，HDD）[2]，和單盤容量達20TB 的瓦記錄磁盤（shingled write disk，SWD）[3].存儲廠商Nimbus Data 推出單盤最大容量高達100TB 的固態硬盤（solid state disk，SSD）[4].

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

對于SSD，文獻[7-8]的研究表明：頻繁地隨機寫請求處理，會導致嚴重的內部碎片，影響SSD 的持續性能表現.SFS[9]研究發現：SSD 的隨機寫帶寬和順序寫帶寬的差異超過10 倍；隨機寫會增加單位寫請求的閃存塊平均擦除次數，從而減少SSD 的使用壽命.為解決上述問題，SFS 以NILFS 為基礎針對閃存介質特性，實現新的文件系統，提升系統吞吐率，降低閃存塊平均擦除次數，減少SSD 元數據管理開銷，從而提升SSD 壽命.

近年來，業界又先后推出了JFFS[10]，F2FS[11-14]等日志結構文件系統.除了文件系統外，日志結構技術還被應用于塊存儲系統，例如BW-RAID[15]存儲系統的ASD 子系統[16-17]，ASD 系統向上提供標準塊設備接口，將上層寫請求轉換為本地磁盤RAID 的順序寫，以提升BW-RAID 系統的吞吐率.本文把這類系統統稱為日志結構存儲系統.

雖然日志結構存儲系統可以將所有的寫請求轉換為順序寫，但是因為日志結構存儲系統要求數據和元數據的修改都采用異地更新的方式，它面臨元數據異地更新帶來的連鎖更新問題.樹狀結構通常被用于保存元數據，例如B+tree，RB-tree（red-black tree），而一旦樹狀結構的某個結點執行了異地更新，就會觸發遞歸更新樹狀結構，這一問題通常被稱作wandering tree 問 題[18].因 為B+tree 被廣泛 應用于 存儲系統中，所以本文主要關注wandering B+tree 問題.

針對wandering tree 問題，現有日志結構存儲系統均提出了各自的解決方法：例如，NILFS2[19]使用B+tree 管理所有元數據，引入特殊的內部文件DAT（data address translation file）管理所有B+tree 樹結點；DAT 文件的每個數據塊為B+tree 的樹結點，在文件內的偏移作為B+tree 樹結點的邏輯索引（用于索引在內存中的樹結點）.但是，DAT 文件的地址映射關系仍然使用B+tree 維護，以此保存邏輯索引和物理地址的映射（元數據塊和數據塊在物理設備上的地址），因此當DAT 文件更新時，DAT 文件的映射管理仍然面臨wandering B+tree 的問題.

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

綜上，上述系統均使用額外的數據結構和物理設備空間管理樹結點邏輯索引和物理地址的映射，以此解決元數據管理的wandering tree 問題.但引入額外的數據結構和物理設備空間，會增加系統設計的復雜度、降低寫物理設備的連續度.

采用日志結構設計的文件系統和塊設備系統在業界均有廣泛的應用，然而針對大容量塊存儲系統，若采用高扇出、樹操作效率高的B+tree 管理塊設備邏輯地址和物理地址的映射關系，則需要解決wandering B+tree 問題，現有的塊設備解決方法及日志結構文件系統的解決方法均需要引入額外的數據結構和物理設備空間.為解決wandering B+tree 問題，本文提出IBT（internal node based translation）B+tree.本文的主要貢獻有3 個方面：

1）提出IBT B+tree 樹結構.中間結點記錄孩子結點的邏輯索引和物理地址，避免引入額外數據結構和物理設備空間.

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

3）設計實現Monty-Dev 塊存儲系統，評價IBT B+tree 在寫放大和下刷效率方面的優化效果.

1 相關工作

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

日志結構存儲系統要求樹結點的更新方式為異地寫，且為寫時分配物理地址.如果樹結點邏輯索引和物理地址相同，則在樹結點下刷時需要遞歸更新祖先結點中記錄的孩子結點物理地址，因此存在wandering tree 問題.本節分別介紹NILFS2，F2FS，ASD系統針對wandering tree 問題的解決方法.

1.1 NILFS2

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

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

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

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

圖1（a）中樹結點修改下刷只需要修改DAT 文件，無需遞歸更新圖1（a）；而圖1（b）中樹結點修改下刷時，仍然需要遞歸更新.

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

1.2 F2FS

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

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

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

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

隨著設備的增大，文件系統的元數據量也在增大，因此NAT 區域就需要管理更多的NAT 塊.但NAT 的隨機修改會導致嚴重的寫放大，為解決該問題，引入了journal 的設計，將最近對NAT 的修改記錄在CP 區域中，journal 無可用空間時再更新NAT 并下刷.

綜上，F2FS 采用NAT 和journal 的設計解決了wandering tree 問題.但NAT 設計無法利用負載的空間局部性，隨著NAT 空間的增大，寫放大問題會更嚴重，且物理設備的訪問模式不是順序寫.

1.3 ASD

ASD 系統提供Linux 標準塊設備語義，以虛擬塊設備（virtual device，VD）的形式提供存儲服務.ASD系統在物理設備之上創建一個日志結構存儲池，存儲池之上有多個邏輯地址空間，每個邏輯地址空間對應一個虛擬塊設備VD，每個VD 向上提供存儲服務.對于塊設備，最重要的元數據信息是邏輯地址和物理地址的映射關系.

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

Fig.3 ASD system metadata structure [16-17]圖3 ASD 系統元數據結構[16-17]

上述Extent，Subtree，Group 結構均采用RB-tree進行組織，每個Group 在內存中索引多個Extent.對于Group 信息的下刷，需要先調整樹結構，使得一個Group 索引到的Extent 信息可以記錄到物理設備上一個定長的數據塊中，Group 的下刷方式為異地寫.因此，ASD 也存在wandering tree 的問題，ASD 的解決方法是：

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

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

3）系統重啟時通過掃描固定區域重構RB-tree.

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

2 wandering B+tree 問題分析和結構設計

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

2.1 wandering B+tree 問題分析

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

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

綜上，要解決wandering B+tree，需要滿足日志結構系統設計需求：樹結點寫時分配物理地址，且更新方式為異地寫；同時，避免B+tree 樹結點下刷時遞歸更新非葉子結點.

如第1 節所述，針對wandering tree 問題，NILFS2,F2FS,ASD 解決方法的共同點是：樹結點邏輯索引和物理地址不同，即樹結點的邏輯索引和物理地址分離，額外的數據結構和物理設備空間維護樹結點邏輯索引和物理地址的映射關系.

因此，解決wandering B+tree 問題的難點是：

1）支持樹結點邏輯索引和物理地址分離，且不引入新的數據結構和物理設備空間，降低復雜度；

2）避免B+tree 下刷時遞歸更新樹結構.

針對這2 個難點，2.2 節提出第1 個難點的解決方法，2.3 節和2.4 節支撐第3 節提出的IBT B+tree 下刷算法解決第2 個難點.

2.2 IBT B+tree 樹結點布局

IBT B+tree 的中間結點和葉子結點結構圖如圖5所示，圖5 中各字段的含義如表1 所示.接下來，分別介紹表1 中各字段的用途.

Fig.5 The internal node and leaf node of IBT B+tree圖5 IBT B+tree 中間結點和葉子結點

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

1）state字段為孩子結點的狀態，dirty 代表孩子結點需要持久化到物理設備，clean 代表孩子結點已經持久化且可以在內存緊張時回收.因此，state僅描述內存中的樹結點內容是否與設備上的一致.

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

3）中間結點記錄孩子結點的index和pbid，在內存中的B+tree 樹結點，以index為關鍵字，使用紅黑樹進行組織.各類B+tree 操作執行過程中，如果樹結點不在紅黑樹中，則需要通過pbid從底層設備讀取樹結點.

2.3 IBT B+tree 鏈表設計

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

擴展并修改B+tree 鏈表維護方法.傳統B+tree只維護葉子結點鏈表，用來管理所有葉子結點，按照關鍵字升序或降序排列.本文修改并擴展樹結點鏈表：B+tree 的每一層均有一個dirty 鏈表；引入全局clean 鏈表.2 類鏈表設計主要有2 個特點：

1）B+tree 各層dirty 鏈表管理相應層中狀態為dirty 的樹結點，dirty 樹結點按照LRU 的方式管理，而非按照關鍵字排序；

2）clean 鏈表管理所有狀態為clean 的樹結點，clean 鏈表也采用LRU 的方式管理，目的是為了在內存緊張時釋放不經常訪問的樹結點.

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

2.4 IBT B+tree 基本操作設計

B+tree 在插入、查找、刪除操作中對key-value的管理，與采用shadow-clone 設計的B+tree[20-21]沒有差異.為使用lock-coupling 細粒度加鎖協議支持B+tree 并發操作[22]，B+tree 采用預先rebalance、分裂的方式調整樹結構，避免B+tree 樹操作執行過程中對孩子結點的修改導致父親結點rebalance、分裂.

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

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

2.4.1 插入操作

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

1）初始狀態如圖6（a）所示，所有樹結點狀態均為clean.

2）圖6（b）將結點R標記為dirty，并將結點R插入list[0]；由于結點R的key-value 數量達到上限，因此需要分裂結點R，分配D和E這2 個結點.將結點R的key-value 平均分配給結點D和E.將結點D和E中記錄的最小key 與結點D和E的邏輯索引分別作為key 和value 插入到結點R中.此時不需要為結點D和E分配物理地址.樹高加1，相應地調整鏈表.

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

如圖6（b）所示，新創建的鏈表為B+tree 的第2 層.因為除樹根結點外，B+tree 其他任何層都可能存在兄弟結點，為降低B+tree 樹操作復雜度，僅允許樹根結點分裂出孩子結點.綜上，新插入的dirty 鏈表只發生在第2 層，這一特性適用于任何高度大于1的B+tree.

圖6 所示的每個階段操作過程中，都將所有需要訪問的樹結點狀態標識為dirty，同時除樹根結點外，將所有dirty 樹結點在其父親結點中的狀態標識為dirty.

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

由于dirty 鏈表的引入，2 個并發的插入操作①和②，①先執行，②后執行；如果插入②導致樹高加1，①獲得的樹高信息不正確，則樹結點可能插入錯誤的鏈表.因此，B+tree 無法支持插入和插入的并發.由于clean 鏈表對樹高不敏感，B+tree 仍可支持插入和查找操作并發執行.

2.4.2 刪除操作

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

1）訪問樹根結點R，將結點R標記為dirty，并加入到dirty 鏈表list[0]中.

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

3）圖7（c）和圖7（d），逐級向下訪問到結點A，將〈10,11〉從結點A中刪除.

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

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

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

3 IBT B+tree 下刷

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

B+tree 下刷存在2 種情況：下刷所有樹結點，包括B+tree 創建完成并插入多次關鍵字之后的狀態和B+tree 非首次下刷且所有樹結點狀態均為dirty；部分下刷，包括部分B+tree 樹結點為dirty 的情況和經過多次刪除后B+tree 為空.

多次插入、刪除操作后，dirty 樹結點的內存占用或下刷時間間隔達到一定閾值，需要將B+tree 所有狀態為dirty 的樹結點下刷到物理設備.

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

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

1）根據該dirty 鏈表上所有樹結點，下刷該樹結點所有狀態為dirty 的孩子；

2）為孩子結點分配物理地址并下刷，將孩子結點的物理地址記錄到父結點中，并更新父結點中記錄的狀態.

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

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

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

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

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

2）如圖8（a）所示，對于list[1]的結點D，調用函數flush_dirty_nodes，結點D只有一個狀態為dirty 的孩子結點A.因此，如圖8（b）所示，為結點A分配物理地址并記錄在結點D中，同時將結點D中記錄的結點A狀態標更新為clean.同樣的方式處理list[1]上所有樹結點.

3）圖8（c）下刷list[0]，為結點D和E分配物理地址并下刷.至此，函數flush_dirty_lists執行完成.

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

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

4 IBT B+tree 評價系統設計實現

本文以日志結構塊設備系統為背景，在第2 節和第3 節提出了IBT B+tree，解決了wandering B+tree問題.但是，僅有IBT B+tree 只可進行樹操作測試，難以測試在不同負載下的表現.

Fig.8 Flush dirty node of IBT B+tree圖8 下刷IBT B+tree 的dirty 結點

為全面評價IBT B+tree 在Fio 和Filebench 場景下的寫放大和下刷效率表現，需要設計實現能夠覆蓋IBT B+tree 支持的各類樹操作和下刷，且避免I/O上下文干擾的日志結構塊存儲系統Monty-Dev.

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

本文以Linux 系統為平臺，設計實現Linux 內核標準塊設備Monty-Dev 系統.下面分別介紹評價系統Monty-Dev 的總體設計、元數據管理和系統layout.

4.1 Monty-Dev 系統整體架構

該設計暫不考慮宕機恢復和下刷數據塊的反向映射信息，B+tree 樹結點和NAT 塊均緩存在內存中，本文聚焦寫放大和固定物理設備空間非順序寫開銷的評價.為評價刪除操作的影響，Monty-Dev 系統支持Linux 內核中通用塊層的Discard I/O 語義.

Monty-Dev 系統總體架構如圖9 所示.使用橫向的虛線標識系統的分層，下面逐層介紹.“用戶接口”用來管理Monty-Dev 系統，比如創建、刪除設備和修改系統配置等.其他系統可通過“標準塊設備接口”，直接向Monty-Dev 提交讀寫I/O 請求.ext4/xfs 等文件系統實例，可向通用塊層提交讀寫I/O、Discard I/O 請求，Discard I/O 用來支持文件系統的trim 操作.

Fig.9 Architecture of Monty-Dev system圖9 Monty-Dev 系統整體架構

Monty-Dev 核心模塊實現了通用塊層的部分接口，處理上層發往通用塊層的請求.基于Monty-Dev系統可執行Fio 測試，將Monty-Dev 設備格式化為特定文件系統可支持Filebench 測試.

因此，通過Monty-Dev 系統測試Fio 和Filebench負載，可覆蓋B+tree 的查找、插入、刪除操作及其并發，以及元數據下刷.

4.2 元數據管理模塊

Monty-Dev 的元數據管理模塊結構圖如圖10 所示，后文稱作Meta tree.

Fig.10 Structure diagram of Meta tree圖10 Meta tree 結構圖

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

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

log tree 功能需求有：

1）將上層寫I/O 對元數據的修改以log 的方式記錄下來，記錄的內容為邏輯塊號和對映射關系的修改操作.

2）log tree 的內存占用達到一定閾值或其他條件觸發下刷，如設備關閉、下刷超時.Meta tree 下刷時需要遍歷log tree 中所有log 將映射關系的修改按照log 類型在Disk tree 上執行相應的樹操作.合并結束后，刪除log tree.

3）查詢操作時，先查詢log tree 再查詢Disk tree，因為最新的映射關系修改都記錄在log tree 中.

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

通過Meta tree 管理元數據，解決B+tree 下刷時不能更新映射關系的問題，從而避免元數據下刷阻塞用戶I/O 請求，影響系統整體性能表現，同時也避免了I/O 上下文對元數據下刷的干擾.

4.3 Monty-Dev 系統layout

使用IBT B+tree 管理邏輯地址和物理地址的映射關系，則需要預留空間滿足第3 節中所述的2 階段提交下刷B+tree 的需求，以及存儲塊設備系統的必要信息.

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

5 測評與分析

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

5.1 測試環境

第5 節的相關測試均在表2 所示的測試環境上進行.5.2 節和5.3 節的測試均分別在SSD 和HDD 上進行測試，以驗證IBT B+tree 在2 種介質上的優化效果.

Table 2 The Hardware Configuration of Testing Server表2 測試服務器硬件配置

測試的軟件環境如表3 所示.由于NAT 版本和IBT 版本的元數據構成存在差異：NAT 版本的元數據包括NAT 塊和B+tree 樹結點，而IBT 版本僅包括B+tree 樹結點.因此，NAT 版本和IBT 版本在相同測試用例下，元數據的下刷量可能存在差異.此外，NAT版本存在固定物理設備空間隨機寫的問題，而IBT版本不存在.因此，元數據下刷效率也可能存在差異.

Table 3 The Software Configuration of Testing Server表3 測試服務器軟件配置

5.2 Fio 測試

2 個版本的Monty-Dev 系統，采用精簡配置設計，讀測試和讀寫混合測試均存在空讀的問題，且B+tree 樹結點均緩存在內存中，IBT B+tree 和NAT B+tree 的查詢效率沒有差異，因此僅測試Fio 隨機寫.

Fio 測試的參數如表4 所示，以表4 中參數連續測試2 次，分別測試首次寫和覆蓋寫的吞吐率表現，測試3 次取平均值.由于Fio 隨機寫測試發送的I/O 請求為偽隨機請求序列，因此在參數不變的情況下每次Fio 測試的I/O 序列均相同.第2 輪測試即為覆蓋寫，覆蓋寫測試對于IBT B+tree 和NAT B+tree 而言均為插入更新操作.因此，該測試用例可先后評價NAT版本和IBT 版本在插入和插入更新場景下的差異.

Table 4 Fio Configuration Parameters表4 Fio 配置參數

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

由于NAT 版本和IBT 版本的有效元數據量相同，因此本節通過元數據下刷量評價元數據下刷寫放大.

5.2.1 基于SSD 的Fio 測試

Fio 測試中，首次寫和覆蓋寫的吞吐率、元數據下刷量對比如圖11 所示.觀察分析圖11，可得出4 個結論：

1）對于元數據下刷量，IBT 版本在大多數情況下均優于NAT 版本，但差異很小；

2）log tree 內存占用上限越大，元數據下刷量越小；

3）NAT 版本和IBT 版本，在覆蓋寫測試中log tree 內存占用上限越大，吞吐率越大；

4）log tree 大小相同時，dirty 樹結點內存占用上限對元數據下刷量影響很小.

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

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

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

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

從表5 可以看出，IBT 版本的元數據下刷量略低于NAT 版本，但NAT B+tree 下刷時存在非順序寫.NAT 版本的元數據包括NAT 塊和B+tree 樹結點，NAT 塊下刷的物理設備訪問模式為固定物理設備空間的非順序寫，而數據寫為順序寫，NAT 塊和數據可并發寫.2 輪測試中NAT 塊下刷情況如表6 所示.

Table 6 Statistics of Flushed NAT Block Under Fio Test Based on SSD表6 基于SSD 的Fio 測試中NAT 塊下刷統計

覆蓋寫測試中NAT 塊的寫入量和比例都有所增加.主要原因是B+tree 樹結點總量增多，導致NAT塊總數增多，隨機修改NAT 塊的范圍增大.但由于NAT 塊寫相對于順序寫的比例較小，對用戶數據寫性能影響較小，所以NAT 版本和IBT 版本的吞吐率差異很小.然而，隨機寫會導致閃存塊碎片增多，降低閃存性能和壽命，這在短期測試中不能體現出來.

NAT B+tree 下刷需要下刷葉子結點和NAT 塊，IBT B+tree 對于狀態為dirty 的葉子結點，其查詢路徑上所有的祖先結點一定為dirty，而IBT 版本的元數據下刷量小于NAT 版本.因此，IBT 版本雖然理論上存在一定的寫放大，但由于NAT 塊的寫開銷，IBT版本實際表現與NAT 版本相當或優于NAT 版本.

5.2.2 基于HDD 的Fio 測試

Fio 測試經過首次寫和覆蓋寫2 輪測試后，吞吐率、元數據下刷量對比如圖12 所示.觀察分析圖12，可得出5 個結論：

1）對于元數據下刷量，IBT 版本在大多數情況下均優于NAT 版本；

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

3）IBT 版本吞吐率表現幾乎不受dirty 樹結點內存占用上限影響，而NAT 版本受影響較大，特別是圖12（b）；

4）log tree 內存占用上限越大，吞吐率越大；

5）log tree 內存占用上限相同，大多數情況下，dirty 樹結點內存占用上限越大，元數據下刷量越小.

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

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

IBT 版本比NAT 版本元數據下刷量略小，但由于NAT 塊下刷不是順序寫，且HDD 的吞吐率受I/O連續度的影響較SSD 更大，少量的非順序寫也會造成磁頭的抖動，因此導致吞吐率提升比例更大.表8中展示了2 輪測試中NAT 塊下刷情況.

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

Table 8 Statistics of Flushed NAT Block Under Fio Test Based on HDD表8 基于HDD 的Fio 測試中NAT 塊下刷統計

如表8 所示，覆蓋寫測試中NAT 塊的寫入量和比例都增加了，從而導致固定位置非順序寫請求增多.IBT B+tree 葉子結點需要下刷，其父親結點必須下刷，對于局部性比較好的樹操作，多個被修改的葉子結點可能有相同的祖先結點.而NAT 塊的設計不確保1 個塊涵蓋的多個樹結點在一輪元數據下刷時同時下刷，所以局部性較好的樹操作不一定能減少NAT 塊的下刷量.

綜上，IBT B+tree 的設計能夠更好地利用空間局部性降低元數據的下刷量，避免隨機訪問提升元數據的下刷效率.NAT 版本，B+tree 樹結點總量越多，更新NAT 塊越多，寫放大越嚴重，增加HDD 尋道時間從而降低系統吞吐率.因此，IBT 版本在元數據寫放大和下刷效率方面的表現均優于NAT 版本.

5.3 Filebench 測試

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

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

2）fileserver，模擬文件服務器上的I/O 負載，該負載多線程執行相同任務.順序創建、寫整個文件、追加寫、讀整個文件、刪除文件、查看文件狀態.

測試方法為：分別基于HDD 和SSD 創建4TB 的Monty-Dev 設備，格式化為ext4 文件系統，使用discard選項掛載文件系統以測試B+tree 的刪除操作，每類負載執行1 h，每個測試執行3 次，結果取平均值.

5.3.1 基于SSD 的Filebench 測試

Filebench 測試結果，IBT 版本和NAT 版本基 本相同，差異較小.主要原因有：文件系統并不會將寫請求直接轉發至底層設備，設備利用率低；文件系統下發的寫請求基本為順序寫，2 個版本差異較小.因此，本節及5.3.2 節主要通過元數據下刷量評價IBT版本和NAT 版本.由于Filebench 測試按照指定時長進行測試，不同測試中Monty-Dev 設備收到的I/O 請求數量存在差異，因此，本節及5.3.2 節使用元數據下刷比例指標評價元數據的寫放大情況：

通過式（1）的計算方法，計算結果如圖13 所示.

Fig.13 Comparison of Filebench test based on SSD圖13 基于SSD 的Filebench 測試對比

相對于NAT 版本，IBT 版本在varmail 負載和fileserver 負載測試中，元數據下刷比例分別減少0.67%和0.69%.經統計，若元數據寫比例僅統計樹結點下刷量，則2 類負載測試中IBT 版本均大于NAT版本，該現象符合IBT 版本和NAT 版本設計的差異.因此，導致NAT 版本元數據下刷比例高的主要原因是NAT 塊下刷的開銷大.接下來，具體分析NAT 版本元數據下刷量的組成.

如表9 所示，NAT 塊下刷量占元數據下刷比例較表6 所示的更高.較Fio 負載，Filebench 負載支持discard I/O 請求，系列刪除操作完成后，一些樹結點需要被釋放，釋放樹結點需要將NAT 塊中的記錄更新為無效映射.經統計，varmail 和fileserver 負載測試中discard I/O 占寫I/O 請求的比例分別為81.5%和76%.因此，刪除操作會嚴重影響NAT 版本的NAT塊下刷量，從而影響元數據下刷比例，導致NAT 版本寫放大更加嚴重.

Table 9 Statistics of Flushed NAT Block for Different Loads Under Filebench Test Based on SSD表9 基于SSD 的Filebench 測試不同負載NAT 塊下刷統計

5.3.2 基于HDD 的Filebench 測試

評價方法與SSD 上測試相同，元數據下刷比例對比結果如圖14 所示.

Fig.14 Comparison of Filebench test based on HDD圖14 基于HDD 的Filebench 測試對比

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

NAT 塊下刷量相對于元數據下刷量的比例如表10所示.discard I/O 占比的差異與NAT 塊占比為正相關.綜上，在元數據寫放大方面，相對于NAT 版本，IBT版本在刪除操作中的表現也更優.

綜上，進行了Fio 測試和Filebench 測試，IBT 版本相對于NAT 版本：在HDD 上的吞吐率和元數據下刷寫放大方面，較SSD 上的優化效果更顯著；在處理大規模隨機更新和刪除操作時，開銷更小.

Table 10 Statistics of Flushed NAT Block for Different Loads Under Filebench Test Based on HDD表10 基于HDD 的Filebench 測試不同負載NAT 塊下刷統計

6 總結

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

作者貢獻聲明：楊勇鵬負責論文撰寫、部分實驗方案設計、實驗執行和論文修訂；蔣德鈞負責部分實驗方案設計和論文修訂.