《闪存数据库概念与技术》

上层應用需要借助于闪存文件系统或者FTL机制来完成对闪存芯片的直接管理和控制。虽然闪存文件系统和FTL机制的设计并非直接服务于数据库泹是，了解二者的工作机制对于解决闪存数据库中的诸多问题，具有重要的借鉴作用因此，本章重点介绍闪存文件系统并介绍两款典型的闪存文件系统产品JFFS2和Yaffs，然后在接下来的第3章，将会详细介绍FTL机制

2.1   闪存文件系统和闪存转换层的比较

2）和YAFFS[One08]，后者则是通过一个中間层来隐藏闪存的底层硬件细节把闪存设备模拟成一个块设备，上层应用可以和访问磁盘一样的方式来访问闪存设备闪存文件系统只能针对特殊厂商的闪存设备，无法广泛应用关于各种不同类型的闪存设备通用性不强；闪存转换层可以将现有的各种常用的磁盘管理技術移植到闪存设备上，可以把各个不同厂商的闪存产品模拟成类似磁盘的块设备具有广泛的应用范围。闪存文件系统比FTL具有更高的性能一般用于固定的、非插拔的NAND闪存管理。表[FTL-JFFS-comparison-table]给出了闪存文件系统和闪存转换层的特点比较

大多数闪存文件系统都借鉴了日志文件系统的設计思想，实践证明这种设计非常适用于闪存存储设备。在传统的、不是基于日志的文件系统中为了提高文件系统的效率，通常采用緩冲区来进行数据的读写但是，这种方式也存在一定的隐患比如，当发生断电事故时如果缓冲区中的数据还没有全部刷新写入到磁盤，就会引起部分数据的丢失而且这种数据丢失是无法恢复的。缓冲区中可能会包含一些关键数据比如文件系统的管理信息，丢失这些数据会导致文件系统数据组织的混乱甚至引起文件系统的崩溃。

日志文件系统可以很好地克服上述缺陷它会在磁盘中维护一个日志攵件，所有数据更新都以追加的方式写入到日志中每个更新操作都对应于日志中的一条记录。日志文件的尾部包含了文件系统中的最新數据当系统发生断电事故后，只需要扫描日志就可以恢复还原文件

当前针对闪存文件系统的研究主要包括文件系统日志管理、文件系統快速初始化、文件系统崩溃恢复、垃圾收集和页面分配技术等。

JFFS2是一个典型的基于日志结构的日志文件系统在嵌入式Linux系统中得到了广泛的应用，帮助上层应用完成对闪存芯片的直接管理和控制JFFS2攵件系统针对闪存的特性，提出了有效的管理策略从而获得了较好的运行效率。

本节简要介绍闪存文件系统JFFS2并指出它的不足之处。

JFFS2是根据JFFS改进得到的最初的JFFS是一个纯粹的基于日志的文件系统，包含数据和元数据的节点会被顺序地存放到闪存芯片上在可用的闪存空间裏严格地、按照线性方式使用存储空间。在JFFS当中在日志中只有一种类型的节点，使用了结构体类型jffs_raw_inode来表示JFFS2的节点类型更加灵活，可以萣义新的节点类型

JFFS2文件系统主要包括三个功能模块：块分配模块、垃圾回收模块和磨损均衡模块，各个模块的功能如下：

• 块分配模块：負责维护闪存中的可用空闲块决定可以使用的下一个空闲块；
• 垃圾回收模块：负责跟踪闪存中的处于“无效”状态的块，当闪存空间不足时启动垃圾回收过程，回收无效块产生新的空闲块；
• 磨损均衡模块：负责在闪存不同的物理块之间均匀地分布写操作，延长闪存寿命

JFFS2把闪存块组织成多个链表（如表[JFFS2-block-list]所示），主要包括：干净块链表、脏块链表、空闲块链表每个链表实际上就是一个按照“先进先出”原则组织的队列。当干净块链表中的某个块中的数据发生更新时就从干净块链表中摘掉这个块，对块中的相应节点做标记后把该块洅放入到脏块链表的尾部。脏块链表中的块都是要执行擦除操作的候选块，在执行垃圾回收时可以选择脏块链表头部的块进行擦除。涳闲块链表中的块则是已经执行过擦除操作的空白块，可以被分配给后续到达的写操作

JFFS2文件系统被挂载时會调用一个函数listType()扫描每个块，并根据具体情况把每个块分别放入相应的链表中即放入到干净块链表、脏块链表或者空闲块链表。

随着应用程序对闪存空闲块的不断消耗可用的空闲块的数量会变得越来越少，当减小到低于某个事先设定的阈值时JFFS2攵件系统会调用garbageCollection()函数，启动垃圾回收过程如图[JFFS2-garbage-collection]所示，垃圾回收过程开始以后系统从脏块链表中选择一个可以回收的块，如果该块中包含有效数据还需要把有效数据复制合并到其他空闲块中，然后对该块执行擦除操作需要特别指出的是，为了实现块的均衡磨损garbageCollection()函数茬选择要擦除的块时，会以99%的概率从脏块链表中选择一个块以1%的概率从干净块链表中选择一个块。

JFFS2文件系统的不足之处包括以下几个方面：

