File System (18,19,20)

Building a File System

文件系统 (File System) 是操作系统基于块存储 (block devices) 之上提供的一层逻辑抽象，使得用户能够将数据以文件、文件夹的形式组织起来。

文件系统的功能主要包括：

  • Disk Management：将磁盘块 (disk blocks) 组织成文件

  • Naming：方便用户重命名文件，从而通过文件名找到数据，而不是直接指定磁盘块

  • Protection：保证数据安全，不被破坏

  • Reliability/Durability：保证数据在可能出现的崩溃、故障、攻击下依然能够持久化

在不同角色的眼中，文件 (File) 呈现的样子不同：

  • 在用户眼里，文件是持久化的数据结构

  • 在系统调用接口眼里，文件是字节集合 (collection of bytes)

  • 在操作系统眼里，文件是块集合 (collection of blocks)

因此假如用户想要读取某文件中第 2 字节到 12 字节的数据，操作系统需要将 2-12 字节所在的数据块读到 kernel space，再复制到 user space，最终返给用户。即使用户使用 getc(), putc() 这种 api，操作系统仍然需要整块地读写数据。

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

  • 数据持久化：使用磁盘

  • 磁盘性能：尽量使用线性访问 (sequential access)，减少寻道

  • 在读写文件之前需要打开文件：在打开的过程中实现保护、检查、索引等逻辑

  • 在使用中才能决定文件大小：可以从小文件开始，不断往里写数据，需要增量地扩容

  • 支持组织成文件夹：存储文件夹及其中文件的信息

  • 动态分配和释放数据块

Disk Management Policies

扇区组织

文件在逻辑上是数据块线性排列的数据块，而文件夹是从文件名到文件的映射关系。想要优化文件的读取性能，就需要将文件的数据块线性地排列在磁盘的连续扇区 (sectors) 上。有两种可能的做法：

  1. 给每个扇区赋予坐标 [cylinder, surface, sector]，然后按字典序排列，坐标相邻即相邻。

  2. 利用 Logical Block Addressing (LBA) 模块，为每个扇区赋予一个整数编号，通过 controller 将扇区编号转化成其真实的物理位置

若使用方法 1，OS/BIOS 需要直接面对坏死的扇区 (bad sectors)；若使用方法 2，磁盘的这些信息就能够对 OS 不可见，使得后者无需关心这些问题。目前普遍使用方法 2，方法 1 已被弃用。

空闲数据块管理

空闲数据块管理模块负责回收和分配空闲的数据块，一次申请的数据块理论上应当尽量相邻 (locality)。用于管理的两种常见数据结构是：

  • 链表 (linked list)

  • 位图 (bitmap)

前者的查询速度太慢，现在以及基本被弃用。

文件布局

需要文件头 (File Header) 来保存文件元数据，跟踪文件数据所在的数据块地址，以及让文件数据块的分布于使用模式更加匹配，从而达到优化文件读写性能的目的。

Components of a File System

文件系统的主要职责就是根据文件路径找到文件数据，而这其中最重要的两个概念就是文件夹与文件。

文件夹

文件夹就是一个层级结构，每个文件夹可能包含多个文件以及子文件夹。文件与文件、文件夹还可以通过硬链接和软链接相互引用，最终使得整个系统的文件夹结构成为一个有向无环图 (DAG)。

文件

文件是带名字的持久化存储，它由数据与元数据构成：

  • 数据：磁盘上的数据块

  • 元数据：

    • owner, size, last opened, ...

    • 访问控制

      • R, W, X

      • Owner, Group, Other (Linux)

      • ACL in Windows

如上图所示：每个文件夹中的文件实际上对应着一个文件号 (File Number)，它指向文件索引结构 (File Index Structure)，而该索引结构最后会引导指向文件数据所处的数据块上。

FAT (File Allocation Table)

由于存储设备是按块读写，我们可以将所有数据块编号，记录在一张表上，如下图所示：

这张表的每个位置对应着存储设备上相应位置的数据块，我们称之为 FAT。FAT 实际上就是一个文件索引结构，每个文件的文件号可能是 FAT 上 [0, N-1] 的任意一个，如果某个文件的大小超过一个数据块，则在 FAT 中，属于该文件的相邻的数据块会以链表的形式被串联起来，而文件号对应的 FAT 元素就指向这个链表的根节点：

