操作系统复习-持久化部分

36. I/O Devices

input/output (I/O) device，显然是计算机必不可少的两个部分。

系统架构

CPU直接通过专用的内存总线和内存进行数据传输。另一些设备通过通用IO总线和系统交流，PCI就是其中的一部分（和显卡连接的，当然不止显卡）最后，也是最低级的就是一些周边设备的总线了，比如USB之类的与你的键盘、硬盘、鼠标等慢速设备进行连接。

注意，总线越快，那么就会越短，所以内存总线不能插太多.的设备。现在也有部分设备把内存和图形放到了同一个重要的层面上，大概长这样：

可以看到网络是通过PCIe进行连接的，所以速度很快。而图形和内存被直接与CPU进行连接，CPU还直接和一块io片通过DMI连接。

一个典型的设备

我们模拟一个设备，这个设备并不是真的。

可以看到一个设备主要分成了两个部分，上面代表了这个设备的“系统”，这部分被称为接口，是因为可以通过操控这个接口来控制整个设备。第二部分就是internal structure，这个相当于接口的实现部分，简单的设备就是一块物理芯片，而复杂一点的会包含一个简单的CPU。

一种典型的协议

还是上面的设备图，一个设备有状态寄存器，命令寄存器和数据寄存器，听名字就知道是干什么的了，操作系统只需要操作这三个寄存器，就能得到相应的结果。数据会在使用CPU的前提下，首先从内存到磁盘的寄存器中，然后磁盘会将寄存器中的值放到内部的盘面上。如果设备的CPU的时间被用来进等待数据从磁盘数据寄存器中，那么就叫做**programmed I/O (PIO)**。

一个简单的协议可能可以这么设计：

1. 不停判断设备是否是忙的，即轮询polling。
2. 如果设备不忙，就把数据写到data寄存器中。
3. 把命令写到command寄存器中，然后开始执行。
4. 继续等待，直到设备完成（可能成功也可能失败）。

这个协议看上去简单，而且也能工作，但是有很多问题：比如需要不停判断设备的状态，这样会导致CPU浪费。

通过中断

不是通过设备的轮询，而是通过让设备自己触发一个硬件中断，然后CPU就会跳转到操作系统指定好的interrupt handler中去，操作系统会执行相关的操作，比如唤醒一个进程去操作。

当然如果你的设备足够快，那么用轮询也是OK的。如果不确定设备的快慢，可以先轮询一会会，然后在使用中断。

在网络中也不建议使用，因为到达一个包就触发一次中断，可能会引起活锁：操作系统永远在处理中断反而没把精力花在处理数据上面了。

有一种优化就是合并，就是不要完成任务就去触发中断，而是稍微等一等，没准能和别的中断合并，减少系统负担。

DMA更有效的数据传输

如果需要将大量数据写入到磁盘中，也就是说需要CPU时间，把数据从内存搬动到设备中，对于大数据来说这部分时间还是很多的。

这个问题的解决办法是**Direct Memory Access (DMA)**，该设备对应的是芯片上的DMA控制器，它无需CPU过多的干预就可以在内存和设备之间传输消息。

还是上面的例子，CPU这次不是直接把数据从内存搬动到设备了，而是告诉DMA，数据放在内存哪里了，需要搬动多少，然后接下来就交给DMA去处理，DMA完成之后会触发中断告知已经完成。

设备通信

硬件该如何与设备进行通信呢？

有两种主流的方法

• 一种是显式的IO指令，该指令让OS把数据发送给设备寄存器，接下来就按照协议的内容操作。在x86上，通过in和out可以与设备进行交流。如果要发送数据给设备，那就指定好data寄存器已经对应的port，然后执行指令。当然这个指令是特权的，所以只有操作系统可以进行操作。
• 另外一种是通过memory- mapped I/O，内存映射IO。首先硬件把设备的寄存器映射成内存地址，那么OS只需要向内存写东西，就可以直接写到设备里取了。

这两种方式各有优缺点，而且目前仍然都在使用。

设备驱动

由于设备千千万，所以这里只能从大体上聊。我们如何才能使大多数OS设备保持中立，从而隐藏主要OS子系统中设备交互的详细信息？

