shan

操作系统-持久性

2020-06-06

本文为操作系统导论中关于持久性部分的读书笔记。其中主要涉及I/O设备，文件系统等相关知识。

I/O设备

I/O对于计算机系统非常重要，对于I/O主要有如下的问题：I/O该如何集成进入系统？一般机制是什么？如何让它变得高效？

系统架构

下图展示了一个典型的系统架构，其中CPU通过某种内存总线（memory bus）或互联电缆连接到系统内存。图像或其他高性能I/O设备通过常规的I/O总线（I/O bus）连接到系统，现代系统中一般是PCI或其延伸形式。最后是外设总线（peripheral bus），如SCSI、SATA或USB，它们将最慢的设备连接至系统，如磁盘、鼠标及其他类设备。这样分层的目的是为了物理布局及造价成本，越快的总线越短，无法连接太多设备，并且造价高。

image-20200606101547485

标准设备

下面通过一个标准设备更好的理解设备交互的机制。从下图可以看到，一个包含两部分重要组件的设备。

第一部分是向系统其他部分展现的硬件接口（interface），和软件一样，硬件也需要接口，让系统软件来控制它的操作，因此，所有设备都有自己特定接口以及典型交互的协议。

第二部分是它的内部结构（internal structure）。这部分包含设备相关的特定实现，负责具体实现设备展示给系统的抽象接口。

image-20200606125130513

标准协议

在上面的图中可以看到，一个设备接口包含3个寄存器：

  • 一个状态寄存器(status)，可以读取并查看设备当前状态；
  • 一个命令寄存器(command)，用于通知设备某个具体任务；
  • 一个数据寄存器(data)，将数据传给设备或者从设备接收数据。

下面伪代码描述操作系统与该设备的交互：

1
2
3
4
5
6
7
while (STATUS == BUSY)
    ; // 等待，直到设备不忙
//将数据写入数据寄存器
//将命令写入命令寄存器
//开启设备并且执行命令
while(STATUS == BUSY)
    ; //等待直到设备做完了你的请求

上面描述的协议包含四步：

  1. 操作系统通过反复读取状态寄存器，等待设备进入可以接受命令的就绪装态。称之为轮询（polling）设备。
  2. 操作系统下发数据到数据寄存器。如果CPU主动参与数据移动，称之为编程的I/O（PIO）。
  3. 操作系统将命令写入命令寄存器，这样设备就知道数据已完成准备，并开始执行。
  4. 操作系统轮询设备，等待并判断设备是否已经完成。

利用中断减少CPU开销

对于CPU的轮询可以使用中断来减少CPU的开销。有了中断以后，CPU不在需要不断轮询设备，而是向设备发出一个请求，然后就可以让对应进程睡眠，切换执行其他任务。当设备完成了自身操作，会抛出一个硬件中断，引发CPU跳转执行操作系统预先定义好的中断服务例程（Interrupt Service Routine，ISR），或更为简单的中断处理程序（interrupt handler）。中断处理程序是一小段操作系统代码，它会结束之前的请求，并且唤醒等待I/O的进程继续执行。

因此中断允许计算与I/O重叠（overlap），这是提高CPU利用率的关键。但是如果设备性能非常高，使用中断，可能导致系统变慢。

如果设备性能未知，可以考虑使用混合策略（hybrid）。先尝试轮询一小段时间，如果设备没有完成操作，此时在使用中断，这种两阶段的办法可以实现两种方法的好处。

另一个基于中断的优化就是合并（coalescing）。设备在抛出中断之前往往会等待一小段时间，在此期间，其他请求可能很快完成，多个中断可以合并为一次中断抛出，从而降低处理中断的代价。

利用DMA进行高效的数据传送

如果使用编程的I/O将一大块数据传送给设备，CPU又会因为琐碎的任务而变得负载很重，浪费了时间和算力，本来更好是用于运行其他进程。使用PIO 的方式，CPU 的时间会浪费在向设备传输数据或从设备传出数据的过程中。如何才能分离这项工作，从而提高CPU 的利用率？

解决方案就是使用DMA（Direct Memory Access），DMA引擎是系统中的一个特殊设备，它可以协调完成内存和设备之间的数据传递，不需要CPU的介入。其工作流程如下：为了能将数据传送给设备，操作系统会通过编程告诉DMA引擎数据在内存中的位置，要拷贝的大小以及拷贝到哪个设备。之后，操作系统可以处理其它请求了，当DMA的任务完成后，DMA控制器会抛出一个中断来告诉操作系统自己已经完成了数据传输。

设备交互的方法

只要有两种方式实现与设备的交互：

  1. 用明确的I/O指令，这些指令规定了操作系统将数据发送到特定设备寄存器的方法，从而允许构造上文提到的协议。这些指令通常是特权指令（privileged），操作系统是唯一可以直接与设备交互的实体。
  2. 内存映射I/O（memory-mapped I/O），通过这种方式，硬件将设备寄存器作为内存地址提供。当需要访问硬件设备寄存器时，操作系统装载或者存入到该内存地址，然后硬件会将装载/存入转移到设备上，而不是物理内存。

将设备纳入操作系统

可以通过抽象（abstraction）技术来解决。在最底层，操作系统的一部分软件清楚地知道设备如何工作，我们将这部分软件称为设备驱动程序（device driver），所有设备交互的细节都封装在其中。

这种封装有一些不做，如，假设一个设备可以提供很多特殊的功能，但是为了兼容大多数操作系统它不得不提供一个通用的接口，这样就使得自身的特殊功能无法使用。

磁盘驱动器

磁盘驱动器在过去数十年来一直是计算机系统持久数据存储的主要形式，文件系统技术的大部分发展都是基于它们的行为。因此，在构建管理它的文件系统软件之前，需要先了解磁盘操作的细节。那么问题是：现代磁盘驱动程序是如何存储数据的？接口是什么？数据如何安排和访问的，磁盘调度如何提高性能。

接口