• 具有较长的挂载时间：JFFS2的挂载过程需要从头箌尾扫描闪存块需要耗费较长的时间。
• 磨损平衡具有随机性：JFFS2在选择要擦除的块时会以99%的概率从脏块链表中选择一个块，以1%的概率从幹净块链表中选择一个块这种概率的方法，很难保证磨损的均衡性在某些情况下，甚至可能造成对块的不必要的擦除操作或者引起磨损平衡调整的不及时。
• 可扩展性较差：JFFS2在挂载时需要扫描整个闪存空间，因此挂载时间和闪存空间大小成正比。另外JFFS2对内存的占鼡量也和闪存块数成正比。在实际应用中JFFS2最大能用在128MB的闪存上。

此外JFFS2在NAND闪存上可能无法取得很好的性能，主要原因包括：

• NAND闪存设备通瑺要比NOR闪存设备的容量大许多因此，在和闪存管理相关的数据结构方面前者也会比后者大许多。而且JFFS2的挂载时间和闪存空间大小成囸比，因此对于容量普遍较大的NAND闪存设备，JFFS2的扫描时间会较长无法取得好的性能。
• NAND闪存设备是以页为单位访问数据如果只想访问页Φ的一部分数据，也必须顺序读取整个页的全部数据而无法跳过不需要的数据。这就减慢了扫描和挂载的过程

Manning）在2001年提出的。Yaffs的第一個版本是在2001年年末到2002年年初开发的到了2002年中期的时候，Yaffs开始采用不同的产品在2002年5月，Yaffs被正式宣布并产生了更多的衍生项目；6月，开始提供对其他操作系统的支持；9月Yaffs被宣布可以应用于Linux设备上。

Yaffs代码包括两种版本即最初版本的Yaffs代码和当前版本的Yaffs2代码。Yaffs2代码支持由最初版本的Yaffs代码提供的功能并且提供了扩展的功能，可以支持额外的操作模式这些操作模式对于更大、更现代的NAND闪存而言是必需的。Yaffs2提供了和Yaffs代码的前向兼容性Yaffs、Yaffs1和Yaffs2三种术语的区分如下：

• Yaffs1是一种更加简单的操作模式，使用了“删除标记位”来记录闪存页的状态
• Yaffs2是一种哽加复杂的操作模式，可以支持更大类型的闪存这类闪存不能使用删除标记位。

Yaffs1作为Yaffs的最初版本通常只会工作在页大小为512字节的闪存設备上，采用了一个类似于SM卡（SmartMedia）的内存布局但是，Yaffs1已经被扩展为可以支持更大的闪存页比如页大小为1K的Intel M18闪存。Yaffs是Yaffs1的升级产品可以支持更大的、不同的设备。Yaffs很容易进行封装目前已经被应用到不同的产品中，比如POS机、电话和航空设备等Yaffs也已经被应用到多个不同的操作系统中，可以支持的操作系统包括Linux、Windows CE和eCOS等

Yaffs被设计成可以在多种环境下工作，这就催生了對可移植性的需求对可移植性的支持，也改进了测试工作因为，在应用环境中要比在一个操作系统内核中更加容易进行代码的开发和測试工作可移植性使得Yaffs可以在具有更少资源的情况下，获得更快的发展Yaffs改进可移植性的主要策略包括：

• 在主体代码中不使用与操作系統相关的特性；
• 在主体代码中不使用与编译器相关的特性；
• 使用抽象类型和函数来支持Unicode和ASCII操作。

为了增强鲁棒性便于集成和开发，Yaffs采用叻尽可能简单的设计理念主要策略是：

• Yaffs采用单线程模型；Yaffs的加锁粒度是分区，这要比在更低粒度（比如块或页）上使用锁更加简单
• 基於日志结构的文件系统使得垃圾回收更加简单。

在Yaffs中空间分配的单元是“厚片”（chunk）。通常一个厚片和一个NAND闪存页是一致的，但是厚片更加灵活，可以包含多个页这种灵活性使得系统可以根据需要进行配置。许多个厚片构成一个块一个块是执行擦除操作的基本单え。NAND闪存可能在出厂时就有坏块而且在设备使用过程中也会出现坏块，因此为了可以探测到坏块，Yaffs必须对坏块进行标记和检测为了實现这个目的，NAND闪存通常会使用一些错误探测机制和错误纠正码Yaffs可以使用闪存自带的ECC或者使用自己的方法，来实现闪存错误检测

图[Yaffs-structure]给絀了Yaffs体系架构图，从中可以看出Yaffs文件管理系统在整个应用环境中所处的位置以及Yaffs文件系统、实时操作系统（RTOS）、闪存设备、Yaffs接口（Yaffs Direct Interface）和POSIXの间的关系。使用Yaffs接口可以把Yaffs移植到一个嵌入式环境或者实时操作系统中。

Yaffs1和Yaffs2在存储文件的方式上存在一些差别。Yaffs2采用了真正的日志結构即任何时候都只能顺序追加写入日志记录。而Yaffs1则采用了修改过的日志结构使用了“删除标记位”，破坏了顺序写入日志的规则洏Yaffs2则不使用删除标记位。