答案就是抽象。在操作系统最低级层次中，有一个软件，叫做device driver，这个软件把和设备的交互细节全部封装在了里面，也就是操作系统通过它可以便利地操作硬件，而且这个驱动程序本身就是由硬件制造厂商提供的，所以能够充分发挥其作用。

举一个真正访问设备的例子。一个应用希望访问一个文件的内容，首先会产生一个read系统调用，然后通过文件系统，在到Generic Block Interface，然后是Generic Block Layer，再到Specific Block Interface，最后才是设备驱动。当然也可以不走文件系统，而是直接通过raw interface来访问。

一项研究表明，操作系统中70%的代码是设备驱动。

总结

在这一章中，对操作系统如何和设备进行交互有了基本的了解，具体讲了两种技术：DMA和中断，同样介绍两种方式去访问设备寄存器：指令和内存映射IO。最后还了解了一下设备驱动。

37. Hard Disk Drives

这一章中，了解一下硬盘是如何存储数据的，接口是什么。

接口

一个扇区是512字节，而硬盘有许许多多的这样的扇区，每个扇区都可以读和写。

大部分系统都是用页来作为基本单位的，也就是4K，但是硬盘只能保证对一个扇区（512字节）的读写是原子性的。

如果读取连续两块block（block和sector是等价的），那么速度会明显快于读取两块分开的block。顺序读是最快，而且远远快于随机读写。

基本结构

这个建议找个视频看看。

简单的硬盘

The Rotational Delay

就是虽然已经定位到了对应的一圈，但是还需要等待磁盘转到指定的位置才可以读写。

Seek Time

如果之前的磁道是错误的，还需要移动磁臂，移动到指定的磁道上面才可以。当然移动并没有想象中那么简单，因为需要什么加速减速啥的，涉及到一些物理的惯性之类的问题。

其它的细节

使用 track skew来保证就算跨越磁道，读取也是正确的。

第二点就是明显外部的扇区比内部的扇区多。

最后，一个重要的部分就是cache，也可以叫做track buffer，大概再8-16M之间。

在写入的时候，硬盘有一个选择：到底是等数据真正落到了磁道上之后，才报告完成呢，还是只要到了硬盘的内存中，就报告完成呢？

IO时间

T_I/O = T_seek + T_rotation + T_transfer ，这里给一个参考值：seek=4ms，rotation=2ms，transfer=0.03ms

显而易见嘛，需要先把磁头移动到磁道，然后要等待转到指定的扇区，最后还需要把数据写上去。

文中举了一个例子来说明，顺序读写的速度几乎是随机的200倍-300倍。

硬盘调度

之前在CPU虚拟化的时候提到过job scheduling，分成FIFO，SJF，RR等，而在磁盘这里有所不同，磁盘的job是可以预估出大概要花多少时间的，所以在这里，使用SJF是非常合适的。

SSTF: Shortest Seek Time First

该算法在早期的硬盘中很流行，核心思路就是根据磁头目前的位置，选择出最近的磁道，以最小化seek time。

但是也有弊端，首先是操作系统它并不知道硬盘的这个结构，所以操作系统实现了nearest-block-first (NBF)，即地址最接近的块优先。其次是第二个问题，饥饿。也就是我们只要解决了饥饿问题，这算法就非常的棒。

电梯算法（也叫SCAN）

我们把磁头从最外面到最里面（或者反向也可）称为一次sweep，如果有一个请求，并不会立即处理，而是在下一次sweep中处理。

这个就跟我们电梯一模一样，我从20楼坐电梯到1楼，当我达到3楼的时候，一个人进来了想要上去4楼，按了4。如果使用SSTF，那么就应该让它先，但是如果用电梯算法，我会先到1楼，然后才处理他的请求。

然而，这些算法其实都没有表现的很好，因为我们只考虑了seek time，而忽略了rotation time。

SPTF: Shortest Positioning Time First

和之前的页面置换算法中的那个完美算法一样，这个算法也是不现实的，只能说尽量逼近。

其它调度问题

在现代操作系统中，操作系统的调度器决定好request，然后交给磁盘，磁盘已经有能力自己来实现SPTF了。

另外一功能就是I/O merging，这一部分在OS中完成。

总结

我们了解了硬盘是如何工作的。

38. RAIDS