驱动器是由大量扇区（512字节块）组成，每个扇区都可以读取或者写入，在具有n个扇区的磁盘上，扇区从0到n-1编号。因此我们可以将磁盘视为一组扇区，0到n-1是驱动器的地址空间。多扇区操作是可行的，许多文件系统一次读取或者写入4KB或者更多。但在更新磁盘时，需要保证单个512字节的写入是原子的。

基本几何形状

一个磁盘由多个盘片（platter）组成，每个盘片有两面，每个面都称为表面。

所有的盘片都围绕主轴（spindle）连接到一起，主轴连接到一个电机，以一个恒定的速度旋转盘片。旋转速度通常以每分钟转数（Rotations Per Minute， RPM）来测量。

数据在扇区的同心圆中的每个表面上被编码，我们称这样的同心圆为一个磁道（track）。一个表面有数以千计的磁道，彼此紧密排在一起。

要从表面进行读写操作，我们需要一种机制，使我们能够感应磁盘上的磁性图案，或者让他们发生变化。读写由磁头（disk head）完成；驱动器表面有一个这样的磁头。磁头连接到单个磁盘臂（disk arm）上，磁盘臂在表面上移动，将磁头定位在期望的磁道上。

I/O 时间

磁盘读写主要包含以下类型的延迟时间：

  • 旋转延迟（rotational delay）
  • 寻道时间（seek）
  • 传输（transfer）

一个磁盘的I/O时间通常用以下形成表示：
$$
T_{I/O} = T_{寻道} + T_{旋转} + T_{传输}
$$
那么驱动器I/O速率为：
$$
R_{I/O} = \frac{SIZE_{传输}}{T_{I/O}}
$$

磁盘调度

由于I/O 的高成本，操作系统在决定发送给磁盘的I/O 顺序方面历来发挥作用。更具体地说，给定一组I/O 请求，磁盘调度程序检查请求并决定下一个要调度的请求。

与任务调度不同，每个任务的长度通常是不知道的，对于磁盘调度，我们可以很好地猜测“任务”（即磁盘请求）需要多长时间。通过估计请求的查找和可能的旋转延迟，磁盘调度程序可以知道每个请求将花费多长时间，因此（贪婪地）选择先服务花费最少时间的请求。因此，磁盘调度程序将尝试在其操作中遵循SJF（最短任务优先）的原则（principle of SJF，shortest job first）。

SSTF

SSTF ：一种早期的磁盘调度方法，被称为最短寻道时间优先，Shortest-Seek-Time-First。SSTF 按磁道对I/O 请求队列排序，选择在最近磁道上的请求先完成。

电梯：SCAN

简单地以跨越磁道的顺序来服务磁盘请求。我们将一次跨越磁盘称为扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立即处
理，而是排队等待下次扫一遍。

SPTF

最短定位时间优先调度，Shortest Positioning Time First，SPTF，有时也称为最短接入时间优先，Shortest Access Time First，SATF。

廉价冗余磁盘阵列

在整个计算机系统中，I/O操作是很慢的，它会成为整个系统的瓶颈。那么我们如何构建一个大型的、快速的、可靠的存储系统？

这里用的主要手段是廉价冗余磁盘阵列：Redundant Array of Inexpensive Disk，更多时候称为RAID，这种技术使用多个磁盘一起构建更大、更快、更可靠的磁盘系统。从外部来看，RAID看起来像是一个磁盘，一组可以读取或者写入的块。在内部，它是由多个磁盘、内存以及一个或多个处理器来管理的系统。

RAID与单个磁盘相比，有许多的优点：

  • 提高性能，并行使用多个磁盘可以大大加快I/O时间；
  • 高容量，大型数据集需要 大型磁盘；
  • 提高可靠性，在多个磁盘上传输数据会使数据易受到单个磁盘丢失的影响。

映射问题：这个问题出现在所有的RAID阵列中，简单的说，就是给定一个逻辑块来读或者写，RAID如何确切知道要访问哪个物理磁盘和偏移量？

RAID 一致性问题：一些特殊情况（如掉电）会导致数据块在连个副本中不一致，其一般解决方案是：使用某种预写日志（write-ahead log），在做之前首先记录RAID 将要执行的操作（即用某个数据更新两个磁盘）。通过采取这种方法，我们可以确保在发生崩溃时，会发生正确的事情。通过运行一个恢复（recovery）过程，将所有未完成的事务重新在RAID 上执行，我们可以确保两个镜像副本（在RAID-1 情况下）同步。

根据容量、可靠性、性能三个方面评估 RAID 设计：

  • RAID 0级，条带化，没有冗余，以轮转方式将磁盘阵列的块分布在磁盘上。这种方法的目的是在对数组的连续块进行请求时，从阵列中获取最大的并行性。其容量和性能都是顶级的，但是任何磁盘故障都会导致有用数据丢失。
  • RAID 1级，镜像，只需生成系统中每个块的多个副本，每个副本单独放在一个单独的磁盘上，其允许磁盘故障，这个其镜像级别有关。容量只有有用容量的1/n，其顺序读取和写入的性能只有最大带宽的1/n；其随机读取的性能为完整的带宽，随机写入的性能为1/n;
    • RAID-10使用镜像对其生成副本，使用条带化增强性能与容量。
    • RAID-01包含两个大型条带化阵列，然后对其进行镜像。
  • RAID 4级，基于奇偶校验的冗余，这种方式试图以减小的容量解决副本问题，对条带中每块的每一位进行奇偶校验，填入对应的位置，这么做的代价是性能。其容量为N(磁盘数) - 1；其允许一个磁盘故障；其连续读取性能为 N - 1，顺序写入的性能为N-1(全条带写入)，随机读取的性能为N-1，小的随机写入性能为R/2；
  • RAID 5级，旋转奇偶校验，每个条带奇偶校验都在磁盘上旋转，以消除RAID-4的奇偶校验盘的瓶颈。性能基本与RAID-4相同，其随机读取稍微好一点（可以利用所有磁盘），随机写入性能明显提高，因为它能够跨请求进行并行处理，为NR/4。因为它与RAID-4 基本相同，部分情况完全好于RAID-4，故基本上已经取代了RAID-4。

