摘要
我们描述了UNIX文件系统的一种新实现，通过使用更灵活的allocation policy，提供了更好的locality of reference，并且可以适配于不同处理器和外设，大大提升了throughput。新文件系统聚集了被序列访问的数据，提供了两种block size，加速了大文件的访问同时不浪费小文件的空间，相比于旧系统提高了10倍的文件访问速度。
新文件系统讨论了对于长期需求的编程接口的改进，包括：
- 文件的咨询锁机制（advisory lock）
- 跨文件系统名称空间拓展（name space across file system）
- 长文件名使用
- 资源利用的管理权限（administrative control of resource usage）
关键词： UNIX，文件系统组织，文件系统性能，文件系统设计，API
旧文件系统
在贝尔实验室的传统文件系统中，磁盘被分为几个分区，每一个分区都容纳一个文件系统，且不会跨分区。文件系统用superblock描述，包含基本参数：block数，最大文件数，free list指针。
文件系统中包含着文件，部分作为目录，其中的指针指向着同时也可能是目录的文件。文件用inode进行描述，其中包含了所有权，时间戳，block索引数组。
在这里我们假设，inode中直接存储了file的前八个block，更多的block通过引用间接访问，类似于页表的分级索引，512-byte的文件系统中每级都会指向128个下一级block。
150M的文件系统中，4M inode和146M data被隔离，因此通过inode访问data需要一个long seek。同时，目录中的inode也不是连续的，因此操作目录也不是locality。
block的分配也不最优，传统的文件系统每次磁盘传输都不超过512byte，通常下一个block也不会在同一个cylinder上，因此每次都必须再次寻道。小的block size，有限的read-ahead，过度的寻道，都限制了系统的throughput。
此前，伯克利曾经翻倍了block size从而提升throughput，但是就文件系统仍然只能发挥磁盘百分之四的传输速率。主要问题在由于文件的创建和移除，free list被迅速抢占，最终几乎完全随机，文件的block被随机分配，强制了每次访问都需要寻道。因此文件系统在一段时间后性能迅速下降，并且除了重置，无法恢复性能。另一种方式是定期地重新组织数据，整理磁盘，恢复其locality。
新文件系统组织
Cylinder Group
新文件系统同样使用superblock，这些block一旦丢失会导致灾难性的损失，因此它们都是创建后即只读的。一旦某些磁盘错误发生破坏了这些superblock，副本才会被引用。
为了减少间接访问的层级，block size被加倍到4096 byte，或者4096×任意二的幂。block size在superblock中记录，文件系统可以同时访问不同size的block。
一个分区被分为几个cylinder group，每个cylinder group包括了几个连续的cylinder。cylinder group包含了 bookkeeping information（距离头部不同偏移量，防止在同一个platter，出了问题全家暴毙，通常每个group递增一个track，也就是说在空间上螺旋向下排列）：
- superblock的冗余副本
- inode空间（默认为每2K空间在开始时分配一个inode，假设绰绰有余）
- 可分配空间的bit map（取代了free list）
- block利用的概况
EX:
需要注意，第一个group的位置不一定一直确定，因为磁盘最开始有8K的bootstrap程序，由于需要对齐block size，因此block size超过8K时，第一个group的位置必须先读取sblock size才能确定。
Block Size
block size 1048 -> 4096, 磁盘事务四倍效率。但是小文件则会浪费大量空间，典型trade-off。为了避免浪费，一个block被分为几个fragment（2、4、8），并且可以寻址，最小可以设置为512byte（sector size）。bit map在fragment level记录了空间是否可用。
block size/fragment size = 4096/1024
fragment需要对齐，跨block的fragment不能被当做整体使用。上图中O表示可用，X表示占用，则只有12-15fragment才能被当做一个整体的block。
当要分配文件时，零头优先分配不完整的block，如果找不到，再分配给完整的block，然后剩余空间留给其他文件分配。（a）
让写文件时，如果已分配空间不足，则需要再分配。
- 原文件不含fragmented block：先把之前的full block全部填满，remainder data按block分配，零头同策略（a）
- 原文件包含了fragmented block：先把之前的full block全部填满，remainder data fragment data合起来，分配一个full block，先填fragment data（并释放之前的fragment），然后填remainder data，如果remainder data空间不足，则按照上述策略1
可以看出，含了fragment的file必须copy很多次才能拓展为full block，因此用户程序每次写一整个block可以最小化这种代价。
block size增大减少了大文件的索引信息，同时小文件保持不变，但同时也需要更多的空间使用bit追踪free block。最终来看，磁盘的利用率几乎没变。为了保证再分配的效率，文件系统预留了一定的空间（根据空间浪费，给出合理的值），从而保证一定的free space。一旦空间不足，locality会迅速下降，但是通过删除文件从而给出足够的空间并且移动数据还是能够恢复性能。（感觉和他说的旧版本没啥区别，都是得重排）
File System Parameterization
对于没有IOchannel的处理器，中断机制导致几次磁盘访问必须存在一定间隔。磁盘的物理性质可以计算出一个跳过block所需的时间，处理器的特性可以计算出处理中断并进行下一次磁盘访问的时间，这样我们可以计算出，当处理器恰好进行下次从磁盘访问时，跳过的block个数。这样的block在物理上不连续，但是逻辑上是连续的。
cylinder group summary information存储了不同旋转位置下，可用block的数目。（例如跳过6个，k，k 1，...，k 5构成一共六组连续）
superblock还包含了一组旋转布局表，使用旋转位置索引，从中可以获取该旋转位置下所有block的block map。
在找到可用block不为0的旋转位置后，文件系统将会在这些逻辑连续的block上进行分配。
这些参数都是可以动态修改的，所以根据合适的磁盘或处理器设置对应的参数，就可以针对性地进行优化。
Layout Policies
global policy
use file system wide summary information to make decisions regarding the placement of new inodes and data blocks
通过这些信息计算最佳的旋转布局（上文），确定什么时候开辟在新的cylinder group
local allocation
Below the global policy routines are the local allocation routines that use a locally optimal scheme to lay out data blocks.
- increase the locality of reference to minimize seek latency
- improve the layout of data to make larger transfers possible
全局布局聚集相关信息，对于superblock，inode，data的访问在同一cylinder group进行。过度的局部性可能导致单cylinder group无法储存为被迫分散；也可能导致某个cylinder group中存放大量的数据退化成旧文件系统。
大量命令都涉及目录，例如ls file就需求对同一目录下连续访问，因此目录和子节点放在同一cylinder groupcylinder group。
分配directory时，新目录放在free inode较多的cylinder group，这样做的目的主要为了便于进行inode的聚集。
inode block分配使用next-free策略（参考next-fit类似），尽管位置随机，但是仍然可以视作固定时间（一个cylinder group的inode数目不多，本身就限制了）。
data block则采取上文的rotationally optimal position，但是有一个顾虑在于，大文件会很快占据所有的空间，也会导致其他的inode无法存储，从而不得不溢出。
一种启发式算法是，文件超过48kb则分配到不同的cylinder，每 1mb就再分配一次，分配的策略是从free block较多的group里随便挑个。这样每1mb的访问仍然能保证一定的locality。
全局策略会指定一个block，当全局策略不成功时，局部策略生效，
1.下一个旋转最近的block
2.如果没有的话，同group的block
3.满了的话，把当前的group number 进行hash二次探查寻找另一个block
4.hash失败，全局搜索
API拓展
Long File Names
主要是先在entry里存了字符串的大小，这样字符串就可变长
File Locking
emmm，建立了一个sys call级别的互斥锁和共享锁。之前是必须使用文件进行加锁。
主要是弥补三个痛点
- 轮询浪费CPU
- 系统挂了锁作为文件没处理干净
- 管理员可以随意操控文件
Symbolic Links
用文件存pathname建立link，如果是绝对地址就不会翻译，否则这个file会翻译到对应的path上去。这样做通过pathname一层，而不是直接进行inode的alias，有利于跨文件系统。
Rename
过去的rename不是原子性的，先创建临时文件指向同一个inode，然后改名，然后删原文件的link，一旦崩溃那么会导致临时文件存留而且没有变成新名字。现在改用单个sys call。
Quotas
对于用户进行限额，防止某个用户使用过多的inode或者block
