文件系统概述:性能指标、设计思路、可靠性保障

发布网友 发布时间：2024-09-27 04:57

我来回答

共1个回答

热心网友 时间：2024-10-04 04:42

文件系统可能是操作系统中最为复杂的一块，相比内存管理和进程调度，其涉及到的问题更加多，软件需要帮硬件解决的问题也更多。相比网络IO，文件IO没有权威性的，能从IO栈顶讲到IO栈底的书。

本文不适合初学者，但是适合作为初学者的复习资料和面试党的学习资料。

目前最主流的持久化存储硬件包括SSD（固态硬盘）和HDD（机械硬盘）。一般而言，SDD的速度是HDD的十倍到二十倍，成本是HDD的五倍到十倍。

在京东分别搜索机械硬盘和固态硬盘，按销量排行，选取前三（2021/4/24），感*知一下价格差异（忽视机械硬盘之间、固态硬盘之间的差异）（不构成选购建议）

汇总成表格，平均每10GB的价格

如果想详细比较价格和容量，可以参考这里。

不管是HDD还是SSD，其管理组织形式基本是一致的，都是以sector（扇区）为单位，一般是512B或者4KB。

文件系统对于磁盘的管理有着另一重定义，文件系统以block（有时也称为page）为单位分配、记录磁盘的使用。page一般是4KB、8KB、16KB、32KB。

对于sector、block、page这几个名词有时候会有一些歧义，这里做一个个人向的梳理：

sector 一定指的是硬件管理资源的最小单位

block 可能同sector、可能同page，大多数时候指的是多个sector，即page

page 一定指的是操作系统管理资源的最小单位

下文中将尽量使用sector和page，block的含义皆同page。

很遗憾，广泛而言，目前硬件可以提供的保证很少。

在随时可能断电的情况下，大多数硬件能提供单个sector的原子性写入；但是也有少数硬件连单个sector的写入都无法保证；如果一个page对应多个sector，则单个page的完整写入总是无法得到保障。更加详细的情况可以查看这个讨论：crash - Are disk sector writes atomic?。

另一方面，对于机械硬盘来说，环道可能会损坏；对于固态硬盘来说，存储颗粒可能会损坏。有些硬盘会帮我们解决这些问题，但有些不会。

最后一个方面，对于同时发给硬盘的多个操作（比如写多个不连续的sector），硬盘并不保证操作的顺序。结合其弱原子性，所以硬盘可能处在任何一个中间状态。这主要是由于机械硬盘的寻址优化策略和固态/机械硬盘的缓存策略导致的。

以上这些问题，硬件厂商和文件系统都在尝试解决，有些已经取得了不错的结果。但是对于软件开发者来说，特别是数据密集型软件开发者（比如数据库），屏蔽硬件和操作系统的差异，提供始终如一可靠的软件，是逃避不开的责任。

了解这些“不可靠”带来的另一个启示是，我们可能会为了高性能而使用O_DIRECT模式跳过文件系统（的部分功能，比如page buffer和log系统）来操作文件。但是这样也会损失了操作系统提供的一些可靠保障。

在知道了底层硬件组织之后，我们再来看看文件系统希望对外提供什么样的接口（也就是最上层的API），最后再结合顶层的要求和底层的硬件，看看我们应该怎么实现一个文件系统，其中有哪些困难需要我们去解决。

作为操作系统最上层的使用者，我们希望文件系统能提供

尽可能快的并发读写

尽可能接近硬件本身的吞吐量

多层文件目录结构

随机地址读写

足够、甚至无限长的文件名

足够、甚至无限大的文件大小

足够、甚至无限多的文件，包括总文件数和单个目录下的文件数

原子性的写操作，包括写文件、重命名、创建文件等

在多个位置对同一个文件的映射（类似windows的快捷方式）

屏蔽宇宙射线对硬件造成的损坏

对于操作系统和文件系统的开发者，又有些不太相同的诉求和考虑点

怎么让操作系统和文件系统解耦合

怎么启动一个操作系统

怎么启动一个文件系统

怎么实现文件系统多个版本的无感知升级

