基于對象模型的閃存文件系統研究

摘 要：提出了一種基于對象的存儲系統管理框架，它使用統一的對象接口來訪問flash或者磁盤。重點對基于對象模型的閃存文件系統進行了研究設計，在系統中引入了段的層次來進行對象管理，通過分析能夠顯著減少徘徊樹問題引起的大量數據更新次數，并避免了垃圾回收時多余的I/O操作，緩解了垃圾回收過程中的數據鎖定問題。

關鍵詞：對象存儲； 基于對象模型的閃存文件系統； 垃圾回收

中圖分類號：TP333 文獻標志碼：A 文章編號：1001-3695(2008)08-2316-03

OFFS：research on object-based flash file system

LIN Wei， ZHANG Yan-yuan， LI Zhan-huai， WANG Yan-long

(School of Computer Science Engineering， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract: This paper presented a management framework of object-based storage system， which used the uniform object interface to access flash and disk. It designed object-based flash file system(OFFS) to manage the flash storage. In OFFS， introduced a segment level to store the object. The discuss shows it can reduce the update time caused by wonder tree， easy to implement and can work without serious locking problems during garbage collection.

Key words：object-based storage; object-based flash file system(OFFS); garbage collection

閃存（flash memory）是一種可以按存儲單元塊進行擦寫和再編程非易失性的存儲器，具有低成本、抗振蕩、低功耗、高密度和非易失性等優點^[1]，在嵌入式系統中得到廣泛的應用。近些年，由于閃存存儲技術的飛速發展，Intel^[2]等廠商準備在筆記本電腦上使用NAND閃存，以幫助系統獲得更快的啟動速度并降低能耗，并計劃在未來完全使用閃存作為存儲介質。然而硬盤的大容量和廉價仍然具有巨大的優勢，閃存和硬盤如何在同一個文件系統中共同使用成為了亟待解決的問題。

閃存文件系統有兩種主要的實現方法：a)通過FTL(flash translation layer)^[3]將閃存模擬成與磁盤具有相同接口的塊設備，然后在上面運行傳統的文件系統，數據更新和均衡磨損都在塊設備驅動中通過FTL來完成。這類辦法實現簡單，但運行效率低，實時性和防掉電性都比較差。b)專門針對閃存特性而設計的文件系統^[4，5]，在閃存原始操作接口上利用日志結構文件系統的思想直接實現整個文件系統。在分配文件存儲塊時就考慮閃存對數據更新和均衡磨損的要求，但它的管理方式與磁盤文件系統相差太多，只能在用戶應用級別上共同使用。

本文在傳統閃存文件系統的基礎上設計了OFFS。它使用對象存儲的思想將文件系統的文件管理模塊和存儲管理模塊分離開來，這樣存儲管理模塊有足夠的信息來進行垃圾回收、均衡磨損等閃存日志結構文件系統的特殊功能；使用一種新的數據分布策略，減少徘徊樹問題^[6]引起的大量數據更新次數，并緩解了垃圾回收時的數據鎖定問題。

1 OFFS設計

整個文件系統的構架如圖1所示。File management實現文件系統接口；object management主要提供全局的對象分布和管理；OSTFS（object storage target file system）進行磁盤介質的數據對象的管理；OFFS負責閃存對象的存儲管理，包括數據存儲、均衡磨損、垃圾回收等功能。本文主要討論OFFS的設計方法和原理。OFFS借鑒了JFFS3的設計思想，將整個對象數據都存儲于一個巨大的B+樹中，所有對象存儲于樹的葉子節點；非葉子節點只包含用于索引和查找對象的屬性。為了便于管理，本文設定每個對象的元數據至少占有一個扇區。

1.1 數據布局

在系統中引入了段（segment）^[7]的層次，整個flash被分成多個段，每一個段由固定數量的擦除塊組成，每個段都有一個物理段號和邏輯段號。圖2是flash的數據布局，SB（super block）位于flash最開始的多個擦除塊，它主要記錄了flash型號、大小等靜態信息以及元數據段的位置信息等動態信息；SIB（segment information block）則記錄了每個段的狀態、邏輯段號到物理段號的映射，以及段中擦除塊的使用狀況等信息；所有對象的屬性和索引信息將集中存放到對象索引段（object inode segment，OIS）中。

1.2 徘徊樹問題

為了保證flash存儲的可靠性，flash文件系統大都使用了異地更新策略，這樣其數據更新方式就如圖3中的徘徊樹所示。葉節點F的數據更新將使得從該葉節點到根節點之間所有的節點（F、D、A）都要進行一次更新操作，這將大大影響系統的性能。目前解決的方法主要是通過緩沖機制將多次寫操作合并或者減少樹的層次，以減少寫操作次數。文獻[8]中甚至不記錄dentry信息，并限制inode只能有二級索引，這樣雖然減少了更新次數但是降低了數據塊定位速度，而且無法支持大文件的存儲。分析可知，多余的更新操作主要是由于父節點對于子節點的位置信息過于敏感引起的。如果將flash上父節點中記錄的子節點詳細位置（如扇區號）改為段號（segment number），這將顯著減少更新次數。如圖中A指向的是D所在的段號，D指向的是E和F的段號；如果F更新后的數據依然存在同一個段內，就不必更新D和A節點。

