Fast File System

英文原文：

1. A Fast File System for UNIX, 1984
   作者：Marshall McKusick, William Joy, Samuel Leffler, Robert Fabry

点评：
这篇文章可以说是 File System 里面最经典的文章之一。现在 Unix File System 也是 FFS 的延伸。

作者发现了 Old Unix System 的许多问题。做出了改进。

（1）首先，以前的 FS，由于硬件的限制，把 block size 设计的很小，只有 512KB
对于大文件的读取 overhead 很大。以读取一个 2MB 的文件为例，需要四次读取。 FFS 的block size 增加到 2MB, 大大减小了 overhead, 2MB 的文件只需要一次 disk access。但是大的 block size 也带来了问题，如果整个系统的文件都很小，比如只有 512KB，那么会浪费空间。

FFS 的解决方法是：
把 block 分为几个 fragments, 如果一个文件只占用了 block 的一部分，其它文件还可以继续使用。不浪费空间。

（2）其次，作者观察到以前的 FS 随着时间的推移，其 disk access time 会变得越来越大。
原因是一开始系统有一个 list of free space, 随着使用越来越多，删除，添加，更新文件。这个 free list 变成了一个 random list. 一个文件可能被放在相隔很远的 cylinder, 或者 sector 里面，读取一个 block 之后，disk head move 到下一个 block 需要花费很长时间。

FFS 的解决方案是：
给出 Global 和 local layout policy， 对文件或者文件夹位置的安排进行优化，尽量缩短 seek 的时间。但是也有缺点：当硬盘使用率非常高的时候，这个优化的时间会变得非常高，因此效率会大幅下降。

2. Locality and The Fast File System

FFS 是 对 VSFS 的一种优化改进使其可以被实际使用。

1. FFS 基于 VSFS 的改进思想是什么？

这个呢，VSFS 在存储文件的时候，根本没有考虑磁盘的寻址时间，把磁盘当做了一种随机存储介质！事实上由于局域性原理的存在，依据局域性而对存储做相应改进是非常有助于性能提升的。FFS 则正是看到了这一点，其改进是将磁盘划分为多个子区域（Cylinder Groups），存储文件的时候同一文件夹下的文件尽可能放在同一个 Group。Cylinder Groups是FFS最大的改进来源。

2. FFS文件系统的实现

首先，FFS将磁盘划分为很多子区域，也就是很多个 Cylinder Groups，如下图：

每个组内的结构跟 VSFS 基本一样，对于这里面的 SuperBlock 每个组都会有。

文件存储
既然 FFS 号称利用局域性原理，那么具体是什么操作的呢？

• 对于文件夹，它会选择一个包含文件夹少而且剩余的空闲 inode 数目多的组来存储；
• 对于文件，它确保一个文件的inode和data是属于同一个组的；而且，将同一文件夹的文件尽量放在一个组，这里面的“尽量”是考虑到大文件可能需要被存在好几个组。
• 大文件 大文件是需要特殊处理的，因为否则的话因为组内空间被大文件大量占用，这就会使得很难实现“相关文件放一起”的那个使用局域性原理的设计。那么大文件就必须被“分割”为多块分别存储在各个组内，那么如何设定这个切割的大小呢，或者说大文件的每一块设置为多大。
  这个需要一点计算。设置大文件切割大小核心在于，设置的太小了，那么读取它的时候影响效率（因为是需要额外寻址的，如果太小，这总的传输效率低）。假设磁盘的平均寻址时间是10ms，那么为了达到一半的传输效率，这意思是说磁盘真正用来传数据的时候和寻址时间相同，假设磁盘传输效率是40MB/s，那么10ms传输的数据是409.6KB。换句话说，只需要409KB，就可使的传输效率为50%。事实上，大约3.7MB就可使得磁盘平均传输效率为90%。所以，切割大小设置为4M左右就可以了。

