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是一级间接块可以表示的最大长度。