我们希望中的硬盘：快速，容量大，可靠。而RAID就是通过让多块硬盘共同工作，来完成这个任务的。

个人觉得raid这一章，其实是完全没必要写在操作系统中的，因为大部分人接触不到这个技术，需要的时候再拿出来翻翻看即可。

RAID接口

当文件系统产生一个逻辑IO的请求的时候，RAID内部则必须要计算出那个硬盘来完成这个request。raid其实甚至可以说是一个小型的系统，有CPU，有内存还有磁盘。

错误模型

raid被设计用来从错误中恢复，所以知道错误模型很有帮助。

第一种模型叫做fail-stop，磁盘要么是工作的，要么的坏的。而一旦坏了则是很容易检测到的。

剩下的模型等下介绍。

如何评估raid

我们从三个角度来陪你一股股，第一个是capacity，第二个是reliability，最后一个是performance。在接下来的内容中，我们认为一个block的大小是4K。

RAID0：striping

这其实压根不算是raid，因为根本没有redundancy。简单来说就是把多个硬盘合并成一个。把每个块按照磁盘分，比如0，4，8分给磁盘1，1，5，9分给磁盘2，以此类推。这个的好处是最大限度提高并行性。

RAID1：复制

在读取的时候可以任选其中一部分，但是写入的时候需要两个都写。

显然，从容量的角度来说，只有所有硬盘总和的一半（甚至更低，如果复制的多的话）。性能方面，读取性能和单硬盘的速度是一样的，在写入方面由于是并行写入的，所以速度也差不到哪里去，但是会略有下降（因为是取两者中比较差的那个）。

在多个硬盘中写入会遇到一个问题：内容更新不一致的问题，我们希望写入到两个硬盘中是原子性的，有一种办法能够解决：使用write-ahead log。

剩下的跳过

实际中暂时真的用不上。

39. Interlude: Files and Directories

操作系统如何操作这些可持久化设备，具体的API是什么呢，如何实现呢？

文件和目录

两个抽象：file和directory。

file其实就是一个字节数组，每个文件都有一个low-level name（不是文件名，而是inode number），directory其实和文件一样，也有low-level name（不是目录名字，而是inode number），只不过它里面的内容就是一堆（文件名-inode number）的pair，这样就可以堆砌出一棵树，树的根就是/，

创建文件

通过open这个系统调用就可以创建一个文件，该函数返回一个文件标识符，对于每个进程来说，唯一的一个整数。文件标识符是由操作系统来管理的，每个进程都有一个文件标识符的数组，标识了每个打开的文件。

读写文件

系统中读取一个文件最简单的命令应该就是cat了，然后我们还可以用strace来追踪命令执行过程中使用的系统调用并展示在屏幕上，所以可以用strace cat 文件：

这里只截取了部分重要的内容，可以看到首先最重要的是打开文件（只读模式），并且返回了文件描述符3。因为每个进程都有三个默认已经打开的文件，分别是标准输入0，标准输出1和标准错误2，所以只能从3开始了（大多数情况下是3）。

然后打开文件之后就可以用read读取了，可以看到第一个参数是3，就是用来指代那个文件，第二个参数指向了一个缓冲区buffer，该缓冲区用来存放结果，第三个是缓冲区的长度，上图中是128KB，返回值是6，说明真正的长度是6字节。

然后就是往文件描述符1写入内容，也就是在屏幕上打印。

然后紧接着又是一个读取，但是因为已经读完了，所以返回了0。最后就是关闭文件了。

不顺序读写

之前学习了如何把一个文件从头读到尾，这一部分学习读取文件的一部分。用到了另外一个系统调用——lseek。

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

第一个参数是文件描述符，第二个是偏移量，第三个指明了offset的含义：从头开始计算，从当前开始计算还是从尾开始计算。

从上面也不难推论出，对于进程打开的每个文件，操作系统都知道当前的位置，而lseek则是用来改变这个位置的系统调用。下面是操作系统对于文件的抽象：

struct file {
    int ref;
    char readable;
    char writable;
    struct inode *ip;
    uint off;
};

操作系统对于每个打开的文件（不管是不是同一个文件）都维护了一个结构，所以如果同时打开了一个文件两次，那么会有两个文件描述符，虽然都是指向相同的文件，但是offset是独立的。

