看完了闪存,继续看文件系统。网上搜了一圈,发现都是讲 Andriod 的目录结构的,讲文件系统本身的少。目前能确认的是历史上曾经用过 ext4,yaffs,yaffs2 等。
估计目前主流的应该是 ext4。不过在搜索的时候先发现了一篇讲 jffs3 的,它在嵌入式系统上应用比较广泛,也是针对 Flash 存储特定设计的文件系统。不太确定现在的使用范围,但是拿出来研究下还是不错的。

闪存对文件系统的影响#

闪存跟磁盘有很多不同的地方,在设计文件系统的时候,二者有很多不同的考量。简单的对比表格如下

闪存 磁盘
最小寻址单位(读) 字节 扇区
最小寻址单位(写) NOR FLASH 是字节,NAND FLASH 是页,擦除是块 扇区
寿命 由擦写块的最大可擦写次数 机械故障

闪存的这些特性,导致我们在设计文件系统的时候,必须考虑以下的问题:

  1. out of place update: 对于磁盘来讲,我们更新数据可以直接原地更新。但是闪存不行,因为无法将 bit 位从 0 -> 1。所以对于闪存的数据更新只能是在另外一个地方写入数据,然后将原数据标记为 dirty,再通过 GC 来定期回收.
  2. wear leveling: 磨损平衡。闪存的使用寿命是由擦写块的最大可擦写次数来决定的。超过了最大可擦写次数,这个擦写块就成为坏块(bad block)了。因此为了避免某个擦写块被过度擦写,以至于它先于其他的擦写块达到最大可擦写次数,我们应该在尽量小的影响性能的前提下,使擦写操作均匀的分布在每个擦写块上

闪存转换层#

为了能让普通的文件系统(磁盘上的)能够在闪存上正常运行,需要有一个转换层:Flash Translation Layer(FTL)。它的功能就是将底层的闪存模拟成一个具有 512 字节扇区大小的标准块设备(block device)。对于文件系统来说,就像工作在一个普通的块设备上一样,没有任何的差别。

基本的实现思路就是对磁盘的扇区和闪存的块做映射。当上层的文件系统要写一个块设备的扇区时,闪存转换层要做下面的操作来完成这个写请求:

  1. 将这个扇区所在擦写块地数据读到内存中,放在缓存(buffer)中

  2. 将缓存中与这个扇区对应的内容用新的内容替换掉

  3. 对该擦写块执行擦写操作

  4. 将缓冲中的数据写回该擦写块

这种实现方式的缺点是很明显的:

  1. 效率低,对一个扇区的更新要重写整个擦写块上的数据,造成数据带宽很大的浪费。
  2. 没有提供磨损平衡,那些被频繁更新的数据所在擦写块将首先变成坏块。
  3. 非常不安全,很容易引起数据的丢失。如果在上面的第三步和第四步之间发生了突然掉电(power loss),那么整个擦写块中的数据就全部丢失了。这在突然掉电经常发生的嵌入式系统中是不能接受的。

当然,实际的 FTL 肯定不是这么简单,需要对这种模式做很多的优化。但不论怎么优化,性能以及可靠性上都不算很好。最终还是需要专门针对闪存的文件系统。

JFFS3#

JFFS 的全称是Journalling Flash File System,有 JFFS3 肯定也有 JFFS2 以及 JFFS,只不过不是本文关注的重点。JFFS3 的存在本来也是为了解决 JFFS2 的一些问题,所以肯定也会附带介绍到。
从其名字可以看出,重点是journal。JFFS 文件系统整体可以看作一个大的日志(跟 LSM 有点像),根源就是上面所说的out of place update, 更新和新加数据都是不断地 append -> mark dirty -> gc 的过程。

JFFS2 的问题#

对于文件系统来说,index都是非常重要的一环。index 能让我们更快地定位到文件和数据,其维护和更新也是文件系统设计的核心。JFFS2 将 index 放在了 RAM 中,很特殊,有很多优势,也是它很多问题的根源。
在比较小的闪存上,它的吞度量和性能很好,因为 index 的更新都是在内存中。但是闪存的容量越来越大,问题也就越来越凸显了:

  1. 挂载时,JFFS2 需要扫描整个闪存来建立 index, O(S)的复杂度,闪存容量越大,挂载越慢
  2. 同样的,闪存越大,index 越大,内存占用越大。同样是 O(S)

除开这些缺点,其优势也是很多的

  1. index 不占用闪存空间
  2. 吞吐量高
  3. 磨损平衡好,因为更新比较频繁的 index 都在内存中了

Index 的存储#

