基于FAT16元数据一致性的设计

周燕艳 海深

（1.合肥工业大学，安徽合肥 230009；2.铜陵学院，安徽铜陵 244000）

基于FAT16元数据一致性的设计

周燕艳1，2海深2

（1.合肥工业大学，安徽合肥 230009；2.铜陵学院，安徽铜陵 244000）

随着嵌入式系统的不断发展，将数据以某种常用文件系统的形式保存在外存中的方法也得到了越来越广泛的使用。由于嵌入式系统的运行环境和缓存机制的引入，可能导致文件系统的一致性被破坏的可能性更高，因而采取某种应对系统故障的恢复机制显得十分必要。基于对FAT16文件系统，结合已有的一致性方法提出了一种数据恢复机制，以维护系统的一致性。

一致性；FAT16；嵌入式系统；文件系统

1.引言

嵌入式系统来采集现场数据在工业控制、智能家电和车载电子等多个领域已经得到了非常普遍的应用。为了便于上位机的处理，将采集来的数据在嵌入式系统中采用某种上位机所熟悉的文件格式进行存储是一种比较可行的方案，目前已经相继出现相关的研究。以本文的数据存储处理系统为例，系统将从现场采集的数据以FAT16的文件格式存储在U盘中，然后通过USB接口将存储在U盘中的文件在上位机中读出并进行处理。

文件系统是提供组织和管理保存在持久存储介质上的用户数据的手段，文件系统的组成包括用户数据（即文件内容）和元数据（即描述文件系统组织结构的数据）。一个文件操作通常是由一系列更基本的子操作构成，构成一个文件操作的子操作序列是不可分割的整体，因此，文件操作具有与事务类似的ACID特性。如果文件系统的内容（包括用户数据和元数据）是而且仅是所有已成功完成的文件操作按顺序完成的结果，就说这个文件系统是一致的。文件系统在使用过程中有许多中间状态，在这些中间状态时文件系统不一定是一致的，但是在系统稳定时它必须是一致的。如果在中间状态时系统突然崩溃，则可能导致系统的一致性被破坏。另一方面，文件系统广泛使用缓存机制来缓解外存与CPU速度上的差距，缓存引入后，使文件系统在系统崩溃时的不一致问题更加严重[1]。

2.背景及相关研究

文件系统的一致性关系到系统的可用性、完整性等重要方面，当系统崩溃时，文件系统的一致性与否可能直接决定数据能否正常使用甚至系统是否可以恢复。为了实现该目标，一般可以通过在系统崩溃前在永久存储器上已经保存的一些信息来完成恢复系统的一致性操作，从而使得系统依然是一致的。由于文件系统的不一致问题只发生在系统出现故障时，因此维护文件系统的一致性的方法又称为故障恢复技术。

在桌面系统中，维护文件系统一致性主要有以下两种策略：

第一种采用写前日志（write-ahead logging）的方法。如果系统崩溃，在外存中有足够的信息让元数据恢复到一致的状态日志[2]。（journaling）、日志结构[3]（log-structured）及元数据快照[4][5]（meta-data snapshotting）等方法就是基于这种方案。许多现代文件系统就有这些技术的应用，如CedarFS，Episode，JFS，XFS，ext2，ext3，NTFS，BFS，Sprit LFS等。但是，采用日志或日志结构的文件系统对日志自由空间如何管理十分难以设计，将一块数据从一个段移到一个新的位置需要一个专门的空间回收机制；快照技术可以在一个时间点上对文件系统生成一个称为快照的映像，当系统发生故障后，通过以前的快照映像来维护系统的一致性，但是为了存储映像有时需要很多的空间支持。

第二种策略采用对外存数据的更新操作必须要求按照一个严格的操作顺序，这样，系统发生故障时，即使外存上的元数据不能正确无误，系统的一致性仍然可以保证。如FFS通过将每一个元数据块采用同步写的手段来实现这个目标，而软更新[6]（soft updates）则采取一个规定操作序列来维护文件系统的一致性。但是使用此种方法恢复系统，如回滚（rollback）操作，可能产生频繁的I/O操作而导致系统整体的性能损失。

3.FAT16一致性策略的设计

3.1 FAT16文件系统原理与结构

FAT16文件系统是Microsoft较早推出的文件系统，具有高度兼容性，目前仍然广泛应用于嵌入式存储设备中，这里对FAT16做简要介绍。FAT格式的磁盘上数据大致可分为5部分：MBR区、DBR区、FAT区、FDT区和DATA区。MBR区又称为主引导记录，其后为64字节的磁盘分区表(disk partition table，DPT)。DBR区即操作系统引导记录区，占用一个扇区，共512个字节，由跳转指令、BPB、结束标志几部分组成。FAT区用于存放文件分配表(file allocation table，FAT)。文件分配表是一一对应于数据区簇号的列表，反映了所有簇的使用情况。每个表项单元的大小决定了FAT的类型，比如FAT16的表项单元为16位。FAT表一般都有一个备份。FDT区存放着文件目录表，位于备份FAT表之后。FDT由32位的目录项线性构成，记录着根目录下每个文件(子目录)的起始单元、属性等。FDT大小为32个扇区，最多可以保存512个目录项。DATA区是真正意义上的数据存储的地方，位于FDT之后，占据外存上的大部分空间[7]。

