動(dòng)機(jī)和背景

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

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

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

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

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

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

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

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

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

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

丟棄無(wú)效塊

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

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

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

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

丟棄日志

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

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

中間映射表設(shè)計(jì)

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

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

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

評(píng)估

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

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

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

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

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

IPLFS的丟棄策略

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

地址轉(zhuǎn)換開(kāi)銷(xiāo)測(cè)試

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

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

總結(jié)

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

編輯：黃飛