同时操作系统整体维护了一个叫open file table的东西，其实就是file的数组，这东西可不是进程独享的，而是整个系统共享的。进程持有一个file数组，是该进程打开的文件描述符的集合，而操作系统则有open file table，是整个操作系统打开的文件描述符的集合。这两个数组都允许有相同的文件，即一个文件可以打开多次，在数组中创建多个。

fork和dup

之前说了，每个进程打开的文件都是各自独立的。那么当使用fork来创建子进程的时候呢？

仔细观察上面的file结构体，可以发现还有一个ref，说明有多少个引用。如果真的是进程之间完全独立，那么根本就不需要这个整数了。所以在父子进程之间，这个文件是共享的，而这是非常有用的。

除了fork之外，还有一个调用是dup，这个调用接受一个文件标识符作为参数，并且返回一个文件标识符。

系统调用——fsync

通常我们使用了write系统调用之后，操作系统为了效率考虑，不是马上写到硬盘上去，而是写到内存的一个buffer里去，然后过一会再写回到磁盘中。当使用fsync的时候就可以强行把数据写入到磁盘中。

然而事实上，你可能还需要把该文件对应的目录也强行刷一遍。

文件重命名

在Linux中，如果希望重命名一个文件，用的是mv指令‘；而mv指令底层用的是rename这一系统调用。这个系统调用很有意思，它（通常）是原子性的。

获取关于文件的信息

除了访问文件，我们希望文件系统能够存储关于文件的一些信息，即metadata，为了访问这些metadata，我们可以使用stat系统调用。而这些信息其实就是存储在inode中的。

删除文件

本质上是unlink系统调用，为什么不用delete或者是别的代表删除的词汇呢？这里可以暂且先放一放，看完后面的目录之后再决定。

创建目录

在Linux中，万物皆文件。但是目录也算是一个特殊的文件了，因为你不能直接在目录中写。这是因为需要保证目录数据的完整性，所以你不能直接修改目录的数据，只能通过间接的创建文件等方式来修改。

如果要创建目录，可以用mkdir命令，这同时也是一个系统调用，当一个目录创建完成之后，默认有两个目录，分别是.和..

读取目录

读取目录其实用的就是ls，和文件不同，读取目录的过程有三个系统调用，opendir，readdir和closedir。

下面是通过这三个系统调用实现的一个简易版ls：

#include <sys/types.h>  
#include <dirent.h>
#include <stdio.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("%lu %s\n", (unsigned long)d->d_ino, d->d_name);
    }
    closedir(dp);
    return 0;
}

删除目录

系统调用rmdir（Linux命令同名），这个调用必须确保目录是空的（只有.和..）才可以。

硬链接

现在我们来解决上面的问题，为什么删除是unlink呢。link的本质上其实就是创建对文件的一个引用而已。该引用具有和源文件相同的inode。

我们在创建文件的时候，其实做了两件事：首先是创建了一个inode，这个inode会存储文件的信息，包括大小，在磁盘中的block等等。其次就是把文件的名字link到文件，并且放到目录中。

如果只是link（系统命令ln）到一个文件的话，那么其实本质上只是在目录创建了一条inode和文件名的对应关系，同时对应的inode上面增加一个引用计数，几次而已。

当系统执行unlink的时候，会通过reference count来确认有多少个引用。它当然会断开指定的文件名和inode之间的联系，同时吧reference count减一，如果减完之后发现是0了，那么就会去硬盘中释放对应的Block的内容，此时真正把文件删除。

符号链接

硬链接不可以创建目录的复制（怕成环，比如一个子目录是祖父目录的硬链接，这样你可以永远cd下去，像du这类的统计磁盘空间的程序就会出问题，因为它会一直循环下去），不可以跨越文件系统（inode本身只在同一个文件系统中独一无二）。硬链接的本质，其实就是创建了一个文件名到inode的关系而已。

软链接的本质，其实是一个文件的绝对路径，通过它你可以找到真实的文件，所以路径越长，软连接的大小就越大。

Permission Bits And Access Control Lists

文件系统也抽象了磁盘，就如之前所述的文件和目录。但是和之前的CPU内存抽象不同，文件和目录是共享的，所以需要有一种机制来保护这些共享资源。

