IPLFS的設(shè)計與實(shí)現(xiàn)

動機(jī)和背景

IPLFS是一個避免文件系統(tǒng)層垃圾回收的日志結(jié)構(gòu)文件系統(tǒng)。作者發(fā)現(xiàn)，日志結(jié)構(gòu)文件系統(tǒng)的僅追加寫入方式會帶來不可避免的文件系統(tǒng)層次垃圾回收。十?dāng)?shù)年來，學(xué)界已經(jīng)提出多種緩解垃圾回收開銷的方式，包括空閑時段垃圾回收、預(yù)先垃圾回收、選擇最合適的回收段算法等。

與此同時，SSD的設(shè)備端垃圾回收同樣給存儲系統(tǒng)帶來可觀的帶寬下降和延遲。當(dāng)日志結(jié)構(gòu)文件系統(tǒng)和SSD一起使用時，兩端的垃圾回收開銷可能會疊加影響。為了解決這種問題，大多數(shù)工作提出讓主機(jī)端直接管理閃存頁，以解決設(shè)備端垃圾回收開銷，比如最近的ZNS技術(shù)等。

而作者發(fā)現(xiàn)，隨著計算機(jī)系統(tǒng)的發(fā)展，大多數(shù)組件，比如CPU、內(nèi)存等都已經(jīng)支持虛擬化技術(shù)，而存儲設(shè)備則不支持虛擬化。因此作者提出，可以將SSD的LBA和PBA分離，實(shí)現(xiàn)SSD的地址虛擬化，從而避免文件系統(tǒng)垃圾回收。

IPLFS的設(shè)計與實(shí)現(xiàn)

IPLFS的設(shè)計目標(biāo)是在保持日志結(jié)構(gòu)文件系統(tǒng)僅追加更新特性的同時，完全取消文件系統(tǒng)層垃圾回收。IPLFS的設(shè)計共有三個重點(diǎn)：多區(qū)域分區(qū)布局、無GC的元數(shù)據(jù)設(shè)計、全新的丟棄映射和丟棄日志。

多區(qū)域分區(qū)布局

為了減小LBA映射表的大小，IPLFS把整個LBA地址空間分為7個大小相同的區(qū)域，分別是一個用于存儲超級塊、節(jié)點(diǎn)映射表等數(shù)據(jù)的IPLFS元數(shù)據(jù)區(qū)，和6個對應(yīng)存儲F2FS不同熱度、不同類型數(shù)據(jù)的段的數(shù)據(jù)區(qū)。在地址空間使用上，IPLFS使用最高的3比特作為區(qū)域標(biāo)識符，剩余58位用來作為地址使用，因此每個區(qū)域可以保存258個塊，共計1ZB。

元數(shù)據(jù)設(shè)計

元數(shù)據(jù)的設(shè)計要求最小化原始F2FS元數(shù)據(jù)的盤上數(shù)據(jù)修改。由于IPLFLS不再需要文件系統(tǒng)垃圾回收，同時由于地址空間過大，因此IPLFS僅移除了F2FS中用于垃圾回收和塊丟棄的兩個元數(shù)據(jù)：反向映射表和塊分配映射位圖。

而IPLFS仍舊保留了節(jié)點(diǎn)分配表NAT，而NAT的大小決定了文件系統(tǒng)中文件數(shù)量的上限，因此NAT的大小不再是傳統(tǒng)的由LBA大小決定，而修改為由PBA大小決定。被移除的分配映射表和反向映射信息由全新的丟棄映射位圖和丟棄日志取代。

丟棄無效塊

F2FS使用塊分配位圖有兩個原因：一是代表每個段空間利用率，二是追蹤最新無效的文件系統(tǒng)塊。而在IPLFS中，空間利用率不再重要，而被無效的塊仍然需要追蹤。IPLFS使用使用丟棄映射位圖取代了F2FS的塊分配位圖，用于表征自最后一個檢查點(diǎn)后無效的塊，每個位圖表示一個分區(qū)，每個分區(qū)包括一個或多個段。一個丟棄映射位圖包括分區(qū)的起始地址和映射位圖兩部分。

當(dāng)文件系統(tǒng)標(biāo)識一個塊無效，則設(shè)置對應(yīng)的丟棄映射表的無效位，多個丟棄映射表使用哈希表組織為一組，使用段編號作為鍵。當(dāng)塊被無效時，IPLFS搜索哈希表并查找對應(yīng)丟棄映射位圖，若找到則更新位圖；若更新位圖不存在則分配一個新的丟棄映射位圖并更新，之后將新的位圖插入哈希表。

段的大小和文件系統(tǒng)性能存在trade-off。段大小越大，丟棄映射位圖越大。段越小則哈希表中的丟棄映射位圖條目越多，查詢延遲升高。實(shí)驗(yàn)表明，最佳段大小為1GB，同時平衡性能和內(nèi)存壓力。