FFS 的设计者挺聪明的，其实按照之前的 VSFS 的设计，每个 inode 里面会有15个块指针用来索引文件占用磁盘块的，前面12个直接索引可表示12*4KB=48KB的空间，而一级间接索引就可表示4M的空间。所以除了前48KB，之后的每4M数据均放置在不同的组内，这个刚好可以使用一一级间接索引表示。

3. FFS 设计细节

小文件问题 这个是说很多文件太小了，用一个磁盘块（4KB）存储有点浪费空间啊！！所以呢，FFS 引入sub-blocks这个概念，一般是512B，也就是一个sector扇区的大小。那么这样一来又会使得写小文件的操作台低效了，哈哈，不用担心，我们可以写文件的时候现在 Cache 中缓存一下，等到收集了 4KB 的数据再一次性写入。这就是 FFS 提供的 libc 库的作用啦。
parameterized placement 这个呢，有点难理解，先看这个图吧：

假设一个文件就包含了12个磁盘块，而且如左边显示的那样存储于一个磁道上面。那么序列读取数据的时候就会有一个很小的问题：当磁头达到0块的时候读取数据，可是等它读完了准备读1块的数据的时候，磁头早就转过去了（假设转到2块的位置），于是需要接着等磁头转回来！！这样是不是很慢，事实上磁盘会将一个磁道的数据一下子缓存在磁盘里面，但是即使是这样，也需要两圈才能读完。因为你在等1快的数据的时候，磁盘转了一圈读出了整个磁道的数据，然后你获得了1块的数据，可是还是需要转一圈才能依次获得每一块的数据。于是乎就很聪明的将数据排列成右边那个样子，这样一来就只需要一圈啦。。。。

Fast File System，快速文件系统，是由 Berkeley 大学研究人员设计并实现的建立在UNIX操作系统的一套文件系统。这个系统主要目标已经体现在它的名字上，就是建立一个快速的文件系统。因为他们发现之前的UNIX的文件系统（参考之前的Blog文章“Concepts of Unix File System”）在性能方面存在问题，主要问题是在磁头定位，位置转化过程中浪费了大量的时间，导致效率不高。所以FFS的一大设计思路就是降低磁头的seek时间，而解决方案也很简单，keep related stuff together，这样seek的时候就可以节省时间。整个FFS涉及几个关键概念

Creating New File

Cylinder Group翻译过来就是柱组，已经在之前Blog文章Concepts of Unix File System介绍过了，设计Cylinder Group的目的就是为了完成keep related stuff together，因为在一个柱组的文件可以快速访问。所以相关文件就可以放在一个柱组里。每个Group先包含一个superblock来保存一些metadata，后面接着是inode bitmap和data bitmap用来显示每个block的位置和其是不是已经写满了。

当创建一个文件的时候，比如/foo/bar.txt，并且这个文件大小是4kb。那么因为这是一个新的文件，所以需要分配新的inode而且inode bitmap也需要更新。同时，这个文件大小4kb，在cylinder group中就要分配一个4kb的block然后更新data bitmap来表示对应的data block已经占用。所以这就需要有四次写操作，但是这只是完成了这个文件的创建，并没有把它放进文件目录中。所以父目录/foo也要更新，来把bar.txt放到这个目录下。如此才算完成了一个文件的创建

Put Related File Together

具体策略也很简单。第一，将一个文件的所有block放到一个group，这样就避免了磁盘磁头的long seek，从而节省了时间。第二，在相同目录的文件放在一个group里，比如/dir1/1.txt, /dir1/2.txt, /dir1/3.txt, 和/dir99/4.txt，那么前三个就会被放到一个group里，最后一个就被放到另一个group里。

Large File Exception

Put Related File Together的策略有一个例外，就是写入当大文件时。按照之前的策略一个大文件的所有block都会被放到一个group中，但是由于文件太大，可能整个group或者大部分group都被这个文件占满了，这就不符合把相关的文件放在一起的原则，因为这个group里只有这一个文件，只要有再访问别的文件就需要seek别的group，这大大降低了FFS的性能。对于写入大文件的策略就是，把它所有block平均的放到不同的group中。