第一种就是permission bits，这块Linux都讲烂了，所以跳过先。这里稍微留意的就是：对于目录的执行权限，就是你能不能进入目录的意思。

对于目录来说，还有一个叫access control list (ACL)的东西。简单点说就是谁可以访问，谁不可以访问。

挂载文件系统

假设我们现在手头上有一个硬盘，然后需要写入文件系统，那么就需要使用mkfs命令，就可以写入文件系统了。

但是，一旦文件系统创建了，我们需要做的就是访问它，通过一棵统一的文件树来进行访问。通过mount系统调用可以完成，简单来讲就是把一个目标的挂载点，粘贴到原有的统一的文件树中。

我为什么需要挂载呢？我直接访问/dev/sda1不行吗？

不行，因为你不知道内容的格式，你必须指定相应的文件系统，才可以进行读取和写入。

总结

虽然这部分内容多又杂，但是细读一遍收获颇丰。

家庭作业

1. 自己实现一个stat：

   #include <stdio.h>
   #include <sys/stat.h>
   int main(int argc, char const *argv[], char *envp[])
   {
       struct stat mystat;
       if (argc != 2)
       {
           fprintf(stderr, "Usage: %s <pathname>\n", argv[0]);
           return -1;
       }
   
       if (stat(argv[1], &mystat) == -1)
       {
           perror("fatal error");
       }
   
       printf("inode = %ld\n", (long)mystat.st_ino);
       printf("link = %d\n",mystat.st_nlink);
   
       return 0;
   }

   就是通过一个系统调用把数据放到结构体里面，然后读取结构体里面的内容就可以知道对应的内容了，剩下的部分就。

2. 实现ls，并且实现对应的参数-l。其实这里主要是使用getopt这个函数来获取命令行参数，并且利用课上的demo进行扩写。

3. 实现tail命令。主要熟练使用lseek这个函数。

4. 实现一个递归的东西。

40. File System Implementation

在这一部分，我们实现一个简单的文件系统——vsfs (the Very Simple File System)。

思考方式

我们从两个方面来思考，首先是文件系统的数据结构。应该使用什么样的数据结构来组织数据和metadata。其次就是文件系统的访问方式，怎么把这些系统调用映射到这个数据结构呢？

整体思考

首先我们需要把硬盘分成blocks，那既然是一个简单的系统，我们就只用一种大小：4K（在我的Mac上和ubuntu上，默认的页大小也正好是4K，这样刚好一一对应）。有了block之后，我们需要知道我们在里面写些什么呢？用户的数据呗，这是自然的。我们把这部分称为data region。文件系统自然还要能够追踪这些用户数据，这部分信息叫做metadata，为了能够保存这些信息，我们需要一种叫inode的数据结构。我们把所有的inodes放到一起存放，并且放在一起叫做inode table。

现在有了用户数据存储区和一个inode table，之后我们需要一个数据结构来追踪，哪些数据存储区是空着的，哪些inode是可以使用的，这部分的数据结构的选择有很多，为了间接性，我们选择了bitmap，一个bitmap对应数据区，另外一个对应inode。

最后还需要一块superblock，来记录整个文件系统的信息。所以当挂载一个文件系统的时候，只需要读取它的superblock，就可以知道一些关键参数，并执行相对应的操作。

下面是一个简单的示意图：

Inode

inode其实是index node的缩写，每一个inode都有一个数字，叫做i-number。在文件系统中，只要给定一个i-number，就可以直接计算出inode位于硬盘的哪个位置。

上图是ext2文件系统的inode内容。这其中最重要的就是就是如何通过inode来找到数据块。最简单的实现就是在里面保存指针，指向真正的block，但是如果这么做，你的文件就不能很大了。

多层index

为了支持更大的文件，我们可以通过层次目录结构来解决。使用 indirect pointer，我不直接指向data block，而是指向另外一个block，这个block里面存放了很多直接pointer。

除了这个方法，还可以使用extents，即我只需要指定数据文件是从哪里开始的，长度多少就可以指定了，缺点么就是文件内容它必须在硬盘中是连续的。

甚至你还可以让data block组成一个链表。当然如果直接去遍历链表，效率是非常低的。于是在操作系统内存中有一个hashtable，key是数据块的地址，值则是下一个数据块的地址。这个思想就是著名的file allocation table（FAT）文件系统——Windows早期的文件系统。