其性能比较如下表所示，其中假设共有N块磁盘，连续工作负载下以S MB/s 传输数据，并且在随机工作负载下以R MB/s 传输数据：

RAID-0 RAID-1 RAID-4 RAID-5
容量 N N/2 N-1 N-1
可靠性 0 1(肯定) / N/2(运气)
顺序读 N * S N/2 * S (N -1) * S (N -1) * S
顺序写 N * S N/2 * S (N -1) * S (N -1) * S
随机读 N * R N * R (N -1) * R N * R
随机写 N * R N/2 * R 1/2 * R N/4 * R
读延迟 T T T T
写延迟 T T 2T 2T

文件和目录

我们在虚拟化章节了解了进程和地址空间的概念，进程是CPU的虚拟化，地址空间时内存的虚拟化。在这里，我们了解虚拟化中更为关键的一部分：持久存储（persistent storage）。永久存储设备永久地存储信息。如传统硬盘驱动器（hard disk drive）或者更加现代的固态存储设备（solid state storage device）。其与内存不同，内存在断电时，其内容会丢失，而持久存储设备会保持这些数据不变。那么这里的问题是：操作系统该如何管理持久存储设备？需要哪些API？实现有哪些重要方面？

概念

存储虚拟化形成了两个关键的抽象：

  1. 文件（file）：其是一个线性字节数组，每个字节都可以读取或者写入，每个文件都有某种低级名称，称为inode号，通常是某种数字。
  2. 目录（directory）：像文件一样，也有一个低级的名字，即inode号，但它的内容非常具体，它包含一个（用户可读名字，低级名字）对的列表。目录中每个条目都指向文件或其它目录。通过将目录放入其他目录中，用户可以构建任意的目录树（directory tree，或目录层次结构，directory hierarchy），在该目录树下存储所有文件和目录。

目录层次结构从根目录开始，并使用某种分隔符（separator）来命名后续子目录（sub-directories），直到命名所需的文件夹。

文件

我们下面从创建、访问、删除文件来了解文件系统的接口。

创建文件

创建一个文件，可以通过open系统调用完成，通过调用open() 并传入O_CREAT标志，程序就可以创建一个新文件。如创建一个名为foo的文件：

1
int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC)

函数open() 接受不同的标志，如上面的例子中，程序创建文件（O_CREAT），只能写入该文件，因为以（O_WRONLY）这种方式打开，并且如果文件已经存在，首先将其截断为0字节大小，删除所有现有内容（O_TRUNC）。

open() 的一个重要方面是其返回值：文件描述符（file descriptor）。文件描述符只是一个整数，每个进程私有，在Unix中用于访问文件。因此，一旦文件打开，你就可以使用文件描述符来读取或写入文件。一个描述符就是一种权限（capability），即一个不透明的句柄，可以让你执行某些操作。另一种看待文件描述符的方法，就是将其作为指向文件类型对象的指针。一旦你有这种对象，你就可以调用其他方法访问文件。

读写文件

一旦我们有了文件，就会想要去读取或者写入。例如，我们向读取一个文件，在命令行中，可以使用cat程序，将文件的内容显示到屏幕上：

1
2
3
4
prompt> echo hello > foo
prompt> cat foo
hello
prompt>

上面的整个调用过程，我们可以用strace这个工具进行追踪，它的作用就是跟踪程序在运行时所做的每个系统调用，然后将跟踪程序显示在屏幕上供你查看。其接受一些有用的参数：-f跟踪所有fork的子进程，-t报告每次调用的时间，-e trace=open,close,read,write 只跟踪对这些系统调用的调用，忽略其他，等等参数。下面展示一个例子：

1
2
3
4
5
6
7
8
9
10
prompt> strace cat foo
...
open("foo", O_RDONLY|O_LARGEFILE)		= 3
read(3, "hello\n", 4096)				= 6
write(1, "hello\n", 6)					= 6
hello
read(3, "", 4096)						= 0
close(3)								= 0
...
prompt>
  • 首先cat打开文件准备读取，这里该文件仅为可读，O_RDONLY标识所示。使用64位偏移量 O_LARGEFILE 。open() 调用成功后，返回为3，因为0,1,2 为标准输入，标准输出和标准错误的文件描述符。
  • 打开成功后，cat使用read() 系统调用重复读取文件中的一些字节。read() 的第一个参数是文件描述符，告诉系统读取哪个文件，第二个参数指向一个用于放置read() 结果的缓冲区，第三个参数为缓冲区大小。这次系统调用返回它读取的字节数。
  • 之后，会调用系统调用write() 对标准输出的文件描述符进行操作，将读取的内容打印到屏幕上。
  • 然后cat试图从文件中读取更多的内容，但是由于文件中没有剩余字节，read()返回0，程序表明它已经读取了整个文件。
  • 调用close() ，传入对应的文件描述符，关闭该文件。

不按顺序读取和写入

有时读取或者写入特定偏移量是有用的，这里使用的lseek() 系统调用，下面是函数的原型：

1
off_t lseek(int fildes, off_t offset, int whence)

第一个参数是文件描述符，第二个是偏移量，它将文件偏移量定位到文件的特殊位置。第三个参数，称为whence, 明确地指定了搜索的执行方式。

第三个参数的英文描述是：

If whence is SEEK_SET, the offset is set to offset bytes.

If whence is SEEK_CUR, the offset is set to its current location plus offset bytes.

If whence is SEEK_END, the offset is set to the size of the file plus offset bytes.

对于每个进程打开的文件，操作系统都会跟踪一个“当前”偏移量，这将决定在文件中读取或写入时，下一次读取或写入开始的位置。因此，打开文件的
抽象包括它具有当前偏移量，偏移量的更新有两种方式。第一种是当发生N 个字节的读或写时，N 被添加到当前偏移。因此，每次读取或写入都会隐式更新偏移量。第二种是明确的lseek，它改变了上面指定的偏移量。