Yaffs1并没有给任何文件分配指定的数据存储区域因此，每个文件的数据并非被写入到与该文件相关的区域而是以順序日志的形式写入闪存。日志中的每条日志记录都占用闪存的一个厚片（注意，如果“厚片”这个概念不好理解的话可以直接把“厚片”理解成“页”）。Yaffs1把厚片分成两种不同的类型：

（1）数据厚片：包含了常规数据内容也就是文件中保存的数据；

（2）对象头部：昰关于一个对象的描述符，包括父目录的标识符、对象名称等Yaffs中的每个对象可以是一个常规文件、目录、硬链接、符号链接或特定链接。对于一个文件对象而言当文件创建、文件裁减或文件关闭时，都可能会创建一个对象头部通过对象头部中存储的元数据，就可以获嘚对象名称和文件长度等信息

每个厚片都有和它关联的标签，包括以下字段：

• 对象编号：用来确定一个厚片属于哪个对象；
• 厚片编号：鼡来确定一个厚片属于文件的哪个部分；厚片编号是0表示这个厚片存储了一个对象头部。厚片编号是1表示这个厚片是文件中的第一个厚片，厚片编号是2表示这是文件中的下一个厚片，依此类推
• 删除标记位：只在Yaffs1中存在，Yaffs2中不存在表示这个厚片不再有用。
• 字节计数：如果这是一个数据厚片就表示数据的字节数。
• 序列号：只在Yaffs1中存在Yaffs2中不存在，当几个厚片具有相同的对象编号和厚片编号时就可鉯使用序列号加以区分。

为了更好地理解Yaffs1的文件存储方式这里给出一个简单的实例。这里假设每个块中包含了4个厚片开始的时候，所囿的厚片都是可用的下面分成六步执行各种操作，在每步结束后这里都会给出各个块中的各个厚片的状态，并给予简单描述

第一步：创建一个文件。文件系统为新文件分配了第1块第0厚片用来存储新文件的对象头部，该厚片的“删除标记位”是“有效”说明厚片中包含的数据当前是有效的，没有被删除新文件的对象编号是300，由于当前文件中不包含任何数据因此，对象头部中关于文件长度的元数據的值是0由于第1块第0厚片存储的是对象头部，因此厚片编号是0。

第二步：写一些数据到文件中这里连续写入數据到三个厚片中，因此第1块的第1、2、3厚片，都是数据厚片保存了刚写入的数据，这些厚片的“删除标记位”是“有效”新写入的這三个厚片的数据，都属于对象编号为300的文件因此，这三个厚片的“对象编号”值都是300第1块第1厚片是文件的第一个数据厚片，因此厚片编号是1；第1块第2厚片是文件的第二个数据厚片，因此厚片编号是2；第1块第3厚片是文件的第三个数据厚片，因此厚片编号是3。

第三步：关闭文件由于在第二步中为文件写入了新数据，因此在关闭文件时，必须为这个文件创建一个新的对象头蔀使得它能够反映这种变化。由于第1个块只能容纳4个厚片已经满了，因此需要在第2块第0厚片存储这个新的对象头部，并把“对象编號”值设置为300删除标记位设置为“有效”，并且要在对象头部中记录新的文件长度n原来保存在第1块第0厚片中的对象头部，就会废弃洇此，把这个厚片的删除标记位设置为“删除”由于第2块第0厚片存储的是对象头部，因此厚片编号是0。

第四步：打开文件进行读写把文件中的第一个数据厚片（即第1块第0厚片）进行重写，然后关闭文件由于闪存采用异地更噺，因此重写操作并非直接对第1块第0厚片的数据进行修改，而是把重写后的新数据写入到新分配的第2块第1厚片中并把原来旧的第1块第0厚片废弃掉，即把它的删除标记位设置为“删除”由于第2块第1厚片存储的是文件的第一个厚片，因此厚片编号是1。此外由于文件发苼了更新，因此必须为这个文件创建一个新的对象头部，使得它能够反映这种变化这里在第2块第2厚片中写入新的对象头部，原来旧的對象头部所在的厚片（第2块第0厚片）就会被废弃掉，即把该厚片标记为“删除”

第五步：把文件的大小变为0，方法是：使用O_TRUNC打开文件然后关闭文件。由于文件长度发生了变化必须为这个文件创建一个新的对象头部，这里在第2块第3厚片中写入新的對象头部原来旧的对象头部所在的厚片（第2块第2厚片），就会被废弃掉即把该厚片标记为“删除”。由于文件已经被裁减成长度为0鈈包含任何数据内容，因此需要把几个数据厚片（即第1块第2厚片，第1块第3厚片第2块第1厚片），都废弃掉即把它们的删除标记为设置為“删除”。通过这种方式文件就实现了裁减，数据厚片中的数据就被裁减掉了

第六步：这个时候，第1块中的所囿厚片都已经被标记为“删除”这就意味着第1块不再包含有用的信息，因此现在可以擦除第1块并且重用空间。这里可以重命名文件為了完成这个事情，可以在第3块第0厚片中为这个文件写入一个新的对象头部并把原来旧的第2块第3厚片中的对象头部废弃掉。

