文件系统

fs 组成

linux fs 会为每个文件分配两个元数据结构：index inode & directory entry

• inode 指向数据所在块，并记录文件元信息，例如大小权限访问创建修改时间等等
• 目录项记录目录结构，并指向inode所在的块，会被缓存在内存

文件的块可能会被缓存在内存，例如目录结构块、inode块、数据块等。目录是一个特殊的文件，有自己的inode。超级块始终会被缓存到内存中。

目录不等于目录项，前者是一种fs组织结构，后者是目录中的一个具体条目，包含文件的与其他目录项的关联信息

磁盘的最小读写单位为扇区，保证它写入的原子性；fs 将一个或多个扇区封装为块，由fs实现额外的逻辑保证块写入的原子性

假设一个扇区512B，一个块4KB，则一次可写入8个扇区

磁盘的每个分区一般被fs划分为三个部分：

• superblock：记录fs元数据，例如大小状态空闲块、inode数量
• inode区：存inode
• 数据块区

vfs

fs需要把自己的根目录挂载到某个现有目录上才可以正常使用，例如把根目录挂载到 /mnt/usb

fs可分为三类：

• 磁盘fs
• 内存fs
• 网络fs

我们希望为用户提供一个统一的fs接口，这被称为vfs

文件使用

• syscall->vfs->fs->存储器

linux 中，打开的文件被抽象为一个描述符，即 fd。每个进程都有自己的文件描述符表，即打开的文件的表。每个表项包含以下信息：

• 文件描述符：标识该文件
• 文件指针：当前读写位置
• 文件状态：文件打开模式和属性
• 引用计数：表示有多少个文件描述符引用这个文件，为0时即可关闭文件
• fs相关：指向文件的inode或其他元数据

用户以字节为单位读写数据，内核以块为单位读写。fs提供了二者之间的桥梁：

文件存储

连续存储/非连续存储

连续存储

• 顺序摆放，高效读写
• 存在磁盘碎片以及文件不易扩展问题

inode/文件头需要记录其起始块以及长度，以找到整个文件

非连续存储

• 无磁盘碎片，文件大小可动态扩展
• 通过链表或索引记录数据块的块号

链表方式又分为隐式链表和显示链表

• 对于隐式链表，inode指向起始块和末尾块，每一个数据块留出一部分空间指向下一个数据块

  • 无法直接访问数据块，且指针消耗了一定的磁盘空间
  • 稳定性较差，若磁盘损坏导致指针丢失/破坏，则后续文件数据难以寻回

• 对于显示链表，它将链接各个数据块的指针都存到一个表里，以-1标记结束，解决了隐式链表的两个问题

  • 这也被称为 FAT 文件分配表，FAT会被加载到内存中，减少了磁盘访问次数
  • 不适用于大磁盘，200GB的磁盘和1KB大小的块、4B的表项，需要800MB存储FAT

对于索引，它为每个文件创建一个指向文件数据块的索引块，可以通过索引块找到数据块

• 优点在于：易于扩展、无碎片、支持顺序和随机读写
• 缺点在于索引块有很多空白未使用，浪费空间

对于更大的文件，可以采用链式索引块，即在每个索引块的末尾指向下一个索引块

或者多级索引块，索引块里面可以指向索引块，类似于多级页表：

Unix 文件实现方式

早期Unix FS使用了多级索引：0~n级索引，文件头/inode中存放 13 个指针：

• 10个直接块、1个一级块、1个二级块、1个三级块
• 若一个块可以放n个指针，则这种方式可以表示 $10+n+n^2+n^3$ 个数据块
• 这是 Linux Ext 2/3 FS 的方案，大块的访问仍需很多查询，Ext4做了一定的优化，暂不讨论

空闲空间管理

有三种常见的方式：空闲表、空闲链表、位图

空闲表：每个表项=首块块号+个数，连续分配

• 删除一个文件时，需要顺序扫描表，较耗时
• 适用于连续分配，以及有少量空闲区的磁盘

空闲链表：每个空闲块指向下一个空闲块，主存中只需保存指向首个空闲块的指针

• 易于增删，但不支持随机访问，需要大量的磁盘I/O，且消耗空间存储指针

以上二者都不适用于大型的文件系统，因为建立的空闲表和空闲链表都可能太大。

通常使用位图表示大型文件系统的块使用情况：0空闲1已分配

• 1个块4KB，一位表示一个数据块，那么一个位图块可以表示 $2^{15}$ 个数据块，即128MB
• 通常使用多个的位图块表示磁盘使用情况

FS结构

上述的位图表示使用 1个位图块+一些列数据块 可表示128MB的空间，这远远不够。

linux 把磁盘划分为多个相等的部分，每个部分被称为一个块组，它由以下内容构成：

• 1超级块+1数据位图+1inode位图+多块inode+多块数据
• 另还有多块块组描述符，它描述了每个块组的元数据，表示例如块组中空闲块和inode的数目
• 超级块和块组描述符表都是全局信息，被所有块组持有
  • 增强了系统的稳定性，提供多个副本，易于在崩溃时恢复
  • 使文件和管理数据更可能的接近，减少磁头寻道和旋转，提高性能
  • Ext2的后续版本使用了 稀疏技术，超级块和块组描述符只被保存在块组0、1和id为3/5/7的幂的块组中

目录存储

目录也是文件，也有自己inode，其数据块中存储的是目录项

原始的目录项由inode号+文件类型+文件名构成，但在这个目录下查找文件则效率不高。我们可以把他们改成一个哈希表

• 其key由文件名计算得出，value为原阿里的目录项
• 我们只需要处理一下哈希冲突就可以得到一个查找插入删除非常迅速的数据结构