注意：调用lseek()与移动磁盘臂的磁盘的寻道（seek）操作无关。对lseek()的调用只是改变内核中变量的值。执行I/O 时，根据磁盘头的位置，磁盘可能会也可能不会执行实际的寻道来完成请求。

用 fsync() 立即写入

大多数情况下，当程序调用write()时，它只是告诉文件系统，在将来的某个时刻，将此数据写入持久存储，出于性能考虑，文件系统会将这些写在缓存中，在稍后的时间点，写入将实际发送到存储设备。

但在数据库管理系统中，不需要这种缓存，开发正确的恢复协议要求能够经常强制写入磁盘。在Unix中提供了此类的API，被称为 fsync(int fd)。当进程针对特定的文件描述符调用fsync()时，文件系统通过强制将所有的脏数据写入磁盘来响应，一旦所有这些写入完成，fsync() 例程就会返回。

文件重命名

在命令行是通过mv命令完成文件的重命名的。mv命令使用了系统调用rename(char *old, char *new)，此系统调用需要两个参数：文件的原名称和新名称。rename() 这个调用时原子调用。

获取文件信息

除了文件访问外，我盟有时也希望文件系统能够保存关于它正在存储的每个文件的大量信息，我们将这些数据称为元数据（metadata）。要查看特定文件的元数据，可以使用stat() 或fstat()系统调用。这些调用将一个路径名添加到一个文件中，并填充一个stat结构，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct stat {
    dev_t    st_dev;			/* ID of device containing file */
    ino_t    st_ino;			/* inode number */
    mode_t    st_mode;			/* protection */
    nlink_t    st_nlink;		/* number of hard links */
    uid_t    st_uid;			/* user ID of owner */
    gid_t    st_gid;			/* group ID of owner */
    dev_t	st_rdev;			/* device ID (if special file) */
    off_t	st_size;			/* total size, in bytes */
    blksize_t	st_blksize;		/* blocksize for filesystem I/O */
    blkcnt_t	st_blocks;		/* number of blocks allocated */
    time_t    st_atime;			/* time of last access */
    time_t    st_mtime;			/* time of last modification */
    time_t    st_ctime;			/* time of last status change */
};

这里可以看到文件大量的信息，包括其大小，低级名称，所有权信息以及有关文件被访问或者修改信息等等。

事实表明，每个文件系统通常将这种类型的信息保存在一个名为inode的结构中。就目前而言，你应该将inode看作是由文件系统保存的持久数据结构，包含上述信息。

删除文件

我们知道了如何创建文件并访问他们，但如何删除，在Unix中，只需要运行rm命令，这里rm命令调用了一个叫unlink() 的系统调用，其接受待删除文件的名称，并在成功时返回0，向了解这个系统调用，不仅需要了解文件，也需要了解目录。

目录

除了文件外，目录也有一组系统调用，来创建、读取和删除目录。注意不能直接写入目录，因为目录的格式被视为文件系统的元数据，你只能间接更新目录，如在其中创建文件，目录或者其他对象。

创建目录

创建目录，可以通过系统调用mkdir() 来进行。同名的mkdir程序可以用来创建这样一个目录。使用程序mkdir创建一个名为foo的简单目录时，会进行下面的操作：

1
2
3
4
5
prompt> strace mkdir foo
...
mkdir("foo", 0777) 				= 0
...
prompt>

这样创建的目录，它被认为是空的，但它实际上包含最少量的内容。具体来说，空目录有两个条目，一个引用自身的条目，一个引用其父目录的条目，前者称为“.”目录，后者称为“..”目录。可以通过向程序传递ls传递一个-a的标志来查看这些目录。

读取目录

程序ls正是用来读取目录的程序，下面我们编写一个类似的小程序，来实现相关的功能。通过对opendir()、readdir()和closedir() 三个系统调用完成工作。只需要使用一个简单的循环就可以一次读取一个目录条目，并且打印目录中每个文件的名称和inode号。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <dirent.h>
#include <assert.h>

int main(int argc, char *argv[]) {
    DIR *dp = opendir(".");
    assert (dp != NULL);
    struct dirent *d;
    while ((d = readdir(dp)) != NULL) {
        printf("%d %s\n", (int) d->d_ino, d->d_name);
    }
    closedir(dp);
    return 0;
}

删除目录

删除目录可以通过调用rmdir() 这个系统抵用来实现，和删除文件不同，删除目录十分危险，因为目录中可能有大量的数据。因此rmdir() 要求该目录在被删除之前时空的，如果你删除的是一个非空目录，那么对rmdir() 这个系统调用会失败。

硬链接

在文件系统树中创建新条目的方法，即通过link() 系统调用，link()有两个参数：一个旧路径名和一个新路径名。当将一个新的文件名链接到旧文件名时，你实际上创建了另一种引用同一文件的方法。ln命令程序用于执行此操作，如下：

1
2
3
4
5
6
prompt> echo hello > file
prompt> cat file
hello
prompt> ln file file2
prompt> cat file2
hello

link只是在要创建链接的目录中创建了另一个名称，并指向原文件的相同inode号。该文件不以任何方式复制，相反，你现在有了两个名称都指向同一个文件。通过带-i标志的ls，它会打印出每个文件的inode号。

所以说创建一个文件，其实做了两件事情，首先构建一个结构，它将跟踪几乎所有有关文件的信息，包括其大小、文件块在磁盘的位置等，其次，将人类可读的名称链接到该文件，并将该链接放入目录中。在创建文件的硬链接后，文件系统中原有文件名和新文件名没什么区别。

因此从文件系统删除一个文件，我们调用unlink()。当删除某个链接之后，他检查inode号中引用计数。该引用计数允许文件系统跟踪有多少不同的文件名已链接到这个inode。调用unlink()时，会删除人类可读的名称与给定inode号之间的链接，并减少引用计数。只有当引用计数为0时，文件系统才会释放inode和相关的数据块，从而删除该文件。