嵌入式文件系统在进行数据存储时，系统要完成以下的操作：系统要在FDT表（如果文件建立在根目录下）或存放FDT的数据区中申请一个表项，写入相应的文件描述符信息也即元数据；申请空闲簇，并对FAT表的内容进行修改；将数据作为该文件的用户数据写入相应正确的扇区等等。读取文件的操作是通过文件名在外存中找到它的FDT项，通过该项的首簇域在FAT表中找到它的簇链，从而可以读取相应扇区的数据[8]。

3.2 元数据一致性设计原理

和桌面系统相比，嵌入式环境中如存储空间和CPU的速度等软硬件资源相对有限，因而以上在桌面环境中应用的故障恢复机制并不太适合嵌入式系统；第二，如果文件系统可以将元数据和用户数据两种数据的一致性都可以维护，显然代价太高，很多嵌入式环境并不允许，这里只考虑元数据的一致性。借鉴以上恢复机制，再结合FAT16文件系统的特点，提出针对该文件系统的一致性策略，即日志记录的方法：

（1）在外存中专门开辟一个自由空间来存放日志记录

该日志不是以文件的形式存储在外存上，否则，日志也得采用缓存机制来写入外存，即当写日志时也要用到文件系统的缓存，这样在系统崩溃时日志记录也会存在一致性问题。可以将外存的最后一个扇区或若干个扇区作为存储日志记录的专用扇区。这样外存的存储结构如下图：

图1 外存存储区分布图

（2）日志记录结构的设计

日志记录结构包括当前操作的文件名，首簇号，当前扇区号(如果外存一次写入一个扇区)，文件所在目录的开始簇号，当前文件的大小等信息。日志记录的数据结构定义如下：

这样使得每条记录共需要32个字节空间（以ARM9为平台）。

（3）日志记录的管理

在文件系统中，涉及到对文件的操作包括：对文件的读和写。其中，仅仅对文件的读操作一般不涉及到对文件信息的修改，所以，只读操作的文件不记录它的操作日志，因为即使系统发生故障，也不会破坏它们的一致性；日志是记录涉及到对文件信息予以修改的操作，如文件的创建，添加，删除，重命名或复制等操作。下面分别分析每种操作：

1 ）创建一个文件。创建文件时，系统就要为该文件添加一条FDT表项，当该文件仅仅拥有该表项，而没有正真的数据块时，不需要为其增加日志记录，也即只有该文件拥有了正真的数据块且该块已经存储在外存时，则需要为其添加日志记录；

2 ）对一个已经存在的文件添加操作。当执行该操作时，只要添加的数据块写入外存时，则添加相应日志记录；

3 ）删除。删除操作可能删除某文件的一部分数据块或者删除整个文件，无论是那种删除动作，均应添加其相关记录；

4 ）重命名操作。该操作不涉及到具体数据块的操作，只是对有关FDT表项对应属性进行修改，也是需要予以记录；

5 ）复制操作。复制操作涉及到FDT表项的添加，数据块的复制，这些操作均应以日志来记录相应的操作。

在系统中定义一个和外存存储日志记录空间相同的数据结构log_REC数组，数组中每一项可以记录一条日志记录，采用先来先服务的机制来存放日志，当该结构存满时，一次写入外存的日志记录区中，在写入该数据前，必须将上一次存放的日志记录调出，并根据其内容对FAT表项进行相应的修改。

（4）该恢复模块在系统的位置

该恢复模块是独立于FAT16文件系统之外，作为一个专门的功能块，并不局限于特定的系统，因而可以移植到其他的文件系统。整个系统的组成示意图如下：

3.3 系统恢复一致性处理过程

系统每次重新启动时，首先取出日志记录块，取出记录中的第一条记录项，再通过文件名和该文件的目录开始簇号查找FDT表中该文件的信息(如果外存中没有该文件FDT项，则根据日志记录创建该文件)，两者比较，如果相关数据一致，则不需要进行修改操作；否则，从FDT中的文件记录处开始根据日志记录的内容对该文件的FAT和FDT的相关数据进行修改，直到将日志记录块中所有的记录处理完毕，从而实现该文件系统的一致性。具体流程图如下：

4.结束语

本文根据基于FAT16文件系统与嵌入式系统的自身特点，结合了桌面系统应用中的一致性策略，提出日志记录的恢复机制：弥补了软更新等技术导致系统严重的性能下降的不足，同时在恢复时不需扫描整个系统，提高了恢复处理的速度；和其他基于日志记录技术相比，修改日志的操作在数据块写入外存后，这样执行恢复操作时则没有撤销的操作，降低了系统复杂性，相对更适合嵌入式环境。文章详细分析了该机制的设计原理和实现方法，使得系统在崩溃后能正确恢复，已经存入到外存的数据依然被系统正确处理，从而保证了文件系统的一致性。

［1］熊劲，范志华，马捷，等.DCFS2的元数据一致性策略[J].计算机研究与发展，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］吴丽彬，王劲林，孙鹏，等.基于嵌入式文件系统的媒体文件快照技术[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主机文件系统设计与优化[J].计算机工程与设计，2008，29（10）：2671-2677.

［8］周立功，等.ARM嵌入式系统软件开发实例（一）[M].北京：北京航天航空大学出版社，2004.

TP391

：A

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

2010－05－24

周燕艳（1978－），女，安徽枞阳人，铜陵学院数学与计算机科学系讲师，合肥工业大学硕士研究生，研究方向：网络技术、数据处理；

海深（1974－），男，安徽无为人，铜陵学院数学与计算机科学系讲师，研究方向：嵌入式系统、自动控制。