1.3 掛載過程

當掛載一個文件系統時，需要對flash進行掃描，以確定flash的使用狀況。OFFS采用了多級超級塊管理策略^[6]，在掃描前先找到超級塊，檢查其uptodate標志位，如果有該標志位表明上次文件系統是正常卸載。接下來通過SB中的信息找到SIB的位置，并在SIB信息中得到所有的OIS的信息。通過讀取所有對象索引段的信息在內存中建立對象緩存樹以便于以后定位對象，并建立文件系統目錄結構。

如果uptodate標志位沒有被置上，則表明上次的卸載并沒有正常完成，OFFS將直接讀取每個段頭一個扇區的空閑區域（spare region），在空閑區域上記錄了該段的類型，這樣就能找到所有對象索引段的信息。由于每個段包括了多個擦除塊，系統中段的數目并不大（表1）。相對于其他文件系統，OFFS的掛載掃描過程要快得多。

表1 同等大小flash中的段和擦除塊數目比較flash大小/GB擦除塊大小/KB擦除塊數目每段擦除塊數段數412832 76884 096412832 768162 048425616 38482 048425616 384161 0241.4 空間分配算法

與磁盤文件系統有所不同，flash文件系統中所有的寫操作都涉及到空間分配的問題。OFFS中擦除操作的單位由一個擦除塊變成了一個段，將段分為三種類型：empty、data、full，分別表示空白、有部分空白和滿數據的段。由于大于一個empty段的空間申請可以分拆成多個小于empty段的申請，只考慮一次小于一個empty段大小的空間分配申請。為了減少I/O次數（參看1.1節），在進行空間分配時，如果是對數據的更新操作則首先檢查該數據本身所在段的剩余空間大小是否足夠分配，如果是新的節點則首先檢查其父節點所在段的剩余空間是否足夠分配。如果該段的剩余空間小于需要分配的空間，或者就在所有的其他data段中查找符合條件的剩余空間最小的段。如果沒有一個段符合分配條件，就使用一個擦除次數最少的empty段來進行分配。如果系統中empty段的個數小于2，就要進行垃圾回收。

1.5 緩存機制

文件系統在進行讀寫操作時，需要將flash上存儲的數據讀取出來。如果每次讀寫操作都進行一次I/O操作將大大降低系統的性能。為了提高對象的訪問速度，大多數的文件系統都提供了緩存機制，其原理是將以前讀取的數據保存在內存中并通過哈希函數或者是別的方法將其組織起來，以便下次直接使用，但是要確保內存中的數據是最新的。由于OFFS中的數據都存儲在一個B+樹上，本文設計了與其類似的緩存樹。在進行讀寫操作之前都要先搜索緩存樹，如果找到就直接返回數據；否則將從flash上讀取數據并將其加入到緩存樹上。

2 垃圾回收機制

閃存文件系統每次對數據的更新都需要寫到新的地方，原來的數據頁面則成為了垃圾頁面（dirty page），需要擦除后才能使用。為了避免頻繁擦除引起的性能下降，同時平衡閃存各個頁面的擦除次數，在垃圾回收過程中采用了lazy delay的思想，就是不立即對數據塊進行回收，而是等待觸發了某個條件后才進行垃圾回收。在對選擇好的擦除塊進行垃圾回收時，被回收的擦除塊內如果還有正在使用的數據頁面（live page），則需要將這些live page搬移到其他地方。垃圾回收策略的核心思想就是在回收更多的dirty page時盡量減少因live page的移動引起的I/O次數，同時還要考慮磨損均衡的問題。

目前主要有三種垃圾回收策略^[9]：貪心策略，選擇垃圾最多的擦除塊進行回收；成本收益策略，同時考慮垃圾多少和數據的年齡來進行回收；數據年齡策略，選擇數據年齡最長的進行回收，防止形成靜態數據。最新的研究則是基于數據訪問的冷熱模型^[10]來進行的，熱數據代表該數據接下來被更新的可能性較高，而冷數據較低。就文件系統來說，元數據就比普通數據要熱，因為每次對普通數據的更新都涉及到元數據的更新，而且對文件進行改名、屬性修改等操作也會引起元數據的更新。將熱數據集中起來存儲能夠使得更多的垃圾頁面集中在少數擦除塊中，這樣能減少垃圾回收過程中live page的數目，增加回收dirty page的數目。

OFFS在設計中考慮到了數據訪問的冷熱模型，將對象屬性以及元數據等與普通數據分割開來，將它們統一分配到OIS中。同時筆者還考慮到在移動live page過程中的一系列因數據位置變化而產生的I/O操作。圖4中，如果準備對2號segment進行垃圾回收，則將2號segment上的live page移動到3號segment；然后將原來的物理上3號segment映射成邏輯的2號segment；最后再對物理2號segment實行擦除操作。這樣就避免了多余的I/O操作，相應地也縮短了數據遷移過程中對數據塊的鎖定時間。