目录组织

在目录中，就是一些pairs，每一个pair里面是文件名和Inode号。假设一个目录下有3个文件（不包含默认的两个），那么data block可能就长这样：

为什么需要reclen呢？因为当删除目录中的文件的时候，下一次可能会有新的文件到来，此时就需要这个字段。

空闲空间管理

之前提到过用到了两个bitmap，分别用来管理inode和data block。由于空闲空间是要分配给新的文件的，而顺序读取的速度远快于随机读取，所以最好能保证连续性。

访问路径

首先我们假设superblock已经放到内存里面了，其余的则全部还在硬盘里。

读文件

现在你要读取一个文件，第一步首先是找到它并且打开它。所以操作系统首先要找到对应的inode，然而目前只有superblock和文件的路径信息。所以不得不进行遍历。

所有的遍历肯定是从根路径开始的。我们如果要找到inode，必须先找到inumber，根据inumber可以直接计算出inode。但是这里有个循环的问题了，inumber需要首先找到它的父目录，父目录中才有对应的信息，但是根路径的父目录是谁？根路径没有父目录。所以在大多数系统中都规定了，根目录的inode是2。通过计算即可知道，inode是磁盘中的第一个inode block，所以去读取内容。

通过读取inode的内容，可以知道data block在哪里；通过读取data block，就可以知道里面存储了哪些文件以及文件的inode，然后就可以递归了查找了。

最终能够找到指定的文件，并且通过open系统调用把它的内容读取进内存中。然后文件系统还需要给这个进程分配一个文件描述符。有了文件描述符，就可以进行接下来的各项操作了。

写文件

首先文件必须被打开，这个过程上面有了，不在赘述。在写文件的时候，需要一个决定应该写到哪个block里面。所以写IO很麻烦：需要更新两个bitmap，需要读取和重写inode，还需要重写数据块。

如果是新建文件，除了上面的修改，还需要到对应的目录中进行修改。所以肯定需要有相应的优化措施。

Caching and Buffering

缓存和缓冲可以有效解决这些问题。

从上面的例子我们不难发现，访问任何一个文件都是从根目录下开始找的。早期的系统使用固定大小的cache来保存常用的Block，这部分大概会占用大约10%的内存。

现代的操作系统用的则是dynamic partitioning，把内存的虚拟页面和磁盘文件系统的block集成到统一的page cache中。这样就有了更大灵活性。

如果是写文件，那么使用的是write buffering，通首先，过延时，可以把一些工作聚集在一起做。其次，系统可以决定什么时候执行IO，得到最高的性能。最后，没准可以抵消（创建了文件但是转念一想不对又删除了）。

数据库系统除外，它们对数据正确性要求极高，所以一般就直接写到硬盘里了，甚至都不使用操作系统提供的文件系统，而是直接使用物理磁盘的接口。

总结

在这一章里我们见识了如何实现一个文件系统。

41. Locality and The Fast File System

结合上一章的vsfs，我们不难得出硬盘上的数据结构是这个样子的（漏掉了两个Bitmap）：

问题：性能低下

早期的操作系统把硬盘当成随机存取的设备使用，数据散落在磁盘各个角落，导致其性能极其低下，当然这个可以通过磁盘碎片整理工具来解决。另外一个问题是早期的block太小了，只有512字节。

柱面

首先我们来改善磁盘对应的数据结构。把磁盘分成柱面，然后把几个连续的柱面合成一个组。这些细节对于操作系统来说是透明的。在操作系统上，是把一个一个block组成 block groups。也就是物理上实际是柱面组，但是逻辑上是一个一个块组。逻辑上，我们只需要把两个文件放到同一个组（物理上就是放到同一个柱面组）里，就可以快速读取了。其中每个组的结构是这样的：

每个组都有一个superblock的拷贝。通过分组，可以有效降低整体的负担。

策略：如何安放文件和目录

我们可以把相关的东西放在一起，不相关的东西分开放。那么问题来了，什么是相关的，什么是不相关的呢？

首先放置的是目录，用一个简单的方法：找到一个柱面组，目录分配的少并且inode空闲的数量多。