在了解诉求之后，我们可以将诉求量化成性能指标。

文件系统中最主要的两个因变量是IOPS和吞吐量

IOPS：Input\Output Pre Second，文件系统每秒处理读写请求的个数，单位 个/s

吞吐量：文件系统每秒读写的数据量，单位 MB/s

文件系统有非常多的自变量，即使用场景。也正因为文件系统的使用场景非常多，所以性能测试非常复杂。主要包括队列深度、并发线程、单次请求的数据大小、读写的方式

队列深度：单个线程发起了多少请求，这里一般是指通过阻塞IO以外的技术实现单线程N队列深度，比如Linux下的AIO和io_uring()。事实上在IO栈的每一层，都可能有队列深度。

并发线程数：同时有多少个线程发起请求。

单次请求的数据大小：可以是block size 的整数倍、非整数倍、小于block size等等。

读的方式：顺序读、随机读、跳跃读（比如固定隔2MB读4KB）、反复读（反复读一个文件)、倒序读（将一个文件从后往前读）

写的方式：顺序写、随机写、跳跃写（同上）、反复写（反复覆盖写一个文件的部分数据）、新建文件（因为新建文件涉及到许多元数据的修改，所以性能会比随机写查）

一般的文件IO benchmark工具（比如CrystalDiskMark 8），都聚焦于前三个自变量（单线程的队列深度、线程数、单次请求的数据大小），且单次请求的数据大小都是4KB的整数倍；在读写方式上，只提供了顺序读写与随机读写（不知道随机读写随机的位置是否是block size的整数倍，也不知道是如何随机的）。因此硬盘的制造商和文件系统都会致力于优化上述的固定场景。但是在工程上，其实际的性能还需要经过更加严谨的测试。

文件系统管理硬盘的存储空间，就内存系统要管理内存空间很像。一般而言，文件系统以4k作为最小管理单位。这个数据也有一些论文的支持，研究表明系统内大多数文件都小于4k。我们将文件系统的最小管理单位称为page，有时候也称为block。

文件系统是需要对硬盘空间进行管理，而内存系统是需要对内存空间进行管理，两者有非常多相似的地方，最主要的相似点就在于分段和分页的思想相似。

为了满足上述的诉求，我们一般将block分为这么几类：

root/boot block

一般这个block是文件系统的第0个block。文件系统不会使用和修改这个block，而这个block一般用于系统启动。

super block

文件系统的元数据，比如page的大小、空闲的page数、文件系统最后一次被修改的时间等等。具体可以查看ext4文件系统的super block来感受一下。

logging block

存放着日志文件。这一部分借鉴了数据库设计中的logging模块，通过write ahead rule来保证写操作的原子化和线性化。事实上因为logging模块比较复杂，且实现方式各不相同，logging block内部通常还有多种block的分类。有些古老的文件系统可能没有这个模块。

bitmap block

记录文件系统中空闲的block。为了实现这一目的，也可以使用其他数据结构。一个文件系统内会有多个bitmap block。

inode block

文件的元数据，不包括文件的数据。比如创建时间、引用计数、文件大小、文件的数据在哪些page上等等。具体可以查看源代码感受一下。

因为一个文件的元数据很小，用不完block size，所以一个inode block其实存放着多个文件的元数据。一个文件系统内会有多个inode block。

data block

文件的数据。每个block只会存访一个文件的数据，所以如果一个文件小于block size，则会产生内部碎片。

directory data block

这也是一个data block，但是和一般文件的data block相比，这里存放的是文件夹的数据，是给操作系统使用的。其内部存放的是一个文件夹下多个文件的文件名和inode。

inode是index node（索引节点）的缩写。在最初的文件系统中，所有的这些节点都放在一个数组之中，我们根据下标访问特定的节点，再访问对应的文件数据。现在基本所有的文件系统都有inode这种结构来保存文件的元数据。

每个inode都有一个id，我们通过id找到对应的inode节点。在directory data中，记录着文件名和inode number的映射关系，所以我们指定一个文件名，就能找到对应的inode。同时因为inode和文件名的解耦合，一个inode可以对应多个文件名。

