IO设备
系统架构
CPU通过某种内存总线（memory bus）或互连电缆连接到系统内存。图像或者其他高性能I/O设备通过常规的I/O总线（I/O bus）连接到系统，在许多现代系统中会是PCI或它的衍生形式。最后，更下面是外围总线（peripheral bus），比如SCSI、SATA或者USB。它们将最慢的设备连接到系统，包括磁盘、鼠标及其他类似设备。
为什么要用这样的分层架构？
因为物理布局及造价成本。
越快的总线越短，因此高性能的内存总线没有足够的空间连接太多设备。另外，在工程上高性能总线的造价非常高。所以，系统的设计采用了这种分层的方式，这样可以让要求高性能的设备（比如显卡）离CPU更近一些，低性能的设备离CPU远一些。将磁盘和其他低速设备连到外围总线的好处很多，其中较为突出的好处就是你可以在外围总线上连接大量的设备。
标准设备
一个标准设备（不是真实存在的）
第一部分是向系统其他部分展现的硬件接口（interface）。同软件一样，硬件也需要一些接口，让系统软件来控制它的操作。因此，所有设备都有自己的特定接口以及典型交互的协议。
第2部分是它的内部结构（internal structure）。这部分包含设备相关的特定实现，负责具体实现设备展示给系统的抽象接口。非常简单的设备通常用一个或几个芯片来实现它们的功能。更复杂的设备会包含简单的CPU、一些通用内存、设备相关的特定芯片，来完成它们的工作。例如，现代RAID控制器通常包含成百上千行固件（firmware，即硬件设备中的软件），以实现其功能。
标准协议
一个（简化的）设备接口包含3个寄存器：一个状态（status）寄存器，可以读取并查看设备的当前状态；一个命令（command）寄存器，用于通知设备执行某个具体任务；一个数据（data）寄存器，将数据传给设备或从设备接收数据。通过读写这些寄存器，操作系统可以控制设备的行为。
1 | While (STATUS == BUSY) |
该协议包含4步。第1步，操作系统通过反复读取状态寄存器，等待设备进入可以接收命令的就绪状态。我们称之为轮询（polling）设备（基本上，就是问它正在做什么）。第2步，操作系统下发数据到数据寄存器。例如，你可以想象如果这是一个磁盘，需要多次写入操作，将一个磁盘块（比如4KB）传递给设备。如果主CPU参与数据移动（就像这个示例协议一样），我们就称之为编程的I/O（programmed I/O，PIO）。第3步，操作系统将命令写入命令寄存器；这样设备就知道数据已经准备好了，它应该开始执行命令。最后一步，操作系统再次通过不断轮询设备，等待并判断设备是否执行完成命令（有可能得到一个指示成功或失败的错误码）。
简单有效但效率低（在等待设备执行完成命令时浪费大量CPU时间）
利用中断减少 CPU 开销
常见的中断（interrupt）来减少CPU开销。有了中断后，CPU 不再需要不断轮询设备，而是向设备发出一个请求，然后就可以让对应进程睡眠，切换执行其他任务。当设备完成了自身操作，会抛出一个硬件中断，引发CPU跳转执行操作系统预先定义好的中断服务例程（Interrupt Service Routine，ISR），或更为简单的中断处理程序（interrupt handler）。中断处理程序是一小段操作系统代码，它会结束之前的请求（比如从设备读取到了数据或者错误码）并且唤醒等待I/O的进程继续执行。
中断允许计算与I/O重叠（overlap），这是提高CPU利用率的关键。
其中，进程1在CPU上运行一段时间（对应CPU那一行上重复的1），然后发出一个读取数据的I/O请求给磁盘。如果没有中断，那么操作系统就会简单自旋，不断轮询设备状态，直到设备完成I/O操作（对应其中的p）。当设备完成请求的操作后，进程1又可以继续运行。
如果我们利用中断并允许重叠，操作系统就可以在等待磁盘操作时做其他事情：
在这个例子中，在磁盘处理进程1的请求时，操作系统在CPU上运行进程2。磁盘处理完成后，触发一个中断，然后操作系统唤醒进程1继续运行。这样，在这段时间，无论CPU还是磁盘都可以有效地利用。
如果设备非常快，那么最好的办法反而是轮询。如果设备比较慢，那么采用允许发生重叠的中断更好。
利用 DMA 进行更高效的数据传送
如果使用编程的I/O将一大块数据传给设备，CPU又会因为琐碎的任务而变得负载很重，浪费了时间和算力，本来更好是用于运行其他进程。下面的时间线展示了这个问题：
进程1在运行过程中需要向磁盘写一些数据，所以它开始进行I/O操作，将数据从内存拷贝到磁盘（其中标示c的过程）(从内存拷贝到磁盘缓冲区)。拷贝结束后，磁盘上的I/O操作开始执行，此时CPU才可以处理其他请求。
使用PIO的方式，CPU的时间会浪费在向设备传输数据或从设备传出数据的过程中。如何才能分离这项工作，从而提高CPU的利用率？
解决方案就是使用DMA（Direct Memory Access）。DMA引擎是系统中的一个特殊设备，它可以协调完成内存和设备间的数据传递，不需要CPU介入。
DMA工作过程如下。为了能够将数据传送给设备，操作系统会通过编程告诉DMA引擎数据在内存的位置，要拷贝的大小以及要拷贝到哪个设备。在此之后，操作系统就可以处理其他请求了。当DMA的任务完成后，DMA控制器会抛出一个中断来告诉操作系统自己已经完成数据传输。修改后的时间线如下：
从时间线中可以看到，数据的拷贝工作都是由DMA控制器来完成的。因为CPU在此时是空闲的，所以操作系统可以让它做一些其他事情，比如此处调度进程2到CPU来运行。因此进程2在进程1再次运行之前可以使用更多的CPU。
PIO通过在计算机系统的总线上进行并行数据传输来完成输入和输出操作。在PIO模式下，数据是逐位地在系统总线上传输的，需要使用多个时钟周期完成一个数据传输操作。此外，PIO通常涉及主处理器的直接参与，主处理器负责控制和协调数据传输操作。
相比之下，DMA（Direct Memory Access，直接内存访问）是另一种数据传输模式。在DMA模式下，数据传输由DMA控制器负责，而不再需要主处理器直接参与。这种方式可以降低主处理器的负载，并提高数据传输效率。
设备交互的方法
硬件如何如与设备通信？是否需要一些明确的指令？或者其他的方式？
主要有两种方式来实现与设备的交互。第一种办法相对老一些（在IBM主机中使用了多年），就是用明确的I/O指令。这些指令规定了操作系统将数据发送到特定设备寄存器的方法，从而允许构造上文提到的协议。
例如在x86上，in和out指令可以用来与设备进行交互。当需要发送数据给设备时，调用者指定一个存入数据的特定寄存器及一个代表设备的特定端口。执行这个指令就可以实现期望的行为。
这些指令通常是特权指令（privileged）。操作系统是唯一可以直接与设备交互的实体。
第二种方法是内存映射I/O（memory- mapped I/O）。通过这种方式，硬件将设备寄存器作为内存地址提供。当需要访问设备寄存器时，操作系统装载（读取）或者存入（写入）到该内存地址；然后硬件会将装载/存入转移到设备上，而不是物理内存。
纳入操作系统：设备驱动程序
如何保持操作系统的大部分与设备无关，从而对操作系统的主要子系统隐藏设备交互的细节？
在最底层，操作系统的一部分软件清楚地知道设备如何工作，我们将这部分软件称为设备驱动程序（device driver），所有设备交互的细节都封装在其中。
文件系统（当然也包括在其之上的应用程序）完全不清楚它使用的是什么类型的磁盘。它只需要简单地向通用块设备层发送读写请求即可，块设备层会将这些请求路由给对应的设备驱动，然后设备驱动来完成真正的底层操作。
磁盘驱动器
接口
驱动器由大量扇区（512字节块）组成，每个扇区都可以读取或写入。在具有n个扇区的磁盘上，扇区从0到n−1编号。因此，我们可以将磁盘视为一组扇区，0到n−1是驱动器的地址空间（address space）。
多扇区操作是可能的。实际上，许多文件系统一次读取或写入4KB（或更多）。但是，在更新磁盘时，驱动器制造商唯一保证的是单个512字节的写入是原子的（atomic，即它将完整地完成或者根本不会完成）。
基本几何形状
让我们开始了解现代磁盘的一些组件。我们从一个盘片（platter）开始，它是一个圆形坚硬的表面，通过引入磁性变化来永久存储数据。磁盘可能有一个或多个盘片。每个盘片有两面，每面都称为表面。这些盘片通常由一些硬质材料（如铝）制成，然后涂上薄薄的磁性层，即使驱动器断电，驱动器也能持久存储数据位。
所有盘片都围绕主轴（spindle）连接在一起，主轴连接到一个电机，以一个恒定（固定）的速度旋转盘片（当驱动器接通电源时）。旋转速率通常以每分钟转数（Rotations Per Minute，RPM）来测量，典型的现代数值在7200～15000 RPM范围内。请注意，我们经常会对单次旋转的时间感兴趣，例如，以10000 RPM旋转的驱动器意味着一次旋转需要大约6ms。
数据在扇区的同心圆中的每个表面上被编码。我们称这样的同心圆为一个磁道（track）。一个表面包含数以千计的磁道，紧密地排在一起，数百个磁道只有头发的宽度。
要从表面进行读写操作，我们需要一种机制，使我们能够感应（即读取）磁盘上的磁性图案，或者让它们发生变化（即写入）。读写过程由磁头（disk head）完成；驱动器的每个表面有一个这样的磁头。磁头连接到单个磁盘臂（disk arm）上，磁盘臂在表面上移动，将磁头定位在期望的磁道上。
简单的磁盘驱动器
该磁道只有12个扇区，每个扇区的大小为512字节（典型的扇区大小，回忆一下），因此用0到11的数字表示。这里的单个盘片围绕主轴旋转，电机连接到主轴。当然，磁道本身并不太有趣，我们希望能够读取或写入这些扇区，因此需要一个连接到磁盘臂上的磁头:
单磁道延迟：旋转延迟
现在收到读取块0的请求。磁盘应如何处理该请求？
简单磁盘中，磁盘不必做太多工作。具体来说，它必须等待期望的扇区旋转到磁头下。这种等待在现代驱动器中经常发生，并且是I/O服务时间的重要组成部分，它有一个特殊的名称：旋转延迟（rotational delay，有时称为rotation delay，尽管听起来很奇怪）
多磁道：寻道时间
到目前为止，我们的磁盘只有一条磁道，这是不太现实的。现代磁盘当然有数以百万计的磁道。因此，我们来看看更具现实感的磁盘表面，这个表面有3条磁道（见图37.3左图）。在该图中，磁头当前位于最内圈的磁道上（它包含扇区24～35）。下一个磁道包含下一组扇区（12～23），最外面的磁道包含最前面的扇区（0～11）。
读取扇区11。为了服务这个读取请求，驱动器必须首先将磁盘臂移动到正确的磁道（在这种情况下，是最外面的磁道），通过一个所谓的寻道（seek）过程。寻道，以及旋转，是最昂贵的磁盘操作之一。
寻道有许多阶段：首先是磁盘臂移动时的加速阶段。然后随着磁盘臂全速移动而惯性滑动。然后随着磁盘臂减速而减速。最后，在磁头小心地放置在正确的磁道上时停下来。停放时间（settling time）通常不小，例如0.5～2ms，因为驱动器必须确定找到正确的磁道（想象一下，如果它只是移到附近！）。
寻道之后，磁盘臂将磁头定位在正确的磁道上。
在这个例子中，大约旋转了3个扇区。因此，扇区9即将通过磁头下方，我们只能承受短暂的转动延迟，以便完成传输。
当扇区11经过磁盘磁头时，I/O的最后阶段将发生，称为传输（transfer），数据从表面读取或写入表面。因此，我们得到了完整的I/O时间图：首先寻道，然后等待转动延迟，最后传输。
一些其他细节
许多驱动器采用某种形式的磁道偏斜（track skew）(轻微错位)，以确保即使在跨越磁道边界时，顺序读取也可以方便地服务。
扇区往往会偏斜，因为从一个磁道切换到另一个磁道时，磁盘需要时间来重新定位磁头（即便移到相邻磁道）。如果没有这种偏斜，磁头将移动到下一个磁道，但所需的下一个块已经旋转到磁头下，因此驱动器将不得不等待整个旋转延迟，才能访问下一个块。
任何现代磁盘驱动器都有一个重要组成部分，即它的缓存（cache），由于历史原因有时称为磁道缓冲区（track buffer）。该缓存只是少量的内存（通常大约8MB或16MB），驱动器可以使用这些内存来保存从磁盘读取或写入磁盘的数据。例如，当从磁盘读取扇区时，驱动器可能决定读取该磁道上的所有扇区并将其缓存在其存储器中。这样做可以让驱动器快速响应所有后续对同一磁道的请求。
在写入时，驱动器面临一个选择：是先写入缓存再写入磁盘？还是边写缓存边写入磁盘？前者被称为后写（write back）缓存（有时称为立即报告，immediate reporting），后者则称为直写（write through）。后写缓存有时会使驱动器看起来“更快”，但可能有危险。
I/O 时间：用数学
现在可以将I/O时间表示为3个主要部分之和：
TI/O = T寻道+ T旋转+ T传输
为了更好地感受I/O时间，我们执行以下计算。假设有两个我们感兴趣的工作负载。第一个工作负载称为随机（random）工作负载，它向磁盘上的随机位置发出小的（例如4KB）读取请求。随机工作负载在许多重要的应用程序中很常见，包括数据库管理系统。第二种称为顺序（sequential）工作负载，只是从磁盘连续读取大量的扇区，不会跳过。顺序访问模式很常见，因此也很重要。
提示：顺序地使用磁盘
尽可能以顺序方式将数据传输到磁盘，并从磁盘传输数据。如果顺序不可行，至少应考虑以大块传输数据：越大越好。如果I/O是以小而随机方式完成的，则I/O性能将受到显著影响。而且，用户也会痛苦。而且，你也会痛苦，因为你知道正是你不小心的随机I/O让你痛苦。
磁盘调度
与任务调度不同，每个任务的长度通常是不知道的，对于磁盘调度，我们可以很好地猜测“任务”（即磁盘请求）需要多长时间。通过估计请求的查找和可能的旋转延迟，磁盘调度程序可以知道每个请求将花费多长时间，因此（贪婪地）选择先服务花费最少时间的请求。因此，磁盘调度程序将尝试在其操作中遵循SJF（最短任务优先）的原则（principle of SJF，shortest job first）。
SSTF：最短寻道时间优先
SSTF按磁道对I/O请求队列排序，选择在最近磁道上的请求先完成。例如，假设磁头当前位置在内圈磁道上，并且我们请求扇区21（中间磁道）和2（外圈磁道），那么我们会首先发出对21的请求，等待它完成，然后发出对2的请求。
第一个问题，主机操作系统无法利用驱动器的几何结构，而是只会看到一系列的块。幸运的是，这个问题很容易解决。操作系统可以简单地实现最近块优先（Nearest-Block-First，NBF），而不是SSTF，然后用最近的块地址来调度请求。
第二个问题更为根本：饥饿（starvation）。想象一下，在我们上面的例子中，是否有对磁头当前所在位置的内圈磁道有稳定的请求。然后，纯粹的SSTF方法将完全忽略对其他磁道的请求。
电梯（又称 SCAN 或 C-SCAN）
简单地以跨越磁道的顺序来服务磁盘请求。我们将一次跨越磁盘称为扫一遍。因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立即处理，而是排队等待下次扫一遍。
SCAN有许多变种，所有这些变种都是一样的。例如，Coffman等人引入了F-SCAN，它在扫一遍时冻结队列以进行维护[CKR72]。这个操作会将扫一遍期间进入的请求放入队列中，以便稍后处理。这样做可以避免远距离请求饥饿，延迟了迟到（但更近）请求的服务。
C-SCAN是另一种常见的变体，即循环SCAN（Circular SCAN）的缩写。不是在一个方向扫过磁盘，该算法从外圈扫到内圈，然后从内圈扫到外圈，如此下去。
它们忽视了旋转。
SPTF：最短定位时间优先
8还是16?
这里的情况是旋转与寻道相比的相对时间。如果在我们的例子中，寻道时间远远高于旋转延迟，那么SSTF（和变体）就好了。但是，想象一下，如果寻道比旋转快得多。然后，在我们的例子中，寻道远一点的、在外圈磁道的服务请求8，比寻道近一点的、在中间磁道的服务请求16更好，后者必须旋转很长的距离才能移到磁头下。
因此SPTF是有用的，它提高了性能。然而，它在操作系统中实现起来更加困难，操作系统通常不太清楚磁道边界在哪，也不知道磁头当前的位置（旋转到了哪里）。因此，SPTF通常在驱动器内部执行.
其他调度问题
磁盘可以接受多个分离的请求，它们本身具有复杂的内部调度程序（它们可以准确地实现SPTF。在磁盘控制器内部，所有相关细节都可以得到，包括精确的磁头位置）。因此，操作系统调度程序通常会选择它认为最好的几个请求（如16），并将它们全部发送到磁盘。磁盘然后利用其磁头位置和详细的磁道布局信息等内部知识，以最佳可能（SPTF）顺序服务于这些请求。
磁盘调度程序执行的另一个重要相关任务是I/O合并（I/O merging）。例如，设想一系列请求读取块33，然后是8，然后是34，如图37.8所示。在这种情况下，调度程序应该将块33和34的请求合并（merge）为单个两块请求。调度程序执行的所有请求都基于合并后的请求。合并在操作系统级别尤其重要，因为它减少了发送到磁盘的请求数量，从而降低了开销。
廉价冗余磁盘阵列(RAID)
如何得到大型、快速、可靠的磁盘?
廉价冗余磁盘阵列(RAID)这种技术使用多个磁盘一起构建更快、更大、更可靠的磁盘系统。
在内部，RAID是一个复杂的庞然大物，由多个磁盘、内存（包括易失性和非易失性）以及一个或多个处理器来管理系统。硬件RAID非常像一个计算机系统，专门用于管理一组磁盘。
接口和 RAID 内部
当文件系统向RAID发出逻辑I/O请求时，RAID内部必须计算要访问的磁盘（或多个磁盘）以完成请求，然后发出一个或多个物理I/O来执行此操作。这些物理I/O的确切性质取决于RAID级别。
考虑一个RAID，它保留每个块的两个副本（每个都在一个单独的磁盘上）。当写入这种镜像（mirrored）RAID系统时，RAID必须为它发出的每一个逻辑I/O执行两个物理I/O。
RAID系统通常构建为单独的硬件盒，并通过标准连接（例如，SCSI或SATA）接入主机。然而，在内部，RAID相当复杂。它包括一个微控制器，运行固件以指导RAID的操作。它还包括DRAM这样的易失性存储器，在读取和写入时缓冲数据块。在某些情况下，还包括非易失性存储器，安全地缓冲写入。它甚至可能包含专用的逻辑电路，来执行奇偶校验计算（在某些RAID级别中非常有用，下面会提到）。在很高的层面上，RAID是一个非常专业的计算机系统：它有一个处理器，内存和磁盘。然而，它不是运行应用程序，而是运行专门用于操作RAID的软件。
故障模型
故障—停止（fail-stop）故障模型
磁盘可以处于两种状态之一：工作状态或故障状态。使用工作状态的磁盘时，所有块都可以读取或写入。相反，当磁盘出现故障时，我们认为它永久丢失。
如何评估 RAID
第一个方面是容量（capacity）。在给定一组N个磁盘的情况下，RAID的客户端可用的容量有多少？没有冗余，答案显然是N。不同的是，如果有一个系统保存每个块的两个副本，我们将获得N/2的有用容量。不同的方案（例如，基于校验的方案）通常介于两者之间。
第二个方面是可靠性（reliability）。给定设计允许有多少磁盘故障？根据我们的故障模型，我们只假设整个磁盘可能会故障。在后面的章节（例如，关于数据完整性的第44章）中，我们将考虑如何处理更复杂的故障模式。
最后，第三个方面是性能（performance）。性能有点难以评估，因为它在很大程度上取决于磁盘阵列提供的工作负载。因此，在评估性能之前，我们将首先提出一组应该考虑的典型工作负载。
RAID 0 级：条带化
第一个RAID级别实际上不是RAID级别，因为没有冗余。
以轮转方式将磁盘阵列的块分布在磁盘上。这种方法的目的是在对数组的连续块进行请求时，从阵列中获取最大的并行性（例如，在一个大的顺序读取中）。我们将同一行中的块称为条带，因此，上面的块0、1、2和3在相同的条带中。
补充：RAID映射问题
简单地说，给定一个逻辑块来读或写，RAID如何确切地知道要访问哪个物理磁盘和偏移量？
以上面的第一个条带为例（大块大小= 1块= 4KB）。在这种情况下，给定逻辑块地址A，RAID可以使用两个简单的公式轻松计算要访问的磁盘和偏移量：
磁盘= A % 磁盘数
偏移量 = A / 磁盘数
假设在上面的第一个RAID中，对块15的请求到达。鉴于有4个磁盘，这意味着我们感兴趣的磁盘是（14 % 4 = 2）：磁盘2。确切的块计算为（14 / 4 = 3）：块3。因此，应在第三个磁盘（磁盘2，从0开始）的第四个块（块3，从0开始）处找到块14，该块恰好位于该位置
大块大小
一方面，大块大小主要影响阵列的性能。例如，大小较小的大块意味着许多文件将跨多个磁盘进行条带化，从而增加了对单个文件的读取和写入的并行性。但是，跨多个磁盘访问块的定位时间会增加，因为整个请求的定位时间由所有驱动器上请求的最大定位时间决定。
另一方面，较大的大块大小减少了这种文件内的并行性，因此依靠多个并发请求来实现高吞吐量。但是，较大的大块大小减少了定位时间。例如，如果一个文件放在一个块中并放置在单个磁盘上，则访问它时发生的定位时间将只是单个磁盘的定位时间。
RAID-0 分析
从容量的角度来看，它是顶级的：给定N个磁盘，条件化提供N个磁盘的有用容量。从可靠性的角度来看，条带化也是顶级的，但是最糟糕：任何磁盘故障都会导致数据丢失。最后，性能非常好：通常并行使用所有磁盘来为用户I/O请求提供服务。
RAID 1 级：镜像
第一个超越条带化的RAID级别称为RAID 1级，即镜像。对于镜像系统，我们只需生成系统中每个块的多个副本。当然，每个副本应该放在一个单独的磁盘上。通过这样做，我们可以容许磁盘故障。
在一个典型的镜像系统中，我们将假设对于每个逻辑块，RAID保留两个物理副本。
从镜像阵列读取块时，RAID有一个选择：它可以读取任一副本。例如，如果对RAID发出对逻辑块5的读取，则可以自由地从磁盘2或磁盘3读取它。但是，在写入块时，不存在这样的选择：RAID必须更新两个副本的数据，以保持可靠性。但请注意，这些写入可以并行进行。例如，对逻辑块5的写入可以同时在磁盘2和3上进行。
RAID-1 分析
从容量的角度来看，RAID-1价格昂贵。在镜像级别=2的情况下，我们只能获得峰值有用容量的一半。因此，对于N个磁盘，镜像的有用容量为N/2。
从可靠性的角度来看，RAID-1表现良好。它可以容许任何一个磁盘的故障。
最后，我们分析性能。从单个读取请求的延迟角度来看，我们可以看到它与单个磁盘上的延迟相同。所有RAID-1都会将读取导向一个副本。写入有点不同：在完成写入之前，需要完成两次物理写入。这两个写入并行发生，因此时间大致等于单次写入的时间。然而，因为逻辑写入必须等待两个物理写入完成，所以它遭遇到两个请求中最差的寻道和旋转延迟，因此（平均而言）比写入单个磁盘略高。
补充：RAID一致更新问题
我们假设对磁盘0的请求已完成（但对磁盘1的请求显然没有完成，因为它从未发出）。
这种不合时宜的掉电，导致现在数据块的两个副本不一致（inconsistent）。磁盘0上的副本是新版本，而磁盘1上的副本是旧的。我们希望的是两个磁盘的状态都原子地（atomically）改变，也就是说，两者都应该最终成为新版本或者两者都不是。
解决此问题的一般方法，是使用某种预写日志（write-ahead log），在做之前首先记录RAID将要执行的操作（即用某个数据更新两个磁盘）。通过采取这种方法，我们可以确保在发生崩溃时，会发生正确的事情。通过运行一个恢复（recovery）过程，将所有未完成的事务重新在RAID上执行，我们可以确保两个镜像副本（在RAID-1情况下）同步。
最后一个注意事项：每次写入都在磁盘上记录日志，这个代价昂贵得不行，因此大多数RAID硬件都包含少量非易失性RAM（例如电池有备份的），用于执行此类记录。因此，既提供了一致的更新，又不需要花费高昂的代价，将日志记录到磁盘。
RAID 4 级：通过奇偶校验节省空间
我们现在展示一种向磁盘阵列添加冗余的不同方法，称为奇偶校验（parity）。基于奇偶校验的方法试图使用较少的容量，从而克服由镜像系统付出的巨大空间损失。不过，这样做的代价是——性能。
这是5个磁盘的RAID-4系统的例子（见表38.4）。对于每一条数据，我们都添加了一个奇偶校验（parity）块，用于存储该条块的冗余信息。例如，奇偶校验块P1具有从块4、5、6和7计算出的冗余信息。
任何一行中的1的数量必须是偶数（而不是奇数）。这是RAID必须保持的不变性（invariant），以便奇偶校验正确。
如何利用奇偶校验信息从故障中恢复?
标为C2的列丢失了。要找出该列中肯定存在的值，我们只需读取该行中的所有其他值（包括XOR的奇偶校验位）并重构（reconstruct）正确的答案。
假设C2列中第一行的值丢失（它是1）。通过读取该行中的其他值（C0中的0，C1中的0，C3中的1以及奇偶校验列P中的0），我们得到值0、0、1和0。因为我们知道XOR保持每行有偶数个1，所以就知道丢失的数据肯定是什么——1。这就是重构在基于异或的方案中的工作方式！还要注意如何计算重构值：只要将数据位和奇偶校验位异或，就像开始计算奇偶校验一样。
可以看出，每个块的每个比特计算奇偶校验，结果放在奇偶校验块中。
RAID-4 分析
RAID-4使用1个磁盘作为它所保护的每组磁盘的奇偶校验信息。因此，RAID组的有用容量是（N−1）。
可靠性也很容易理解：RAID-4容许1个磁盘故障，不容许更多。如果丢失多个磁盘，则无法重建丢失的数据。
改写数据？
存在两种方法。第一种称为加法奇偶校验（additive parity），要求我们做以下工作。为了计算新奇偶校验块的值，并行读取条带中所有其他数据块（在本例中为块0、2和3），并与新块（1）进行异或。结果是新的校验块。为了完成写操作，你可以将新数据和新奇偶校验写入其各自的磁盘，也是并行写入。
这种技术的问题在于它随磁盘数量而变化，因此在较大的RAID中，需要大量的读取来计算奇偶校验。因此，导致了减法奇偶校验（subtractive parity）方法。
想象一下，我们希望用一个新值来覆盖C2位，称之为C2new。减法方法分三步工作。首先，我们读入C2（C2old = 1）和旧数据（Pold = 0）的旧数据。然后，比较旧数据和新数据。如果它们相同（例如，C2new = C2old），那么我们知道奇偶校验位也将保持相同（即Pnew = Pold）。但是，如果它们不同，那么我们必须将旧的奇偶校验位翻转到其当前状态的相反位置，也就是说，如果（Pold == 0），Pnew将被设置为0。如果（Pold == 0），Pnew将被设置为1。我们可以用XOR（⊕是XOR运算符）漂亮地表达完整的复杂情况：
Pnew = (Cold⊕ Cnew) ⊕ Pold
对于每次写入，RAID必须执行4次物理I/O（两次读取和两次写入）
现在想象几乎同时向RAID-4提交2个小的请求，写入块4和块13（在表38.8中标出）。这些磁盘的数据位于磁盘0和1上，因此对数据的读写操作可以并行进行，这很好。出现的问题是奇偶校验磁盘。这两个请求都必须读取4和13的奇偶校验块，即奇偶校验块1和3（用+标记）。估计你已明白了这个问题：在这种类型的工作负载下，奇偶校验磁盘是瓶颈。因此我们有时将它称为基于奇偶校验的RAID的小写入问题（small-write problem）。
RAID 5 级：旋转奇偶校验
每个条带的奇偶校验块现在都在磁盘上旋转，以消除RAID-4的奇偶校验磁盘瓶颈。
RAID 比较：总结
插叙：文件和目录
到目前为止，我们看到了两项关键操作系统技术的发展：
进程，它是虚拟化的CPU；地址空间，它是虚拟化的内存。
在这两种抽象共同作用下，程序运行时就好像它在自己的私有独立世界中一样，好像它有自己的处理器（或多处理器），好像它有自己的内存。
持久存储（persistent storage）。永久存储设备永久地（或至少长时间地）存储信息，如传统硬盘驱动器（hard disk drive）或更现代的固态存储设备（solid-state storage device）。持久存储设备与内存不同。内存在断电时，其内容会丢失，而持久存储设备会保持这些数据不变。因此，操作系统必须特别注意这样的设备：用户用它们保存真正关心的数据。
文件和目录
随着时间的推移，存储虚拟化形成了两个关键的抽象。第一个是文件（file）。文件就是一个线性字节数组，每个字节都可以读取或写入。每个文件都有某种低级名称（low-level name），通常是某种数字。用户通常不知道这个名字（我们稍后会看到）。由于历史原因，文件的低级名称通常称为inode号（inode number）。
第二个抽象是目录（directory）。一个目录，像一个文件一样，也有一个低级名字（即inode号），但是它的内容非常具体：它包含一个（用户可读名字，低级名字）对的列表。例如，假设存在一个低级别名称为“10”的文件，它的用户可读的名称为“foo”。“foo”所在的目录因此会有条目（“foo”，“10”），将用户可读名称映射到低级名称。目录中的每个条目都指向文件或其他目录。通过将目录放入其他目录中，用户可以构建任意的目录树（directory tree，或目录层次结构，directory hierarchy），在该目录树下存储所有文件和目录。
创建文件
通过调用open()并传入O_CREAT标志，程序可以创建一个新文件。
1 | int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC); |
open()的一个重要方面是它的返回值：文件描述符（file descriptor）。文件描述符只是一个整数，是每个进程私有的，在UNIX系统中用于访问文件。因此，一旦文件被打开，你就可以使用文件描述符来读取或写入文件，假定你有权这样做。这样，一个文件描述符就是一种权限（capability）[L84]，即一个不透明的句柄，它可以让你执行某些操作。另一种看待文件描述符的方法，是将它作为指向文件类型对象的指针。一旦你有这样的对象，就可以调用其他“方法”来访问文件，如read()和write()。
句柄（Handle）是计算机科学中的一个术语，用于表示对资源或对象的引用。在操作系统中，句柄通常是一个整数或指针，用于标识和跟踪分配给进程的资源，例如文件、内存、设备或其他系统对象。
句柄可以看作是对实际对象的间接引用，类似于人们使用门牌号码来访问房屋。通过使用句柄，程序可以在需要的时候引用和操作特定的资源，而不需要了解其具体的内部表示或实现细节。
句柄在编程中非常常见，特别是在底层操作系统编程、图形用户界面(GUI)开发和资源管理方面。通过使用句柄，程序可以更有效地管理和控制系统资源，并提高代码的可读性和维护性。
读写文件
使用strace（和类似工具）strace工具提供了一种非常棒的方式，来查看程序在做什么。通过运行它，你可以跟踪程序生成的系统调用，查看参数和返回代码，通常可以很好地了解正在发生的事情。
下面是一个例子，使用strace来找出cat在做什么（为了可读性删除了一些调用）
1 | prompt> strace cat foo |
cat做的第一件事是打开文件准备读取。我们应该注意几件事情。首先，该文件仅为读取而打开（不写入），如O_RDONLY标志所示。其次，使用64位偏移量（O_LARGEFILE）。最后，open()调用成功并返回一个文件描述符，其值为3。
为什么第一次调用open()会返回3，而不是0或1？
每个正在运行的进程已经打开了3个文件：标准输入（进程可以读取以接收输入），标准输出（进程可以写入以便将信息显示到屏幕），以及标准错误（进程可以写入错误消息）。这些分别由文件描述符0、1和2表示。因此，当你第一次打开另一个文件时（如上例所示），它几乎肯定是文件描述符3。
打开成功后，cat使用read()系统调用重复读取文件中的一些字节。read()的第一个参数是文件描述符，从而告诉文件系统读取哪个文件。一个进程当然可以同时打开多个文件，因此描述符使操作系统能够知道某个特定的读取引用了哪个文件。第二个参数指向一个用于放置read()结果的缓冲区。在上面的系统调用跟踪中，strace显示了这时的读取结果（“hello”）。第三个参数是缓冲区的大小，在这个例子中是4KB。对read()的调用也成功返回，这里返回它读取的字节数（6，其中包括“hello”中的5个字母和一个行尾标记）。
write()系统调用的一次调用，针对文件描述符1。如上所述，此描述符被称为标准输出，因此用于将单词“Hello”写到屏幕上，这正是cat程序要做的事。但是它直接调用write()吗？也许（如果它是高度优化的）。但是，如果不是，那么可能会调用库例程printf()。在内部，printf()会计算出传递给它的所有格式化细节，并最终对标准输出调用write，将结果显示到屏幕上。
然后，cat程序试图从文件中读取更多内容，但由于文件中没有剩余字节，read()返回0，程序知道这意味着它已经读取了整个文件。因此，程序调用close()，传入相应的文件描述符，表明它已用完文件“foo”。该文件因此被关闭，对它的读取完成了。
读取和写入，但不按顺序
有时能够读取或写入文件中的特定偏移量是有用的。例如，如果你在文本文件上构建了索引并利用它来查找特定单词，最终可能会从文件中的某些随机（random）偏移量中读取数据。为此，我们将使用lseek()系统调用。下面是函数原型：
1 | off_t lseek(int fildes, off_t offset, int whence); |
第一个参数是熟悉的（一个文件描述符）。第二个参数是偏移量，它将文件偏移量定位到文件中的特定位置。第三个参数，由于历史原因而被称为whence，明确地指定了搜索的执行方式。
从这段描述中可见，对于每个进程打开的文件，操作系统都会跟踪一个“当前”偏移量，这将决定在文件中读取或写入时，下一次读取或写入开始的位置。因此，打开文件的抽象包括它具有当前偏移量，偏移量的更新有两种方式。第一种是当发生N个字节的读或写时，N被添加到当前偏移。因此，每次读取或写入都会隐式更新偏移量。第二种是明确的lseek，它改变了上面指定的偏移量。
调用lseek()不会执行磁盘寻道
lseek()调用只是在OS内存中更改一个变量，该变量跟踪特定进程的下一个读取或写入开始的偏移量。如果发送到磁盘的读取或写入与最后一次读取或写入不在同一磁道上，就会发生磁盘寻道，因此需要磁头移动。
用 fsync()立即写入
大多数情况下，当程序调用write()时，它只是告诉文件系统：请在将来的某个时刻，将此数据写入持久存储。出于性能的原因，文件系统会将这些写入在内存中缓冲（buffer）一段时间（例如5s或30s）。在稍后的时间点，写入将实际发送到存储设备。从调用应用程序的角度来看，写入似乎很快完成，并且只有在极少数情况下（例如，在write()调用之后但写入磁盘之前，机器崩溃）数据会丢失。
在数据库管理系统（DBMS）中，开发正确的恢复协议要求能够经常强制写入磁盘。
当进程针对特定文件描述符调用fsync()时，文件系统通过强制将所有脏（dirty）数据（即尚未写入的）写入磁盘来响应，针对指定文件描述符引用的文件。一旦所有这些写入完成，fsync()例程就会返回。
以下是如何使用fsync()的简单示例。代码打开文件foo，向它写入一个数据块，然后调用fsync()以确保立即强制写入磁盘。一旦fsync()返回，应用程序就可以安全地继续前进，知道数据已被保存（如果fsync()实现正确，那就是了）。
1 | int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC); |
在某些情况下，还需要fsync()包含foo文件的目录。添加此步骤不仅可以确保文件本身位于磁盘上，而且可以确保文件（如果新创建）也是目录的一部分。
文件重命名
有时需要给一个文件一个不同的名字。在命令行键入时，这是通过mv命令完成的。
1 | prompt> mv foo bar |
利用strace，我们可以看到mv使用了系统调用rename(char * old, char * new)，它只需要两个参数：文件的原来名称（old）和新名称（new）。
rename()调用提供了一个有趣的保证：它（通常）是一个原子（atomic）调用，不论系统是否崩溃。如果系统在重命名期间崩溃，文件将被命名为旧名称或新名称，不会出现奇怪的中间状态。因此，对于支持某些需要对文件状态进行原子更新的应用程序，rename()非常重要。
1 | int fd = open("foo.txt.tmp", O_WRONLY|O_CREAT|O_TRUNC); |
编辑器做的事很简单：将文件的新版本写入临时名称（foot.txt.tmp），使用fsync()将其强制写入磁盘。然后，当应用程序确定新文件的元数据和内容在磁盘上，就将临时文件重命名为原有文件的名称。最后一步自动将新文件交换到位，同时删除旧版本的文件，从而实现原子文件更新。
获取文件信息
除了文件访问之外，我们还希望文件系统能够保存关于它正在存储的每个文件的大量信息。我们通常将这些数据称为文件元数据（metadata）。要查看特定文件的元数据，我们可以使用stat()或fstat()系统调用。这些调用将一个路径名（或文件描述符）添加到一个文件中，并填充一个stat结构，如下所示：
1 | struct stat { |
要查看此信息，可以使用命令行工具stat：
1 | prompt> echo hello > file |
事实表明，每个文件系统通常将这种类型的信息保存在一个名为 inode
①的结构中。应该将 inode看作是由文件系统保存的持久数据结构，包含上述信息。
删除文件
1 | prompt> strace rm foo |
unlink()只需要待删除文件的名称，并在成功时返回零。
创建目录
除了文件外，还可以使用一组与目录相关的系统调用来创建、读取和删除目录。永远不能直接写入目录。因为目录的格式被视为文件系统元数据，所以你只能间接更新目录，例如，通过在其中创建文件、目录或其他对象类型。通过这种方式，文件系统可以确保目录的内容始终符合预期。
要创建目录，可以用系统调用mkdir()。同名的mkdir程序可以用来创建这样一个目录。
1 | prompt> strace mkdir foo |
这样的目录创建时，它被认为是“空的”，尽管它实际上包含最少的内容。具体来说，空目录有两个条目：一个引用自身的条目，一个引用其父目录的条目。前者称为“.”（点）目录，后者称为“..”（点-点）目录。你可以通过向程序ls传递一个标志（-a）来查看这些目录：
1 | prompt> ls -a |
读取目录
创建了目录，也可能希望读取目录。实际上，这正是ls程序做的事。
1 | int main(int argc, char *argv[]) { |
删除目录
可以通过调用rmdir()来删除目录（它由相同名称的程序rmdir使用）。然而，与删除文件不同，删除目录更加危险，因为你可以使用单个命令删除大量数据。因此，rmdir()要求该目录在被删除之前是空的（只有“.”和“..”条目）。如果你试图删除一个非空目录，那么对rmdir()的调用就会失败。
硬链接
理解在文件系统树中创建条目的新方法，即通过所谓的link()系统调用。
link()系统调用有两个参数：一个旧路径名和一个新路径名。当你将一个新的文件名“链接”到一个旧的文件名时，你实际上创建了另一种引用同一个文件的方法。
1 | prompt> echo hello > file |
link只是在要创建链接的目录中创建了另一个名称，并将其指向原有文件的相同inode号（即低级别名称）。该文件不以任何方式复制。相反，你现在就有了两个人类可读的名称（file和file2），都指向同一个文件。通过打印每个文件的inode号，我们甚至可以在目录中看到这一点：
1 | prompt> ls -i file file2 |
创建一个文件时，实际上做了两件事。首先，要构建一个结构（inode），它将跟踪几乎所有关于文件的信息，包括其大小、文件块在磁盘上的位置等等。其次，将人类可读的名称链接到该文件，并将该链接放入目录中。
在创建文件的硬链接之后，在文件系统中，原有文件名（file）和新创建的文件名（file2）之间没有区别。实际上，它们都只是指向文件底层元数据的链接，可以在inode编号67158084中找到。
这样的结果是因为当文件系统取消链接文件时，它检查inode号中的引用计数（reference count）。该引用计数（有时称为链接计数，link count）允许文件系统跟踪有多少不同的文件名已链接到这个inode。调用unlink()时，会删除人类可读的名称（正在删除的文件）与给定inode号之间的“链接”，并减少引用计数。只有当引用计数达到零时，文件系统才会释放inode和相关数据块，从而真正“删除”该文件。
可以使用stat()来查看文件的引用计数。让我们看看创建和删除文件的硬链接时，引用计数是什么。在这个例子中，我们将为同一个文件创建 3 个链接，然后删除它们。仔细看链接计数！
1 | prompt> echo hello > file |
符号链接
还有一种非常有用的链接类型，称为符号链接（symbolic link），有时称为软链接（soft link）。事实表明，硬链接有点局限：你不能创建目录的硬链接（因为担心会在目录树中创建一个环）。你不能硬链接到其他磁盘分区中的文件（因为inode号在特定文件系统中是唯一的，而不是跨文件系统），等等。因此，人们创建了一种称为符号链接的新型链接。
要创建这样的链接，可以使用相同的程序ln，但使用-s标志。
1 | prompt> echo hello > file |
如你所见，创建软链接看起来几乎相同，现在可以通过文件名称file以及符号链接名称file2来访问原始文件。但是，除了表面相似之外，符号链接实际上与硬链接完全不同。第一个区别是符号链接本身实际上是一个不同类型的文件。我们已经讨论过常规文件和目录。符号链接是文件系统知道的第三种类型。
1 | prompt> stat file |
如果仔细观察 ls 输出的长格式的第一个字符，可以看到常规文件最左列中的第一个字符是“-”，目录是“d”，软链接是“l”。你还可以看到符号链接的大小（本例中为 4 个字节），以及链接指向的内容（名为 file 的文件）。
1 | prompt> ls -al |
1 | prompt> echo hello > file |
符号链接与硬链接完全不同，删除名为file的原始文件会导致符号链接指向不再存在的路径名。
创建并挂载文件系统
如何从许多底层文件系统组建完整的目录树。这项任务的实现是先制作文件系统，然后挂载它们，使其内容可以访问。
为了创建一个文件系统，大多数文件系统提供了一个工具，通常名为mkfs（发音为“make fs”），它就是完成这个任务的。思路如下：作为输入，为该工具提供一个设备（例如磁盘分区，例如/dev/sda1），一种文件系统类型（例如ext3），它就在该磁盘分区上写入一个空文件系统，从根目录开始。mkfs说，要有文件系统！
但是，一旦创建了这样的文件系统，就需要在统一的文件系统树中进行访问。这个任务是通过mount程序实现的（它使底层系统调用mount()完成实际工作）。mount的作用很简单：以现有目录作为目标挂载点（mount point），本质上是将新的文件系统粘贴到目录树的这个点上。
因此mount的美妙之处在于：它将所有文件系统统一到一棵树中，而不是拥有多个独立的文件系统，这让命名统一而且方便。
要查看系统上挂载的内容，以及在哪些位置挂载，只要运行mount程序。你会看到类似下面的内容：
1 | /dev/sda1 on / type ext3 (rw) |
文件系统实现
VSFS（Very Simple File System，简单文件系统）。它是典型UNIX文件系统的简化版本，用于介绍一些基本磁盘结构、访问方法和各种策略。
文件系统是纯软件。与CPU和内存虚拟化的开发不同，我们不会添加硬件功能来使文件系统的某些方面更好地工作。
思考方式
考虑文件系统时，考虑它们的两个不同方面。
第一个方面是文件系统的数据结构（data structure）。文件系统在磁盘上使用哪些类型的结构来组织其数据和元数据？我们即将看到的第一个文件系统（包括下面的VSFS）使用简单的结构，如块或其他对象的数组，而更复杂的文件系统（如SGI的XFS）使用更复杂的基于树的结构。
文件系统的第二个方面是访问方法（access method）。如何将进程发出的调用，如open()、read()、write()等，映射到它的结构上？在执行特定系统调用期间读取哪些结构？改写哪些结构？所有这些步骤的执行效率如何？
整体组织
VSFS文件系统在磁盘上的数据结构的整体组织。我们需要做的第一件事是将磁盘分成块（block）。简单的文件系统只使用一种块大小，这里正是这样做的。我们选择常用的4KB。
我们对构建文件系统的磁盘分区的看法很简单：一系列块，每块大小为4KB。在大小为N个4KB块的分区中，这些块的地址为从0到N−1。假设我们有一个非常小的磁盘，只有64块。
实际上，任何文件系统中的大多数空间都是（并且应该是）用户数据。我们将用于存放用户数据的磁盘区域称为数据区域（data region），简单起见，将磁盘的固定部分留给这些块，例如磁盘上64个块的最后56个：
文件系统必须记录每个文件的信息。该信息是元数据（metadata）的关键部分，并且记录诸如文件包含哪些数据块（在数据区域中）、文件的大小，其所有者和访问权限、访问和修改时间以及其他类似信息的事情。
为了存储这些信息，文件系统通常有一个名为inode的结构。为了存放inode，我们还需要在磁盘上留出一些空间。我们将这部分磁盘称为inode表（inode table），它只是保存了一个磁盘上inode的数组。因此，假设我们将64个块中的5块用于inode，磁盘映像现在看起来如下：
还需要某种方法来记录inode或数据块是空闲还是已分配。因此，这种分配结构（allocation structure）是所有文件系统中必需的部分。
我们可以用一个空闲列表（free list），指向第一个空闲块，然后它又指向下一个空闲块，依此类推。我们选择一种简单而流行的结构，称为位图（bitmap），一种用于数据区域（数据位图，data bitmap），另一种用于inode表（inode位图，inode bitmap）。位图是一种简单的结构：每个位用于指示相应的对象/块是空闲（0）还是正在使用（1）。因此新的磁盘布局如下，包含inode位图（i）和数据位图（d）：
在极简文件系统的磁盘结构设计中，还有一块。我们将它保留给超级块（superblock），在下图中用S表示。超级块包含关于该特定文件系统的信息，包括例如文件系统中有多少个inode和数据块（在这个例子中分别为80和56）、inode表的开始位置（块3）等等。它可能还包括一些幻数，来标识文件系统类型（在本例中为VSFS）
因此，在挂载文件系统时，操作系统将首先读取超级块，初始化各种参数，然后将该卷添加到文件系统树中。当卷中的文件被访问时，系统就会知道在哪里查找所需的磁盘上的结构。
文件组织：inode
文件系统最重要的磁盘结构之一是inode，几乎所有的文件系统都有类似的结构。名称inode是index node（索引节点）的缩写，它是由UNIX开发人员Ken Thompson [RT74]给出的历史性名称，因为这些节点最初放在一个数组中，在访问特定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区域的偏移量（32×inode的大小，即8192），将它加上磁盘inode表的起始地址（inodeStartAddr = 12KB），从而得到希望的inode块的正确字节地址：20KB。
在每个inode中，实际上是所有关于文件的信息：文件类型（例如，常规文件、目录等）、大小、分配给它的块数、保护信息（如谁拥有该文件以及谁可以访问它）、一些时间信息（包括文件创建、修改或上次访问的时间文件下），以及有关其数据块驻留在磁盘上的位置的信息（如某种类型的指针）。我们将所有关于文件的信息称为元数据（metadata）。实际上，文件系统中除了纯粹的用户数据外，其他任何信息通常都称为元数据。
多级索引
为了支持更大的文件，文件系统设计者必须在inode中引入不同的结构。一个常见的思路是有一个称为间接指针（indirect pointer）的特殊指针。它不是指向包含用户数据的块，而是指向包含更多指针的块，每个指针指向用户数据。因此，inode可以有一些固定数量（例如 12个）的直接指针和一个间接指针。如果文件变得足够大，则会分配一个间接块（来自磁盘的数据块区域），并将inode的间接指针设置为指向它。假设一个块是4KB，磁盘地址是4字节，那就增加了1024个指针。文件可以增长到（12 + 1024）×4KB，即4144KB。
这种不平衡树被称为指向文件块的多级索引（multi-level index）方法。我们来看一个例子，它有12个直接指针，以及一个间接块和一个双重间接块。假设块大小为4KB，并且指针为4字节，则该结构可以容纳一个刚好超过4GB的文件，即（12 + 1024 + 10242）×4KB。
目录组织
在VSFS中（像许多文件系统一样），目录的组织很简单。一个目录基本上只包含一个二元组（条目名称，inode号）的列表。对于给定目录中的每个文件或目录，目录的数据块中都有一个字符串和一个数字。
删除一个文件（例如调用unlink()）会在目录中间留下一段空白空间，因此应该有一些方法来标记它（例如，用一个保留的inode号，比如0）。这种删除是使用记录长度的一个原因：新条目可能会重复使用旧的、更大的条目，从而在其中留有额外的空间。
通常，文件系统将目录视为特殊类型的文件。因此，目录有一个inode，位于inode表中的某处（inode表中的inode标记为“目录”的类型字段，而不是“常规文件”）。该目录具有由inode指向的数据块（也可能是间接块）。这些数据块存在于我们的简单文件系统的数据块区域中。我们的磁盘结构因此保持不变。
空闲空间管理
文件系统必须记录哪些inode和数据块是空闲的，哪些不是，这样在分配新文件或目录时，就可以为它找到空间。因此，空闲空间管理（free space management）对于所有文件系统都很重要。在VSFS中，我们用两个简单的位图来完成这个任务。
例如，当我们创建一个文件时，我们必须为该文件分配一个inode。文件系统将通过位图搜索一个空闲的内容，并将其分配给该文件。文件系统必须将inode标记为已使用（用1），并最终用正确的信息更新磁盘上的位图。分配数据块时会发生类似的一组活动。
访问路径：读取和写入
我们假设文件系统已经挂载，因此超级块已经在内存中。其他所有内容（如inode、目录）仍在磁盘上。
从磁盘读取文件
想打开一个文件（例如/foo/bar，读取它，然后关闭它）。对于这个简单的例子，假设文件的大小只有4KB（即1块）。
当你发出一个open(“/foo/bar”, O_RDONLY)调用时，文件系统首先需要找到文件bar的inode，从而获取关于该文件的一些基本信息（权限信息、文件大小等等）,必须能够找到inode，但它现在只有完整的路径名。文件系统必须遍历（traverse）路径名，从而找到所需的inode。
所有遍历都从文件系统的根开始，即根目录（root directory），它就记为/。因此，文件系统的第一次磁盘读取是根目录的inode。但是这个inode在哪里？要找到inode，我们必须知道它的i-number。通常，我们在其父目录中找到文件或目录的i-number。根没有父目录（根据定义）。因此，根的inode号必须是“众所周知的”。在挂载文件系统时，文件系统必须知道它是什么。在大多数UNIX文件系统中，根的inode号为2。因此，要开始该过程，文件系统会读入inode号2的块（第一个inode块）。
一旦inode被读入，文件系统可以在其中查找指向数据块的指针，数据块包含根目录的内容。因此，文件系统将使用这些磁盘上的指针来读取目录，在这个例子中，寻找foo的条目。通过读入一个或多个目录数据块，它将找到foo的条目。一旦找到，文件系统也会找到下一个需要的foo的inode号（假定是44）。
下一步是递归遍历路径名，直到找到所需的inode。在这个例子中，文件系统读取包含foo的inode及其目录数据的块，最后找到bar的inode号。open()的最后一步是将bar的inode读入内存。然后文件系统进行最后的权限检查，在每个进程的打开文件表中，为此进程分配一个文件描述符，并将它返回给用户。
打开后，程序可以发出read()系统调用，从文件中读取。第一次读取（除非lseek()已被调用，则在偏移量0处）将在文件的第一个块中读取，查阅inode以查找这个块的位置。它也会用新的最后访问时间更新inode。读取将进一步更新此文件描述符在内存中的打开文件表，更新文件偏移量，以便下一次读取会读取第二个文件块，等等。
写入磁盘
写入文件是一个类似的过程。首先，文件必须打开（如上所述）。其次，应用程序可以发出write()调用以用新内容更新文件。最后，关闭该文件。
要创建一个文件，文件系统不仅要分配一个inode，还要在包含新文件的目录中分配空间。这样做的I/O工作总量非常大：一个读取inode位图（查找空闲inode），一个写入inode位图（将其标记为已分配），一个写入新的inode本身（初始化它），一个写入目录的数据（将文件的高级名称链接到它的inode号），以及一个读写目录inode以便更新它。如果目录需要增长以容纳新条目，则还需要额外的I/O（即数据位图和新目录块）。所有这些只是为了创建一个文件！
缓存和缓冲
读取和写入文件可能是昂贵的，会导致（慢速）磁盘的许多I/O。这显然是一个巨大的性能问题，为了弥补，大多数文件系统积极使用系统内存（DRAM）来缓存重要的块。
早期的文件系统因此引入了一个固定大小的缓存（fixed-size cache）来保存常用的块。正如我们在讨论虚拟内存时一样，LRU及不同变体策略会决定哪些块保留在缓存中。
现代系统采用动态划分（dynamic partitioning）方法。具体来说，许多现代操作系统将虚拟内存页面和文件系统页面集成到统一页面缓存中（unified page cache）[S00]。通过这种方式，可以在虚拟内存和文件系统之间更灵活地分配内存，具体取决于在给定时间哪种内存需要更多的内存。
局部性和快速文件系统
当UNIX操作系统首次引入时，Ken Thompson编写了第一个文件系统。我们称之为“老UNIX文件系统”，它非常简单，基本上，它的数据结构在磁盘上看起来像这样：
超级块（S）包含有关整个文件系统的信息：卷的大小、有多少inode、指向空闲列表块的头部的指针等等。磁盘的inode区域包含文件系统的所有inode。最后，大部分磁盘都被数据块占用。
老文件系统的好处在于它很简单，支持文件系统试图提供的基本抽象：文件和目录层次结构。
问题：性能不佳
老UNIX文件系统将磁盘当成随机存取内存。 数据遍布各处，而不考虑保存数据的介质是磁盘的事实.
例如，文件的数据块通常离其inode非常远，因此每当第一次读取inode然后读取文件的数据块（非常常见的操作）时，就会导致昂贵的寻道。
更糟糕的是，文件系统最终会变得非常碎片化（fragmented），因为空闲空间没有得到精心管理。空闲列表最终会指向遍布磁盘的一堆块，并且随着文件的分配，它们只会占用下一个空闲块。结果是在磁盘上来回访问逻辑上连续的文件，从而大大降低了性能。
例如
假设以下数据块区域包含4个文件（A、B、C和D），每个文件大小为两个块：
如果删除B和D，则生成的布局为：
如你所见，可用空间被分成两块构成的两大块，而不是很好的连续4块。假设我们现在希望分配一个大小为4块的文件E：
E分散在磁盘上，因此，在访问E时，无法从磁盘获得峰值（顺序）性能。你首先读取E1和E2，然后寻道，再读取E3和E4。这个碎片问题一直发生在老UNIX文件系统中，并且会影响性能。
这个问题正是磁盘碎片整理工具要解决的。它们将重新组织磁盘数据以连续放置文件，并为让空闲空间成为一个或几个连续的区域，移动数据，然后重写inode等以反映变化。
另一个问题：原始块大小太小（512字节）。因此，从磁盘传输数据本质上是低效的。较小的块是好的，因为它们最大限度地减少了内部碎片（internal fragmentation，块内的浪费），但是由于每个块可能需要一个定位开销来访问它，因此传输不佳。
快速文件系统（Fast File System，FFS）：磁盘意识是解决方案
组织结构：柱面组
第一步是更改磁盘上的结构。FFS将磁盘划分为一些分组，称为柱面组（cylinder group，而一些现代文件系统，如Linux ext2和ext3，就称它们为块组，即block group）。因此，我们可以想象一个具有10个柱面组的磁盘：
这些分组是FFS用于改善性能的核心机制。通过在同一组中放置两个文件，FFS可以确保先后访问两个文件不会导致穿越磁盘的长时间寻道。
因此，FFS需要能够在每个组中分配文件和目录。每个组看起来像这样：
出于可靠性原因，每个组中都有超级块（super block）的一个副本（例如，如果一个被损坏或划伤，你仍然可以通过使用其中一个副本来挂载和访问文件系统）。
在每个组中，我们需要记录该组的inode和数据块是否已分配。每组的inode位图（inode bitmap，ib）和数据位图（data bitmap，db）起到了这个作用，分别针对每组中的inode和数据块。位图是管理文件系统中可用空间的绝佳方法，因为很容易找到大块可用空间并将其分配给文件，这可能会避免旧文件系统中空闲列表的某些碎片问题。
最后，inode和数据块区域就像之前的极简文件系统一样。像往常一样，每个柱面组的大部分都包含数据块。
策略：如何分配文件和目录
相关的东西放一起
首先是目录的放置。FFS采用了一种简单的方法：找到分配数量少的柱面组（因为我们希望跨组平衡目录）和大量的自由inode（因为我们希望随后能够分配一堆文件），并将目录数据和inode放在该分组中。
对于文件，FFS做两件事。首先，它确保（在一般情况下）将文件的数据块分配到与其inode相同的组中，从而防止inode和数据之间的长时间寻道（如在老文件系统中）。其次，它将位于同一目录中的所有文件，放在它们所在目录的柱面组中。因此，如果用户创建了4个文件，/dir1/1.txt、/dir1/2.txt、/dir1/3.txt和/dir99/4.txt，FFS会尝试将前3个放在一起（同一组），与第四个远离（它在另外某个组中）。
测量文件的局部性
大文件例外
在FFS中，文件放置的一般策略有一个重要的例外，它出现在大文件中。如果没有不同的规则，大文件将填满它首先放入的块组（也可能填满其他组）。以这种方式填充块组是不符合需要的，因为它妨碍了随后的“相关”文件放置在该块组内，因此可能破坏文件访问的局部性。
因此，对于大文件，FFS执行以下操作。在将一定数量的块分配到第一个块组（例如，12个块，或inode中可用的直接指针的数量）之后，FFS将文件的下一个“大”块（即第一个间接块指向的那些部分）放在另一个块组中（可能因为它的利用率低而选择）。然后，文件的下一个块放在另一个不同的块组中，依此类推。
让我们看一些图片，更好地理解这个策略。如果没有大文件例外，单个大文件会将其所有块放入磁盘的一部分。我们使用一个包含10个块的文件的小例子，来直观地说明该行为。
FFS没有大文件例外时的图景：
有了大文件例外，我们可能会看到像这样的情形，文件以大块的形式分布在磁盘上：
关于 FFS 的其他几件事
当时许多文件大小为2KB左右，使用4KB块虽然有利于传输数据，但空间效率却不太好。因此，在典型的文件系统上，这种内部碎片（internal fragmentation）可能导致大约一半的磁盘浪费。
FFS设计人员采用很简单的解决方案解决了这个问题。他们决定引入子块（sub-block），这些子块有512字节，文件系统可以将它们分配给文件。因此，如果你创建了一个小文件（比如大小为1KB），它将占用两个子块，因此不会浪费整个4KB块。随着文件的增长，文件系统将继续为其分配512字节的子块，直到它达到完整的4KB数据。此时，FFS将找到一个4KB块，将子块复制到其中，并释放子块以备将来使用。
崩溃一致性：FSCK和日志
文件系统管理一组数据结构以实现预期的抽象：文件、目录，以及所有其他元数据，它们支持我们期望从文件系统获得的基本抽象。
文件系统面临的一个主要挑战在于，如何在出现断电（power loss）或系统崩溃（system crash）的情况下，更新持久数据结构。
一个详细的例子
先看一个例子。我们需要一种工作负载（workload），它以某种方式更新磁盘结构。这里假设工作负载很简单：将单个数据块附加到原有文件。通过打开文件，调用lseek()将文件偏移量移动到文件末尾，然后在关闭文件之前，向文件发出单个4KB写入来完成追加。
假定磁盘上使用标准的简单文件系统结构，类似于之前看到的文件系统。这个小例子包括一个inode位图（inode bitmap，只有8位，每个inode一个），一个数据位图（data bitmap，也是8位，每个数据块一个），inode（总共8个，编号为0到7，分布在4个块上），以及数据块（总共8个，编号为0～7）。以下是该文件系统的示意图：
查看图中的结构，可以看到分配了一个inode（inode号为2），它在inode位图中标记，单个分配的数据块（数据块4）也在数据中标记位图。inode表示为I [v1]，因为它是此inode的第一个版本。它将很快更新（由于上述工作负载）。
再来看看这个简化的inode。
在这个简化的inode中，文件的大小为1（它有一个块位于其中），第一个直接指针指向块4（文件的第一个数据块，Da），并且所有其他3个直接指针都被设置为null（表示它们未被使用）。当然，真正的inode有更多的字段。
向文件追加内容时，要向它添加一个新数据块，因此必须更新3个磁盘上的结构：inode（必须指向新块，并且由于追加而具有更大的大小），新数据块Db和新版本的数据位图（称之为B[v2]）表示新数据块已被分配。
更新的数据位图（B[v2]）现在看起来像这样：00001100。最后，有数据块（Db），它只是用户放入文件的内容。我们希望文件系统的最终磁盘映像如下所示：
要实现这种转变，文件系统必须对磁盘执行3次单独写入，分别针对inode（I[v2]），位图（B[v2]）和数据块（Db）。请注意，当用户发出write()系统调用时，这些写操作通常不会立即发生。脏的inode、位图和新数据先在内存（页面缓存，page cache，或缓冲区缓存，buffer cache）中存在一段时间。然后，当文件系统最终决定将它们写入磁盘时（比如说5s或30s），文件系统将向磁盘发出必要的写入请求。遗憾的是，可能会发生崩溃，从而干扰磁盘的这些更新。特别是，如果这些写入中的一个或两个完成后发生崩溃，而不是全部 3个，则文件系统可能处于有趣的状态。
崩溃场景
只将数据块（Db）写入磁盘。在这种情况下，数据在磁盘上，但是没有指向它的inode，也没有表示块已分配的位图。因此，就好像写入从未发生过一样。从文件系统崩溃一致性的角度来看，这种情况根本不是问题①。
只有更新的inode（I[v2]）写入了磁盘。在这种情况下，inode指向磁盘地址（5），其中Db即将写入，但Db尚未写入。因此，如果我们信任该指针，我们将从磁盘读取垃圾数据（磁盘地址5的旧内容）。
遇到了一个新问题，我们将它称为文件系统不一致（file-system inconsistency）。磁盘上的位图告诉我们数据块5尚未分配，但是inode说它已经分配了。文件系统数据结构中的这种不同意见，是文件系统的数据结构不一致。要使用文件系统，我们必须以某种方式解决这个问题。
- 只有更新后的位图（B [v2]）写入了磁盘。在这种情况下，位图指示已分配块5，但没有指向它的inode。因此文件系统再次不一致。如果不解决，这种写入将导致空间泄露（space leak），因为文件系统永远不会使用块5。
在这个向磁盘写入3次的尝试中，还有3种崩溃场景。在这些情况下，两次写入成功，最后一次失败。
inode（I[v2]）和位图（B[v2]）写入了磁盘，但没有写入数据（Db）。在这种情况下，文件系统元数据是完全一致的：inode有一个指向块5的指针，位图指示5正在使用，因此从文件系统的元数据的角度来看，一切看起来都很正常。但是有一个问题：5中又是垃圾。
写入了inode（I[v2]）和数据块（Db），但没有写入位图（B[v2]）。在这种情况下，inode指向了磁盘上的正确数据，但同样在inode和位图（B1）的旧版本之间存在不一致。因此，我们在使用文件系统之前，又需要解决问题。
写入了位图（B[v2]）和数据块（Db），但没有写入inode（I[v2]）。在这种情况下，inode和数据位图之间再次存在不一致。但是，即使写入块并且位图指示其使用，我们也不知道它属于哪个文件，因为没有inode指向该块。
解决方案 1：文件系统检查程序
早期的文件系统采用了一种简单的方法来处理崩溃一致性。基本上，它们决定让不一致的事情发生，然后再修复它们（重启时）。这种偷懒方法的典型例子可以在一个工具中找到：fsck①。fsck是一个UNIX工具，用于查找这些不一致并修复它们[M86]。
它在文件系统挂载并可用之前运行（fsck假定在运行时没有其他文件系统活动正在进行）。一旦完成，磁盘上的文件系统应该是一致的，因此可以让用户访问。
超级块：fsck首先检查超级块是否合理，主要是进行健全性检查，例如确保文件系统大小大于分配的块数。通常，这些健全性检查的目的是找到一个可疑的（冲突的）超级块。在这种情况下，系统（或管理员）可以决定使用超级块的备用副本。
空闲块：接下来，fsck扫描inode、间接块、双重间接块等，以了解当前在文件系统中分配的块。它利用这些知识生成正确版本的分配位图。因此，如果位图和inode之间存在任何不一致，则通过信任inode内的信息来解决它。对所有inode执行相同类型的检查，确保所有看起来像在用的inode，都在inode位图中有标记。
inode状态：检查每个inode是否存在损坏或其他问题。例如，fsck确保每个分配的inode具有有效的类型字段（即常规文件、目录、符号链接等）。如果inode字段存在问题，不易修复，则inode被认为是可疑的，并被fsck清除，inode位图相应地更新。
fsck还会验证每个已分配的inode的链接数。你可能还记得，链接计数表示包含此特定文件的引用（即链接）的不同目录的数量。为了验证链接计数，fsck从根目录开始扫描整个目录树，并为文件系统中的每个文件和目录构建自己的链接计数。如果新计算的计数与inode中找到的计数不匹配，则必须采取纠正措施，通常是修复inode中的计数。如果发现已分配的inode但没有目录引用它，则会将其移动到lost + found目录。
重复：fsck还检查重复指针，即两个不同的inode引用同一个块的情况。如果一个inode明显不好，可能会被清除。或者，可以复制指向的块，从而根据需要为每个inode提供其自己的副本。
坏块：在扫描所有指针列表时，还会检查坏块指针。如果指针显然指向超出其有效范围的某个指针，则该指针被认为是“坏的”，例如，它的地址指向大于分区大小的块。在这种情况下，fsck不能做任何太聪明的事情。它只是从inode或间接块中删除（清除）该指针
目录检查：fsck不了解用户文件的内容。但是，目录包含由文件系统本身创建的特定格式的信息。因此，fsck对每个目录的内容执行额外的完整性检查，确保“.”和“..”是前面的条目，目录条目中引用的每个inode都已分配，并确保整个层次结构中没有目录的引用超过一次。
fsck（和类似的方法）有一个更大的、也许更根本的问题：它们太慢了。对于非常大的磁盘卷，扫描整个磁盘，以查找所有已分配的块并读取整个目录树，可能需要几分钟或几小时。
解决方案 2：日志（或预写日志）
基本思路如下。更新磁盘时，在覆写结构之前，首先写下一点小注记（在磁盘上的其他地方，在一个众所周知的位置），描述你将要做的事情。写下这个注记就是“预写”部分，我们把它写入一个结构，并组织成“日志”。因此，就有了预写日志。
通过将注释写入磁盘，可以保证在更新（覆写）正在更新的结构期间发生崩溃时，能够返回并查看你所做的注记，然后重试。因此，你会在崩溃后准确知道要修复的内容（以及如何修复它），而不必扫描整个磁盘。
现在将描述Linux ext3（一种流行的日志文件系统）如何将日志记录到文件系统中。大多数磁盘上的结构与Linux ext2相同，例如，磁盘被分成块组，每个块组都有一个inode和数据位图以及inode和数据块。新的关键结构是日志本身，它占用分区内或其他设备上的少量空间。因此，ext2文件系统（没有日志）看起来像这样：
假设日志放在同一个文件系统映像中（虽然有时将它放在单独的设备上，或作为文件系统中的文件），带有日志的ext3文件系统如下所示：
数据日志
假设再次进行标准的更新，我们再次希望将inode（I[v2]）、位图（B[v2]）和数据块（Db）写入磁盘。在将它们写入最终磁盘位置之前，现在先将它们写入日志。这就是日志中的样子：
事务开始（TxB）告诉我们有关此更新的信息，包括对文件系统即将进行的更新的相关信息（例如，块I[v2]、B[v2]和Db的最终地址），以及某种事务标识符（transaction identifier，TID）。中间的3个块只包含块本身的确切内容，这被称为物理日志（physical logging），因为我们将更新的确切物理内容放在日志中（另一种想法，逻辑日志（logical logging），在日志中放置更紧凑的更新逻辑表示，例如，“这次更新希望将数据块Db追加到文件X”，这有点复杂，但可以节省日志中的空间，并可能提高性能）。最后一个块（TxE）是该事务结束的标记，也会包含TID。
一旦这个事务安全地存在于磁盘上，我们就可以覆写文件系统中的旧结构了。这个过程称为加检查点（checkpointing）。因此，为了对文件系统加检查点（checkpoint，即让它与日志中即将进行的更新一致），我们将I[v2]、B[v2]和Db写入其磁盘位置，如上所示。如果这些写入成功完成，我们已成功地为文件系统加上了检查点，基本上完成了。因此，我们的初始操作顺序如下。
日志写入：将事务（包括事务开始块，所有即将写入的数据和元数据更新以及事务结束块）写入日志，等待这些写入完成。
加检查点：将待处理的元数据和数据更新写入文件系统中的最终位置。
在我们的例子中，先将TxB、I[v2]、B[v2]、Db和TxE写入日志。这些写入完成后，我们将加检查点，将I[v2]、B[v2]和Db写入磁盘上的最终位置，完成更新。
在写入日志期间发生崩溃时，事情变得有点棘手。
为避免该问题，文件系统分两步发出事务写入。首先，它将除TxE块之外的所有块写入日志，同时发出这些写入。当这些写入完成时，日志将看起来像这样（假设又是文件追加的工作负载）：
当这些写入完成时，文件系统会发出TxE块的写入，从而使日志处于最终的安全状态：
此过程的一个重要方面是磁盘提供的原子性保证。事实证明，磁盘保证任何512字节写入都会发生或不发生（永远不会半写）。因此，为了确保TxE的写入是原子的，应该使它成为一个512字节的块。因此，我们当前更新文件系统的协议如下，3个阶段中的每一个都标上了名称。
- 日志写入：将事务的内容（包括TxB、元数据和数据）写入日志，等待这些写入完成。
- 日志提交：将事务提交块（包括TxE）写入日志，等待写完成，事务被认为已提交（committed）。
- 加检查点：将更新内容（元数据和数据）写入其最终的磁盘位置。
恢复
如果崩溃发生在事务被安全地写入日志之前（在上面的步骤2完成之前），那么我们的工作很简单：简单地跳过待执行的更新。如果在事务已提交到日志之后但在加检查点完成之前发生崩溃，则文件系统可以按如下方式恢复（recover）更新。系统引导时，文件系统恢复过程将扫描日志，并查找已提交到磁盘的事务。然后，这些事务被重放（replayed，按顺序），文件系统再次尝试将事务中的块写入它们最终的磁盘位置。
批处理日志更新
为了解决这个问题，一些文件系统不会一次一个地向磁盘提交每个更新（例如，Linux ext3）。与此不同，可以将所有更新缓冲到全局事务中。在上面的示例中，当创建两个文件时，文件系统只将内存中的inode位图、文件的inode、目录数据和目录inode标记为脏，并将它们添加到块列表中，形成当前的事务。当最后应该将这些块写入磁盘时（例如，在超时5s之后），会提交包含上述所有更新的单个全局事务。因此，通过缓冲更新，文件系统在许多情况下可以避免对磁盘的过多的写入流量。
使日志有限
日志的大小有限。如果不断向它添加事务（如下所示），它将很快填满。
日志越大，恢复时间越长，因为恢复过程必须重放日志中的所有事务（按顺序）才能恢复。第二个问题更重要：当日志已满（或接近满）时，不能向磁盘提交进一步的事务，从而使文件系统“不太有用”（即无用）。
日志文件系统将日志视为循环数据结构，一遍又一遍地重复使用。
1．日志写入：将事务的内容（包括TxB和更新内容）写入日志，等待这些写入完成。2．日志提交：将事务提交块（包括TxE）写入日志，等待写完成，事务被认为已提交（committed）。3．加检查点：将更新内容写入其最终的磁盘位置。4．释放：一段时间后，通过更新日志超级块，在日志中标记该事务为空闲。
补充：优化日志写入
写入日志的效率特别低。也就是说，文件系统首先必须写出事务开始块和事务的内容。只有在这些写入完成后，文件系统才能将事务结束块发送到磁盘。
将事务写入日志时，在开始和结束块中包含日志内容的校验和。这样做可以使文件系统立即写入整个事务，而不会产生等待。如果在恢复期间，文件系统发现计算的校验和与事务中存储的校验和不匹配，则可以断定在写入事务期间发生了崩溃，从而丢弃了文件系统更新。因此，通过写入协议和恢复系统中的小调整，文件系统可以实现更快的通用情况性能。最重要的是，系统更可靠了，因为来自日志的任何读取现在都受到校验和的保护。
元数据日志
我们上面描述的日志模式通常称为数据日志（data journaling，如在Linux ext3中），因为它记录了所有用户数据（除了文件系统的元数据之外）。一种更简单（也更常见）的日志形式有时称为有序日志（ordered journaling，或称为元数据日志，metadata journaling）它几乎相同，只是用户数据没有写入日志。
1．数据写入：将数据写入最终位置，等待完成（等待是可选的，详见下文）。
2．日志元数据写入：将开始块和元数据写入日志，等待写入完成。
3．日志提交：将事务提交块（包括TxE）写入日志，等待写完成，现在认为事务（包括数据）已提交（committed）。
4．加检查点元数据：将元数据更新的内容写入文件系统中的最终位置。
5．释放：稍后，在日志超级块中将事务标记为空闲。
棘手的情况：块复用
假设你有一个名为foo的目录。用户向foo添加一个条目（例如通过创建文件），因此foo的内容（因为目录被认为是元数据）被写入日志。假设foo目录数据的位置是块1000。因此日志包含如下内容：
此时，用户删除目录中的所有内容以及目录本身，从而释放块1000以供复用。最后，用户创建了一个新文件（比如foobar），结果复用了过去属于foo的相同块（1000）。foobar的inode提交给磁盘，其数据也是如此。但是，请注意，因为正在使用元数据日志，所以只有foobar的inode被提交给日志，文件foobar中块1000中新写入的数据没有写入日志。
现在假设发生了崩溃，所有这些信息仍然在日志中。在重放期间，恢复过程简单地重放日志中的所有内容，包括在块1000中写入目录数据。因此，重放会用旧目录内容覆盖当前文件foobar的用户数据！
总结日志：时间线
日志结构文件系统
LFS永远不会覆写现有数据，而是始终将段写入空闲位置。由于段很大，因此可以有效地使用磁盘，并且文件系统的性能接近其峰值。
按顺序写入磁盘
我们正在将数据块D写入文件。将数据块写入磁盘可能会导致以下磁盘布局，其中D写在磁盘地址A0：
但是，当用户写入数据块时，不仅是数据被写入磁盘；还有其他需要更新的元数据（metadata）。在这个例子中，让我们将文件的inode（I）也写入磁盘，并将其指向数据块D。写入磁盘时，数据块和inode看起来像这样（注意inode看起来和数据块一样大，但通常情况并非如此。在大多数系统中，数据块大小为4KB，而inode小得多，大约128B）
顺序而高效地写入
例如，假设我们在时间T向地址A写入一个块。然后等待一会儿，再向磁盘写入地址A+1（下一个块地址按顺序），但是在时间T+δ。遗憾的是，在第一次和第二次写入之间，磁盘已经旋转。
实际上，你必须向驱动器发出大量连续写入（或一次大写入）才能获得良好的写入性能。
为了达到这个目的，LFS使用了一种称为写入缓冲①（write buffering）的古老技术。在写入磁盘之前，LFS会跟踪内存中的更新。收到足够数量的更新时，会立即将它们写入磁盘，从而确保有效使用磁盘。
LFS一次写入的大块更新被称为段（segment）。
下面是一个例子，其中LFS将两组更新缓冲到一个小段中。实际段更大（几MB）。第一次更新是对文件j的4次块写入，第二次是添加到文件k的一个块。然后，LFS立即将整个七个块的段提交到磁盘。这些块的磁盘布局如下：
要缓冲多少
取决于磁盘本身，特别是与传输速率相比定位开销有多高。
问题：查找 inode
老UNIX文件系统将所有inode保存在磁盘的固定位置。因此，给定一个inode号和起始地址，要查很特定的inode，只需将inode号乘以inode的大小，然后将其加上磁盘数组的起始地址，即可计算其确切的磁盘地址。给定一个inode号，基于数组的索引是快速而直接的。因为它们以数组形式组织，并放在磁盘的固定位置上。
在FFS中查很给定inode号的inode仅稍微复杂一些，因为FFS将inode表拆分为块并在每个柱面组中放置一组inode。因此，必须知道每个inode块的大小和每个inode的起始地址。
我们已经设法将inode分散在整个磁盘上！更糟糕的是，我们永远不会覆盖，因此最新版本的inode（即我们想要的那个）会不断移动。
通过间接解决方案：inode 映射
为了解决这个问题，LFS的设计者通过名为inode映射（inode map，imap）的数据结构，在inode号和inode之间引入了一个间接层（level of indirection）。imap是一个结构，它将inode号作为输入，并生成最新版本的inode的磁盘地址。因此，你可以想象它通常被实现为一个简单的数组，每个条目有4个字节（一个磁盘指针）。每次将inode写入磁盘时，imap都会使用其新位置进行更新。
LFS将inode映射的块放在它写入所有其他新信息的位置旁边。因此，当将数据块追加到文件k时，LFS实际上将新数据块，其inode和一段inode映射一起写入磁盘
在该图中，imap数组存储在标记为imap的块中，它告诉LFS，inode k位于磁盘地址A1。接下来，这个inode告诉LFS它的数据块D在地址A0。
检查点区域
LFS在磁盘上只有这样一个固定的位置，称为检查点区域（checkpoint region，CR）。检查点区域包含指向最新的inode映射片段的指针（即地址），因此可以通过首先读取CR来很到inode映射片段。请注意，检查点区域仅定期更新（例如每30s左右），因此性能不会受到影响。因此，磁盘布局的整体结构包含一个检查点区域（指向内部映射的最新部分），每个inode映射块包含inode的地址，inode指向文件（和目录），就像典型的UNIX文件系统一样。
inode映射在LFS中的意义是将文件或目录与其对应的inode号码进行关联，通过inode号码可以快速访问文件或目录的元数据信息，从而实现文件系统的高效管理和访问。
下面的例子是检查点区域（注意它始终位于磁盘的开头，地址为0），以及单个imap块，inode和数据块。一个真正的文件系统当然会有一个更大的CR（事实上，它将有两个，我们稍后会理解），许多imap块，当然还有更多的inode、数据块等。
从磁盘读取文件：回顾
假设从内存中没有任何东西开始。我们必须读取的第一个磁盘数据结构是检查点区域。检查点区域包含指向整个inode映射的指针（磁盘地址），因此LFS读入整个inode映射并将其缓存在内存中。在此之后，当给定文件的inode号时，LFS只是在imap中查很inode号到inode磁盘地址的映射，并读入最新版本的inode。要从文件中读取块，此时，LFS完全按照典型的UNIX文件系统进行操作，方法是使用直接指针或间接指针或双重间接指针。在通常情况下，从磁盘读取文件时，LFS应执行与典型文件系统相同数量的I/O，整个imap被缓存，因此LFS在读取过程中所做的额外工作是在imap中查很inode的地址。
目录如何
目录结构与传统的UNIX文件系统基本相同，因为目录只是（名称，inode号）映射的集合。例如，在磁盘上创建文件时，LFS必须同时写入新的inode，一些数据，以及引用此文件的目录数据及其inode。请记住，LFS将在磁盘上按顺序写入（在缓冲更新一段时间后）。因此，在目录中创建文件foo，将导致磁盘上的以下新结构：
inode映射的片段包含目录文件dir以及新创建的文件f的位置信息。因此，访问文件foo（具有inode号f）时，你先要查看inode映射（通常缓存在内存中），很到目录dir（A3）的inode的位置。然后读取目录的inode，它给你目录数据的位置（A2）。读取此数据块为你提供名称到inode号的映射（foo，k）。然后再次查阅inode映射，很到inode号k（A1）的位置，最后在地址A0处读取所需的数据块。
一个新问题：垃圾收集
LFS会在整个磁盘中分散旧版本的文件结构。我们（毫不客气地）将这些旧版本称为垃圾（garbage）。
在图中，可以看到inode和数据块在磁盘上有两个版本，一个是旧的（左边那个），一个是当前的，因此是活的（live，右边那个）。对于覆盖数据块的简单行为，LFS必须持久许多新结构，从而在磁盘上留下上述块的旧版本。
另外举个例子，假设我们将一块添加到该原始文件k中。在这种情况下，会生成新版本的inode，但旧数据块仍由旧inode指向。因此，它仍然存在，并且与当前文件系统分离：
可以保留那些旧版本并允许用户恢复旧文件版本（例如，当他们意外覆盖或删除文件时，这样做可能非常方便）。这样的文件系统称为版本控制文件系统（versioning file system），因为它跟踪文件的不同版本。
但是，LFS只保留文件的最新活版本。
LFS清理程序定期读入许多旧的（部分使用的）段，确定哪些块在这些段中存在，然后写出一组新的段，只包含其中活着的块，从而释放旧块用于写入。具体来说，我们预期清理程序读取M个现有段，将其内容打包（compact）到N个新段（其中N < M），然后将N段写入磁盘的新位置。然后释放旧的M段，文件系统可以使用它们进行后续写入。
确定块的死活
对于每个数据块D，LFS包括其inode号（它属于哪个文件）及其偏移量（这是该文件的哪一块）。该信息记录在一个数据结构中，位于段头部，称为段摘要块（segment summary block）。
对于位于地址A的磁盘上的块D，查看段摘要块并很到其inode号N和偏移量T。接下来，查看imap以很到N所在的位置，并从磁盘读取N（可能它已经在内存中，这更好）。最后，利用偏移量T，查看inode（或某个间接块），看看inode认为此文件的第T个块在磁盘上的位置。如果它刚好指向磁盘地址A，则LFS可以断定块D是活的。如果它指向其他地方，LFS可以断定D未被使用（即它已经死了），因此知道不再需要该版本。
策略问题：要清理哪些块，何时清理
崩溃恢复和日志
为了确保CR更新以原子方式发生，LFS实际上保留了两个CR，每个位于磁盘的一端，并交替写入它们。当使用最新的指向inode映射和其他信息的指针更新CR时，LFS还实现了一个谨慎的协议。具体来说，它首先写出一个头（带有时间戳），然后写出CR的主体，然后最后写出最后一部分（也带有时间戳）。如果系统在CR更新期间崩溃，LFS可以通过查看一对不一致的时间戳来检测到这一点。LFS将始终选择使用具有一致时间戳的最新CR，从而实现CR的一致更新。
我们现在关注第一种情况。由于LFS每隔30s左右写入一次CR，因此文件系统的最后一致快照可能很旧。因此，在重新启动时，LFS可以通过简单地读取检查点区域、它指向的imap片段以及后续文件和目录，从而轻松地恢复。但是，最后许多秒的更新将会丢失。
数据完整性和保护
磁盘故障模式
在早期的RAID系统中，故障模型非常简单：要么整个磁盘都在工作，要么完全失败，而且检测到这种故障很简单。
具体来说，两种类型的单块故障是常见的，值得考虑：潜在扇区错误（Latent-Sector Errors，LSE）和块讹误（block corruption）
当磁盘扇区（或扇区组）以某种方式讹误时，会出现LSE。例如，如果磁头由于某种原因接触到表面（磁头碰撞，head crash，在正常操作期间不应发生的情况），则可能会讹误表面，使得数据位不可读。宇宙射线也会导致数据位翻转，使内容不正确。幸运的是，驱动器使用磁盘内纠错码（Error Correcting Code，ECC）来确定块中的磁盘位是否良好，并且在某些情况下，修复它们。如果它们不好，并且驱动器没有足够的信息来修复错误，则在发出请求读取它们时，磁盘会返回错误。