符号链接

有一种称为符号链接（symbolic link）的链接类型，称为软链接（soft link）。硬链接有相当的局限，不能创建目录的硬链接。不能硬链接到其他磁盘分区中的文件等等。

要创建软链接，同样使用程序ln，使用-s标志，如下：

1
2
3
4
prompt> echo hello > file
prompt> ln -s file file2
prompt> cat file2
hello

这种链接看起来相同，同样可以通过文件名称和链接名称访问文件。但是它们之间存在本质的区别：

  • 符号链接本身实际上是不同类型的文件，符号链接是文件系统中除了常规文件和目录外的第三种类型，通过ls -al可以看到常规文件最左列第一个字符是“-”，目录是“d”，软链接是“l”。
  • 形成符号链接的方式是指向文件的路径名作为链接文件的数据。
  • 由于创建符号链接的方式，有可能造成所谓的悬空引用（dangling reference）。删除原始文件会导致符号链接指向不存在的文件名。

创建并挂载文件系统

上面已经了解了文件目录等类型基本接口，那么我们如何从许多底层文件系统中组建完整的目录树？

为了创建一个文件系统，大多数文件系统提供了一个工具，一般名为mkfs，其过程如下：作为输入，为该工具提供一个设备（如磁盘分区），一种文件系统类型（如ext3），它就从根目录开始在该磁盘分区上写入一个空文件系统。

一旦创建了这样的文件系统，需要在同一的文件系统树中进行访问。一般通过mount程序实现的。其作用很简单：以现有目录作为目标挂载点（mount point），本质上是将新的文件系统粘贴到目录树的这个点上。

要查看系统上挂载的内容，以及挂载位置，可以运行mount程序，你会看到下面的内容：

1
2
3
4
5
6
7
/dev/sda1 on / type ext3 (rw)
proc on /proc type proc (rw)
sysfs on /sys type sysfs (rw)
/dev/sda5 on /tmp type ext3 (rw)
/dev/sda7 on /var/vice/cache type ext3 (rw)
tmpfs on /dev/shm type tmpfs (rw)
AFS on /afs type afs (rw)

文件系统的实现

下面介绍一个简单的文件系统实现，称为VSFS。它是一个简化的Unix文件系统。那么如何构建一个简单的文件系统？需要什么数据结构？需要记录什么？如何访问？

考虑文件系统时，我们通常建议考虑它们两个不同的方面:

  1. 文件系统的数据结构，VSFS使用简单的数据结构，文件系统在磁盘上使用哪些类型的结构来组织其数据和元数据？如块或者其他对象数组，而更复杂的文件系统使用基于树的结构。
  2. 文件系统的访问方法，如何将进程发出的调用，映射到它的结构上？在执行特定系统调用期间读取哪些结构？改写哪些结构？执行效率如何？

需要建立一个关于文件系统的数据结构的访问方法的心智模型，这是系统思维的关键部分。

整体组织

现在开发VSFS文件系统在磁盘上的数据结构的整体组织。

第一步是将磁盘划分为块，这里划分为一种大小的块，通常选择4KB。在大小为N个4KB块的分区中，这些块的地址从0到N-1。

那么为了构建文件系统，需要在这些块中存储什么：

  1. 首先需要考虑的是用户数据，存放用户数据的磁盘区域称为数据区域（data region）。
  2. 其次，文件系统必须记录每个文件的信息。该信息是元数据的关键部分，并且记录了诸如文件包含哪些数据块，文件大小，所有者和访问权限，访问和修改时间以及其他类似的事情。为了记录这些信息，文件系统通常会有一个名为inode的结构，并且需要在磁盘上留出空间。我们将这部分磁盘称为inode表，其是一个保存在磁盘上的inode数组。
  3. 我们也需要一种分配结构来记录inode表中的所有文件是空闲的还是已分配的。有许多种分配方法，如空闲列表，位图（bitmap）等。一种用于数据区域，称为数据位图，另一种用于inode表，inode位图。
  4. 在极简的文件系统中，保留一个超级块（superblock），此块包含关于特定文件系统的信息，包块文件系统中有多少inode和数据块、inode表的开始位置等，还可能包含一些幻数，来标记文件系统的类型。

位图：每个位用于指示相对应的对象/块是空闲的还是正在使用的。

文件组织：inode

文件系统中最重要的磁盘结构之一是inode，几乎所有的文件系统都有类似的结构，名称inode是index node的缩写，因为这些节点最初是放在一个数组中的，访问特定的inode时，会用到该数组的索引。其一般用于描述保存给定文件的元数据的结构，例如长度以及其组成块的位置。

每个inode都由一个数字隐式引用，之前称之为文件的低级名称。在VSFS中，给定一个inumber，你可以直接计算磁盘上相应节点的位置。

每个inode中，实际上是所有关于文件的信息：文件类型、大小、分配给它的块数，保护信息、一些时间信息，以及有关数据块驻留在磁盘上的位置信息。我们将这些信息称为元数据，文件系统中除了纯粹的用户数据外，其他任何信息都为元数据。

设计inode时，最重要的决定之一是它如何引用数据块的位置。一种简单的方法是在inode中有一个或多个直接指针。每个指针指向属于该文件的一个磁盘块。这种方法不适用于处理大文件。

为了支持更大的文件，需要引入不同的结构：

  • 可以使用一个称为间接指针的特殊指针，它不是指向包含用户数据的块，而是指向包含跟多指针的块，每个指针指向用户数据。因此inode可以有些固定数量的直接指针和一个间接指针。
  • 使用范围，而不是指针。范围就是一个磁盘指针加一个长度。因此，不需要指向文件的每个块的指针，只需要指针和长度来指定文件的磁盘位置。基于范围的文件系统通常允许多个范围，从而在文件分配期间给与文件系统更多的自由。
  • 使用链表，在一个inode中，只用一个指针，指向文件的第一块，要处理较大的文件，则在该数据块的末尾添加另一个指针。为了处理对某些情况负载不佳的情况，可以在内存中保留链接信息表，而不是将下一个指针与数据块一起存储。该表用用数据块D的地址来索引，一个条目的内容就是D的下一个指针，即D后面的文件中下一个块的地址。这是文件分配表FAT（File Allocation Table）的基本结构。

