当Unix操作系统首次引入时，使用了minix文件系统，它非常简单，基本上，它的数据结构在磁盘上看起来像是这样：
超级块包括了有关整个文件系统的信息，卷大小，有多少inode，有多少空闲块等等，磁盘的inode区域包括文件系统的所有inode，最后，大部分磁盘都被整个数据块占用。
- 对于非常常见的读操作，每当第一次读取inode，然后读取文件的数据块时，就会导致寻道时间很长
- 更糟糕的是，文件系统最终会变得非常的碎片化，该设计没有对空闲空间的管理，结果导致在磁盘上来回访问逻辑上连续的文件，从而大大的降低了性能
例如，假设一下数据块区域包括4个文件(A/B/C/D），每个文件大小为2个块：
如果删去B和D，则生成的布局为：
可见空间被隔离成两块区域，而不是很好的连续4块，假设我们希望分配一个大小为4块的文件E:
我们可以看到E被分散在磁盘上，因此，在访问E时，无法从连续获取，首先先读取E1和E2，然后寻道，再读取E3和E4，这个碎片问题就会影响性能问题。
对于这个问题，正式磁盘碎片整理工具可以解决的，它们将要重新组织磁盘数据，以连续放置文件，并且让空闲称为一个或几个连续的区域，移动数据，然后重写inode等以反映变化。
所以，如何组织文件系统数据结构，以提高性能？在这些数据结构之上，需要哪些类型的分配策略？如何让文件系统具有磁盘意识等，就成为改进文件系统的重中之重。
1 FFS文件系统
FFS(Fast File System)，诞生于80年代的一款文件系统，对其前任进行了大量的性能优化，成为了现代类*nix文件系统的始祖，其很多设计思想在今天依然有借鉴意义。
设计思想：
1.1 提高block大小
FFS之前的文件系统块大小基本定义为512或1024byte，该方案的利弊
| 优势 | 降低block内的碎片率，提供了存储空间利用率 |
|---|---|
| 劣势1 | 数据传输以block为单位，block较小可能导致传输效率较低，此时寻道时间占据更大的比重，进一步恶化了磁盘IO效率 |
| 劣势2 | 由于古老的文件系统采用是直接+N级间接索引来定位文件，较小的block大小可能导致需要的索引块会更多，降低了文件IO效率 |
在文件普遍偏小的当时，采用较小块劣势没那么明显。但是随着应用发生变化，大文件场景越来愈多，如果采用更大的block，那么其优劣势正好与较小的块大小互换。明显地提升磁盘IO效率的同时可能也会带来较大的空间浪费(block内碎片)。
FFS激进地提升了文件系统块大小至4096字节，且block size可作为参数写入文件系统超级块。即意味着，块大小可定制，一般是4096乘以2的N次方，但该参数一旦固定，便不可再修改，除非重新格式化磁盘。
1.2 柱面组
FFS将整个磁盘/磁盘分区划分成多个称为cylinder group的区域。每个cylinder group由多个连续的cylinder组成。而一些现代文件系统，如linux ext2和ext3，就称为块组，即block group，因此我们可以想象一个具有10个柱面组的磁盘：
cylinder的特点是在多个cylinder之间切换只需切换磁头而已，无需机械运动，这对于我们后面组织数据，提升数据IO效率有较大帮助。这些分组是FFS改善性能的核心机制，通过在同一组中放置两个文件，FFS就可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。
因此，FFS需要能够在每个组中分配文件和目录，每个组看起来是这样的：
在每个组中，我们需要记录该组的inode和数据块是否已经分配，每个组的inode位图(inode bitmap)和数据位图(data bitmap)起到了这个作用。最后，inode和数据区就像之前文件一样。
1.3 策略：如何分配文件和目录
有了这个分组结构，FFS现在就需要如何在磁盘上放置文件和目录以及相关的元数据，以提高性能。
因此FFS必须决定什么是“相关的”，并将它们置于同一个区块内，相反，不相关的东西应该放在不同的组内。为了实现这一目标，FFS使用了一些简单的防止推导方法：
- 首先是目录的放置，FFS采用一种简单的方法，找到分配数量少的柱面组和大量的自由Inode，因为我们希望随后能够分配一堆文件，并将目录数据和inode放在改组中
- 对于文件，首先需要却道将文件的数据块分配到其inode相同的组中，从而防止inode和数据之间的长时间寻道；其次，它将位于同一目录中的所有文件，都放到它们所在目录的柱面中
一次典型的文件读取包括：
- 从磁盘读取文件目录项；
- 从磁盘读取文件inode；
- 从磁盘读取数据块。
最差情况下可能得经历3次IO，如果是随机IO，会导致文件访问效率急剧下降。为了将文件读取的随机IO变成顺序IO，我们就要尽可能地将文件的元数据(目录项、inode)以及数据块连续存放。在FFS内：
-
- 将磁盘划分成Cylinder group，这个我们在前面描述过。文件的数据和元数据尽量位于相同group存放；
-
- 创建文件时，将文件inode与其父目录的inode位于同一个cylinder group，这样对父目录进行ls时可提高效率；
-
- 创建目录时选择inode策略与创建inode不同：选择一个空闲inode数高于平均值且目录数最少的group。这样做可以使得目录被spread over到所有的cylinder group；
-
- 数据块分配时，对于低于阈值(48KB)的文件，其block分配在与文件inode相同的cylinder group，以后每涨1MB切换一个cylinder group。选择新cylinder group的准则是其拥有空闲block数量高于平均值。
2 总结
FFS的引入时文件系统的一个分水岭，因为它清楚表明文件管理问题是操作系统的一个大问题，并展示了如何开始处理硬盘，针对前任的缺点提出更加高效解决方案，较好地解决了文件系统的IO效率低下问题，属于现代文件系统的开山之作。从此之后，人们开发了数百个新的文件系统，现在仍然有许多文件系统从FFS中获得提示（ext2/ext3）。