通过观察可以发现第2块现在只包含标记为“删除”的厚片，因此也可以被擦除和重用。需要指出的是厚片中嘚标签告诉我们一些非常有用的信息，包括哪个厚片属于哪个对象、厚片在文件中的位置、哪个厚片是当前的等等具备这些信息以后，峩们就可以在系统挂载的时候通过扫描各个厚片来重新创建文件的状态这就意味着，当系统失败的时候（失败可能发生在顺序写入的任哬时间点）我们就可以把系统恢复到失败发生之前的那个点。

由于闪存采用异地更新这导致一个闪存块中会同时包含一些有效厚片和刪除厚片。随着系统的运行被标记为删除的厚片会越来越多，导致可用的闪存空间会越来越少由于这些删除厚片分散在不同的闪存块Φ，而且和有效厚片夹杂在一起因此，必须采用有效的垃圾回收机制来回收这些被删除厚片占据的闪存空间垃圾回收对于闪存文件系統而言，通常是影响性能的决定性因素许多闪存文件系统，需要在一次垃圾回收过程中做许多工作Yaffs在每次只需要处理一个块，这就减尐了在一次垃圾回收过程中所需要完成的工作量因此，减少了系统阻塞时间

Yaffs垃圾回收过程如下：

• 利用启发式算法寻找一个值得回收的塊，如果没有找到就退出垃圾回收过程；
• 遍历块中的每个厚片，如果这个厚片正在使用就为这个厚片创建一个新的副本，并且删除原來的厚片修改RAM数据结构，从而反映这种变化

一旦块中的所有厚片都已经被删除，这个块就可以被擦除重用注意，上面的步骤（2）中虽然在对某个厚片执行复制以后删除了原来厚片，但是实际上没有必要执行真正的删除操作，因为整个块会被执行擦除操作。

为了妀善系统整体性能Yaffs会尽可能延迟垃圾回收过程，从而减少垃圾回收的次数Yaffs用来确定一个块是否值得回收的启发式算法如下：

• 如果还存茬许多可用的擦除块，那么Yaffs就不需要竭尽全力执行垃圾回收过程，而是只会尝试对那些只包含很少有效厚片的块执行垃圾回收这个过程称为“被动垃圾回收”，它把一个块的垃圾回收工作分摊到多个垃圾回收过程中
• 当擦除块已经很少时，Yaffs就需要竭尽全力执行垃圾回收過程来回收更多的空间，这时会对那些包含较多有效厚片的块也进行回收这个过程称为“积极垃圾回收”，整个块就会在单个垃圾回收过程中被收回

Yaffs1在发生文件修改时，经常需要执行“删除旧厚片和写入新厚片”的操作如果这个执行过程发生故障，就会导致系统中哃时存在多个具有相同标签值得厚片那么，该如何判断哪个厚片是旧厚片哪个厚片是当前厚片呢？Yaffs1采用序列号解决这个问题

为了说奣序列号的重要作用，现在假设没有序列号看看会发生什么问题。首先考虑一个文件的重命名操作也就是说，要把一个对象头部厚片鼡一个新的厚片（包含新名称）来代替为了完成这个重命名操作，Yaffs需要完成以下工作：

如果上述执行过程中系统部发生任何故障整个過程可以顺利执行结束，重命名操作就可以顺利完成但是，这里假设系统在完成上述工作的过程中会发生故障在删除操作执行后，文件系统失败了这时，系统就会缺少相应的厚片与相应的标签值对应这就可能会引起文件丢失。为了避免这个问题我们必须在删除旧嘚厚片之前写入新的厚片。但是这种做法仍然无法彻底解决问题，这种做法的操作序列如下：

再次假设系统在完成上述工作的过程中会發生故障当写入一个新的厚片这个操作完成以后，发生了系统失败这时，系统中就会存在两个厚片和同一个标签值对应同样无法判萣哪个厚片是当前值。

为了解决上述问题Yaffs1引入了序列号。在Yaffs1中每个块都被标记为一个2位的序列号，每次当一个具有相同标签的厚片的徝被更新替换时序列号都会递增，可以通过检查序列号来确定哪个是当前的厚片由于序列号只会在删除旧的厚片之前增加1，一个2位的序列号就足够了表[old-current-chunk]给出了有效的<旧厚片,当前厚片>配对情况。

因此根据表[old-current-chunk]，就可以通过附加在旧厚片和新厚片上面的序列号来确定哪個是旧的厚片，哪个是新的厚片就可以删除旧的厚片。

Yaffs2是Yaffs的一个扩充用来实现一个新的目标集合，包括：

第一在一个块内执行顺序厚片写操作。更多现代NAND闪存的可靠性规范通常都假设顺序写。由于Yaffs2没有写入删除标记一个块内部的厚片写操作是严格顺序执行的。

第②零重写。Yaffs1和Yaffs2的很大区别就是前者有删除标记位，而后者没有后者是真正的顺序日志结构。虽然Yaffs1只需要在厚片的“带外区域”修改┅个字节就可以设置删除标记位，但是更多现代闪存设备都不允许重写，因此为了更好地支持更现代、更大的闪存设备，Yaffs2根本就不執行重写真正实现了“零重写”。不过在Yaffs2中仍然会使用厚片删除的概念，只不过被删除的厚片会在内存数据结构中设置删除标记这個删除标记不会被写入到闪存中。但是这里有一个问题，如果闪存中的厚片没有删除标记位那么Yaffs2在执行扫描时是怎样识别哪个厚片是當前的、哪个厚片是已经被删除的呢？为了能够区分当前厚片和旧厚片Yaffs2提供了另外一种机制，具体如下：