通常，文件查找需要反复与磁盘交互，效率极慢，所以一般会缓存当前目录到内存中以加速查找

文件别名：软链接&硬链接

又名 Hard Link & Symbolic Link

硬链接通过让目录项指向同一个inode实现，这意味着它不能跨文件系统。同时系统会维护一个inode的硬链接引用计数，只有删除所有硬链接才会删除该文件。所有硬链接是平等的

软链接重新创建了一个文件，它的内容是另一个文件的文件名，因此可以跨文件系统。若删除原文件，则软链接文件仍存在但找不到指向的文件

文件I/O

常见的I/O方式的特性有：是否缓冲、是否直接、是否阻塞&同步

缓冲与非缓冲 I/O

• 很多库会使用缓冲区加速文件的访问，如果使用这些库，库再通过系统调用访问文件，则称为缓冲IO
• 否则即直接通过系统调用访问文件，为非缓冲IO

缓冲可以加速文件访问，但会有数据不一致的风险，对于重要文件建议手动刷新缓冲区，以维护数据一致性

其他利用缓冲的例子，例如endl才输出，刷新缓冲区，这可以减少系统调用的次数

直接与非直接I/O

OS有页缓存，利用页缓存的文件 I/O 被称为非直接 I/O，否则为直接I/O

• 非直接I/O会发生页缓存与用户空间内存之间的拷贝，而直接I/O不会，但它更慢
• 使用fs接口时，指明O_DIRECT则使用直接I/O，默认使用非直接I/O

页缓存被刷新到磁盘上的时机有：

• 用户主动调用 sync 刷新
• 内存不够了，或者缓存的文件页太多了
• 脏页缓存存在了一定的时间后

阻塞与非阻塞 I/O VS 同步与异步 I/O

• 阻塞I/O：例如用户调用read，CPU被阻塞在内核中，内核读取到数据后，把数据拷贝到用户空间，然后才返回
• 非阻塞I/O：用户直接返回，不阻塞

对于非阻塞I/O，可能需要不断轮询以等待数据准备好，这显然是一种浪费时间的做法。

• 从内核拷贝数据到用户仍是一个同步过程

于是我们有了 事件驱动的I/O 多路复用技术，例如 select、poll、epoll，等数据准备好了再通知应用程序进行操作。当没有事件发生时，当前进程会被阻塞，有事件时，会唤醒这个进程

• 可以在一个进程内注册多个socket，同时处理多个socket的I/O请求。
• 仍是同步

以上都是同步I/O，异步I/O无需等待数据准备、也无需等待数据拷贝，例如：aio_read

Page Cache

• 页缓存，也可被称为文件缓存，它将文件的数据缓存到内存中，加速文件读写
• 其大小为页的整数倍，文件不足大小的部分会用0填充
• 这是vfs对各种存储介质的缓存的抽象，统一称为页缓存，缓存到内存中

通过 mmap 以及 buffered I/O 将文件读取到内存空间实际上都是读取到 Page Cache 中。

buffer cache 与 page cache

• buffer cache 用于缓存块设备（例如磁盘）数据的一种机制，可以加速低层次I/O
• 而 page cache 是对文件数据的缓存，是一种高层次I/O

块缓存会通过拷贝的方式把数据交给页缓存，这会带来一定的性能开销；且相同的数据在内存中会存在两份，浪费内存。通过直接 I/O 可以直接与块设备交互，避免这种开销，但很慢。

在 linux 2.4 版本后，块缓存和页缓存被近似融合到了一起：

• 文件的块只会被缓存一次，位于页缓存中，块缓存维护指向页缓存的指针
• 没有文件表示的块、以及绕过文件系统操作的块则才会放到块缓存中

page cache 中的文件

前缀树/字典树可以快速剪枝，但树如果非常稀疏则会导致树高非常高，效率降低。基数树解决了这个问题，它也可以被称为压缩前缀树

基数树可以用于路由，即一个大的正则表达式：

• 黄色节点是一个通配符

使用在 page cache 中，每一个文件我们都用一个基数树来保存。我们可以根据偏移量在基数树上找到对应的页

page cache 与预读

• PAGE_READAHEAD

用户请求读3KB的数据，则会把整个块（4KB）以及其周围的一些数据都读出来，额外申请几个page

page cache 与文件一致性

• trade off：吞吐量和数据一致性间存在矛盾
• 文件一致性 = 元数据一致 + 数据一致

两种写策略：

• write through：直接同步脏数据。数据一致性强，吞吐量低
• write back：定期同步脏数据。数据一致性低，吞吐量高

这两种写策略基于以下 syscall，要么由用户发起，要么由内核发起：

• write back策略下，由特定持久存储设备的专门刷新线程调用
• 对于多线程架构，linux 内核使用了管理线程+多个刷新线程的方案
  • 管理线程监控脏页，若一段时间无脏页则销毁对应刷新线程；若有脏页且无刷新线程，则创建刷新线程
  • 刷新线程仅负责刷新脏页
  • 设备保存脏文件链表，其中存储脏文件inode节点，回写时写入对应的文件。
  • 在主动调用刷新接口/内核周期性刷新调用/内存不足时刷新

优势与劣势

优势：

• 加速数据访问
• 减少设备I/O次数，提高吞吐量

劣势：

• 额外占用物理空间，空间换时间。可能导致内存不足，频繁swap，系统负载上升
• 难以优化使用策略，无应用API。因此很多应用选择自己实现
• 在例如网卡的应用场景中，比直接I/O多一次设备读写
  • 直接IO直接与设备交互，一旦成功则代表数据一致，真的成功

查看系统的 page cache

可以看到内存中的页由：块缓存+页缓存+swap区缓存组成