《Operating Systems: Three Easy Pieces》学习笔记(三十二) 文件系统实现
本章将介绍一个简单的文件系统实现，称为 VSFS（Very Simple File System，简单文件系统）。它是典型 UNIX 文件系统的简化版本，因此可用于介绍一些基本磁盘结构、访问方法和各种策略，你可以在当今许多文件系统中看到。
整体组织
将磁盘分成块（block），每块大小相同，通常每块为 4 KB
其中一部分作为管理用空间（超级块，位图，inode 结构信息），另一部分作为数据空间
- 超级块（superblock）
- 超级块包含关于该特定文件系统的信息， 包括例如文件系统中有多少个 inode 和数据块（在这个例子中分别为 80 和 56）、inode 表的开始位置（块 3）等等。它可能还包括一些幻数，来标识文件系统类型（在本例中为 VSFS）。本例中为
S块 - 位图（bitmap）
- 用于表示块是否已分配，分为数据位图(data bitmap)， inode 位图(inode bitmap)，分别管理各自区域的块，本例中用
i块和d块表示 - inode 块
- 存放 inode 结构信息
- data 块
- 存放数据
inode
文件系统最重要的磁盘结构之一是 inode，几乎所有的文件系统都有类似的结构。名称 inode 是 index node（索引节点）的缩写，它是由 UNIX 开发人员 Ken Thompson 给出的历史性名称，因为这些节点最初放在一个数组(inode 数组)中，在访问特定 inode 时会用到该数组的索引。
补充：数据结构—— inode
inode 是许多文件系统中使用的通用名称，用于描述保存给定文件的元数据的结构，例如其长度、权限以及其组成块的位置。这个名称至少可以追溯到 UNIX（如果不是早期的系统，可能还会追溯到 Multics）。它是 index node（索引节点）的缩写，因为 inode 号用于索引磁盘上的 inode 数组，以便查找该 inode 号对应的 inode。我们将看到，inode 的设计是文件系统设计的一个关键部分。大多数现代系统对于它们记录的每个文件都有这样的结构，但也许用了不同的名字（如 dnodes、fnodes 等）
每个 inode 都由一个数字（称为 inumber）隐式引用，我们之前称之为文件的低级名称（low-level name）。在 VSFS（和其他简单的文件系统）中，给定一个 inumber，你应该能够直接计算磁盘上相应节点的位置。例如，如上所述，获取 VSFS 的 inode 表：大小为 20KB（5 个 4KB 块），因此由 80 个 inode（假设每个 inode 为 256 字节）组成。进一步假设 inode 区域从 12KB 开始（即超级块从 0KB 开始，inode 位图在 4KB 地址，数据位图在 8KB，因此 inode 表紧随其后）。因此，在 VSFS 中，我们为文件系统分区的开头提供了以下布局（特写视图）
要读取 inode 号 32 所在的 inode 结构位置，文件系统首先会计算 inode 区域的偏移量（32×inode 的大小(256 B) = 8192 B），将它加上磁盘 inode 表的起始地址（inodeStartAddr = 12KB），从而得到希望的 inode 结构的正确字节地址：20 KB。磁盘实际上是通过扇区来读取的，所以需要转为扇区地址，如扇区大小为 512 B，20x1024/512=40，也就是 40 号扇区 sector。
1
2
blk = (inumber * sizeof(inode_t)) / blockSize;
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;
在每个 inode 中，实际上是所有关于文件的信息：文件类型（例如，常规文件、目录等）、大小、分配给它的块数、保护信息（如谁拥有该文件以及谁可以访问它）、一些时间信息（包括文件创建、修改或上次访问的时间文件下），以及有关其数据块驻留在磁盘上的位置的信息（如某种类型的指针）。我们将所有关于文件的信息称为元数据（metadata）。实际上，文件系统中除了纯粹的用户数据外，其他任何信息通常都称为元数据。下表所示的是 ext2 的 inode 的例子。
| 大小（字节） | 名称 | inode 字段的用途 |
|---|---|---|
| 2 | mode | 该文件是否可以读/写/执行 |
| 2 | uid | 谁拥有该文件 |
| 4 | size | 该文件有多少字节 |
| 4 | time | 该文件最近的访问时间是什么时候 |
| 4 | ctime | 该文件的创建时间是什么时候 |
| 4 | mtime | 该文件最近的修改时间是什么时候 |
| 4 | dtime | 该 inode 被删除的时间是什么时候 |
| 2 | gid | 该文件属于哪个分组 |
| 2 | links count | 该文件有多少硬链接 |
| 4 | blocks | 为该文件分配了多少块 |
| 4 | flags | ext2 将如何使用该 inode |
| 4 | osd1 | OS 相关的字段 |
| 60 | block | 一组磁盘指针（共 15 个） |
| 4 | generation | 文件版本（用于 NFS） |
| 4 | file acl | 一种新的许可模式，除了 mode 位 |
| 4 | dir acl | 称为访问控制列表 |
| 4 | faddr | 未支持字段 |
| 12 | i osd2 | 另一个 OS 相关字段 |
设计 inode 时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在 inode 中有一个或多个直接指针（磁盘地址）。每个指针指向属于该文件的一个磁盘块。这种方法有局限：文件太大时指针不够用
多级索引
为了支持更大的文件，文件系统设计者必须在 inode 中引入不同的结构。一个常见的思路是有一个称为间接指针（indirect pointer）的特殊指针。它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据。因此，inode 可以有一些固定数量（例如 12 个）的直接指针和一个间接指针。如果文件变得足够大，则会分配一个间接块（来自磁盘的数据块区域），并将 inode 的间接指针设置为指向它。假设一个块是 4KB，磁盘地址是 4 字节，那就增加了 1024 个指针。文件可以增长到（12 + 1024）×4KB，即 4144KB
对于更大的文件，可以使用双重间接指针（double indirect pointer），即间接指针再指向间接指针，这样就扩展了 1024x1024 个 4KB 块。当然还有三重间接指针
这种不平衡树被称为指向文件块的多级索引（multi-level index）方法。
这种方法经过实践证明最符合当前的文件特征
文件系统测量汇总:
| 特征 | 说明 |
|---|---|
| 大多数文件很小 | 大约 2KB 是常见大小 |
| 平均文件大小在增长 | 几乎平均增长 200 KB |
| 大多数字节保存在大文件中 | 少数大文件使用了大部分空间 |
| 文件系统包含许多文件 | 几乎平均 100 KB |
| 文件系统大约一半是满的 | 尽管磁盘在增长，文件系统仍保持约 50% 是满的 |
| 目录通常很小 | 许多只有少量条目，大多数少于 20 个条目 |
补充：基于链接的方法
设计 inode 有另一个更简单的方法，即使用链表（linked list）。这样，在一个 inode 中，不是有多个指针，只需要一个，指向文件的第一个块。要处理较大的文件，就在该数据块的末尾添加另一个指针等，这样就可以支持大文件。
主要问题是链表不支持随机访问
目录组织
一个目录基本上只包含一个二元组（条目名称，inode 号）的列表。
假设目录 dir（inode 号是 5）中有 3 个文件（foo、bar 和 foobar），它们的 inode 号分别为 12、13 和 24。dir 在磁盘上的数据可能如下所示：
| inum | reclen | strlen | name |
|---|---|---|---|
| 5 | 4 | 2 | . |
| 2 | 4 | 3 | .. |
| 12 | 4 | 4 | foo |
| 13 | 4 | 4 | bar |
| 24 | 8 | 7 | foobar |
每个目录有两个额外的条目：.（点）和..（点点）。点目录就是当前目录，而点点是父目录。
删除一个文件（例如调用 unlink()）会在目录中间留下一段空白空间，因此应该有一些方法来标记它，比如 inum 标为 0，以便以后复用
可以看到扩充了 reclen（记录长度）和 strlen（文件名长度）两个字段
通常，文件系统将目录视为特殊类型的文件。同样由 inode 结构管理，指向的数据空间存放了目录结构数据，也就是上面提到的二元组或加了扩展的组
简单的线性目录列表并不是存储这些信息的唯一方法。还有 B 树也可以表示目录，参考数据结构–树，可以带来更好的查找和插入性能
空闲空间管理
- 位图
- 空闲链表：超级块中只包含指向第一个空闲块的指针，后面都是链表
- XFS 使用的 B 树
创建新文件时，为了性能和后续扩展性，可能会预分配（pre-allocation）一定数量连续空闲块，保证文件的一部分是连续的
访问路径：读取和写入
我们假设文件系统已经挂载，因此超级块已经在内存中。其他所有内容（如 inode、目录）仍在磁盘上。
从磁盘读取文件
先读根目录 inode 信息，找到存根目录结构的数据块，找到对应子目录的 inode 号，重复步骤，一直到路径的末尾
很明显这么操作会导致大量的随机读取，性能很差
写入磁盘
写入过程和读取类似，在路径的末尾，
如果要创建文件，需要一下步骤：
- 读取位图（查找空闲 inode 和数据块），更新 inode 位图和数据位图
- 更新 inode 结构
- 在对应的目录结构里插入一个新条目，需要读取并修改目录结构所在块，还要读写目录 inode 结构
每一步都包含很多 IO，性能很差
缓存和缓冲
将访问频率比较高的块放入内存，即可减少 IO 频率，如 inode 块，位图块等
一般有两种缓存策略：
- 静态分配：早期的文件系统因此引入了一个固定大小的缓存（fixed-size cache）来保存常用的块
- 动态分配：许多现代操作系统将虚拟内存页面和文件系统页面集成到统一页面缓存中（unified page cache）
写缓存也有好处，比如合并多个写入，但也带来了掉电丢失数据的风险，一般数据库会禁止写缓存