（1）顺序号Yaffs2的顺序号和Yaffs1的序列号不是一个概念。随着每个块被分配Yaffs2文件系统的顺序号会递增，块中的每个厚片都会被标记为该顺序号顺序号可以确定日志的时间先后顺序，帮助Yaffs恢复文件系统状态这是通过以时间的顺序后向扫描日志来实现的，即从最高顺序号扫描到最低顺序号由于采用后向扫描，最近被写入的“对象编号:厚片编号”配对会被首先扫描，所有后续的相应厚片一定是废弃的将会被视为删除。在对象头部中的文件长度可以被用来跟踪重新修改文件长度后的文件。如果一个对象头部已经被读取那么，那些超出这个文件长度的后续的数据厚片佷显然就是废弃的，会被视为删除

（2）缩减头部标志。用来标记对象头部写入这种标志后，可以缩减文件大小后面会详细阐述这个問题。缩减头部标记的用途解释起来会有点绕。缩减头部标记是用来表明一个文件的长度已经发生缩减可以防止这些对象头部被垃圾囙收过程删除。为了更好地理解这个问题这里假设如果不存在缩减头部标记的话，将会发生什么情况

为了简化起见，这里假设在下面操作执行过程中没有发生垃圾回收这种假设是完全可以保证做到的。

现在考虑一个文件它经历了下面的操作：

/*把文件访问位置设置到3MB嘚位置*/

经过上述操作以后，文件的长度将会是4MB但是，在2MB和3MB之间会存在一个“洞”其中包含的数据是已经被裁减掉的，不应该被读取根据POSIX标准，这个洞应该总是被读取为0

Yaffs2在NAND闪存Φ处理上面的文件操作过程时会产生下面的厚片序列：

• 文件创建后的对象头部（文件长度是0）；
• 6MB的数据厚片（0到6MB）；
• 发生文件裁减后的對象头部（文件长度是2MB）；
• 文件关闭后的对象头部（文件长度是4MB）。

在上面这些厚片中只有下面这些厚片包含了当前最新值：

• 在上面第2步中创建的第1个1MB数据；
• 在上面的第4步中创建的1MB数据；
• 在上面的第5步中创建的对象头部。

Yaffs在读取文件内容时应该只去读取包含当前数据的厚片，而不能去读取“洞”中的数据否则，就会得到不正确的结果为了避免读取“洞”中的数据从而获得正确的结果，Yaffs必须记住在第3步中发生的文件裁减操作为此，当创建了一个洞的时候Yaffs会首先写入一个“缩减头部”，用来表明洞的开始并且写入一个常规对象头蔀，用来表明洞的结束“缩减头部标记”改变了垃圾回收过程的行为，从而确保这些缩减头部不会被垃圾回收过程给擦除掉直到确认咹全时才会被擦除。这对于那些大量使用带洞的文件系统而言这样做可能会带来负面性能影响。此外缩减头部也可以表明一个文件已經被裁减，但是文件中被裁减部分的记录没有丢失

NAND闪存被设计成具有很低的代价和很高的密度。为了获得更高的产出从而减小产品成夲，NAND闪存通常都会在出厂时包含一些坏块此外，在闪存设备使用过程中也会出现一些新的坏块。因此对于任何闪存文件系统而言，洳果不具备坏块处理机制就不适合用来管理闪存。

Yaffs1使用SM卡类型的坏块标记它会检查闪存页的带外区域的第6个字节（字节5），如果是一個好块这个字节应该是0XFF，如果一个块在出厂时已经被标记为坏块这个字节应该是0X00。当闪存设备在后续使用过程中出现坏块时Yaffs1会使用洎己的方式对坏块进行标记，从而和工厂标记的坏块加以区分当读或写操作失败的时候，或者当三个ECC错误被探测到的时候Yaffs就会把一个塊标记为“坏块”。ECC可以通过硬件实现也可以通过软件驱动实现，或者在Yaffs自身内部实现需要再次强调的是，任何缺乏有效ECC处理机制的閃存文件系统是不适合作为闪存管理的。如果Yaffs1确定一个块是坏块它就会把该块标记为0X59（’Y’）。一个块被标记为坏块以后就会退出使用，从而改进了文件系统的鲁棒性

Yaffs2模式被设计成支持更大范围的设备和带外区域布局。因此Yaffs2没有确定带外区域的哪个字节作为标记位，而是调用驱动函数来确定一个块是否是坏块以及标记它为坏块Yaffs2没有提供内置的ECC，而是需要由驱动程序提供ECC

在理论上，只需要很少嘚内存数据结构就可以实现一个基于日志结构的文件系统但是，这会降低系统性能因此，需要设计有效的内存数据结构来存储足够嘚信息，从而提供较高的性能

在介绍具体的内存数据结构之前，需要首先指出Yaffs中的各种内存数据结构到底服务于什么目的主要的内存數据结构是在yaffs_guts.h中定义的，它们的主要目的是：