同时，FAT 中未被分配的数据块同样被一个链表串联，该链表被称为 FAT free list。新建文件、分配文件空间的过程就是从 free list 中分配数据块，并返回根节点编号的过程；删除文件的过程就是回收文件号，将文件对应链表回收到 free list 中的过程；格式化磁盘的过程，就是将所有文件号都释放，所有数据块回收到 free list 中的过程。

FAT 的设计十分轻巧、简单，被许多系统广泛使用，如 DOS，Windows，thumb drives 等等。那么 FAT 这个结构本身存在哪里呢？显然 FAT 需要持久化，因此它也需要被存储在磁盘中，每次启动时读入内存。

FAT Assessment

我们可以从许多角度评价 FAT：

  • 访问单个文件多个数据块耗时

    • 顺序访问

    • 随机访问

  • 磁盘碎片

  • 存储小文件

  • 存储大文件

FAT Directory

FAT 中的文件夹实际上就是一个普通文件，它内部保存着 <文件名, 文件号> 的映射关系。

在 FAT 中：

  • 所有的文件元数据都保存在文件夹中，这个设计在实践中被验证并不是很合理

  • 文件夹中的文件数据使用链表串联，这意味着找到其中单个文件都是 O(n) 复杂度

通常根目录 "/" 被保存在固定的位置，以此解决万物之源的问题。

思考这样一个问题，想要访问文件 "/my/book/count"，需要访问几次磁盘？

  1. 从磁盘的固定位置读取 root 文件夹的文件头 (header)

  2. 读取 root 文件 (夹) 的第一个数据块，遍历 <文件名/文件号> 链表，检索 my 文件 (夹) 对应的文件号

  3. 读取 my 文件 (夹) 的文件头

  4. 读取 my 文件 (夹) 的第一个数据块，检索 book 文件 (夹) 对应的文件号

  5. 读取 book 文件 (夹) 的文件头

  6. 读取 book 文件 (夹) 的第一个数据块，寻找 count 文件对应的文件号

  7. 读取 count 文件的文件头

  8. 读取 count 文件的数据块

FAT 存在两个问题：

  • FAT 没有访问控制

  • FAT 中文件的元 (头) 信息存储在文件夹中，而文件数据块中只有文件数据本身

Characteristics of Files

在题为 "A Five-Year Study of File-System Metadata" 的一篇论文中，作者分析了用户在真实场景下存储的文件特点，基本符合 2/8 定律：

  • 大部分文件都很小

  • 大部分空间都被少数的大文件所占据

因此一个好的文件系统既需要能够存储大量的小文件，也要具备存储大型文件的能力，同时还要保证两种极端情况的读写效率。

从这个角度来看 FAT：小文件的读写性能很好；但由于单个文件中的数据块是通过链表串联，且在使用过程中容易产生外部碎片，使得读写大文件的性能则要大打折扣。

那么更好的文件系统应该长什么样？

Unix Fast File System (Optimization on Unix Filesystem)

inode

为了解决大小文件读写性能，以及其它 FAT 存在的问题，在 Unix Fast File System 中引入了 inode --- 一个存储文件所有信息的数据结构，每个文件号对应一个 inode。

inode 由文件的元数据以及若干数据块指针构成，这些指针包括：

  • Direct Pointers：直接指向数据块 (叶节点深度为 2)

  • Indirect Pointer：间接指向数据块 (叶节点深度为 3)

  • Double Indirect Pointer：间接地间接指向数据块 (叶节点深度为 3)

  • Triple Indirect Pointer: 间接地间接地间接指向数据块 (叶节点深度为 4)

inode 的设计使得：

  • 利用定长 inode 存储大小范围极广的文件的元信息

  • 小文件通过 Direct Pointers 可直接访问数据，效率不比 FAT 差

  • 大文件通过 Indirect Pointer 可访问数据块，且可以告别线性读取数据模式，提高大文件读写效率

  • 文件元数据与文件数据集中管理，而不是在文件夹中

inode 在 BSD (Berkeley Standard Distribution Unix) 4.1 中被首次提出，在 BSD 4.2 中增加了一些 Locality Heuristics，包括 Block group placement 和 Reserve space 的策略，有兴趣可以翻阅相关标准文档。值得一提的是，本门课程正是 Berkeley 的公开课，在 Berkeley 的课堂中听到这样的课程，学生应该会由衷地为自己的学校和专业感到骄傲吧！

