很多时候我们修改一个重要的文件时都会先把文件复制一份作为备份，然后才对原文件进行修改，这样既可以防止修改错误无法恢复到原来正确的状态，也防止计算机突然断电造成数据不一致。当我们确定修改没有问题时会把原来的备份删掉（当然也可以保留下来），然后把修改后的文件再复制一份作为备份，再在当前的基础上进行修改，修改完成后再删掉原来的备份……如果文件较小，一般的版本控制工具都可胜任，但是如果数据很大（几百 G 到上 T，例如虚拟机镜像，数据库文件等），每次修改都要复制一遍或者比较和上一版本的差异以便增量保存，这样的做法无论是时间还是空间上都是难以忍受的。

快照（snapshot）

快照（snapshot） 就像上面提到的备份功能，即把某一时刻的状态保存起来，像照相机照相一样把当时的情景记录下来，虽然照相之后环境有变化，但是照片的内容不会随着环境变化而改变，这样的快照就是只读快照。另外还有支持修改的可写快照。经常使用的虚拟机软件如 vmware，virtualbox 等都提供快照的功能。有时我们需要尝试新软件或观察病毒的行为，但是又不想让它们修改真实的计算机，就可以先对虚拟机做一个快照，然后再做测试，测试完后恢复到快照的状态就可以了，既安全又快捷。

一般来说快照功能都是虚拟机软件或数据库自己实现的，对文件系统的使用只限于基本的读写新增删除操作，不只是因为 POSIX 标准只提供最基本的文件系统功能的接口，也因为没有几个文件系统具有文件快照的功能，文件系统的快照功能一般都由卷管理器实现。新出现的一些“现代文件系统”（参考资料 [1]）如 zfs，btrfs，除了文件系统的基本功能外还有快照和卷管理功能，抢了逻辑卷管理器如 lvm 等的饭碗。

快照在读多写少的情况下可以避免读写锁的竞争。对于实时性要求不高的应用来说，可以先对某一时刻的状态做一个快照，然后让读进程对快照进行访问（只读进程不需要加锁），而其它写进程则在另一个版本上进行更新，一段时间后再修改指针让其指向新的版本，等所有的读进程都完成旧快照的读取后就可以把旧快照删除。

写时复制（copy-on-write）

写时复制（copy-on-write） 的意思是多个用户共享一块相同的数据时，如果其中某个用户要对数据进行修改，系统会把这块数据复制一份然后进行修改，修改完成后让该用户的记录指向新修改的数据，这样其它用户看到的还是原来的数据而该用户看到的是已经修改过的数据。如果数据没有被修改则不会被复制，这样可以节省存储空间，像共享链接库，一个程序的多个进程实例等都用到了这个技术。

对于快照来说写时复制几乎是一个必需的功能。像上面所说的虚拟机文件来说，保存了快照之后要基于快照之上进行修改，但是由于虚拟机文件很大，而且修改的只是文件的一部分，不同状态的多个虚拟机文件可以共享大部分相同的数据块。

实现方法

比较容易想到的简单方法是使用线性表来实现，即为每个历史记录创建一个索引，这个索引指向该快照所有的数据块。elephant 文件系统（参考资料 [2]）就使用了这种方法。

参考资料 [3] 中使用了一种类似于内存地址转换的方法，即为每个数据块分配一个逻辑地址，另外还有一个逻辑地址到实际地址的映射表，访问数据块内容的时候要从映射表中找到实际的地址。这样建立快照的时候只需修改映射表就行了，坏处是映射表难以维护，地址转换也降低了性能。

还有一种方法就是下面要说的 B+ 树实现。

B+ 树的自顶向下操作

在看具体实现之前，先说说 B+ 树的自顶向下操作方法。上一篇笔记 说的是自底向上的方法，即分裂是从叶节点到根节点进行的。而自顶向下的方法是指，在查找叶节点的过程中对有可能会造成分裂/合并的节点预先进行分裂/合并，这样当最后对叶节点操作时不需要重新检查从该叶节点到根节点路径上的节点。这些预先分裂/合并操作并不会改变 B+ 树的性质。

