设计一个文件系统，需要考虑哪些因素？

文件系统的实现

在对文件有了基本认识之后，现在是时候把目光转移到文件系统的上了。之前用户关心的一直都是文件是怎样命名的、可以进行哪些操作、目录树是什么，如何找到正确的文件路径等问题。而设计人员关心的是文件和目录是怎样存储的、磁盘空间是如何管理的、如何使文件系统得以流畅运行的问题，下面我们就来一起讨论一下这些问题。

文件系统布局

MBR 可以用在 DOS 、Microsoft Windows 和 Linux 操作系统中。从 2010 年代中期开始，大多数新计算机都改用 GUID 分区表（GPT）分区方案。

下面是一个用 进行分区的磁盘，表中的分区都被认为是 。

超级块

紧跟在引导块后面的是 ，超级块 的大小为 4096 字节，从磁盘上的字节偏移 4096 开始。超级块包含文件系统的所有关键参数

• 文件系统的大小
• 文件系统中的数据块数
• 指示文件系统状态的标志
• 分配组大小

在计算机启动或者文件系统首次使用时，超级块会被读入内存。

空闲空间块

接着是文件系统中的信息，例如，可以用位图或者指针列表的形式给出。

BitMap 位图或者 Bit vector 位向量

位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0和1，0表示已分配该块，而1表示一个空闲块。下图中的磁盘上给定的磁盘块实例（分配了绿色块）可以用16位的位图表示为：0000111000000110。

碎片

inode 节点主要包括了以下信息

• 模式/权限（保护）
• 所有者 ID
• 组 ID
• 文件大小
• 文件的硬链接数
• 上次访问时间
• 最后修改时间
• inode 上次修改时间

文件分为两部分，索引节点和块。一旦创建后，每种类型的块数是固定的。你不能增加分区上 inode 的数量，也不能增加磁盘块的数量。

紧跟在 inode 后面的是根目录，它存放的是文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。

文件的实现

最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是和 ，主要有三种分配方案

• 连续分配
• 链表分配
• 索引分配

连续分配

最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此，在具有 1KB 块的磁盘上，将为 50 KB 文件分配 50 个连续块。

这里有两个文件 D 和 F 被删除了。当删除一个文件时，此文件所占用的块也随之释放，就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块，因为这会复制空闲块之后的所有文件，可能会有上百万的块，这个量级就太大了。

刚开始的时候，这个碎片不是问题，因为每个新文件都会在之前文件的结尾处进行写入。然而，磁盘最终会被填满，因此要么压缩磁盘、要么重新使用空闲块的空间。压缩磁盘的开销太大，因此不可行；后者会维护一个空闲列表，这个是可行的。但是这种情况又存在一个问题，为空闲块匹配合适大小的文件，需要知道该文件的。

想象一下这种设计的结果会是怎样的。用户启动 word 进程创建文档。应用程序首先会询问最终创建的文档会有多大。这个问题必须回答，否则应用程序就不会继续执行。如果空闲块的大小要比文件的大小小，程序就会终止。因为所使用的磁盘空间已经满了。那么现实生活中，有没有使用连续分配内存的介质出现呢/p>

就广泛的使用了连续分配方式。

即只读光盘，也称作只读存储器。是一种在电脑上使用的光碟。这种光碟只能写入数据一次，信息将永久保存在光碟上，使用时通过光碟驱动器读出信息。

每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。如果上面这张图你看的不是很清楚的话，可以看看整个的链表分配方案

上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件，文件 A 依次使用了磁盘块地址 4、7、 2、 10、 12，文件 B 使用了6、3、11 和 14。也就是说，文件 A 从地址 4 处开始，顺着链表走就能找到文件 A 的全部磁盘块。同样，从第 6 块开始，顺着链走到最后，也能够找到文件 B 的全部磁盘块。你会发现，这两个链表都以不属于有效磁盘编 的特殊标记（-1）结束。内存中的这种表格称为 。