FFS：File Attributes

文件的元数据主要记录权限控制信息，即我们所熟知的 user, group, owner 以及对应的 read, write, exec 权限配置，除此之外，还包括 setuid bit 和 getgid bit，用于让 root 用户以某个 owner、group 的权限来执行文件中的程序。

FFS：Data Storage

正如上文所描述，FFS 使用了多级的文件索引结构，来解决不同大小文件的读写效率问题，总结如下：

类别

数量

能覆盖的文件大小

Direct Pointer

12

48KB

Indirect Pointer

1

+4MB

Double Indirect Pointer

1

+4GB

Triple Indirect Pointer

1

+4TB

Freespace Management

FFS 利用 bit vector 来保存数据块的闲置信息，每个 bit 对应一个数据块，bit 值用于标记该数据块是否已被分配。bit vector 被存储在文件系统的固定位置。

Where are inodes stored?

在早起的 UNIX 和 DOS/Windows' FAT 文件系统，通常文件系统的元信息存储在磁盘最外圈，在磁盘格式化的时候，创建这些 file allocation table 信息，然而这种存储方式的问题在于：

  • 元数据与数据块距离较远，读取小文件需要先到外圈找 header，再回到内圈访问数据。想象刚才介绍的访问 "/my/book/count" 的例子，这产生了大量的额外寻道成本。

  • 一旦外圈磁盘被破坏，所有数据都不可用

在后期版本的 UNIX 系统中，文件系统的元数据被移动到离数据块更近的地方，并将属于同一个文件夹的文件及其元数据放到一起，组成 block group，且每个 group 都有各自的 freespace bit vector，如下图所示：

这种设计的好处在于：

  • 逻辑上可能被一起访问的文件更可能被存储在一起，从而加快这些文件元数据及文件数据读写效率。想象 ls 命令的功能，需要访问到当前文件夹下的所有文件数据，这种设计就能很好的适应该场景。

  • 无论磁盘发生什么样的局部损坏，总是有一些数据能够被恢复。

除此之外，FFS 还预留了 10-20% 的存储空间，即 reserve space 策略，来保证在为同一个文件分配数据块时，能够尽量分配到连续的数据块，使得碎片化不至于太严重。

说一千道一万，这些设计最终目的都在于：根据用户的访问习惯，相关的文件靠近一些，不相关的文件隔远一些，达到优化读写性能的目的。

FFS First Fit Block Allocation

FFS 的 bitmap 分配策略很简单，就是最近匹配，如下图所示：

Pros & Cons

FFS 的优点已经多次介绍，它的主要缺点在于：

  • 对极小的文件存储不够高效，因为每个文件至需要占用一个 inode 和一个数据块，即使这个文件本身只有 1byte 大小。

  • 当文件在磁盘上几乎连续存储时，读取反而不够高效（树状结构）

  • 需要保留 10 - 20% 的空间放置碎片化。

Directories

文件夹实际是一种特殊的文件，但是只有文件系统可以对它进行读写。应用程序只能通过系统调用来访问文件夹，如：

  • Open/Create

  • mkdir/rmdir

  • Link/Unlink

利用 Link 命令，不同的文件夹可以链接到相同的文件：

Link 有两种：

  • Hard link：实打实的链接，与正常的链接没有区别，相当于给文件创建了另一个文件名，文件的 ref-count 会增加 1，如果其它文件夹删除了该文件，该文件仍然存在。直到 ref-count 为 0 时，文件才会被真正删除。

  • Soft (Symbolic) Link：实际上是在文件夹文件 (directory file) 中存储着文件的路径。读取文件时，程序会顺着真正路径重新访问文件。如果实际文件地址指向的文件已经被删除，则该链接失效。

Large Directories: B-Trees (dirhash)

到目前为止，我们见到的文件夹内部的文件信息都是以链式存储的形式存在，每次寻找子文件 (夹) 的过程都是线性检索。当文件夹内的文件数量较多时，这种检索方式效率问题就开始凸显。因此有些标准也新增了树形结构组织的文件夹特性，如下图所示：

NTFS