如果是自顶向下的插入操作，考虑到插入节点的时候可能要分裂，在查找要插入的叶节点的过程中如果遇到一个非叶节点已经满了，就要把这个叶节点分裂成两个新节点，然后再继续往下查找，直到找到要插入元素的叶节点。因为在查找叶节点的过程中已经将可能分裂的非叶节点（即已经满了的节点）分裂了，所以最后在叶节点中插入元素就行了。

例如一棵 B+ 树如下：

              +--------+----------+--------+
              |    e   |     m    |    t   |
              +--------+----------+--------+
             /         |          |         \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f | h |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

插入“g”：

                            +---------+---+---+
                            |    m    |   |   |
                            +---------+---+---+
                           /           \
          +-------+---+---+             +------+---+---+
          |   e   |   |   |             |  t   |   |   |    =>
          +-------+---+---+             +------+---+---+
         /         \                   /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f | h |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

                                  +------------------+---+---+
                                  |         m        |   |   |
                                  +------------------+---+---+
                                 /                    \
              +----+--------+---+                      +------+---+---+
              |  e |        |   |                      |  t   |   |   |    =>
              +----+--------+---+                      +------+---+---+
             /     |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

                                  +------------------+---+---+
                                  |         m        |   |   |
                                  +------------------+---+---+
                                 /                    \
              +----+--------+---+                      +------+---+---+
              |  e |   g    |   |                      |  t   |   |   |
              +----+--------+---+                      +------+---+---+
             /     |         \                        /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

与自底向上的操作方式不同的是，在向下查找“g”的插入位置的过程中，遇到根节点已经满了，因此将其分裂，然后再继续往下查找。这样当找到要插入的叶节点时只需将元素插入即可，而不需再检查查找路径上的节点是否需要分裂。

然后删除元素“t”：

                           +--------------+---+---+
                           |      g       |   |   |
                           +--------------+---+---+
                          /                \
          +------+---+---+                  +--------+--------+---+
          |   e  |   |   |                  |    m   |    t   |   |        =>
          +------+---+---+                  +--------+--------+---+
         /        \                        /         |         \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->| t | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

                           +--------------+---+---+
                           |      g       |   |   |
                           +--------------+---+---+
                          /                \
          +------+---+---+                  +--------+--------+---+
          |   e  |   |   |                  |    m   |    t   |   |        =>
          +------+---+---+                  +--------+--------+---+
         /        \                        /         |         \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p |   |->|   | x |   |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

                           +----------+---+---+
                           |    g     |   |   |
                           +----------+---+---+
                          /            \
          +------+---+---+              +------+---+---+
          |   e  |   |   |              |  m   |   |   |
          +------+---+---+              +------+---+---+
         /        \                    /        \
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+
| b | d |   |->| e | f |   |->| g | h |   |->| m | p | x |
+---+---+---+  +---+---+---+  +---+---+---+  +---+---+---+

因为右子树的根节点只有一个元素“t”，当往下查找时先从左兄弟节点“借”一个节点，然后再继续往下查找。当最后删除“t”后合并叶节点，并且从父节点中删除索引元素“t”。注意合并并没有引起连锁的合并操作，这是因为预先对节点进行了调整。

使用 B+ 树实现（参考资料 [4]）

一棵 B+ 树如下：

             +-----------+
             |    A,1    |
             +-----------+
            /             \
     +-----+               +-----+
     | B,1 |               | C,1 |
     +-----+               +-----+
    /       \             /       \
+-----+    +-----+    +-----+    +-----+
| D,1 | -> | E,1 | -> | F,1 | -> | G,1 |
+-----+    +-----+    +-----+    +-----+

节点中的数值表示当前节点的引用计数，例如 (B,1) 表示节点 B 只有一个节点指向它。然后对整棵树做一个快照：

             +-----------+
             |    A,2    |
             +-----------+
            /             \
     +-----+               +-----+
     | B,1 |               | C,1 |
     +-----+               +-----+
    /       \             /       \
+-----+    +-----+    +-----+    +-----+
| D,1 | -> | E,1 | -> | F,1 | -> | G,1 |
+-----+    +-----+    +-----+    +-----+

这时根节点 A 的引用计数变为 2。做一次快照仅仅是修改了 A 的引用计数，这几乎是一瞬间的事。

