基于FAT16元數(shù)據(jù)一致性的設計

周燕艷 海深

（1.合肥工業(yè)大學，安徽合肥 230009；2.銅陵學院，安徽銅陵 244000）

基于FAT16元數(shù)據(jù)一致性的設計

周燕艷1，2海深2

（1.合肥工業(yè)大學，安徽合肥 230009；2.銅陵學院，安徽銅陵 244000）

隨著嵌入式系統(tǒng)的不斷發(fā)展，將數(shù)據(jù)以某種常用文件系統(tǒng)的形式保存在外存中的方法也得到了越來越廣泛的使用。由于嵌入式系統(tǒng)的運行環(huán)境和緩存機制的引入，可能導致文件系統(tǒng)的一致性被破壞的可能性更高，因而采取某種應對系統(tǒng)故障的恢復機制顯得十分必要。基于對FAT16文件系統(tǒng)，結合已有的一致性方法提出了一種數(shù)據(jù)恢復機制，以維護系統(tǒng)的一致性。

一致性；FAT16；嵌入式系統(tǒng)；文件系統(tǒng)

1.引言

嵌入式系統(tǒng)來采集現(xiàn)場數(shù)據(jù)在工業(yè)控制、智能家電和車載電子等多個領域已經得到了非常普遍的應用。為了便于上位機的處理，將采集來的數(shù)據(jù)在嵌入式系統(tǒng)中采用某種上位機所熟悉的文件格式進行存儲是一種比較可行的方案，目前已經相繼出現(xiàn)相關的研究。以本文的數(shù)據(jù)存儲處理系統(tǒng)為例，系統(tǒng)將從現(xiàn)場采集的數(shù)據(jù)以FAT16的文件格式存儲在U盤中，然后通過USB接口將存儲在U盤中的文件在上位機中讀出并進行處理。

文件系統(tǒng)是提供組織和管理保存在持久存儲介質上的用戶數(shù)據(jù)的手段，文件系統(tǒng)的組成包括用戶數(shù)據(jù)（即文件內容）和元數(shù)據(jù)（即描述文件系統(tǒng)組織結構的數(shù)據(jù)）。一個文件操作通常是由一系列更基本的子操作構成，構成一個文件操作的子操作序列是不可分割的整體，因此，文件操作具有與事務類似的ACID特性。如果文件系統(tǒng)的內容（包括用戶數(shù)據(jù)和元數(shù)據(jù)）是而且僅是所有已成功完成的文件操作按順序完成的結果，就說這個文件系統(tǒng)是一致的。文件系統(tǒng)在使用過程中有許多中間狀態(tài)，在這些中間狀態(tài)時文件系統(tǒng)不一定是一致的，但是在系統(tǒng)穩(wěn)定時它必須是一致的。如果在中間狀態(tài)時系統(tǒng)突然崩潰，則可能導致系統(tǒng)的一致性被破壞。另一方面，文件系統(tǒng)廣泛使用緩存機制來緩解外存與CPU速度上的差距，緩存引入后，使文件系統(tǒng)在系統(tǒng)崩潰時的不一致問題更加嚴重[1]。

2.背景及相關研究

文件系統(tǒng)的一致性關系到系統(tǒng)的可用性、完整性等重要方面，當系統(tǒng)崩潰時，文件系統(tǒng)的一致性與否可能直接決定數(shù)據(jù)能否正常使用甚至系統(tǒng)是否可以恢復。為了實現(xiàn)該目標，一般可以通過在系統(tǒng)崩潰前在永久存儲器上已經保存的一些信息來完成恢復系統(tǒng)的一致性操作，從而使得系統(tǒng)依然是一致的。由于文件系統(tǒng)的不一致問題只發(fā)生在系統(tǒng)出現(xiàn)故障時，因此維護文件系統(tǒng)的一致性的方法又稱為故障恢復技術。