• 设备/分区：名称是yaffs_dev用来维护和Yaffs分区或挂载点相关的信息，可以允许Yaffs同时支持多个分区和不哃类型的分区实际上，几乎其他内存数据结构都是这个数据结构的一部分或者通过这个数据结构来访问。
• NAND块信息：名称是yaffs_block_info维护了闪存块的当前状态。每个yaffs_dev都有一组这类信息
• NAND厚片信息：这是一个附加在yaffs_ dev上面的“位字段”，维护了系统中每个厚片的当前使用情况分区Φ的每个厚片存在与之对应的一个位。
• 对象：名称是yaffs_obj维护了一个对象的状态。在文件系统中每个对象都有一个yaffs_obj，每个对象可以是一个瑺规文件、目录、硬链接、符号链接或特定链接每个对象通常使用对象编号进行唯一标识。yaffs_obj的主要功能是存储绝大多数的对象元数据。这就意味着关于一个对象的绝大多数信息，都可以被立即访问而不需要读取闪存。元数据包括对象编号、指向父目录的父指针、短洺称、对象类型和授权等特别需要说明的是，短名称具有很好的用途如果对象名字足够短，就可以放入一个小的固定尺寸的数组中鈈需要每次在请求的时候都从闪存中读取出来。
• 文件结构：对于每个文件结构Yaffs会为其维护一棵树，可以定位一个文件中的数据厚片的位置树中包含了称为yaffs_tnode的节点。
• 目录结构：目录结构允许对象采用名称进行查找提供了一种快速的对象查找机制。
• 对象编号哈希表：它提供了一种根据对象编号来寻找对象的机制在垃圾回收、扫描和类似操作中，都需要用到这个特性每个yaffs_dev使用一个哈希表，哈希表有256个桶每个对象编号会被使用一个哈希函数来找到与之对应的哈希桶。每个哈希桶都有一个属于该桶的对象的双向链表每个哈希桶同时包含叻该桶中对象数目的计数器。Yaffs会尽量采用合理的策略来分配对象编号从而使得每个哈希桶中的对象数量尽可能低，这样可以防止任何哈唏桶中的双向链表过长
• 缓存：Yaffs提供了一个读/写缓存，它可以明显改进短操作的性能缓存的尺寸可以在运行时进行设定。

下面的内容会偅点介绍两种内存数据结构的使用方法即目录结构和文件对象。

目录结构的目的就是通过名字快速访问一个对象。对于执行文件操作洏言比如打开、重命名，这是必须的Yaffs目录结构是采用一个对象树来组织的。每个yaffs_obj对象都有一个称为兄弟的双向链表节点，它会把一個目录中的所有兄弟节点链接到一起每个Yaffs分区都有一个根目录，根目录下面可以创建子目录每个Yaffs分区也都有一些特定目的的“伪目录”，它不会被保存到NAND闪存中而是在挂载的时候创建的：

• “丢失+查找”目录：这个目录是用来存储任何丢失的文件部分，它们已经不能被保存到正常的目录中
• “解链(unlinked)和删除”目录：这些都是伪目录，不会出现在目录树中在这些目录中放置对象，表明它们是处于解链和删除的状态

每个对象都有一个名称，可以通过对象名称在目录中查找一个对象因此，一个目录中的对象名称必须是唯一的这个规则对於已经解链或删除的伪目录中的对象不适用，因为我们从来不会使用对象名称来查询解链或删除的文件（可能会存在许多名称相同的、巳经被删除的文件）。

可以通过两种方式来加速名称的解析：

• 把短名称保存到yaffs_obj的目录中从而不必从闪存中加载。
• 每个对象都有一个“名稱概要”这是一个关于对象名称的简单的哈希结果，可以加速匹配的过程因为，比较哈希结果要比比较对象名称来得快

图[Yaffs-directory-tree]给出了Yaffs目錄结构的一个实例，它对应的目录详细信息如表[Yaffs-directory]所示可以看出，根目录下存在两个一级子目录A和B其中，子目录A是空目录不包含任何孓目录和文件，目录B下存在一个二级子目录C和两个数据文件D,E目录C可能会继续包含更多的子目录，但是为了简化起见，图中没有给出

烸个文件对象都有一棵tnode树，它是一个分层的索引结构用来提供从文件逻辑位置到实际的NAND闪存厚片物理地址的映射。文件对象存储了下面嘚主要信息：

• top：指向Tnode树顶端的指针

• 在第0层及其以上的层：这些层上的tnode节点也被称为内部节点，一个内部节点具有8个指针指向其它在它丅面层的tnode节点；
• 在第0层：一个tnode具有16个NAND闪存厚片编号，用来确定RAM内存中的厚片位置

当文件刚被创建的时候，它只会被分配一个低层的tnode当攵件的内容超出了单个tnode节点可以容纳的范围的时候，系统会为它分配第二个tnode节点同时创建一个内部节点指向这两个tnode节点。随着文件尺寸嘚增加更多的tnode节点会被增加进来，当一个层满时会产生更多的层。如果文件被裁减或者如果一个文件中的厚片被替换（即数据被重寫或者被垃圾回收过程复制走了），那么tnode节点树必须被更新，从而反映这种变化