通过添加不同级别的指针从而满足更大的文件，这种不平衡树被称为指向文件块的多级索引方法（multi-level index）。研究表明，文件系统中大文件相对较少，使用这种不平衡树是有意义的。

目录组织

在VSFS中，目录的组织十分简单，一个目录基本上只包含一个二元组（条目名称，inode号）的列表。对于给定目录中的文件或者目录，当前目录的数据块中都有一个字符串和一个数字。对于每个字符串，可能还有一个长度。

删除一个文件，会在目录中留下一段空白空间，因此应该有一些方法标记删除它，这种删除是使用记录长度的一个原因：新条目可能会重复使用旧的、更大的条目，从而在其中留有额外空间。

通常文件系统将目录视为特殊类型的文件。因此目录有一个inode，位于inode表的某处，该目录具有由inode指向的数据块。这些数据块存储在我们的简单文件系统的数据块区域中。

空闲空间管理

文件系统必须记录哪些inode和数据块是空闲的，哪些不是，这样在分配新文件或者目录时，就可以为它找到空间，因此，空闲空间管理（free space management）对于所有文件系统都很重要。在VSFS中，用两个简单的位图来完成这个任务。还有其他的方式进行管理，如空闲链表，B-tree等。

当我们创建一个文件时，我们必须为该文件分配一个inode，文件系统将通过位图搜索一个空闲的内容，并将其分配给文件。文件系统必须将inode标记为已使用，并最终用正确的信息更新磁盘上的位图。为新文件分配数据块时，还可能会考虑其他一些注意事项。寻找一系列空闲块分配给新创建的文件，保证其是连续的，从而提高性能。

访问路径：读取和写入

我们知道文件和目录如何存储在磁盘上的，那么如何进行文件的读写的呢？

从磁盘读取文件

我们假设倒开一个小文件/foo/bar，并且假设文件只有4KB。

当你发出open(“/foo/bar”, O_RDONLY)调用时，文件系统首先寻找文件bar的inode，从而获取该文件的一些基本信息，如权限，大小。

因为上面的文件只有完整的路径名，所以为了能够找到inode，文件系统必须遍历路径名。所有的遍历都是从文件系统的根开始，即从根目录开始，记为/。因此文件系统的第一次磁盘读取是根目录的inode。要找到inode，需要知道它的i-number。通常在父级目录寻找i-number，但是根目录没有父级目录，所以根目录的inode号是周知的。

一旦inode被读入，文件系统可以在其中查找指向数据块的指针，数据块包含根目录的内容，因此，文件系统将使用这些磁盘上的指针来读取目录。

下一步是递归遍历路径名，直到找到所需的inode。open() 的最后一步是将bar的inode读入内存。然后文件系统进行最后的权限检查，在每个进程打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。

打开后，程序可以发出read()系统调用，从文件中读取。第一次读取将在文件的第一个块中读取，查阅inode以查找这个块的位置。它也会从新的最后访问时间更新inode。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量，以便下一次读取会读取第二个文件块。

在某个时候，文件将被关闭。这里文件描述符会被释放，没有磁盘I/O发生。

写入磁盘

写入文件是一个类似的过程。首先，文件必须打开，其次应用程序必须发出write()调用以更新内容更新文件，最后关闭文件。

与读取不同，文件写入也可能会分配一个块，当写入一个新文件时，每次写入操作不仅需要将数据写入磁盘，还必须首先决定将哪个块分配给文件，从而相应地更新磁盘的其他结构，如数据位图和inode。因此每次写入在逻辑上会导致5个I/O，一个读取数据位图（然后更新以标记新分配的块被使用），一个写入位图（将它的新状态存入磁盘），再两次读取，然后写入inode（用新块的位置更新），最后一次写入真正的数据块本身。

考虑简单和常见的操作（如文件创建），写入的工作量更大。要创建一个文件，文件系统不仅要分配一个inode，还要在包含新文件的目录中分配空间。这样的I/O工作总量非常大：一个读取inode位图（查找空闲的inode），一个写入inode位图（将其标记为已分配），一个写入新的inode位图（初始化），一个写入目录的数据（将文件的高级名称链接到它的inode号），以及一个读写目录inode以便更新它。如果目录需要增长以容纳新条目，则还需要额外的I/O（数据位图和新目录块），这些都只是为了创建一个文件。

缓存和缓冲

读取和写入文件时昂贵的，会导致磁盘产生许多I/O。这是一个巨大的性能问题，为了减轻这个问题，大多数文件系统积极使用系统内存来缓存重要的块。

早期的文件系统引入了一个固定大小了一个固定大小的缓存来保存常用的块，大约站总内存的10%，这样称为静态的内存划分（static partitioning），但其可能导致内存浪费。现代系统采用动态划分（dynamic partitioning）方法，许多现代操作系统将虚拟内存页面和文件系统页面集成到统一页面缓存中（unified page cache）。通过这种方式，可以在虚拟内存和文件系统之间更加灵活的分配内存，具体取决于在给定时间哪种内存需要跟多的内存。

尽管可以通过足够大的缓存来避免读取I/O，但写入必须进入磁盘才能实现持久。因此，高速缓存不能像对读取那样减少写入流量。写缓冲优点

  • 首先通过延时写入，文件系统可以将一些更新编成一批，放入一组较小的I/O中。
  • 其次，通过将一些写入缓冲在内存中，系统可以调度（schedule）后续的I/O，从而提高性能。
  • 最后，一些写入可以通过拖延来完全避免。