现在要修改节点 G（可能是插入/删除/更新一个元素）：

        +---------+  +---------+                 +-------+  +-------+
        |   A,1   |  |  A',1   |                 |  A,1  |  | A',1  |
        +---------+  +---------+                 +-------+  +-------+
             |     \/     |                          |    \/         \
             |     /\     |                          |    /\          \
        +---------+  +---------+                 +-------+  +-------+  +------+
        |   B,2   |  |   C,2   |         =>      |  B,2  |  |  C,1  |  | C',1 |  =>
        +---------+  +---------+                 +-------+  +-------+  +------+
       /      |          |      \               /      |        |    \/   |
      /       |          |       \             /       |        |    /\   |
+-----+    +-----+    +-----+    +-----+    +-----+  +-----+  +-----+  +-----+
| D,1 | -> | E,1 | -> | F,1 | -> | G,1 |    | D,1 |->| E,1 |->| F,2 |->| G,2 |
+-----+    +-----+    +-----+    +-----+    +-----+  +-----+  +-----+  +-----+

     +-------+  +-------+
     |  A,1  |  | A',1  |
     +-------+  +-------+
         |    \/         \
         |    /\          \
     +-------+  +-------+  +------+
     |  B,2  |  |  C,1  |  | C',1 |
     +-------+  +-------+  +------+
    /      |        |    \/        \
   /       |        |    /\         \
+-----+  +-----+  +-----+  +-----+   +------+
| D,1 |->| E,1 |->| F,2 |->| G,1 |   | G',1 |
+-----+  +-----+  +-----+  +-----+   +------+

到这里发现如果要把节点 F 的下一个节点指针指向 G'，则 F 要复制一份为 F'，同样的 E 也要修改为 E'，那么 D，B，A 也要修改，这样引起连锁反应，修改一个节点几乎把整棵树复制一份。造成这样的原因是叶节点之间相连的指针，如果把叶节点之间的指针去掉就不会有这个麻烦：

     +-------+  +-------+
     |  A,1  |  | A',1  |
     +-------+  +-------+
         |    \/         \
         |    /\          \
     +-------+  +-------+  +------+
     |  B,2  |  |  C,1  |  | C',1 |
     +-------+  +-------+  +------+
    /      |        |    \/        \
   /       |        |    /\         \
+-----+  +-----+  +-----+  +-----+   +------+
| D,1 |  | E,1 |  | F,2 |  | G,1 |   | G',1 |
+-----+  +-----+  +-----+  +-----+   +------+

这样只有 G'，C'，A' 为新节点。节点 A 和 R 分别指向两棵不同内容的树，两棵树共享的节点有 B，D，E，F。

从上面的操作可以看出一些规律。在查找修改的节点的过程中，如果遇到的节点的引用计数大于 1，说明该节点被多个快照引用。这时需要复制一个新的节点，同时将其引用计数减 1，并且对该节点的两个子节点引用计数加 1。例如第一次访问根节点 A 时发现其引用计数为 2，因此需要复制一个新的节点 A'，并且把 A 的引用计数减 1，A 的两个子节点 B 和 C 的引用计数都加 1（同时被 A 和 A' 使用）。再往下发现 C 的引用计数为 2，因此也要复制一个新的节点 C' 并且把 C 的引用计数减 1（节点 C 现在只被 A 引用），并且把 A' 原来指向 C 的指针改为指向 C'。同样地需要把 C 的两个子节点 F 和 G 的引用计数加 1，因为此时 F 和 G 被节点 C 和 C' 使用。最后要修改 G 时，因为 G 的引用计数大于 1，所以不能直接修改，要先复制为 G' 再修改。最后得到的两棵树如上图所示。这时候 A 和 A' 分别是两棵不同的树，它们共享一部分节点。

接下来对树 A 做一个快照：

     +-------+  +-------+
     |  A,2  |  | A',1  |
     +-------+  +-------+
         |    \/         \
         |    /\          \
     +-------+  +-------+  +------+
     |  B,2  |  |  C,1  |  | C',1 |
     +-------+  +-------+  +------+
    /      |        |    \/        \
   /       |        |    /\         \