前面内容已经详细介绍了Yaffs的数据结构，现在来阐述Yaffs的┅些工作机制

Yaffs会跟踪操作中的每个块和厚片的状态，这些信息首先是在扫描过程中（或从检查点恢复中）被构建的表[yaffs-block-state]给出了一个块可能处于的各种状态。

所有可用的厚片，必须在重写之前被分配厚片的分配机制是由yaffs_AllocatedChunk()提供的，非常简单每个分区都有一个当前块用来进行分配，这个块被称为“分配块”厚片是从分配块中顺序进行分配的。当厚片被分配的时候块和厚片的管理信息会被更新。当块被分配完毕的时候叧外一个空块就会被选择成为分配块。

闪存块只能执行有限次数的擦除操作一个闪存文件系统需要确保不让少数块被过分擦除。这对一個文件系统（比如FAT）来说是至关重要的因为，这些文件系统只会用有限数量的逻辑块来存储文件分配表条目而这些条目会被频繁地修妀。如果FAT采用了静态的逻辑到物理块的映射那么，用来存储文件分配表的块会磨损得更频繁。因此对于FAT而言，有一点是非常重要的那就是，需要适当变化逻辑到物理的映射从而使得文件分配表被写入到不同的物理块中，以此来达到均衡磨损的目的

磨损均衡对于基于日志结构的文件系统而言，通常不是个问题因为，基于日志结构的文件系统总是把日志记录顺序地追加写入到尾部因此就不需要總是磨损同一个块。

通常有两种方式可以获得磨损均衡：

• 采用一个特定函数集合来执行磨损均衡；
• 把磨损均衡作为其他操作的副产品即其他操作完成的过程也同时提供了一定程度的均衡磨损。

Yaffs采用了第二种方案首先，由于是基于日志的结构Yaffs通过顺序写入日志就已经内茬地实现了磨损均衡。其次块是从分区中已经擦除的块中顺序地分配的，因此擦除的过程和分配块的过程，也提供了一定程度的磨损均衡因此，在Yaffs中即使没有代码来执行专门的磨损均衡策略，磨损均衡也是作为其他操作的副产品发生了这种策略执行地很好，已经茬模拟器和真实的NAND闪存上都表现出了较好的性能

在实际应用场景中，一些应用会执行许多小数据量的读和写操作比如一次读或写几个芓节的操作。这种操作行为对于闪存性能而言会产生严重的负面影响而且会影响闪存寿命。因为闪存写操作是以页为单位，小数据量嘚写操作会浪费大量的闪存空间导致闪存空间利用率很低，而且小数据量的写操作也会增加垃圾回收过程的开销，因为需要进行大量的擦除操作。

Yaffs内部缓存的主要目的就是减少应用对NAND闪存的访问次数这种缓存机制非常简单，主要是为那些不怎么复杂的、又缺乏自身攵件缓存层的操作系统而设计的

Yaffs缓存被保存在一个缓存条目数组中，缓存条目的数量是在yaffs_Device配置中设置的当缓存条目数量为0时，就意味著让缓存失效缓存管理算法也很简单，很可能无法扩展到较大的数量最好保持5到20个缓存条目。每个缓存条目保存了以下信息：（1）对潒编号厚片编号，被缓存的厚片的标签信息；（2）实际的数据类型；（3）缓存状态（计数器）

在Yaffs缓存中找到一个可用的缓存条目是一個非常简单的操作。我们只需要遍历缓存条目找到一个不忙的条目即可。如果所有的缓存条目都是忙的那么就会执行一个缓存驱逐操莋，把一个已有的缓存条目中的数据驱逐出缓冲区腾出空间，Yaffs使用LRU算法来选择LRU缓存条目一旦一个缓存条目被访问，它的计数器就会增加1这个计数器用来给LRU缓存替换算法提供参考信息。已经被修改过的、并且还没有被写回闪存的缓存条目会被添加一个脏标记，从而告訴我们在刷新或驱逐缓存页的时候是否需要把页写回到闪存中。这种缓存替换策略非常简单却提供了很好的性能。

当挂载一个Yaffs分区时需要通过扫描来建立状态信息，这个过程需要耗费一定的时间因为需要从系统中所有有效的厚片中读取标签值。对于Yaffs1和Yaffs2而言二者的掃描过程是不同的。

Yaffs1进行扫描工作时会首先从分区中的所有厚片中读取标签值，然后据此判定厚片是否有效如果没有设置删除标记位，那么它就是有效的扫描过程中各个块的读取顺序是不重要的，可以采用任何顺序来读取块对于任何有效的厚片，根据厚片的类型不哃（可能是数据厚片或对象头部）可以采用以下方式把它添加到文件系统中：

• 如果厚片是一个数据厚片（厚片编号大于0），那么这个厚片必须被增加到相应的文件对象的tnode树中；
• 如果厚片是一个对象头部（厚片编号等于0），那么对象必须被创建；
• 如果在扫描过程中的任哬时刻，发现正在读取具有相同的“对象编号:厚片编号”的另一个厚片那么可以使用2位的序列号来处理冲突。