在桌面系統(tǒng)中，維護文件系統(tǒng)一致性主要有以下兩種策略：

第一種采用寫前日志（write-ahead logging）的方法。如果系統(tǒng)崩潰，在外存中有足夠的信息讓元數(shù)據(jù)恢復到一致的狀態(tài)日志[2]。（journaling）、日志結構[3]（log-structured）及元數(shù)據(jù)快照[4][5]（meta-data snapshotting）等方法就是基于這種方案。許多現(xiàn)代文件系統(tǒng)就有這些技術的應用，如CedarFS，Episode，JFS，XFS，ext2，ext3，NTFS，BFS，Sprit LFS等。但是，采用日志或日志結構的文件系統(tǒng)對日志自由空間如何管理十分難以設計，將一塊數(shù)據(jù)從一個段移到一個新的位置需要一個專門的空間回收機制；快照技術可以在一個時間點上對文件系統(tǒng)生成一個稱為快照的映像，當系統(tǒng)發(fā)生故障后，通過以前的快照映像來維護系統(tǒng)的一致性，但是為了存儲映像有時需要很多的空間支持。

第二種策略采用對外存數(shù)據(jù)的更新操作必須要求按照一個嚴格的操作順序，這樣，系統(tǒng)發(fā)生故障時，即使外存上的元數(shù)據(jù)不能正確無誤，系統(tǒng)的一致性仍然可以保證。如FFS通過將每一個元數(shù)據(jù)塊采用同步寫的手段來實現(xiàn)這個目標，而軟更新[6]（soft updates）則采取一個規(guī)定操作序列來維護文件系統(tǒng)的一致性。但是使用此種方法恢復系統(tǒng)，如回滾（rollback）操作，可能產生頻繁的I/O操作而導致系統(tǒng)整體的性能損失。

3.FAT16一致性策略的設計

3.1 FAT16文件系統(tǒng)原理與結構

FAT16文件系統(tǒng)是Microsoft較早推出的文件系統(tǒng)，具有高度兼容性，目前仍然廣泛應用于嵌入式存儲設備中，這里對FAT16做簡要介紹。FAT格式的磁盤上數(shù)據(jù)大致可分為5部分：MBR區(qū)、DBR區(qū)、FAT區(qū)、FDT區(qū)和DATA區(qū)。MBR區(qū)又稱為主引導記錄，其后為64字節(jié)的磁盤分區(qū)表(disk partition table，DPT)。DBR區(qū)即操作系統(tǒng)引導記錄區(qū)，占用一個扇區(qū)，共512個字節(jié)，由跳轉指令、BPB、結束標志幾部分組成。FAT區(qū)用于存放文件分配表(file allocation table，F(xiàn)AT)。文件分配表是一一對應于數(shù)據(jù)區(qū)簇號的列表，反映了所有簇的使用情況。每個表項單元的大小決定了FAT的類型，比如FAT16的表項單元為16位。FAT表一般都有一個備份。FDT區(qū)存放著文件目錄表，位于備份FAT表之后。FDT由32位的目錄項線性構成，記錄著根目錄下每個文件(子目錄)的起始單元、屬性等。FDT大小為32個扇區(qū)，最多可以保存512個目錄項。DATA區(qū)是真正意義上的數(shù)據(jù)存儲的地方，位于FDT之后，占據(jù)外存上的大部分空間[7]。

嵌入式文件系統(tǒng)在進行數(shù)據(jù)存儲時，系統(tǒng)要完成以下的操作：系統(tǒng)要在FDT表（如果文件建立在根目錄下）或存放FDT的數(shù)據(jù)區(qū)中申請一個表項，寫入相應的文件描述符信息也即元數(shù)據(jù)；申請空閑簇，并對FAT表的內容進行修改；將數(shù)據(jù)作為該文件的用戶數(shù)據(jù)寫入相應正確的扇區(qū)等等。讀取文件的操作是通過文件名在外存中找到它的FDT項，通過該項的首簇域在FAT表中找到它的簇鏈，從而可以讀取相應扇區(qū)的數(shù)據(jù)[8]。