NTFS 的全称是 New Technology File System，常见于 windows 系统中。它的特点包含：

  • 与固定大小的 inode 不同，NTFS 中支持变长 extents，理论上它可以存储的文件大小仅受限于硬件

  • 所有元数据与数据都以 <attribute:value> 的形式存在

  • 自由组合 direct 和 indirect 指针

  • 文件夹中的子文件 (夹) 默认用 B-tree 来存储

NTFS 中有一个 Master File Table (MFT)，类似 FAT 或 inodes array，MFT 中的每个元素被称为 MFT Record：

MFT Record 中保存着权限控制信息、文件名以及 attribute list，其中 attribute 视文件大小保存着任意数据或者索引数据 (类似 indirect pointers)。MFT 可以直接将极小的文件存储在 MFT Record 中，从而解决 FFS 中存在的极小文件的存储空间浪费问题。

对于中等大小的文件，NTFS 可以通过 data extent 来存储：

MFT Record data 中保存着 data extent 的起始位置及长度信息。

对于特大文件，NTFS 可以通过类似 indirect pointers 的方式，通过将 MFT Record 组织成树状结构，指向更多的数据：

In-Memory File System Structures

当应用程序通过系统调用打开文件的过程如上图所示：

  1. 解析文件名，找到对应的 FCB (File Control Block)，即 inode

  2. 在 per-process 和 system-wide table 中存储对应的信息

  3. 将 per-process table 中的 file handle 返回给应用程序

不同应用程序可能打开相同的文件 A，该文件在 kernel memory 中的 system-wide table 只有一份，但在 per-process table 中则各自保存着一份 file handle，且值不一定相同。

当应用程序拿到 file handle 后，利用系统调用读写数据时：

  1. 在 per-process table 中利用 file handle 找到该文件在 system-wide table 中的位置

  2. 执行相应的读写操作

Authorization

Authorization 就是所谓的鉴权，当我们讨论鉴权时，实际上就是在讨论 "谁能做什么操作" 的问题。这里的 "谁" 可以是个人，也可以是一个组，我们称之为 domain；而这里的 "操作" 可以是文件、设备等等资源的访问权限、操作权限、分配权限等等，我们称之为 object，将二者合起来建立一个矩阵：

就是访问控制矩阵 (Access Control Matrix)。但在实践中，用户数量、用户组数量、资源数量、操作类型数量都可能很大，导致这个矩阵变得很大，很稀疏，因此通常我们不会直接使用访问控制矩阵。

Two Implementation Choices

Access Control List

按列存储稀疏矩阵，将每个 object 上的所有用户(组)拥有的权限存成一个列表，最常见的例子就是 unix 系统中每个文件，即 object，的元信息中存储着每个角色 (owner, group 以及 world) 的 rwx 列表。ACL 的好处在于：

  • 节省存储空间

  • 很容易地改变每个资源的权限

但如果用户(组)的数量很大，鉴权系统仍然要存储很多用户的鉴权信息。

Capability List

按行存储稀疏矩阵，存储每个用户(组)拥有的 objects 权限列表，这些权限通常由某个用户(组)自己管控，因此也可以理解成每个用户(组)进程内部存储着拥有的 objects 列表。Capability List 在过去很流行，但逐渐被弃用。想象 page table，如果不是每个 process 自己保存着所有 page，而是每个 page 上保存着 process 列表，会是什么样的结果。CL 的好处在于：

  • 节省存储空间

  • 很容易地改变每个用户(组)拥有的权限

Combination Approach

有些鉴权系统会将 ACL 与 CL 结合：

  • 每个用户拥有一些角色(组)，即它的 CL。就像出国时持有的护照，所有其它国家会给与拥有某国护照的居民某种权限，但这些居民具体是谁其它国家并不关心，只要他持有护照即可。

  • 每个角色 (组) 被被赋予某些权限 (ACL)，这些权限会存储在具体的资源进程上，由资源来判断该角色(组)是否拥有相应权限。

通过修改用户和角色(组) 的关系来修改每个用户拥有的一组权限；通过修改角色(组)与资源权限的关系来修改所有属于该角色(组) 的用户所拥有的权限。

How to Revoke?