某些应用程序不需要这种缓存，为了避免缓存导致意外数据丢失，通过调用fsync()，使用绕过缓存的直接I/O接口，或者使用原始磁盘（raw disk）接口并完全避免使用文件系统。

局部性和快速文件系统

Unix系统中最初的文件系统，其基本结构如下图所示：

image-20200614235551700

其中包含三个部分，超级块（S），其包含有关整个文件系统的信息：卷的大小、有多少inode、指向空闲列表块的头部的指针等。磁盘的inode区域包含文件系统的所有inode。大部分数据都被数据占据。

它的好处在于其简单，并且支持文件系统提供的基本抽象：文件和目录层次结构。但其有很多的问题。

性能

这个文件系统的性能有很大的问题，随着时间的推移，性能越来越差。其主要原因是：

  • 此文件系统将磁盘当成随机存取的内存，数据遍布各处，而不考虑保存的数据的介质是磁盘，其定位成本很高。

  • 并且文件系统最终会变得非常碎片化（fragmented），空闲空间没有得到进行管理。

  • 原始块大小太小（512字节），从磁盘传输数据本质上是低效的。

FFS

为了解决上面的文件系统的问题，一个被称为快速文件系统（Fast File System，FFS）被建立。思路是让文件系统的结构和分配策略具有磁盘意识，从而提高性能。通过保持与文件系统相同的接口，但改变其内部实现，来优化文件系统，所有现代的文件系统都遵循现有的接口，为了性能，可靠性或者其他原因，改变其内部实现。

组织结构：柱面组

第一步更改磁盘上的结构。FFS将磁盘划分为一些分组，称为柱面组（cylinder group）。这些分组是FFS用于改善性能的核心机制。通过在同一组中放置两个文件，FFS确保先后访问的两个文件不会导致穿越磁盘的长时间寻道。因此，FFS需要在每个组中分配文件和目录，看起来如下图：

image-20200615204837975
  • 出于可靠性原因，每个组中都有超级块（super block）的一个副本。
  • 在每个组中，我们需要记录改组的inode和数据块是否已分配。每组的inode位图（inode bitmap，ib）和数据位图（data bitmap，db）起到了这个作用。分别针对每组的inode和数据块。
  • inode和数据块区域类似之前的极简文件系统。每个柱面组的大部分都包含数据块。

分配文件和目录

FFS规定相关的东西放在一起，其推断是否相关的方法如下：

  • 关于目录，FFS采用了一种简单的方法，找到分配数量少的柱面组（跨组平衡目录）和大量的自由inode（之后能够分配一堆文件），并将目录数据和inode放在该分组中。也可以采用其他推断方法，如考虑空闲数据块的数量。
  • 对于文件，FFS做两件事。首先，确保将文件的数据块分配到与其inode相同的组中，从而防止inode和数据之间的长时间寻道。其次它将位于同一目录中的所有文件，放在他们所在的目录的柱面组中。
  • 对于大文件的放置，有不同的规则。将一定数量的块分配到第一个块组之后，将文件的下一个大块放在另一个块组中，以此类推。

FFS的其它优化

  • 解决内部碎片问题，引入了子块（sub-block），大小有512字节，通过对每个子块进行分配，从而节约空间的浪费，修改libc库来避免子块导致的效率低下的问题。
  • 针对性能进行优化的磁盘布局，现代磁盘读取磁道到缓存中。
  • 引入符号链接的概念，允许长文件名的第一个文件系统。

崩溃一致性：FSCK和日志

文件系统管理一组数据结构以实现预期的抽象：文件、目录，以及其所有其他元数据，它们支持我们期望从文件系统获得的基本抽象。与大多数数据结构不同，文件系统数据结构必须持久，即它们必须长期存在，存储在断电也能保存数据的设备上。

文件系统棉铃的一个主要挑战是：如何在出现断电或者系统崩溃的情况下，更新持久数据结构？这个问题称为崩溃一致性问题（crash-consistency problem）。

文件系统检查程序

早期的文件系统采用一种简单的方法来处理崩溃一致性。它决定让不一致的事情发生，然后再修复它们。如Unix中工具：fsck；它用于查找这些不一致并修复它们。工具fsck的一些总结：

  • 超级块：fsck首先检查超级块是否合理，主要进行健全性检查，如确保文件系统大小大于分配的块数。主要目的是找到冲突的块，并决定是否启用副本。
  • 空闲块：接下来，fsck扫描inode、简介块、双重间接块等，以了解当前在文件系统中分配的块。利用这些信息生成正确版本的分配位图。如果位图和inode之间存在不一致，则通过信任inode中的信息来解决。
  • inode状态：检查每个inode是否存在损坏或其他问题。如，fsck确保每个分配的inode具有有效的类型字段。如果inode字段存在问题，不易修复，则inode被认为是可疑的，并被fsck清除，inode位图相应的更新。
  • inode链接：fsck还会验证每个已分配的inode的链接数。为了验证链接计数，fsck从根目录开始扫描整个目录树，并为文件系统中的每个文件和目录构建自己的链接计数。如果新计算的计数与inode中找到的计数不匹配，则必须采取纠正措施，通常是修复inode中的计数。如果发现已分配的inode，但没有目录引用它，则会将其移动到lost+found目录。
  • 重复：fsck还检查重复指针，即两个不同的inode引用同一个块的情况，如果一个inode明显不好，可能会被清除，或者可以复制指向的块，从而根据需要为每个inode提供其自己的副本。
  • 坏块：在扫描所有指针列表时，还会检查坏块指针。如果指针显然指向超出其有效范围的某个指针，则该指针被认为是坏的。在这种情况下，它只是从inode或者间接块中删除该指针。
  • 目录检查：fsck不了解用户文件的内容，但是目录包含由文件系统本身创建的特定格式信息。因此，fsck对每个目录的内容执行额外的完整性检查，确保“.”和“..”是前面的条目，目录条目中引用的每个inode都已分配，并确保整个层次结构没有目录的引用次数超过一次。