3.2 元數(shù)據(jù)一致性設計原理

和桌面系統(tǒng)相比，嵌入式環(huán)境中如存儲空間和CPU的速度等軟硬件資源相對有限，因而以上在桌面環(huán)境中應用的故障恢復機制并不太適合嵌入式系統(tǒng)；第二，如果文件系統(tǒng)可以將元數(shù)據(jù)和用戶數(shù)據(jù)兩種數(shù)據(jù)的一致性都可以維護，顯然代價太高，很多嵌入式環(huán)境并不允許，這里只考慮元數(shù)據(jù)的一致性。借鑒以上恢復機制，再結合FAT16文件系統(tǒng)的特點，提出針對該文件系統(tǒng)的一致性策略，即日志記錄的方法：

（1）在外存中專門開辟一個自由空間來存放日志記錄

該日志不是以文件的形式存儲在外存上，否則，日志也得采用緩存機制來寫入外存，即當寫日志時也要用到文件系統(tǒng)的緩存，這樣在系統(tǒng)崩潰時日志記錄也會存在一致性問題。可以將外存的最后一個扇區(qū)或若干個扇區(qū)作為存儲日志記錄的專用扇區(qū)。這樣外存的存儲結構如下圖：

圖1 外存存儲區(qū)分布圖

（2）日志記錄結構的設計

日志記錄結構包括當前操作的文件名，首簇號，當前扇區(qū)號(如果外存一次寫入一個扇區(qū))，文件所在目錄的開始簇號，當前文件的大小等信息。日志記錄的數(shù)據(jù)結構定義如下：

這樣使得每條記錄共需要32個字節(jié)空間（以ARM9為平臺）。

（3）日志記錄的管理

在文件系統(tǒng)中，涉及到對文件的操作包括：對文件的讀和寫。其中，僅僅對文件的讀操作一般不涉及到對文件信息的修改，所以，只讀操作的文件不記錄它的操作日志，因為即使系統(tǒng)發(fā)生故障，也不會破壞它們的一致性；日志是記錄涉及到對文件信息予以修改的操作，如文件的創(chuàng)建，添加，刪除，重命名或復制等操作。下面分別分析每種操作：

1 ）創(chuàng)建一個文件。創(chuàng)建文件時，系統(tǒng)就要為該文件添加一條FDT表項，當該文件僅僅擁有該表項，而沒有正真的數(shù)據(jù)塊時，不需要為其增加日志記錄，也即只有該文件擁有了正真的數(shù)據(jù)塊且該塊已經存儲在外存時，則需要為其添加日志記錄；

2 ）對一個已經存在的文件添加操作。當執(zhí)行該操作時，只要添加的數(shù)據(jù)塊寫入外存時，則添加相應日志記錄；

3 ）刪除。刪除操作可能刪除某文件的一部分數(shù)據(jù)塊或者刪除整個文件，無論是那種刪除動作，均應添加其相關記錄；

4 ）重命名操作。該操作不涉及到具體數(shù)據(jù)塊的操作，只是對有關FDT表項對應屬性進行修改，也是需要予以記錄；

5 ）復制操作。復制操作涉及到FDT表項的添加，數(shù)據(jù)塊的復制，這些操作均應以日志來記錄相應的操作。

在系統(tǒng)中定義一個和外存存儲日志記錄空間相同的數(shù)據(jù)結構log_REC數(shù)組，數(shù)組中每一項可以記錄一條日志記錄，采用先來先服務的機制來存放日志，當該結構存滿時，一次寫入外存的日志記錄區(qū)中，在寫入該數(shù)據(jù)前，必須將上一次存放的日志記錄調出，并根據(jù)其內容對FAT表項進行相應的修改。

（4）該恢復模塊在系統(tǒng)的位置