鉴权系统如何收回某用户对某资源的访问权限？

  • ACL：很简单，直接将该用户从资源允许访问的列表中删除即可，且修改之后即刻生效，因为每次访问资源进程都会通过 ACL 鉴权。

  • CL：单机环境下不难，可以通过将 CL 存储在操作系统的某个公共区域中，每次鉴权时查询一下即可。在分布式环境下很难，如果将权限分散，如果将权限分发给用户进程，如常见的 token，AK/SK，回收、甚至要求即刻生效的难度就增大了，常见的回收手段包括：

    • 增加过期时间，强制回收，可以支持延期

    • 给所有分发出去的权限加上 epoch 编号，通过增加 epoch 来一次性回收所有已经发出的权限

    • 记录分发出去的权限信息，使用黑名单来回收

Memory Mapped Files

利用传统的 I/O 方式读取文件时，我们需要先把文件数据块从磁盘中读到系统的缓冲区，再从系统的缓冲区复制到用户进程的内存空间上，这个过程中涉及到多次的数据复制以及系统调用。如果我们可以直接将文件映射到内存中的一块确定的区域上，由文件系统自动地按需读写 page，就可以省去不需要的复制和系统调用，这就是所谓的 mmap。

传统的文件数据读取过程如下图所示：

  1. 进程访问虚拟内存地址 VA

  2. MMU 到 Page Table 中查询 VA 对应的 page 所在的物理内存地址 A，未遂，触发 page fault

  3. 操作系统被中断，执行 Page Fault Handler，后者将对应的 page 读进缓冲区，复制到用户进程的内存中，当不同的进程读取相同 page 时，这些 page 会被复制多份到各自的内存空间中

  4. Page Fault Handler 结束，告诉进程重试一次

  5. 进程再次访问虚拟内存地址 VA，MMU 返回对应 page 的物理地址，进程访问对应物理地址上的数据

使用 mmap 的文件数据读取过程如下图所示：

除了第 3 步，其它步骤与传统方式相同。在第 3 步中，Page Fault Handler 会将对应 page 读到内存中的特定位置，无需复制到用户进程的内存空间中，当不同的进程读取相同 page 时，可以复用之前已经读入的数据，从而避免多余的数据复制和系统调用。

mmap 不一定要 map 到物理存储中的真实文件上，如果开始 ANONYMOUS 选项，相当于直接在内存中开辟一块多进程共用的空间，这些进程可以利用该空间进行数据共享和通信：

File System Caching

Buffer Cache

操作系统从磁盘中读取的文件并不会直接复制进入某个用户进程的局部空间，而是在 Kernel space 中做一层缓存 (Buffer Cache)，包括 disk blocks (block address -> disk content) 和 name translations (paths -> inodes)，主要原因在于：如果同时有别的进程访问相同文件，无需重新从磁盘中读取一次，这也是计算机 storage hierarchy 的精髓所在。

但缓存的容量受限于 kernel 分配到的 memory 空间，因此当缓存的体积增大时，操作系统就要选择合理的替换策略 (replacement policy)，将短期不太可能访问到的数据置换出去。常见的置换策略是 LRU：