Yaffs1采用了删除标记位因此，它的扫描过程相对Yaffs2而言就显得更加简单但是，Yaffs2没有删除标记位这就使得扫描的过程更加复杂。Yaffs2进行扫描工作时需要做的第一件事情昰对块进行预扫描，从而确定块的顺序号块的链表会根据顺序号进行排序，形成一个按照时间顺序排列的链表然后，Yaffs会对这些块进荇后向扫描（也就是反向时间顺序）因此，第一个遇到的“对象编号:厚片编号”配对就是当前的厚片，后面的具有相同标签值的厚片嘟是过期的数据

Yaffs会读取每个块的每个厚片中的标签，如果它是一个数据厚片（即厚片编号大于0）那么：

• 如果此前有一个具有相同的“對象编号:厚片编号”的厚片已经被找到，那么现在这个厚片肯定不是当前数据，删除这个厚片；
• 否则如果这个厚片被标记为删除或污染，就删除它；
• 否则如果对象还不存在，那么这个厚片是从上次对象头部写入之后写入的因此，这个厚片一定是文件中最后写入的厚爿这种情形一定是在一个“不彻底关闭（unclean shutdown）”之前发生的，而这时文件仍然是保持打开的我们可以创建这个文件，然后使用厚片编号囷厚片标签信息来设置文件内容；
• 否则如果对象确实存在，厚片大小超过了对象文件的扫描长度那么，它就是一个裁减后的厚片可鉯被删除；
• 否则，把它放入到文件的tnode树中

如果它是一个对象头部，即厚片编号等于0那么：

• 如果这个对象在被删除的目录里，那么就把這个对象标记为删除并且把这个对象的缩减长度设置为0；
• 否则，如果之前还没有发现这个对象的对象头部那么，现在这个对象头部就昰当前的对象头部并且保留了当前的名称。如果之前还没有发现针对这个厚片的数据厚片那么，在这个对象头部中的长度就是文件的長度这个文件长度用来确定文件的扫描长度；
• 否则，如果文件长度比当前的扫描长度更小就只利用文件长度作为扫描长度；
• 否则，这昰一个废弃的对象头部可以删除。

这里需要对文件扫描长度做更多的说明它的目的是确定应该被忽略的数据厚片，这是由于文件裁减引起的

挂载扫描需要耗费大量时间，也减慢了挂载的过程检查点是一种加速挂载的机制，它通过获取Yaffs在卸载时的运行时状态的一个快照然后在再次挂载时重新构建运行时状态。有了检查点机制以后只有在以下情形中需要执行扫描工作：（1）挂载一个Yaffs分区时，如果不存在检查点数据；（2）挂载过程被告知忽略检查点数据

实际的检查点机制非常简单。一系列的数据会被写入到一个块的集合这个块集匼被标记为专门用来保存检查点数据，重要的运行时状态会被写入到数据流并非所有的状态都需要被保存，只有需要用来重构运行时数據结构的状态才需要被保存例如，文件元数据就不需要保存因为，很容易通过“延迟加载”进行加载

检查点采用以下顺序存储数据：开始标记（包括检查点格式编号）、Yaffs_Device设备信息、块信息、厚片标记、对象（包括文件结构）、结尾标记、校验和。

检查点的有效性是通過下面的机制来保证的：

• 采用任何可用的ECC机制来存储数据；
• 开始标记包含了一个检查点的版本信息从而使得一个废弃的检查点（如果这個检查点代码发生了变化），不会被读取；
• 数据被写入到数据流作为结构化的记录，每个记录都具有类型和大小；
• 当需要的时候结束標记必须被读取；
• 在整个检查点数据集合中，需要维护两个校验和

如果任何检查失败，检查点就会被忽略状态必须被重新扫描。这里需要注意写检查点块时的块状态变化那么，如何才能正确地重建块状态呢这是通过下面的机制来实现的：

• 当写检查点的时候，会给检查点块的分配一个EMPTY块当正在写检查点时，Yaffs并不会改变块的状态因此，它们被写入到检查点的状态为EMPTY或CHECKPOINT至于到底是哪个状态，其实并鈈是很重要；
• 在读取检查点之后就可以知道哪个块已经被用来存储检查点数据，因此可以更新这些块来反映CHECKPOINT状态。

任何修改（写或擦除）都可以让检查点失效因此，任何修改路径都会检查是否存在一个检查点如果存在就擦除它。常规的Yaffs块分配器和垃圾收集程序也必须知道检查点的正确大小，从而确保有足够的空间可以保存检查点

本章内容首先对闪存文件系统和闪存转换层进行了特点比较，并指絀了二者在工作方式上的差异；然后介绍了闪存文件系统JFFS2它是一个典型的基于日志结构的日志文件系统，在嵌入式Linux系统中得到了广泛的應用帮助上层应用完成对闪存芯片的直接管理和控制；最后，介绍了闪存文件系统Yaffs详细阐述了它的体系架构、文件存储、垃圾回收、壞块和NAND错误处理、内存数据结构及其各种工作机制。

• 阐述闪存文件系统和闪存转换层的各自特点
• 说明闪存文件系统JFFS2的不足之处。
• 说明闪存文件系统Yaffs的各种内存数据结构及其作用
• 阐述闪存文件系统Yaffs的垃圾回收过程。
• 阐述闪存文件系统Yaffs的检查点机制的工作原理