該恢復模塊是獨立于FAT16文件系統(tǒng)之外，作為一個專門的功能塊，并不局限于特定的系統(tǒng)，因而可以移植到其他的文件系統(tǒng)。整個系統(tǒng)的組成示意圖如下：

3.3 系統(tǒng)恢復一致性處理過程

系統(tǒng)每次重新啟動時，首先取出日志記錄塊，取出記錄中的第一條記錄項，再通過文件名和該文件的目錄開始簇號查找FDT表中該文件的信息(如果外存中沒有該文件FDT項，則根據(jù)日志記錄創(chuàng)建該文件)，兩者比較，如果相關數(shù)據(jù)一致，則不需要進行修改操作；否則，從FDT中的文件記錄處開始根據(jù)日志記錄的內容對該文件的FAT和FDT的相關數(shù)據(jù)進行修改，直到將日志記錄塊中所有的記錄處理完畢，從而實現(xiàn)該文件系統(tǒng)的一致性。具體流程圖如下：

4.結束語

本文根據(jù)基于FAT16文件系統(tǒng)與嵌入式系統(tǒng)的自身特點，結合了桌面系統(tǒng)應用中的一致性策略，提出日志記錄的恢復機制：彌補了軟更新等技術導致系統(tǒng)嚴重的性能下降的不足，同時在恢復時不需掃描整個系統(tǒng)，提高了恢復處理的速度；和其他基于日志記錄技術相比，修改日志的操作在數(shù)據(jù)塊寫入外存后，這樣執(zhí)行恢復操作時則沒有撤銷的操作，降低了系統(tǒng)復雜性，相對更適合嵌入式環(huán)境。文章詳細分析了該機制的設計原理和實現(xiàn)方法，使得系統(tǒng)在崩潰后能正確恢復，已經存入到外存的數(shù)據(jù)依然被系統(tǒng)正確處理，從而保證了文件系統(tǒng)的一致性。

［1］熊勁，范志華，馬捷，等.DCFS2的元數(shù)據(jù)一致性策略[J].計算機研究與發(fā)展，2005，42（6）：1019-1027.

［2］M.Seltzer，G.Ganger，M.K.Mckusick，K.Smith，et al.Journaling versus Soft Updates:Asynchronours Meta-data Protection in File Systems[C].In USENIX Annual Technical Conference，June 2000: 18~23.

［3］M.Rosenblum and J.K.Ousterhout.The Design and Implementation of a Log-Structured File System[J].ACM Transactions on Computer Systems，1992，10（1）：26~25.

［4］Livio Soares，Orran Krieger，Dilma Da Silva.Meta-data Snapshotting: ASimpleMechanismforFileSystemConsistency[C].InProceedings of SNAPI’03，2003.

［5］吳麗彬，王勁林，孫鵬，等.基于嵌入式文件系統(tǒng)的媒體文件快照技術[J].微計算機應用，2008，29（11）：66-71.

［6］G.Ganmer，M.Mckusick，C.Soules，et al.Soft updates:A solution to the metadata update problem in file systems[J].ACM Trans.Computer Systems，2000，18(2):127-153.

［7］許東亮.嵌入式USB主機文件系統(tǒng)設計與優(yōu)化[J].計算機工程與設計，2008，29（10）：2671-2677.

［8］周立功，等.ARM嵌入式系統(tǒng)軟件開發(fā)實例（一）[M].北京：北京航天航空大學出版社，2004.

TP391

：A

：1672-0547（2010）05-0074-02

2010－05－24

周燕艷（1978－），女，安徽樅陽人，銅陵學院數(shù)學與計算機科學系講師，合肥工業(yè)大學碩士研究生，研究方向：網絡技術、數(shù)據(jù)處理；

海深（1974－），男，安徽無為人，銅陵學院數(shù)學與計算機科學系講師，研究方向：嵌入式系統(tǒng)、自動控制。