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

周燕艷 海深

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

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

周燕艷1，2海深2

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

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

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

1.引言

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

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

2.背景及相關(guān)研究

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

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

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

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

3.FAT16一致性策略的設(shè)計(jì)

3.1 FAT16文件系統(tǒng)原理與結(jié)構(gòu)

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

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

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

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

（1）在外存中專門(mén)開(kāi)辟一個(gè)自由空間來(lái)存放日志記錄

該日志不是以文件的形式存儲(chǔ)在外存上，否則，日志也得采用緩存機(jī)制來(lái)寫(xiě)入外存，即當(dāng)寫(xiě)日志時(shí)也要用到文件系統(tǒng)的緩存，這樣在系統(tǒng)崩潰時(shí)日志記錄也會(huì)存在一致性問(wèn)題。可以將外存的最后一個(gè)扇區(qū)或若干個(gè)扇區(qū)作為存儲(chǔ)日志記錄的專用扇區(qū)。這樣外存的存儲(chǔ)結(jié)構(gòu)如下圖：

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

（2）日志記錄結(jié)構(gòu)的設(shè)計(jì)

日志記錄結(jié)構(gòu)包括當(dāng)前操作的文件名，首簇號(hào)，當(dāng)前扇區(qū)號(hào)(如果外存一次寫(xiě)入一個(gè)扇區(qū))，文件所在目錄的開(kāi)始簇號(hào)，當(dāng)前文件的大小等信息。日志記錄的數(shù)據(jù)結(jié)構(gòu)定義如下：

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

（3）日志記錄的管理

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

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

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

3 ）刪除。刪除操作可能刪除某文件的一部分?jǐn)?shù)據(jù)塊或者刪除整個(gè)文件，無(wú)論是那種刪除動(dòng)作，均應(yīng)添加其相關(guān)記錄；

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

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

在系統(tǒng)中定義一個(gè)和外存存儲(chǔ)日志記錄空間相同的數(shù)據(jù)結(jié)構(gòu)log_REC數(shù)組，數(shù)組中每一項(xiàng)可以記錄一條日志記錄，采用先來(lái)先服務(wù)的機(jī)制來(lái)存放日志，當(dāng)該結(jié)構(gòu)存滿時(shí)，一次寫(xiě)入外存的日志記錄區(qū)中，在寫(xiě)入該數(shù)據(jù)前，必須將上一次存放的日志記錄調(diào)出，并根據(jù)其內(nèi)容對(duì)FAT表項(xiàng)進(jìn)行相應(yīng)的修改。

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

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

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

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

4.結(jié)束語(yǔ)

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

［1］熊勁，范志華，馬捷，等.DCFS2的元數(shù)據(jù)一致性策略[J].計(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)的媒體文件快照技術(shù)[J].微計(jì)算機(jī)應(yīng)用，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主機(jī)文件系統(tǒng)設(shè)計(jì)與優(yōu)化[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29（10）：2671-2677.

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

TP391

：A

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

2010－05－24

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

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