梳理一下，文件名、inode、文件数据大概是这么一个关系

一个文件名对应一个inode；一个inode可以对应多个文件名。

一个inode对应一组文件数据；一组文件数据对应一个inode。

由于文件元数据和文件数据的解耦合，文件的类型获得更大的自由度，甚至我们可以新建一个文件，但是文件没有数据，或者数据在内存中。

目录也是一种文件，其数据仅仅由文件系统来读写，数据主要是文件名和inode id的键值对。

inode的基本操作有这么几个，我们的设计和优化也是围绕这几个操作的

根据inode id找到对应的inode

删除一个inode

申请新的inode

在简单的实现中，我们可以设置固定的一块区域为inode block，并且将inode按顺序编号，则根据inode id找到对应的inode是O(1)的，删除也是O(1)。申请新的inode麻烦点，因为inode的编号不能无限增长（因为inode block是固定的，所以inode的编号早就划分好了）。所以要么遍历inode block来查找空闲的inode，那么使用额外的数据结构来管理空闲的inode。

如果我们使用B树，则以上三个操作基本都是O(1)的。唯一的问题就是复杂，容易出问题。

当然还有其他的数据结构，而除了以上这三个基本操作，我们还需要考虑inode的可扩展性和其本身的空间占用，比如上述的简单实现中，就不具备可扩展性。B树相比简单实现有良好的可扩展性，但是占用的额外空间会多一点（但是也还行）。

一个inode可以对应多个文件名。我们把这种共享inode id来共享文件数据的方式，称为硬链接。

与硬链接对应的，是软链接。软链接是一种特殊的文件类型，其值为“链接的文件的文件路径”，这个文件路径可以是绝对路径，也可以是相对路径。因此通过软链接读取文件数据，需要先通过软链接文件的值，找到对应的文件，再找到该文件对应的inode id，再……（省略），在性能上不如硬链接好。同时软链接不会增加inode的引用计数，因此如果源文件被删了，软链接这个文件不会消失，但是会失效。

在一个文件系统中，每个block的大小都是固定的。所以只要知道block的顺序，结合block的大小，就可以很轻易地算出来任意偏移量在哪个data block中。

在inode中，有一些字段记录了文件数据所在的block。如果一个文件很小，那么inode中这些字段就够用了。但是如果一个文件很大，显然我们不可能为了小部分的大文件去增大每个inode结构体的大小。

为了解决这个问题，我们通常使用名为间接指针的技术。在inode结构体中，一般会n个字段（一般是十几个），记录着文件前n个data block所在的位置。还有一个特殊的字段，这个字段也标记了一个block位置，但是这个block存的不是文件数据，而是data block的地址（我们姑且称之为indirect pointer block，间接指针block），这样我们就可以记录更多的data block的地址，来实现更大的文件。

再次扩展这个思路，我们可以实现多级嵌套，一个间接指针block记录着其他间接指针block，就可以实现支持更大的文件。

假设每个block的大小是4kb，block的索引是32位，即4byte（可以索引16TB的空间）。

一个block内可以记录$4KB \div 4B=1024$个block，文件最大为$1024 \times 4KB = 4MB$。

如果使用二级间接指针，就可以记录$(4KB \div 4B)^2= 1024^2=2^{20}$个block，文件最大为$2^{20}\times 4KB = 4GB$。

如果使用*间接指针，就可以记录$(4KB \div 4B)^3= 1024^3=2^{30}$个block，文件最大为$2^{30}\times 4KB = 4TB$。对于一般用户而言，基本是够用了。

但是这些间接指针block带来的消耗也不可小觑。对于二级间接指针，如果我们记录一个4GB的文件，需要额外的$4KB + 1024 \times 4KB\approx1MB $。*间接指针的话需要$4KB + 1024 \times 4KB + 1024^2 \times 4KB\approx 1GB $。这意味着，如果记录一个大文件，大概需要额外四千分之一的空间来记录文件数据在哪。