构建有效工作的fsck 需要复杂的文件系统知识。然而，fsck（和类似的方法）有一个更大的、更根本的问题：它太慢了。

预写日志

预写日志（write-ahead logging）是一个从数据库管理系统中借鉴的一个想法。在文件系统中通常将预写日志称为journaling。其基本思路如下：更新磁盘时，在覆写结构之前，首先写下一点小注记，描述你将要做的事情。写下的这个注记就是预写的部分。我们把它写入一个结构，并组织成日志。

通过将注释写入磁盘，可以保证在更新正在更新的结构期间发生崩溃时，能够返回并查看你所作的注记，然后重试。因此，你会在崩溃后准确知道要修复的内容，而不必扫描整个磁盘。

下面从一个简单的例子来理解数据日志（data journaling）的工作原理。假设再次进行标准的更新，我们希望将inode（I[V2]）、位图（B[v2]）和数据块（DB）写入磁盘。在将它们写入最终磁盘之前，先将它们写入日志，下面是日志的样子：

image-20200617204029126

上图中一共有5个块，事务日志（TxB）告诉我们有关此更新的信息，包括对文件系统即将进行的更新的相关信息（如I[v2]，B[v2]和Db）的最终地址，以及某种事务标识符（transaction identifier，TID）。中间三个块只包含本身确切的内容，被称为物理日志（physical logging），因为我们将更新的确切物理内容放在日志中，最后一个块是该事务结束的标记。

一旦该事务安全的存在于磁盘上，我们就可以覆写文件系统中的旧结构了。这个过程称为加检查点（checkpointing）。我们的操作顺序如下：

  • 日志写入：将事务（包括事务开始块，所有即将写入的数据和元数据更新）写入日志，等待这些写入完成。
  • 日志元数据写入：将开始块和元数据写入日志，等待写入完成。
  • 日志提交：将事务提交块写入日志，等待写入完成，事务被认为已提交。
  • 加检查点：将待处理的元数据和数据更新写入文件系统的最终位置。
  • 释放：一段时间后，通过更新日志超级块，在日志中标记该事务为空闲。

优化日志写入的方式：就是将事务写入日志时，在开始和结束块中包含日志内容的校验和，这样做可以使文件系统立即写入整个事务，而不会发生等待。

恢复

  • 如果崩溃发生在事务日志被安全地写入日志之前，那么就简单地跳过待执行的更新。
  • 如果在事务日志已提交到日志之后但在加载检查点完成之前崩溃，则文件系统可以按照如下的方式恢复：系统引导时，文件系统恢复过程将扫描日志，并查找已提交到磁盘的事物，然后，这些事物被重放，文件系统再次尝试将事务中的块写入它们最终的磁盘位置。这种形式的日志称为重做日志。

其他方法

软更新、写时复制、反向指针的一致性、乐观崩溃一致性。

日志结构文件系统

由于下面的原因，：

  • 内存大小不断增长；
  • 随机I/O性能与顺序I/O性能之间存在巨大的差距，且不断扩大。
  • 现代文件系统在许多常见工作负载上表现不佳。
  • 文件系统不支持RAID；

因此引入了新的文件系统LFS，是日志结构文件系统（Log-structured File System）的缩写。写入磁盘时，LFS首先将所有更新缓冲到内存段中，当段已满时，它会在一次长时间的顺序写入磁盘，并传输到磁盘的未使用部分。LFS永远不会覆写现有数据，而是始终将段写入空闲位置。由于段很大，因此可以有效的使用磁盘，并且文件系统的性能接近其峰值。

关键问题是：如何让所有写入变成顺序写入？

为了达到大量连续写入的目的，LFS使用了一种称为写入缓冲（write buffering）的技术。在写入磁盘之前，LFS会跟踪内存中的更新。收到足量的更新时，会立即将它们吸入磁盘，从而确保有效的使用磁盘，LFS一次写入的大块更新被称为段（segment）。

具体LFS在写入磁盘之前应该缓冲的更新多少次取决于磁盘本身，特别是与传输速率相比定位开销有多高。

为了保证顺序写入，LFS的inode分散在整个磁盘上，并且永远不会覆盖最新版本的inode，导致inode会不断移动，如何查找inode成为一个问题。为了解决这个问题，LFS通过名为inode映射（imap）的数据结构，在inode号和inode之间引入一个间接层。imap是一个结构，它将inode号作为输入，并生成最新版本的inode的磁盘地址。因此，它通常被实现为简单的数组，每个条目有4个字节。每次将inode写入磁盘时，imap都会使用其新位置进行更新。LFS将inode映射到的块放在它写入所有其他新信息的位置旁边，当将数据块追加到文件k时，LFS实际上将新数据块，其inode和一段inode映射一起写入磁盘。

LFS在磁盘上有一个固定的位置，称为检查点区域（checkpoint region，CR）。检查点区域包含指向最新inode映射片段的指针，因此可以通过首先读取CR来找到inode映射片段。因此，磁盘布局的整体结构包含一个检查点区域，每个inode映射包含inode的地址，inode指向文件。

数据完整性和保护

这里的关键问题是，如何确保数据完整性，确保写入存储的数据受到保护？

磁盘故障模式

对于磁盘来说，要么整个磁盘都在工作，要么完全失败，并且检测到这种故障很简单。这种磁盘故障的模型称为故障—停止模型（fail-stop）。

现代磁盘的故障类型一般为：潜在扇区错误（Latent-Sector Errors，LSE）和块讹误（block corruption）。

潜在的扇区错误很容易处理，因为它们（根据定义）很容易被检测到。当存储系统尝试访问块，并且磁盘返回错误时，存储系统应该就用它具有的任何冗余机制，来返回正确的数据。

利用校验和来处理块讹误的错误。

错误写入：错误位置写入（misdirected write），丢失的写入（lost write）;

Tags: 操作系统 持久性 I/O设备 文件系统
← 操作系统-并发 利用二叉堆实现优先级队列 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章