开发一个高效，又节约空间的磁盘文件系统真是好难啊。想了各种办法来优化文件系统，老的UNIX系统算法也是针对它那个时候而设计吧，磁盘小，内存小，存储的也主要是文本小文件所以在那个时候，文件系统是没有问题的，问题是后来计算机系统发展了啊，多媒体文件出现了，文件突然变大了，磁盘也变大了，内存也变大了原来的系统就不适合了，我们可以用更多的空间去换取时间。当然，这篇文章是1984年写的，随着SSD价格不断降低，现在SSD也快普及了，现在的文件系统应该还没有把SSD的性能完全释放出来吧，所以应该会有人续写A Fast Fast Fast Fast File System for UNIX吧，哈哈哈。
下面来分析下，作者到底都使了哪些魔法让文件系统变快了呢？
首先，增加每个block的大小。这个应该是一般的人都想得到的吧，我在做lab1的时候都觉得512字节一个block是不是也忒小了吧，512字节的block意味着superblock也变小了，这样能存储的磁盘信息就更少了，当然较小的block size以为着更少的磁盘浪费，如果系统里面都是小文件的话。作者把磁盘分块大小增加到了4k，这样一次读操作就可以读取更多的数据，意味着读写速度可以提高接近8倍。

问题是这样存储小文件的时候会造成极大的浪费，所以作者又提出了一个新的概念—片段（fragement），这样在存储文件的时候就尽量的用完整的块存储，剩余的那么些位置也不能浪费了，用块的片段，这样这些小地方可以和别的文件公有，这样在不浪费空间的情况下可以大大提高读取速度，这个概念比较创新，设计上也复杂的多，比原来那种简单粗暴的方法好。

磁盘系统里面还有个问题就是磁盘碎片，以前的UNIX系统是通过一个队列保存缓存的block，然后再均匀的释放，这样本身并没有问题，可以解决一部分磁盘碎片的问题，问题是永久了还是会产生大量的碎片，这个在读写大文件的时候尤为严重，因此这个时候可以通过一些高效的hash算法来对文件存储的位置进行一些预判，这样每次存储文件的时候就不是随机分配一些block块了而把文件存储用的块局限在一个小的范围里，提高了寻找文件块的速度。
还是对于大文件，我们知道如果对一个大文件连续分配很多空间的话，它之前的文件如果又增加的话，就只能分配到大文件的后面，这样每次读取这个小文件就得越过这个大文件，这样是很不划算的，所以作者把大文件做了特殊对待，只允许你在一片连续的空间写上几兆的内容，这样对于大文件虽然连续性不好，但是大文件一次读取几兆的内容已经就很快了，所以无所谓了，反而是更多的小文件可以保持连续读取，这样提高的了小文件读取速度，这样从整体上来说还是很划算的。不过这个方法也不是一直都很好用，因为系统需要使用一些hash算法来保证磁盘上文件被分配到比较好位置，问题是当磁盘已经快被放满了呢，这个时候hash算法就基本上失效啦，可供分配文件的位置就大大减少，这样文件系统的性能大大下降，这样来看的，文件系统对磁盘的实际使用率也不算很高啊。
//老规矩，扯一下淡凑字数-_-! 计算机系统原理虽然很难，学起来很痛苦，但是很有意思啊，在老师给出的基本框架下我们自己实现一个简单的文件系统，了解了不少系统底层的知识，对硬件也不那么陌生了，甚至还捡起来一些算法和数据结构的只是，要知道现在天天做web系统开发，基本上不用考虑算法和数据结构的问题，而且web系统本身结构清晰，现代的语言本身也是为简化开发者难度设计的，开发起来很快，有时候常常不知道所以然。通过一个个痛苦的lab，居然慢慢捡起来了原来那么点点的c知识，链表，队列，二叉树这些以前比较头疼的数据结构也不觉得那么难，谢谢老师在这门课上做出的努力，感谢整个计算机系统原理教学团队。