为了减少这些间接指针block的数量（毕竟这些block也要消耗硬盘的存储空间对吧），我们还可以让间接指针block记录block的范围（类似分段式内存管理），比如从block 520 到block 666，都是这个文件的数据。当然，还有很多其他办法和解决这里的问题。

在简单的实现中，会将一块固定的区域划分为inode block，当然这样会*文件的总数。

如果使用B树，那么文件总数就非常好扩展。但是B树也会遇到所有id用完的情况，那么就需要从0找起，寻找之前分配出去但是现在已经被删除的inode id。所以B树可能也需要额外的数据结构来记录空闲的inode id。

我们还可以使用链表来扩展inode block，则单次查找的复杂度都会上升到O(N)。不过也可以优化，比如链表上单个节点非常大，导致N很小，同时在内存中以数组的形式缓存一份链表的信息，那么复杂度也可以很低。

总之，这里的问题是非常清晰的，而解决方案和数据结构的选择与组合是自由而多样的。

对于目录，我们最主要的诉求是记录文件名和inode id组成的键值对。通常情况下，单个目录下的文件都不会很多，我们以数组的形式保存键值对，通过遍历来搜索数据，就足够了。

我们可以假设一般文件名不会超过8字节（不足8字节用0补足），所以以8字节文件名+4字节inode id为一组，作为一个键值对（这12字节也叫一个单位空间）。那么一个4Kb的block，可以放下341.33个键值对。

如果我们想在一个目录下放更多的文件，考虑到目录也是一个文件，所以问题和“无限大的文件”是同一个问题。就不用再赘述啦。

如果想支持无限长的文件名，大体上有两种方案，也可以与分段和分页进行类比：

分段：在每一条记录的开头的2字节，记录文件名的长度n（2字节已经可以记录2^16^个byte，一般一个block也才2^12^个byte），然后紧跟着长度为n的文件名，最后4字节是inode id。或者不用2字节来标记长度，用字符串结束符（8个0）来标记结束。

分页：如果文件名超过8字节，则占用两个8+4的空间。那我们怎么记录一个文件条目占了多少单位空间呢？可以通过字符串结束符来标记结束，如果没结束，则顺延搜索到下一个单位空间；也可以在单位空间一开始就记录一下占用多少单位空间；也可以在data block首部就记录好各个条目所占的单位空间大小。

我们还可以从间接指针中获取一些灵感，比如我们把超长的文件名放在一个专门的block中。毕竟长文件名是极少数，或许性能上不会有什么大问题。

以上我们都是将数据以列表的形式存储。也可以用别的数据结构，比如B树、链表等等。

总而言之，目录的数据结构需求也很明确而简单，其设计也很灵活。

bitmap实现的事情很简单：记录哪些block没有被使用。bitmap是一个简单的，可以实现这一目的的结构。在使用的时候，我们遍历bitmap即可找到未被使用的block。显而易见，这样的性能并不会特别好。

我们还可以吸取分段的思路，记录空闲block的范围。比如1-20是空闲的，30-80是空闲的。

我们还可以不使用额外的数据结构，用这些空闲的block本身来记录“空闲的block”。每个空闲的block记录着连续的空闲block的长度，同时指向下一个连续的空间的block块。比如：1号block（后续连续20个都是空闲的，下一个空闲的block是30号） -> 30号block（后续连续50个都是空闲的，下一个空闲的block是N号）。

无论是什么结构，我们都还希望文件数据能尽可能连续存储，这样读取的时候也会有更好的性能。

我们在了解了inode和directory data之后，看看如果新建一个文件。并写入一些数据，大概是怎么样一个过程，涉及到哪些block。

申请一个新的inode，那么就涉及到一个inode block的写。

可能有额外的数据结构来记录着空闲的inode block，所以还要再写几个block。

申请新的data block，所以需要写bitmap block。

向新申请的多个data block写入数据。

如果写入的数据很多，涉及到了间接指针，则还需要写间接指针block。

新的文件被创建了，其目录的data block也要修改。

因为目录的data block被修改了，所以目录的inode也要修改，又涉及一个inode block。

