Berkeley Fast File System

27 Aug 2012 by fleuria

带着关于文件系统的一些疑惑，又一次翻开了《Understanding Linux Kernel》。然而看到一部分又像以前那样中途搁置了它，翻起历史来——依然觉得要理解Linux的现在，顺着UNIX的发展才是最好的一条路线。

已经有了Unix v7文件系统的基础，就从FFS开始。

FFS自4.2BSD中引入，初衷为提升UNIX文件系统的性能，效果显著，所以敢叫Fast FS；因为基于UNIX v7文件系统改进而来，到现在更多被称作UFS。

FFS可以算是古典文件系统到现代文件系统的一条分界。单从磁盘布局而言，80年代的FFS已经与90年代的Ext2没有多少区别了。

FFS提升性能的中心思想，首先是引入Cylinder Group，提高磁盘访问的局部性，降低寻道的延时；其次增加逻辑块的大小，使文件系统尽可能的大块传输。

Cylinder Group

与Unix v7文件系统相比，FFS最显眼的区别就是Cylinder Group这一结构。

FFS将磁盘分区划分为几个等大的柱面组(Cylinder Group)，将相邻的柱面集合成一个组1，可以认为在一个柱面组内寻道是相对廉价的。

每个Cylinder Group包含一份超级块的拷贝，以及一些概要信息2。同Unix v7文件系统一样，inode数目是固定的3，可以很方便地寻址。

在Ext2中，设定是每个Group大小相等，逻辑块越大Group的数目越少。4

局部化是个很中庸的词，极端的局部化就是把所有的数据揉到一坨里了，显然与初衷相背。靠谱的分配策略，不是试图将所有的数据访问局部化，而是必须做到将不相关的数据分散开。这里所分配的就是inode与数据块两项：

  • 同一目录下的inode常常被一同访问
  • 一个文件的数据块往往被一同访问

这样，同一目录下的inode或者同一文件的数据块，都将尽量在同一柱面组中分配。

同时为避免上面说的极端情况，也有一番分散的策略：

  • 将新分配的目录至于父目录不同的柱面组
  • 避免柱面组被一个大文件填满，每个文件一旦大于48kb5，就将新的块至于另一个柱面组，随后每增长1mb轮换一次柱面组。

增大的逻辑块与Fragments

增加逻辑块的大小可以增大文件系统的吞吐，代价是浪费磁盘空间。

FFS将逻辑块的大小默认设置为8kb，在当时该是非常大了。为减少空间的浪费，FFS将逻辑块划分为Fragments，对于较小的文件末尾的数据，就靠Fragments来表示。

每个逻辑块可以分为2、4或者8个Fragments，每个Fragment都是可寻址的。文件系统的块的位图标志中的每一位表示的是Fragment，而非逻辑块。

Fragment仅仅用于表示文件最后一个块的数据，而且只对直接块可用。因而Fragments只对小文件才有意义。

同一文件中的多个Fragments必须属于同一个逻辑块并保持连续，在小文件增长时，需要将旧的Fragments中的数据拷贝到新分配的大块Fragments中。这里就是时间换空间了。

Sun的改进：Clustering

4.2BSD中的FFS已经拥有了现代文件系统的骨架，仍有许多地方可以改进。文件系统的磁盘结构既已成型且广为接受，在不修改既有结构的前提下，仍有许多优化空间。其一为Clustering，在Ext2中，相应的概念就是块的预分配了。目的都是使文件的块尽量保持连续，可以增大吞吐。

Cluster是一段连续的逻辑块，在读写文件时，都尽量凑在一个Cluster里进行。

Sun的方案是修改了ufs_putpage()与bmap()：

  • 在需要写的时候，先推迟一下，将数据块留在Cache中，直到Cache中的数据块凑满了一整个Cluster、或者写的顺序被破坏，再一股脑的写入磁盘。
  • 在读的时候，bmap()将返回一个额外的值contgsize，表示当前逻辑块所在Cluster中剩余的块的数量，作为readahead使用。

可能的改进：预分配

Ext2文件系统采用了预分配的策略，与Clustering有几分相似，而且同样不需要修改文件系统的磁盘结构。

在分配块时，将同时分配八个连续的块。这些块不一定都用完，如果没有连续写特别多的数据，仍未使用的块会在文件关闭时释放掉。此外，在文件truncated时、或者写的顺序被破坏时，都会将未使用过的预分配块释放。

References

  • Unix Internals
  • the design and implementation of 4.4BSD operating system
  • Understanding Linux Kernel

Footnotes

  1. 这本是一个与硬盘的机械特性相关的设计，后来随着硬盘容量的增加，CHS风格的寻址方式不再适用，Cylinder Group就成了一个纯粹的逻辑结构了。到Ext2，就直接省去了前面”Cylinder”这个词，只称为Group。
  2. FFS中superblock的内容包含文件系统中块的最大数目、inode的最大数目，自文件系统创建时确定即不再改变；至于可用块的数目、可用inode的数目等不停变化的薄记信息，则记录在Summary Infomation中。Summary Infomation跟在第一个superblock后面，不会进行冗余的备份。
  3. inode的最大数目 = 磁盘空间 / 2kb。
  4. 设逻辑块的大小为n字节，那么一个Group将最大含有8*n个块。
  5. 选择48kb这个数字是因为，48kb是直接块可以表示的最大长度，后面的1mb是一级间接块可以表示的最大长度。