转载：https://blog.csdn.net/PANGHAIFEI/article/details/100538268
备注：本文翻译自 IBM Research Report BTRFS - Linux Btree Filesystem
在写的时候，碎片整理以两种不同方式解决。为了碎片整理一个文件，它被读取，COWed，并在下一个检查点写入磁盘。这可能会使他更加顺序，因为分配器尝试在尽可能少的extents里写出来。缺点是与旧快照的共享丢失了。在许多情况下，这个简单的算法是有效的。在一些情况下，一个更加复杂的算法维持共享是需要的。
当缩减文件系统的时候，或者从磁盘删除数据，重新分配会被使用。这是一种算法扫描一个chunk和移动实时数据，同时保持共享。重新分配是复杂的程序，无论怎么样，在我们试图减少空间消耗的时候，无视共享可能会导致空间使用量的增加。
迁移通过chunks basis 工作在一个chunk上。一般的方案是：
1.迁走所有实时的extents（在chunk中）
2.找到所有引用发到chunks中。
3.在保持共享时修复引用
写时复制方法被贯穿使用；引用永远不会更新到位。表1 展示了一个简单的例子。一个数据extent，蓝色，需要被移动。
表1：在extent tree下进行范围内的查找，在chunk中找到所有的extents，拷贝所有的实时extents到新的位置。
为了加速一些引用跟踪，我们跟随back-references去找到所有顶层树块直接或者间接地引用chunk。结果存储在一个叫做backref_cache的DIAG类的数据结构。
表2：上层节点存储在一个backref_cache.
子卷树列表从backref_cache中引用的chunk被计算；这些树被顺序的克隆，看表3。这个操作有两种影响：（1）及时冻结子卷的状态。（2）它允许在为用户提供持续操作的同时对子卷进行即时修改。
表3：迁移树。这个例子中，子卷被克隆。可以对克隆尽心更改。
接下来，所有chunks的引用都被遵循， 使用back-references。COW在reloc tree中被用于更新。看表4。
表4：使用COW去修复在reloc树中的引用
最后一步是合并reloc trees和原始的。我们遍历树。我们找到在reloc树中被修改但是对应的部分在fs tree中没有被修改的子树。这些在reloc tree中的子树与fs树中的老同行交换。最终结果是新的fs-trees。最后，我们丢弃reloc trees，他们不再需要了。表5是一个例子。
合并reloc树和对应的fs树，然后drop掉reloc树。
新的文件系统DIAG在内存中，有正确的共享结构。它和原始的使用一样的数量，这就意味着文件系统空间使用时一样的。将DIAG写出到磁盘可以在连续的范围内完成，从而提高序列性。一旦完成，老的chunk可以被丢弃。
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/PANGHAIFEI/article/details/100538268
