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

快照（snapshot）

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

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

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

写时复制（copy-on-write）

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

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

实现方法

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

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

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

B+ 树的自顶向下操作

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

阅读全文…