JFFS3 的解决方式将 index 从 RAM 放回到闪存上,相当于基本上是重新设计了。这样就解决了 JFFS2 挂载慢的问题,因为不用每次重新在内存中 build index 了。index 放到闪存上面临的第一个问题就是更新数据时引起的 index 的连锁更新,如下图所示:

index 以一个树的结构存在,leaf node 存储最终的数据。假设我们要更新 H,需要在一个新地方写一个 H1,那么指向 H 的 F 以及指向 F 的 A(root)都需要更新,他们的更新也是在一个新地方写数据。JFFS2 因为是在 RAM 中存储了 index,可以原地更新,所以没有这个问题。一旦放到闪存中,这种连锁更新就很难避免了。这种实现方式有个名字叫Wandering tree

显而易见,树的 level 越多,这种方式的效果就越不好。用 B+树来实现是一个非常自然的选择。JFFS3 中所有的对象都是存在一个大 B+树上,index、数据、文件、目录、属性等等。每一个对象都有一个 key,查询的时候就用这个 key 来查询。

leaf node 存储了真正的数据,其他的 index node 存储的都是 index 信息。

The Journal#

Wandering tree 的代价还是挺大的。JFFS3 在设计时参考了 JFFS2 的思路在内存中实现了一种cache来尽量避免这种高频次的更新。这种方式叫做journal(名字起的很不好)

在闪存上预留一些 block 作为 journal eraseblock,当有数据更新时,数据更新到这些 block 上,但是 index 在内存中更新,暂时不修改闪存上的 index。当有读取请求时,先看下内存中的 index(叫The journal tree),如果有那就用,没有的话就去闪存的 index 查。the journal tree 可以在合适的时机同步到闪存的 index 中。这样做的好处很多:

  1. 避免了 wandering tree 的昂贵开销,因为可以合并很多 index update
  2. 平衡损耗也很好。JFFS3 可以用比较好的算法来自己挑选 journal eraseblock

坏处也有,跟 JFFS2 一样,挂载的时候,如果想提前尽可能多的生成 the journal tree 来提升性能,
势必会增加挂载时间,一个权衡的问题。

Garbage collection#

跟 JFFS2 一样,整体思路都是将有效数据挪到别的地方,然后更新 index。JFFS3 因为 index 在闪存上,实现起来更为复杂些。而且会碰到一个尴尬的问题,
因为更新 index 也需要写新的数据,有可能在 GC 的过程中产生的垃圾数据比回收的更多。。。

如上图所示,为了回收 1 中的一块数据,最终产生了 2 中三倍的垃圾数据。原论文直接跳过了这个问题,说是仍在开发中,没有特别好的解决方案。暂时也没有找到引用比较高的研究这个问题的论文。

Superblock#

superblock 也是文件系统很重要的一环,可以说是 metadata 的 metadata。JFFS3 将 superblock 分为了两部分:

  1. static superblock: 固定不变的基本信息,放在第一个 eraseblock 中
  2. superblock: 经常更新的信息

superblock 的位置是不固定的,原因也是因为不能原地更新。JFFS3 在这块的设计也是相当的复杂:

anchor area 的位置是固定的,就是 JFFS3 的第 2,3 个 earseblock,其他的 chain earblock 和 super eraseblock 都是会一直更新的。通过这个链条可以就可以找到 superblock。
真正的 superblock 数据只占一个 sector,所有的指针也只占一个 sector,每个 eraseblock 包含 N 个 sector,每一次的闪存数据更新,superblock 都会更新,
N 次 superblock 更新会导致上一个 chain eraseblock 更新,依次类推一直到 anchor area 的更新。

这里就有一个必须解决的问题: 在可擦除的次数用尽之前,ancher area 必须比 data area 能用的时间更长。不然到某个时刻数据更新时会发现 ancher area 已经无法更新了。这个问题涉及到了几个变量:

  1. 每个 eraseblock 包含的 selector 数量 N
  2. chain 的长度 m
  3. 闪存可用的 eraseblock 的数量 M

具体这几个参数怎么设置来保证这个基本原则论文中已经有详细介绍,本文不再赘述。但可能简单推理这几个变量的变化对于结果的影响。

  1. N 越大,这样 ancher area 的变动频率越低
  2. m 越大,ancher area 的变动频率越低

举个例子,目前 N=64, m=3 已经能支撑 128G 的闪存了。更大的容量需要更大的 N,m 参数。

Links#

  1. IBM Developer: JFFS2 文件系统及新特性介绍
  2. JFFS3 design issues - MTD
  3. LWN: Wandering Tree?
手机的刘海