3 系統分析

下面將分別對OFFS的系統掛載時間、垃圾回收過程中的代價進行分析，并與其他系統作定性比較。假設文件系統所掛載的flash大小為Pf個頁面，每個段包含Ps個頁面，每個擦除塊包含Pe個頁面。文件系統中包含有n個文件，平均每個文件數據占據S個頁面，每個頁面的數據區和空閑區的讀取時間分別為Td和Ts。

JFFS2 的掛載過程需要對閃存從頭到尾的掃描，由此可以知道JFFS2文件系統的掛載時間為

TJ=PfTd（1）

這個過程非常慢，于是有人提出了磨損塊小結補丁程序來縮短掛載時間。其基本思想就是將每個擦除塊每個節點的原數據信息寫在這個擦除塊的最后，當 JFFS2 掛載時，對每個擦除塊只需要讀一次來讀取這個小結節點。這樣得到的掛載時間為

TJfixed=PfTd/Pe（2）

YAFFS中利用每個頁面的空閑區域存儲部分元數據信息。對于文件的元數據頁面需要同時讀取頁面的數據區和空閑區，而對文件的數據頁面也需要讀取空閑區的內容，所以YAFFS文件系統的掛載時間為

TY=n(Td+Ts)+nSTs（3）

在OFFS中，所有對象的元數據信息都集中存儲在OIS段中，只需要將所有的元數據讀出即可。假設文件包含二級以上索引的所占比例是σ2，三級以上索引的所占比例是σ3，依此類推，則其掛載時間為

TO=n(1+σ2+σ3+…)Td（4）

很明顯，JFFS2文件系統的掛載時間是O(N)，其所需時間最長。同時由于大多數的文件都是小文件，只需要一級索引，σ2、σ3等都比較小，一般來說σ2都在0.2以下，σ3就更小。相對于YAFFS可以知道，在大部分情況下OFFS的掛載時間都要短。

其次閃存文件系統在設計中要考慮的重點就是垃圾回收的代價問題，在垃圾回收過程中主要的代價為將擦除塊中的有效數據移動到其他地方。設需要移動的數據頁面數為Nmove，PI代表對象元數據頁面，PD代表對象數據頁面，每個對象所使用的頁面被更新的概率為P(Pk)(1

4 結束語

本文提出了一種同時使用flash和磁盤的存儲管理系統，利用對象存儲技術將flash上存儲的數據和磁盤上存儲的數據都設計成數據對象，然后通過統一的對象管理模塊進行管理。針對當前系統應用的不同需求，用戶可以選擇創建不同屬性的對象來進行數據的存儲，系統將自動根據屬性需求將數據存儲到flash或磁盤上。本文重點設計了基于對象的flash文件系統（OFFS），對OFFS的數據分布、徘徊樹問題、掛載過程、空間分配算法和緩存機制進行了分析設計，并重點對垃圾回收機制進行了研究，在擦除塊之上提出了段的數據管理層次。

參考文獻：

[1]DOUGLIS F， CACERES R， KAASHOEK F， et al. Storage alternatives for mobile computers[C]// Proc of the 1st Symposium Operating Systems Design and Implementation.1994:25-37.

[2]DOLLER E. Meeting the NVM market segment requirement， keynote of flash memory summit 2006 presentations[K].[S.l.]: Intel Corp， 2006.

[3]Intel Corp. Understanding the flash translation layer (FTL) specification[EB/OL]. (1998). http://developer.intel.com/.

[4]WOODHOUSE D. JFFS: the journalling flash file system[EB/OL].(2001). http://sournes.redhat.com/jfs2/ffs2-html/.

[5]Aleph One Ltd， Embedded Debian. YAFFS: a NAND-flash file system [EB/OL].(2002). http://www.aleph1.co.uk/yaffs/.

[6]BITYUTSKIY A B. JFFS3 design issues [EB/OL]. (2005-11). http://www.linux-mtd.infradead.org/tech/JFFS3design.pdf.

[7]HAVASI F， SOGOR Z， MAJZIK M. JFFS3 plan extension[EB/OL]. (2006). http://www.inf.u-szeged.hu/jffs2/jffs3-plan-extension-20060928.pdf.

[8]LIM S H， PARK K H. An efficient NAND flash file system for flash memory storage[J]. IEEE Trans on Computers， 2006，55(7):906-912.

[9]CHIANG M L， LEE P C H， CHANG R C. Using data clustering to improve cleaning performance for flash memory[J]. Software-Practice and Experience， 1999， 29(3):267-290.

[10]CHANG Li-pin， KUO Tei-wei， LO Shi-wu. A real-time garbage collection mechanism for flash memory storage system in embedded systems[C]// Proc of the 8th Int’l Conf on Real-time Computing Systems and Applications. New York: ACM Press， 2002:837-863.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文