总结一下，新建一个文件，需要写2-N个inode block、0-N个间接指针block、1-N个bitmap block、2-N个data block。即使系统能在内存中准备好所有block的数据，并一次性发送给硬盘，由于硬盘不能保证原子性写入和写入的顺序，在断电等情况下，数据还是会出错。

我们需要把这么多block的写包装成一个事务，让这个事务原子性执行，并能够从各种崩溃中恢复（主要是断电和拔线，大水冲了机房那谁都救不了）。

整个基本流程遵照了write ahead rule，意思是在任何写操作前，都先写日志，再写实际的数据。具体而言，整个流程分为write log、commit、install三步。

write log就是写日志，日志中最主要的内容是，一个事务中被修改后的block的数据和block的位置。

commit是写日志结束的标志，同时也是一个写事务完成的标志，我们可以认为在commit之后，消息就已经被安全地写入了，应用程序可以响应用户。

install则发生在commit之后任何一个可能的时间，其将写操作真正应用到文件系统的其他位置，即将这些block的数据写入block的位置。注意这一步是幂等的，即不管执行多少次，甚至在install的过程中发生了崩溃，只要最终执行完成即可。

如果在commit前系统崩溃/断电了，则程序没有响应用户，这条日志最终也不会被install。如果在commit后系统崩溃/断电了，则在之后某次系统上线后，会install这条日志。如果在install的时候系统崩溃/断电了，则下次系统上线会重新install这条日志且不会发生重复写错误。

在同一时间，可能多个程序同时向操作系统提交了写操作。如果每个程序的文件IO操作串行执行的话，硬盘会反复发起IO完成的中断，带来多次CPU上下文的切换。同时硬盘本身也无法充分发挥自己的写性能（比如SSD 1ms 可以写入1M，但是操作系统和CPU 1ms内最多提交一个100k的写请求），且无法优化随机写的性能（比如因为HDD的寻址优化）。因此文件系统总是会尽可能多地将多个写请求（程序 -> 文件系统）合并为一个写事务（文件系统 -> 硬盘驱动）。

具体而言，合并的方式比较多样，比如根据时间片来划分，每10ms内的写请求进行一次合并；或者根据写入的数据的大小做划分，每1MB写入一次；或者采用一些混合策略，或者启发性策略。

一般而言，所有的写请求（比如在C语言中的write函数调用）并不会立马发生磁盘IO，从write函数中返回也不意味着这个写操作已经成功了；这只意味着文件系统已经了解了这个写操作。只有从flush函数中返回，才意味着这个写操作已经随着事务commit了。

和数据库中类似，文件系统的每个事务也都有唯一的id，而且id会不断增长。这个id需要持久化保存。

有些人可能会疑问，为什么我们要单独强调commit这个操作呢？write log写完，不就是写日志结束吗？这是因为write log的过程中，系统也可能会崩溃，进而我们可能无法区分硬盘上的数据，到底是我们写入的，还是由于硬盘的惰性擦除而留下的脏数据。因此对于文件系统而言，需要将commit单独拎出来，视为非常重要的一步。

因此这里的核心问题和计算机网络中某些问题很像：怎么验证消息没有被篡改？最自然而然的方式是，给消息添加一个校验码（hash值）。当文件系统在内存中准备好日志之后，我们可以计算日志的hash值，并放入到日志之前。然后将hash值和日志的写请求一起交给硬盘。

只有hash值和日志都完整写入，之后install前的校验（hash(日志) == hash值）才能通过。有任何一块没写入，或没有完整写入，则校验无法通过，则认为这条日志没有commit，不需要install。

commit之后，数据还没有在其应该在的位置。假如我们修改了一个文件的1字节，并在commit之后，跳过文件系统去查看磁盘的内容，会发现该文件并没有发生改变。但是如果我们通过文件系统去读取这个文件，会发现文件改变了。

在读取过程中，我们可能会命中文件系统的page cache，所以根本不会发生硬盘IO。如果没有命中page cache，则我们要去读硬盘了。而在读硬盘前，我们会检查一下将要读取的block是