使用这种组织方式，整个块都可以存放数据。进而，随机访问也容易很多。虽然仍要顺着链在内存中查找给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。与前面的方法相同，不管文件有多大，在目录项中只需记录一个整数（起始块 ），按照它就可以找到文件的全部块。

这种方式存在缺点，那就是必须要把整个链表放在内存中。对于 1TB 的磁盘和 1KB 的大小的块，那么这张表需要有 10 亿项。。。每一项对应于这 10 亿个磁盘块中的一块。每项至少 3 个字节，为了提高查找速度，有时需要 4 个字节。根据系统对空间或时间的优化方案，这张表要占用 3GB 或 2.4GB 的内存。FAT 的管理方式不能较好地扩展并应用于大型磁盘中。而这正是最初 MS-DOS 文件比较实用，并仍被各个 Windows 版本所安全支持。

inode

最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为 的数据结构，每个文件都与一个 进行关联，inode 由整数进行标识。

下面是一个简单例子的描述。

在这种简单的设计中，目录有一个固定大小的目录项列表，每个文件对应一项，其中包含一个固定长度的文件名，文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址。

对于采用 inode 的系统，会把 inode 存储在属性中而不是目录项中。在这种情况下，目录项会更短：仅仅只有文件名称和 inode 数量。这种方式如下所示

上图是 SPARC 机器使用正序放置。

处理机中的一串字符存放的顺序有 和 之分。正序存放的就是高字节在前低字节在后，而逆序存放的就是低字节在前高字节在后。

这个例子中，有三个文件，分别是 、 和 。每个文件名以一个特殊字符（通常是 0 ）结束，用矩形中的叉进行表示。为了使每个目录项从字的边界开始，每个文件名被填充成整数个字，如下图所示

这个问题与我们上面探讨的连续磁盘文件的问题是一样的，由于整个目录在内存中，所以只有对目录进行操作才可节省空间。另一个问题是，一个目录项可能会分布在多个页上，在读取文件名时可能发生缺页中断。

处理可变长度文件名字的另外一种方法是，使目录项自身具有固定长度，而将文件名放在目录末尾的堆栈中。如上图所示的这种方式。这种方法的优点是当目录项被移除后，下一个文件将能够正常匹配移除文件的空间。当然，必须要对进行管理，因为在处理文件名的时候也会发生缺页异常。

到目前为止的所有设计中，在需要查找文件名时，所有的方案都是线性的从头到尾对目录进行搜索。对于特别长的目录，线性搜索的效率很低。提高文件检索效率的一种方式是在每个目录上使用，也叫做散列表。我们假设表的大小为 n，在输入文件名时，文件名被散列在 0 和 n – 1 之间，例如，它被 n 除，并取余数。或者对构成文件名字的字求和或类似某种方法。

无论采用哪种方式，在添加一个文件时都要对与散列值相对应的散列表进行检查。如果没有使用过，就会将一个指向目录项的指针指向这里。文件目录项紧跟着哈希表后面。如果已经使用过，就会构造一个链表（这种构造方式是不是和 HashMap 使用的数据结构一样，链表的表头指针存放在表项中，并通过哈希值将所有的表项相连。

如果按照如上图的这种组织方式而言，那么 B 的目录与该共享文件的联系称为 。那么文件系统现在就是一个 ，而不是一棵树了。

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个，我们不会在此着重探讨关于图论的东西，大家可以自行 google。

将文件系统组织成为有向无环图会使得维护复杂化，但也是必须要付出的代价。

很方便，但这也会带来一些问题。如果目录中包含磁盘地址，则当链接文件时，必须把 C 目录中的磁盘地址复制到 B 目录中。如果 B 或者 C 随后又向文件中添加内容，则仅在执行追加的用户的目录中显示新写入的数据块。这种变更将会对其他用户不可见，从而破坏了共享的目的。

上面的每一种方法都有各自的缺点，在第一种方式中，B 链接到共享文件时，inode 记录文件的所有者为 C。建立一个链接并不改变所有关系，如下图所示。