然后放置的是文件，文件又分成两部分，首先操作系统确保一个文件的所有data block都放到一个柱面组里，其次是把同一个目录下的文件都放在一个柱面组里。

Measuring File Locality

大部分的文件彼此之间的距离都比较近。

大文件除外

大文件并不受上面的策略影响，它会分散放置在各个group里面。

总结

这一部分主要介绍了对原来操作系统缓慢的文件系统的改进。

42. Crash Consistency: FSCK and Journaling

如何对抗系统崩溃或者突然断电等问题是硬盘需要解决的。

一个具体的例子

为了简单起见，我们现在假设要往一个文件里追加一些内容，那么需要修改磁盘中的三个部分：Inode部分，data的bitmap部分和data block部分。那么会有什么情况发生呢？

• 只更新了data block。因为inode里面没记录，同时data bitmap也没有，所以更新的data block跟没写入是一样的。
• 只更新了inode。由于data block里没有数据，所以读到的是垃圾数据。而且更为严重的是，inode显示可以读取，但是bitmap里面对应的Block却是空的。
• 只更新了bitmap。这样会造成space leak，因为这块空间在inode里面没有记录，永远也释放不了了。
• 同时更新了inode和bitmap。造成垃圾数据的问题。
• 同时更新了inode和data block。冲突问题。
• 同时更新了bitmap和data block。没有inode的内容就没有文件使用，更新了也白更新。

我们希望文件系统保持一致性，但是断电随时可能会发生。我们把这个不一致的问题称为crash-consistency problem。

解决办法1：文件系统checker

早期系统允许上面的情况发生，并且尝试去修复它——fsck。当然你并不能期望它能够解决垃圾数据的问题，它需要在文件系统挂载之前就运行，具体有这些步骤：

• 首先确认一下superblocks。
• 接下来扫描inodes等，对系统里block的分配情况有一个了解。然后根据扫描结果，fsck自动构造出一个bitmap，然后与原来的bitmap进行比较。
• 详细确认每一个inode的情况
• 检查link数量。如果发现一个inode没有被任何目录使用，那么就把它放到lost+found目录中。
• 越界block等检查。
• 其它检查等。

这个命令非常非常的慢，虽然有用但是…太慢了。

解决办法2：Write-Ahead Logging

write-ahead logging，aka journaling，这个办法是从数据库那里“偷”过来的。现在，Linux中的ext3 ext4和Windows的NTFS都是用的这个想法。

核心思想是，在动手更新之前，首先先记录好，然后再开始做。

现在假设我们又想写文件了，还是原来的配方。那我们首先把我们要更新的三个部分写到日志里。日志一共有五个部分，除了要更新的这三个部分（注意，这三个部分是物理日志，即这三个块的内容和最后要到对应位置上面的是完完全全一模一样的）外，还有一个事务头（包含了ID等信息）和事务的尾巴（同样包含了ID等信息）。只要这个事务成功写入了日志（日志也在磁盘上），那么就可以把这些数据真正写到磁盘中对应的位置去了。这个对应的进程叫checkpointing。

当然，在你写入日志文件的时候，也可能发生断电，所以为了保护，文件系统会保证，只有当数据齐全之后，才会加上事务的尾巴。即最后的过程是这个样子的：

1. 将事务的内容，包括事务的头部块和内容部分写入到日志中
2. 将事务的提交块（最后的那一块）写入，写入完成则事务提交
3. 将真正的块写入到磁盘真正的位置。

恢复

如果断电发生在事务还没提交之前，那么就直接无视。

如果发生在事务已经提交，但是还没有写入到硬盘，那么就需要重新再做一次，所以相应的日志就叫做redo logging。

这里仅仅解决了数据冲突的问题，并不能解决数据丢失的问题，事实上，（在极端情况下）没有任何设备可以保证数据的不丢失，除非每次你都愿意等待真正落盘之后才通知你完成。

聚合在一起

显然如果真的每次都先写日志，然后真正写入数据的话，那么会导致磁盘读取写入过于频繁，所以可以使用缓冲技术，把所有的都缓冲到一个事务中去。

元数据日志

根据上面的描述，其实我们在日志中写入的是所有的数据部分，而这种日志叫做数据日志，data journaling，常见的如Linux的ext3系统就是数据日志。但是我们真的有必要把所有的数据写入到日志的磁盘中吗？其实只需要修改下顺序，就可以不用把额外的数据块写入到日志中：