Replacement Policy

  • 成本：每个 disk block 存储一个最后访问的时间戳

  • 优势：

    • 很适合 name translation

    • 当内存大小足够盛放计算机运行时经常需要访问的文件数据集合 (working set of files)

  • 劣势：

    • 当一些应用需要遍历文件系统时效率很低，如 `find . -exec frep foo {} \`

一些系统还支持定制化置换策略。

Cache Size

物理内存的大小有限，操作系需要在 Buffer Cache 与 Virtual Memory 之间做一个权衡，那么它应该如何决定？

  • 给 Buffer Cache 较大的空间会导致允许同时运行的应用数量减少

  • 给 Buffer Cache 较小的空间会导致许多 i/o 密集型应用运行缓慢

理想状态下，操作系统需要动态地摸索分配的边界，来平衡二者对物理内存资源的使用。

Read Ahead Prefetching

通常应用会线性访问文件，因此文件系统也可以通过预取的方式优化文件访问效率，尤其是并发访问。同时也有利于驱动中的 Elevator algorithm 能更高效地运作。应该预取多少也是操作系统需要做的一个决定：预取过多将延迟对别的应用请求响应时间，预取过少将导致并发文件访问的 seeks 过多。

Delayed Writes

通常向文件中写入的数据不会立即落盘，write() 系统调用通常会将数据从用户空间转移到内核空间，即 Buffer Cache，然后操作系统负责每隔一段时间将数据刷入磁盘 (在 UNIX 中这个周期为 30s)。这样做有好有坏：

  • 好处：

    • disk scheduler 可以很方便的重排请求，提高效率

    • 有些临时文件甚至不需要写入磁盘中，因此它们存在的时间很短

    • disk allocation algorithm 可以为单个文件分配更合理大小的空间

  • 坏处：

    • 系统可能在文件落盘的过程中崩溃，如断电

    • 更糟糕的情况时，在将文件信息写入文件夹的过程中崩溃

Important "ilities"

几个重要的 "ilities" 包括：

  • Availability：系统能接收并处理请求的概率，通常描述为 ""k 个 9"，如 99.9% 是 3 个 9 (3-nines of availability)。要注意的是，availability 描述的是系统故障，但系统是否正确处理了请求与 availability 无关。

  • Durability：系统从故障中恢复数据的能力，即数据持久化的容错能力。Durability 并不意味着 availability，比如金字塔里的信息 durability 很好，但在被发现之前一直是 unavailable。

  • Reliability：系统或组件在一定条件下、一定时间内正常运转的能力。它不止要求系统 available，还要求其运作正常，因此 reliability 包括了 availability，security，fault tolerance 以及 durability。必须保证系统在遇到系统崩溃、磁盘崩溃等问题时能恢复到正确的状态。

要注意的是，文件系统的 reliability 主要保证的是文件系统这层软件所存储的数据及元数据在发生故障后能恢复到一致的、正确的状态，而 durability 主要解决的是数据存储媒介本身的问题导致的数据丢失。二者处于不同的抽象层。前者主要靠 transaction 来保证，后者主要靠 redundancy/replication 来保证。

File System Durability

  • ECC：Disk blocks 包含 Reed-Solomon error correcting codes (ECC) ，后者可以从磁盘媒介缺陷 (media defects) 中恢复数据。

  • 保证写入的数据短期持久化：

    • 放弃 Buffer Cache 以及磁盘内部延迟/异步写模式

    • 使用特殊的 battery-backed RAM，非易失性 RAM (NRAM) 来保证 Buffer Cache 中的脏数据写出

  • 保证写入的数据长期持久化：

    • 需要复制多份数据

      • 将复制数据放在同一块磁盘上，如果 disk head 数据丢失，则全盘皆失

      • 将复制数据放在不同磁盘上，可能出现一挂全挂

      • 将复制数据放在不同服务器上，如果这些服务器所在的机房遭遇了火灾或闪电

      • 将复制数据放在不同机房上，...

RAID 1: Disk Mirroring/Shadowing

每个 disk 都有一个单独的 disk 备份，所有数据都需要复制到 shadow 上，如下图所示：

它的特点如下：

  • 适用于高 I/O，高可用环境

  • 成本为 100% 额外资源

  • 写带宽增加一倍，每次数据写入都有两次物理写操作

  • 两倍读请求处理能力

  • 故障恢复处理：将 shadow 替换原磁盘，同时将数据复制到新的 shadow 上

RAID 5+: High I/O Rate Parity

将数据交替分布在多个磁盘上，如下图所示：

利用一个 parity block 来做故障恢复：

P0=D0⊕D1⊕D2⊕D3P0 = D0 \oplus D1 \oplus D2 \oplus D3

恢复时，利用相同的 xor 操作将剩余的 block 合并就得到了原数据。相比于 RAID 1，RAID 5+ 能节省更多的成本。除了 RAID 1 和 RAID 5+ 之外，还有其它的 RAID 解决方案，这里不细说。

Higher Durability/Reliability through Geographic Replication

刚才介绍的 file system durability 方案都是本地方案，为了达到更高程度的 durability 和 repliability，系统需要能够将数据复制到不同地理位置上。

这种方案将对一致性保证造成影响，或多或少地增加写操作成本。我们将在之后的课程中继续讨论。

File System Reliability

磁盘运行到一半忽然断电、系统软件忽然崩溃，对文件系统意味着什么？

  • 一些操作执行完毕

  • 一些操作未执行而丢失

  • 某 block 可能出现部分更新的状态

如果写操作是异步的，就可能出现用户认为数据已经写入，但实际并未写入的现象。理想状态下，写操作最好是一个原子操作，要么成功要么失败回滚，但现实是：连单个 disk block 写出操作都不是原子操作。因此要实现文件系统的 reliability，我们需要 transaction 的抽象。实现 reliability/transaction 的主流做法包括：

  • Careful sequencing of file system operations (实际并不一定可靠)

  • Copy-on-write (WAFL, ZFS)

  • Journalling (NTFS, linux ext4)

  • Log Structure (flash storage)

Storage Reliability Problem

一个文件相关的系统调用可能包含对磁盘多个 blocks 的更新，如 inode，indirect block，data block，bitmap 等等，这些元数据或数据可能处于磁盘的不同地方，即使单个 block 的更新是原子操作 (实际不是)，也无法保证数据在发生崩溃后能保持一致。

More General Solutions - Transaction

transaction 为系统提供了一层抽象，将若干操作捆绑在一起，要么都成功，使得系统从 consistent state 1 转化成 consistent state 2；要么都失败，使得系统回滚到 consistent state 1。通常它的结构如下所示：

BEGIN TX: # get transaction id
  FOR update In UPDATES:
      errOrConflicts = update()
      if errOrConflicts:
          ROLLBACK
COMMIT

理想情况下：transaction 向外层提供 ACID 保证（事实并不一定如此）。那么文件系统应该如何实现这层抽象？

Copy-on-Write (COW)

要在文件系统中提供 transaction 抽象，可以先总结它的特点和用户的使用习惯：

  • 文件是长期存储的、供不同进程共享的数据

  • 文件通常是增量写入，相比随机访问，用户更多倾向于顺序访问

  • 文件载体的容量越来越大、越来越便宜

  • 进程进行文件读写时，通常有一层缓存，满足频繁读请求以及批量写出，提高处理效率

  • 应用通常需要事务抽象，即将一些相关的文件修改合并，原子地写出，要么都成功、要么都失败

假设我们要修改文件 foo，修改后的 foo 为 foo.v，一种思路可能是：

  1. 打开/创建一个新文件 foo.v

  2. 从 foo 中把数据复制到 foo.v，并执行更新操作

  3. 更新文件链接 ln -f foo foo.v

这种方法表面上看没什么问题，但实际上它要求更新文件链接操作是原子的。如果后者不是一个原子操作，遇到多个用户同时更新文件的场景，就可能出现并发问题。甚至有时候我们还需要保留一个文件的历史版本 (git)。

从前面的章节中我们了解到，文件实际上在磁盘中是分块存储的，不同的块位于不同扇区，那么每次更新文件时我们是否可以考虑只复制文件被修改的 block ？如下图所示：

如果是树状结构，那么我们还需要更新对应的分支节点：

一个典型的例子就是 ZFS。

Log Structured and Journaled File Systems

我们可以通过日志来解决 reliability 的问题。在一个日志文件系统中：

  • 所有的数据修改都被当作 transactions

  • 每个 transaction 信息被写入日志之时，就认为它成功 committed

  • 即便数据尚未真正落盘，但它的日志以及落盘，而这些日志实际上包含了所有数据信息。只不过日志中的数据信息的存储结构不一定是最终的存储结构

通常存在两种日志文件系统，Log Structured 和 Journaled，二者的区别在于：Log Structured 文件系统中的数据最终就存储在日志当中，查询也从日志中查询；Journaled 文件系统中的日志仅用于数据恢复，而真正的数据会按照另一种方式存储。因此在 Journaled 文件系统中，transaction 信息会先被写入日志并落盘，之后再由异步进程负责根据日志将数据以正确的形式写入磁盘，再清理日志。在故障恢复时，Journaled 文件系统根据日志来决定如何恢复。Ext3 和 XFS 都是 Journaled 文件系统。

Logging File Systems

Logging File System 在写数据之前会将本次 transaction 的操作内容 (intention list) 先写入磁盘，一旦 commit 信息进入磁盘，就意味着这个 transaction 已经 commit 成功；若 commit 信息未进入磁盘，系统崩溃，则就当一切没发生过。剩下的工作就是异步地修改数据本身。它的好处在于，写日志操作都是 append 操作，顺序访问，速度快性能好。Logging File System 依赖于一个基本假设，就是磁盘扇区的数据更新是按请求的顺序执行，且操作具备原子性，如果这个假设不成立，依然可能出现数据丢失的现象。

Redo Logging

logging 的其中一种就是 redo logging，在一切正常时，它有以下四个阶段：

  • Prepare：将所有修改写入磁盘中

  • Commit：将 commit 信息写入磁盘中

  • Redo：将修改复制到磁盘上

  • Garbage Collection：将已经完成数据写入的日志空间回收

在这些阶段进行的过程中都有可能出现故障，如果在 Prepare/Commit 阶段故障，则所有修改就当没发生过，日志被删除；如果在 Redo 阶段故障，则需进入 Recover 阶段；如果在 Garbage Collection 阶段故障，则再执行一次即可。

  • Recover：

    • 读取 redo 日志

    • 重新执行一遍 redo 操作 (所有操作要求幂等)

    • 忽略未 commit 的 transaction

    • Garbage Collection

举例如下：

redo logging - 1
redo logging-2
redo logging-3
redo logging-4

  • 如果在 Redo 阶段崩溃，且已经写入部分数据怎么办？

    • 保证操作幂等，多次执行与单次执行效果一样

    • 直接在 Recovery 阶段再写一次即可

  • 如果尚未 commit 的 transaction 在 Recovery 阶段被丢弃了怎么办？

    • 应用需要自行负责重试逻辑

    • 数据库当一切未发生过

  • 如果在 Recovery 阶段又发生了一次崩溃怎么办？

    • 操作幂等

    • 再执行一次 Redo 即可

下面做一个简单的计算来体会一下 Logging File System 的性能提升：

  • 假设磁盘的寻道过程平均为 5ms

  • 磁盘写入速度为 100 MB/s，意味着 4KB block 的传输需要 0.04 ms

  • 100 次随机创建文件和写入数据，每次包括 4 个 blocks：free, inode, direct, data

那么一共需要 100×4×5ms=2s100 \times 4 \times 5ms = 2s ，如果仅仅是写入日志，只需要 5ms+400×0.04ms=6.6ms5ms + 400 \times 0.04ms = 6.6 ms ，系统的响应时间将大大缩短，而且文件系统能够在幕后通过重组织、批量写入的方式优化性能。即使更新的数据体量很大，顺序写入也能够提高写入效率。

它的具体实现过程总结在下图中：

我们可能会有一个疑问：写 Redo 日志时，能否将不同的事务的日志同时写出呢？即来自于不同事务的日志信息交织在一起，如下图所示：

这个疑问实际上可以拆成两部分：

  • 对不同文件更新的两个事务的 Redo 日志之间能否交织？(显然可以)

  • 对相同文件更新的两个事务的 Redo 日志之间能否交织？(不好说，通常不能)

最重要的是要确定这两个事务是否可序列化 (serializable)，即将二者一起执行和按某个顺序执行的效果一致。看一个具体的例子：

  • Process A 要将 foo 从文件夹 x 移动到文件夹 y

  • Process B 要读取文件夹 a 和文件夹 b 下的所有文件，并将包含 "162" 的每行文本写入到 log 文件中

假设 x, y 与 a, b 毫不相关，那么 a 与 b 可以同时进行。如果 x == a 且 y == b，就有可能出现很多种结果：

  • foo 中带有 162 的文本被 grep 1 次

  • foo 中带有 162 的文本被 grep 2 次

  • foo 中带有 162 的文本被 grep 0 次

这时候 A 和 B 就不应该被允许同时执行。我们需要 --- Locks!

这里的 Lock 通常分为两种，shared (S) lock 和 exclusive (X) lock，它们的关系这里不再赘述。要保证 A 与 B 在获取文件锁的过程中不发生死锁，需要按固定顺序获取不同的锁，同时使用 Two-Phase Locking (2PL)，它要求：

  • 所有事务必须在读取或写出文件前获取锁：

    • 在读取之前获取 S 或者 X 锁

    • 在写出之前获取 X 锁

  • 一旦事务开始释放任意一个锁后，它就不能再获取新的锁

因此事务的执行过程可以分为两个阶段：获取锁阶段 (growing phase) 和释放锁阶段 (shrinking phase)，故称为 2PL，如下图所示：

需要注意的是：2PL 仅仅能够保证事务之间可序列化，若两个事务不可序列化，那么其中一个事务一定会被另一个事务阻塞，但 2PL 不能保证事务之间不发生死锁，因此需要保证事务获取不同锁的顺序是固定的。因此 Process A 和 B 的实际执行过程如下图所示：

参考

lecture notes: 18, 19, 20

PreviousAddress Translation, CachingNextDistributed Systems, Networking, TCP/IP, RPC (21,22)

Last updated