Interleaved Deltas：被遗忘的版本控制基石

背景

在软件工程的演进史中，人们往往倾向于认为进步是从简单走向复杂的过程。虽然单个系统确实会随着时间推移变得日益复杂，但长期的技术突破通常源于新思想与硬件进步使得原本“简单”的设计重新变得可行。

以最简单的版本控制系统为例：它可能只是将项目快照存储在备份目录中，为了效率对文件进行压缩，再引入哈希值进行内容寻址，其雏形便已酷似 Git。但这并非对 Git 的贬低，相反，这突显了早期系统的复杂性。早在 20 世纪 70 年代初，Marc J. Rochkind 开发的源代码控制系统（Source Code Control System, sccs）就不得不采用更 sophisticated（精密/复杂）的设计。由于当时硬件限制，sccs 必须一次处理一个文件，并将其所有修订版本存储在一个称为“交错增量”（interleaved deltas）或“编织”（weaves）的数据结构中。

对于许多现代开发者而言，Git 的逻辑似乎直观得仿佛是自己能发明出来的；然而，“weave”这一概念曾让作者 dsa- 困惑并敬畏多年。直到作者终于有时间深入研究其算法，发现相关资源稀缺：BitKeeper wiki 提供了不错的介绍，Bram Cohen 编写了参考实现但代码晦涩难懂。因此，作者发布了自己的研究笔记，旨在为未来的探索者提供指引。

核心内容

Weave 结构

Weave 本质上是一系列用于重构文件修订版本的指令序列。每条指令由类型（type）和操作数（operand）组成。

• 行指令与全局行池：所有的行指令必须属于 Insert（插入）或 Delete（删除）块。指令中的整数指向全局行池（global line pool）的索引。使用行索引而非字符串不仅缩小了 weave 的体积，还使得指令保持统一。
• 块重叠特性：与 XML 或 JSON 不同，weave 中的块允许重叠。例如，如果版本 v1 添加了第 1 和 2 行，v2 追加了第 3-6 行，而 v3 删除了第 2-4 行，那么 v3 的增量将与前两个版本的增量发生重叠。
• 依赖关系模糊性：在 weave 中，版本之间相互依赖。上述例子中，v3 依赖于 v1 和 v2，因为它删除了它们引入的行。然而，v1 和 v2 之间的关系是模糊的：v1 可能是 v2 的父版本，或者它们可能是 v3 合并的两个独立分支。仅凭 weave 本身无法推断增量之间的依赖关系，大多数基于 weave 的系统使用“激活集”（activation sets）来表达这些依赖。

活跃修订集（Active Revision Set）

sccs 使用层级修订名称（如 1.4 和 2.1）。当检出某个修订时，系统通过启发式算法计算其激活集——即贡献于文件内容的那些增量的集合。

作者将激活集比喻为控制黑暗大道上路灯的开关：拨动它们可以揭示或隐藏 weave 的特定部分。在作者的实验实现中，采用了扁平的连续修订编号。每个修订可以有一个或多个父修订（多个父修订代表合并提交）。父修订的编号总是小于子修订，因此不存在版本是其自身祖先的情况。激活一个修订也会激活其所有父修订，因此计算激活集需要执行图遍历。

重构修订（Reconstructing Revisions）

为了重构某个修订版本，算法首先计算其激活集，然后扫描指令列表。算法使用一个优先队列（priority queue）来跟踪当前打开的块。

• 如果指令打开了任何版本的 Insert 块，或者某个活跃版本的 Delete 块，则将其推入队列。
• 如果优先队列顶部的块是活跃的，则复制该行。这就是为什么我们需要保留非活跃的 Insert 块在队列中的原因。

由于块可以重叠（如前文所述），必须使用优先队列而非简单的栈。作者的实现为了简洁起见，使用排序切片作为优先队列（因为在 Go 语言中实现堆需要大量样板代码）。

返回启用行指令的位掩码（而非其内容）简化了包括 weave 扩展和增量重构在内的许多操作。

计算增量（Computing Deltas）

给定两个项目序列，目标是找到将第一个序列转换为第二个序列且步骤最少的变换。这种变换称为增量序列（也称为 hunks），指定了操作（Insert、Delete 或 Keep）及其作用的对象。作者称此类变换为 diff 脚本。

作者最熟悉的是 LCS（最长公共子序列）算法。该算法分两个阶段计算最优 diff 脚本：

1. 使用动态规划构建 LCS 表。lcs[i][j] 条目表示 a[i:] 和 b[j:] 的最长公共子序列的长度。表格需从后向前填充。
2. 遍历 LCS 表以恢复操作，当 a 和 b 不对齐时，向 lcs 增加的方向移动。

虽然实际系统通常会使用 Myers diff 或 Bram Cohen 的 Patience diff，但 LCS 算法足以解释核心原理。

扩展 Weave（Extending Weaves）

Interleave 函数接收一个 weave 和该 weave 内的一个版本（通过激活集标识），并合并新的增量，生成一个新的 weave。它调用 Reconstruct 函数对 weave 中每个活跃行进行标注，然后并行遍历指令和增量，添加匹配增量操作的新指令。

并行循环体的逻辑如下：

• 将未标记的指令原样复制到输出中。
• 找到第一个标记行时，停止并查阅增量操作。
• 如果是 Insert 操作，将其项目作为行追加到输出，并用 BeginInsert/End 块包围。
• 如果是 Delete 操作，打开 BeginDelete 块，只要输入流的活跃行与增量项目匹配，就复制输入流，然后关闭块。
• 如果是 Keep 操作，复制输入直到所有项目都作为活跃行出现。

重构增量（Reconstructing Deltas）

如何知道版本 v 中发生了什么变化？虽然可以恢复 v 及其前驱版本并对输出进行 diff，但这很浪费，因为 weave 已经存储了增量。

更直接的方法是利用 Reconstruct 函数返回的位掩码，检测如果停用版本 v 哪些行会变得非活跃。ReconstructDelta 可以计算任意两个版本之间的增量。如果需要特定版本 v 的增量，只需对 v 和 v-1 进行 diff 即可。

至此，我们拥有了构建一个支持 sccs 大部分功能的简单版本控制系统所需的全部机制。

关键要点

• Weave 的核心机制：Weave 是一种通过指令序列存储文件历史的数据结构，其最大特点是允许不同版本的增量块在时间轴上重叠，而非简单的线性嵌套。
• 激活集（Activation Set）：由于 Weave 中版本依赖关系复杂且模糊，系统必须通过“激活集”来动态决定哪些增量对当前文件状态有贡献，这类似于开关控制路灯。
• 重构算法：重构文件内容需要结合激活集和优先队列来处理重叠的插入/删除块，确保正确解析文件的最终状态。
• 增量计算与存储：虽然可以通过 diff 两个版本来计算增量，但直接利用 Weave 中已有的位掩码信息来提取增量更为高效。
• 历史渊源：现代 Git 的许多理念并非凭空产生，而是间接继承了 BitKeeper，而 BitKeeper 又是 sccs 的直接后代，并使用了 Weave 技术来追踪变更。

意义与影响

尽管没有人会在今天直接使用 sccs，但它对现代软件的影响深远。Marc J. Rochkind 的论文获得了 1989 年首届 ICSE 最具