1. 把数据写入到磁盘的最终位置
2. 把事务的开始块、元数据写入到日志中
3. 把事务的结束块（也叫提交块）写入到日志，提交事务。这一步开始前要确保前面的1和2完成，而1和2谁先开始、谁先完成并不重要。
4. 把元数据写入到文件系统的最终位置处。
5. 释放空间。

总结

这一章介绍了通过fsck来保证数据的一致性，但是由于这个检查的太慢，所以一般不采用；然后介绍了基于日志的方法，其中一种叫数据日志。它要把数据写入到日志系统中，另外一种是只需要写元数据就可以了。

我个人的理解：数据日志的感觉就是我先把数据写入到日志系统里面，相当于有了一个备份，有了备份然后再去真正的磁盘处进行写入。而元数据日志则是把数据写入这一部分去掉了，所以可以提升效率。

43. Log-structured File Systems

在前面的学习中，一共提出了两种文件系统，一种是VSFS，就是用来讲述文件系统基本概念的；还有一种是上面提到的FFS，然而FFS仅仅是把在同一个目录下的数据放在一个柱面上进行保存而已。

然后在上一章中提到，为了能够在磁盘崩溃的时候保证一致性，需要有对应的措施。

而在这一章里面，则是学习一个更加现代化，表现更加优异的文件系统——LFS。

LFS的设计人员发现，内存越来越大，而且磁盘中写入的性能成为了其瓶颈，因此迫切需要把日常的一些写入工作变成是顺序写入的以提高性能。

按序写入磁盘

之前讲到VSFS的时候，提到了文件系统必须要有三部分（忽略超级块）：inode和数据的空闲列表（位图）、inode部分和数据部分，而这三个部分在VSFS中，是固定在指定位置的，也正是因为固定在了指定位置，所以才导致了写入速度极其不佳（因为不是顺序写入），而LFS的核心就在于，它把所有的inode和数据块更新顺序写到磁盘上，这样就变成了顺序写入。

如何查找inode

现在inode并不是在硬盘的指定位置了，也就是之前的通过Inode直接计算出inode磁盘地址的方法失效了。

LFS通过使用一种叫做imap的数据结构解决这一问题，即只要有imap，那输入给imap一个inode，就可以得到对应的inode磁盘块的地址。

那问题又来了，imap应该放在磁盘的哪里？如果imap放在磁盘的指定位置，那又回到和最原始的文件系统一样的想法了，所以imap其实是保存在对应的inode的旁边的。

所以其实这是一个永无止境的问题，如果希望 跳出这个循环，那必然需要在磁盘的固定位置处进行存放，才可以打破这个僵局。

检查点

LFS在磁盘上确实有这么一个区域（磁盘的开头），叫做检查点区域（checkpoint region），通过它可以知道最新的imap。而这个检查点更新时间特别久，所以性能影响很小。

LFS读取文件

第一步，必然是从检查点区域读取数据放到内存中，然后就可以获得imap数据，也放到内存中。这样给定每一个inode，都可以直接获取到inode对应的磁盘地址，有了磁盘地址，接下来就一切好说了。

垃圾收集

LFS需要对时时刻刻把新数据和新的inode更新到磁盘中，所以旧的一部分数据就免不了成为了垃圾。

LFS清理是按照段进行清理的。它在清理的时候会读取旧的段，然后把旧的段和新的段进行整合，然后释放空间，把新的段写入到磁盘中。

确定块死活

每个段的头部都会有一个摘要，记录了该段中每个数据块的inode号和偏移量（即这个数据块是文件的哪一部分）。

这样只要有了摘要，就知道了该数据块属于文件的哪一部分。此时LFS只需要去imap里面根据对应的inode就可以找到这个文件的所有数据块，然后根据偏移量可以知道这个当前在段中的这个数据块，是不是inode里面指向的那个数据块。如果是则说明还有效，否则就死亡。

当然还有一些特殊的优化，比如利用版本号。当删除一个文件的时候，直接版本号加一，简单的通过版本号的检查，可以避免上面冗长的检查。

44. SSD

45. Data Integrity and Protection

虚拟机

这并不属于