在每個檢查點(diǎn)觸發(fā)時，IPLFS掃描哈希表，對每個丟棄映射位圖構(gòu)造丟棄指令，之后移除對應(yīng)丟棄映射位圖。IPLFS會定期提交丟棄指令。IPLFS單獨(dú)開啟一個線程用于分發(fā)丟棄指令，每次喚醒最多下發(fā)16條丟棄指令，IPLFS的丟棄指令分發(fā)相較F2FS更加激進(jìn)，無論是否存在等待中的IO，均下發(fā)丟棄指令；而F2FS需要等待直到文件系統(tǒng)中無等待中的IO存在再下發(fā)丟棄指令。在實(shí)驗(yàn)中發(fā)現(xiàn)發(fā)現(xiàn)激進(jìn)的下發(fā)策略獲得了更好的基準(zhǔn)測試表現(xiàn)，因?yàn)檫@樣做使得SSD的GC更加高效，避免了寫放大。

丟棄日志

由于缺乏塊分配位圖，IPLFS難以感知存儲空間泄露，即flash頁存儲了無效的FS塊，但是FS從不回收這些頁。如系統(tǒng)崩潰時為下發(fā)的丟棄指令。F2FS中恢復(fù)程序會根據(jù)恢復(fù)的塊分配位圖重建丟棄指令。為了解決這個問題，IPLFS使用了丟棄日志。丟棄日志在下發(fā)丟棄指令前建立丟棄指令檢查點(diǎn)，保證丟棄指令再下發(fā)到設(shè)備前被持久化。在檢查點(diǎn)包中建立丟棄日志區(qū)保存丟棄日志。在每個檢查點(diǎn)，IPLFS檢查丟棄映射表并創(chuàng)建丟棄指令，IPLFS在丟棄日志區(qū)記錄丟棄指令的信息(起始LBA、長度)，之后將日志同步落盤，檢查點(diǎn)后，IPLFS喚醒丟棄線程提交丟棄指令。

重建丟棄指令分為兩個階段，首先是回滾恢復(fù)，恢復(fù)模塊讀取最近的檢查點(diǎn)包，重建丟棄指令；之后是前滾恢復(fù)，前滾恢復(fù)時識別在最近檢查點(diǎn)后被寫入文件，對比節(jié)點(diǎn)塊，對比前滾恢復(fù)階段的節(jié)點(diǎn)塊和檢查點(diǎn)時的節(jié)點(diǎn)快，識別修改記錄，針對新分配的節(jié)點(diǎn)塊更新文件映射表。

中間映射表設(shè)計

為了解決過大的LBA占用過多SSD映射資源的問題，IPLFS在OpenSSD平臺重新設(shè)計了中間映射表。首先，中間映射表采用LBA充足映射方式，作者稱之為間隔映射，設(shè)計和Interval tree類似，樹高限制為3，通過增加根節(jié)點(diǎn)扇出的方式增加映射節(jié)點(diǎn)，以此降低地址轉(zhuǎn)換相關(guān)內(nèi)存開銷。間隔映射以分區(qū)數(shù)組的形式組織存儲區(qū)域。每個分區(qū)都是一個映射段數(shù)組，每個分區(qū)對應(yīng)16GB，而每個段對應(yīng)16MB；間隔映射樹的根節(jié)點(diǎn)保存一組分區(qū)節(jié)點(diǎn)隊列，每個節(jié)點(diǎn)維護(hù)單個分區(qū)的數(shù)據(jù)。一個分區(qū)節(jié)點(diǎn)維護(hù)1024個映射表節(jié)點(diǎn)作為子節(jié)點(diǎn)，每個映射表節(jié)點(diǎn)維護(hù)一個段的LBA-PBA映射。

映射中間層是一塊需要IM樹進(jìn)行映射的邏輯分區(qū)，映射中間層使用其對應(yīng)邏輯分區(qū)的第一個分區(qū)的起始LBA和最后一個分區(qū)的起始LBA表示。當(dāng)分區(qū)創(chuàng)建時，映射中間層會為IPLFS分區(qū)創(chuàng)建6個獨(dú)立的IM樹，分別對應(yīng)IPLFS的6個數(shù)據(jù)段。

活躍中間層表示的是對應(yīng)映射中間層中活躍的已使用分區(qū)的窗口。活躍分區(qū)類似，活躍中間層起始于對應(yīng)映射中間層中第一個有效分區(qū)，結(jié)束于對應(yīng)映射中間層中最后一個有效分區(qū)。當(dāng)活躍中間層表中第一個分區(qū)被無效時，其起始分區(qū)被更新；當(dāng)新的分區(qū)加到活躍中間層末端時，其結(jié)束分區(qū)被更新。隨著FS老化，活躍中間層的地址表示窗口向高處移動，當(dāng)活躍中間層終點(diǎn)移動到接近映射中間層終點(diǎn)時，中間映射表會構(gòu)造新的根節(jié)點(diǎn)和新的映射中間層以更好容納不斷變化的活躍中間層。

評估