+-----+  +-----+  +-----+  +-----+   +------+
| D,1 |  | E,1 |  | F,2 |  | G,1 |   | G',1 |
+-----+  +-----+  +-----+  +-----+   +------+

然后修改节点 D 的值（图画得丑了点，建议看看参考资料 [4]）：

     +-------+  +-------+    +-------+                     +-------+  +-------+    +-------+
     |  A",1 |  |  A,1  |    | A',1  |                     |  A",1 |  |  A,1  |    | A',1  |
     +-------+  +-------+    +-------+                     +-------+  +-------+    +-------+
         |    \/____|_A'toB_/   |                         /         \/____|_A'toB_/   |
         |    /\    |           |                        /          /\    |           |
     +-------+  +-------+  +------+              +------+  +-------+  +-------+  +------+
     |  B,3  |  |  C,2  |  | C',1 |          =>  | B',1 |  |  B,2  |  |  C,2  |  | C',1 |          =>
     +-------+  +-------+  +------+              +------+  +-------+  +-------+  +------+
    /      |        |    \/        \                 |   \/   |        |_C'toF_\/        \
   /       |        |    /\         \                |   /\   |        |        \         \
+-----+  +-----+  +-----+  +-----+   +------+     +-----+  +-----+  +-----+      +-----+   +------+
| D,1 |  | E,1 |  | F,2 |  | G,1 |   | G',1 |     | D,2 |  | E,2 |  | F,2 |      | G,1 |   | G',1 |
+-----+  +-----+  +-----+  +-----+   +------+     +-----+  +-----+  +-----+      +-----+   +------+

                    +-------+  +-------+    +-------+
                    |  A",1 |  |  A,1  |    | A',1  |
                    +-------+  +-------+    +-------+
                   /         \/____|_A'toB_/   |
                  /          /\    |           |
          +------+  +-------+  +-------+  +------+
          | B',1 |  |  B,2  |  |  C,2  |  | C',1 |
          +------+  +-------+  +-------+  +------+
         /        \/   |        |_C'toF_\/        \
        /         /\   |        |        \         \
+------+   +-----+  +-----+  +-----+      +-----+   +------+
| D',1 |   | D,1 |  | E,2 |  | F,2 |      | G,1 |   | G',1 |
+------+   +-----+  +-----+  +-----+      +-----+   +------+

然后删除快照 A'：

                    +-------+  +-------+
                    |  A",1 |  |  A,1  |
                    +-------+  +-------+
                   /         \/    |
                  /          /\    |
          +------+  +-------+  +-------+
          | B',1 |  |  B,1  |  |  C,2  |
          +------+  +-------+  +-------+
         /        \/   |          |     \
        /         /\   |          |      \
+------+   +-----+  +-----+    +-----+    +-----+
| D',1 |   | D,1 |  | E,2 |    | F,1 |    | G,1 |
+------+   +-----+  +-----+    +-----+    +-----+

删除快照的时候,先把节点的引用计数减 1。如果引用计数变为 0 说明该节点没有被其它快照使用，它所占用的空间可以被释放，如节点 A'，C'，G'；如果引用计数大于 0 说明还有其它快照使用该节点及其子树，因此不需要继续往下遍历，如子树 B，叶子节点 F。

其它

文件系统使用 copy-on-write 技术可以很好的保证数据的一致性。每次要修改文件内容的时候并不是直接修改原文件，而是先对原文件做一个快照，然后再修改，修改完成后把指向旧快照根节点的指针修改为指向新的根节点的指针。因为修改指针的操作几乎是瞬间完成的，因此文件的内容要么是原来的内容，要么是修改过的内容，而不会出现只修改了一部分的情况。

copy-on-write 也有一些不足之处，例如对文件进行多次修改可能会造成文件不连续，数据块散落在整块硬盘上。如果进行碎片整理的话，某个数据块可能被多个文件使用，改变该数据块的位置需要修改所有使用这个数据块的索引，参考资料 [5] 提出了这个问题的一些解决方法。

参考资料

[1] On File Systems
[2] Deciding when to forget in the Elephant file system
[3] Stability in a Persistent Store Based on a Large Virtual Memory
[4] B-trees, Shadowing, and Clones
[5] Tracking Back References in a Write-Anywhere File System