IPLFS實(shí)現(xiàn)在F2FS（Linux 5.11.0）上，中間映射表使用OpenSSD（230GB ,8通道）實(shí)現(xiàn)。測試環(huán)境采用PC服務(wù)器(I7-4770K)+8GB DRAM配合OpenSSD實(shí)現(xiàn)。

文件系統(tǒng)垃圾回收消除效果實(shí)驗(yàn)

首先測試消除文件系統(tǒng)層垃圾回收的前后性能表現(xiàn)，測試方式為：在SSD上構(gòu)建30GB邏輯空間的F2FS，用4線程隨機(jī)寫28GB文件，每2s檢測吞吐量。測試發(fā)現(xiàn)，當(dāng)F2FS開始進(jìn)行文件系統(tǒng)層垃圾回收時，IO性能下降到之前的以下，如下圖所示。

接著作者測試了文件系統(tǒng)層垃圾回收和設(shè)備端垃圾回收對性能的影響權(quán)重。測試方式為：使用與OpenSSD物理容量相同的邏輯分區(qū)大小共230GB，隨機(jī)寫210GB的文件。結(jié)果表明，當(dāng)F2FS開始垃圾回收時，吞吐量下降到接近；而IPLFS消除了文件系統(tǒng)層垃圾回收，但是無法消除設(shè)備側(cè)垃圾回收，當(dāng)OpenSSD開始設(shè)備層垃圾回收時，性能下降60%左右。因此作者認(rèn)為，文件系統(tǒng)層垃圾回收對性能的影響比設(shè)備層垃圾回收更大。

最后，作者使用MySQL數(shù)據(jù)庫和YCSB-A負(fù)載測試數(shù)據(jù)庫操作受文件系統(tǒng)垃圾回收的影響情況。YCSB-A負(fù)載包括等量的讀更新操作。從下圖的吞吐量、延遲變化曲線可以看出，開始測試時文件系統(tǒng)達(dá)到90%占用率，因此快速觸發(fā)文件系統(tǒng)層垃圾回收。IPLFS的平均讀延遲和平均更新延遲僅為F2FS的和。同時作者從實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)：取消文件系統(tǒng)垃圾回收可以顯著提升尾端延遲表現(xiàn)，IPLFS的95%和99%尾延遲相對F2FS分別降低5.2X和5X，并且IPLFS吞吐量保持穩(wěn)定。

IPLFS的丟棄策略

之后進(jìn)行的測試目的是測試激進(jìn)的丟棄策略對設(shè)備層垃圾回收和應(yīng)用性能的影響。作者采用Filebench的fileserver負(fù)載，創(chuàng)建50個線程，更新/刪除2MB文件。測試發(fā)現(xiàn)，在全占用率下，IPLFS的寫放大比F2FS更低，同時吞吐量提升24%。對結(jié)果進(jìn)行分析后，作者認(rèn)為更激進(jìn)的丟棄策略節(jié)省了FTL在垃圾回收時的遷移數(shù)量，因此IPLFS在寫放大和基準(zhǔn)測試方面有了顯著改善。通過IO trace分析，作者發(fā)現(xiàn)IPLFS比F2FS更頻繁的提交丟棄指令，這是由于F2FS僅在無等待IO時提交丟棄指令。然而在測試中，極少有不存咋等待中IO的情況。

地址轉(zhuǎn)換開銷測試

首先作者進(jìn)行了地址轉(zhuǎn)換延遲的測試，測試方法為使用fio對10GB文件進(jìn)行4線程隨機(jī)寫操作。測試發(fā)現(xiàn)，IPLFS的中間映射方式比傳統(tǒng)的頁映射延遲長88%。作者分析這是因?yàn)橹虚g映射層在地址轉(zhuǎn)換時使用的是多索引查找，而當(dāng)構(gòu)建新的映射條目時，中間映射層的延遲為頁映射的3.3倍。

之后作者進(jìn)行了端到端延遲測試，測試發(fā)現(xiàn)中間映射層和頁映射在讀寫延遲上幾乎相同，如下圖所示，而這是因?yàn)閷?shí)際訪問中，Nand的訪問延時和設(shè)備數(shù)據(jù)傳輸延時是延遲的主要部分，而FTL中的延遲影響微不足道。

總結(jié)

作者提出了一種用于無限分區(qū)的日志結(jié)構(gòu)文件系統(tǒng)IPLFS。將文件系統(tǒng)分區(qū)大小從物理存儲大小中分離出來，并使得邏輯文件系統(tǒng)的分區(qū)大小實(shí)際上無限大，這樣就可以使日志結(jié)構(gòu)的文件系統(tǒng)免于回收無效的文件系統(tǒng)塊。為了維護(hù)超大邏輯文件系統(tǒng)分區(qū)的映射信息，作者開發(fā)了中間映射層，只為活躍的LBA區(qū)域維護(hù)LBA-PBA映射。通過將IPLFS和中間映射層結(jié)合在一起，作者成功減輕了日志結(jié)構(gòu)文件系統(tǒng)回收無效塊的開銷。

編輯：黃飛