交错增量编码：从 SCCS 到现代同步系统的数据结构演进

在软件版本控制的历史长河中，有些设计思想看似已被时代淘汰，实则以新的形态持续影响着现代系统。1970 年代早期由 Marc J. Rochkind 开发的 Source Code Control System（SCCS）所采用的 ** 交错增量编码（interleaved deltas）** 或称 weave 结构，正是这样一种被低估但极具启发性的数据组织方式。它不仅在技术史上具有里程碑意义 ——Rochkind 的论文获得了首届 ICSE 最具影响力论文奖 —— 更在当代的 CRDT（无冲突复制数据类型）和分布式版本控制系统中找到了新的表达。

Weave 的核心机制

与 Git 将每个版本作为独立快照存储的方式不同，SCCS 的 weave 将所有修订历史编织进单一的数据结构中。这种结构由四种基本指令构成：Line（输出一行）、BeginInsert（开始插入块）、BeginDelete（开始删除块）和 End（结束块）。每条指令都携带一个版本号作为操作数，指向全局行池中的索引。

Weave 最显著的特征在于块可以重叠。不同于 XML 或 JSON 要求严格的嵌套结构，weave 中的插入和删除块可以相互穿插。例如，若版本 v1 添加了第 1-2 行，v2 追加了第 3-6 行，而 v3 删除了第 2-4 行，则 v3 的删除块会与 v1、v2 的增量块产生重叠。这种设计使得 weave 能够紧凑地表示复杂的修订历史，但也带来了重建算法的复杂性。

激活集与版本重建

重建特定版本的关键在于 ** 激活集（active set）** 的概念 —— 即贡献到该版本文件内容的所有增量集合。计算激活集需要遍历版本依赖图：每个版本可以有一个或多个父版本（多父表示合并提交），激活某个版本会自动激活其所有祖先。

重建算法通过扫描指令列表并维护一个优先队列（而非简单的栈）来跟踪当前打开的块。之所以需要优先队列而非栈，正是因为块可以重叠。当遇到 BeginInsert 指令时，无论其版本是否激活，都需要入队；而 BeginDelete 仅在版本激活时才入队。队列顶部的块决定了当前行是否输出：如果顶部是激活状态的 BeginInsert，则输出行；否则跳过。

这种重建机制的时间复杂度与 weave 的长度和激活集的大小相关。对于频繁访问的历史版本，系统可以通过缓存激活集来优化性能。

增量的计算与交织

向 weave 添加新版本需要两个步骤：首先计算新旧版本之间的差异脚本（diff script），然后将这些增量 "交织" 进现有的 weave 结构中。

差异计算通常采用最长公共子序列（LCS）算法，生成由 Insert、Delete 和 Keep 动作组成的脚本。每个动作作用于特定的行序列。实践中可以使用 Myers diff 或 Bram Cohen 的 patience diff 等更高效的算法替代基础 LCS。

Interleave 函数是 weave 系统的核心操作。它接收当前 weave、目标版本的激活集和差异脚本，输出包含新版本的扩展 weave。算法并行遍历 weave 指令和差异脚本：对于未标记的行直接复制；遇到标记行时根据差异动作插入新的指令块。插入操作会创建新的 BeginInsert/End 包裹块；删除操作则创建 BeginDelete/End 块包裹被删除的行。

从 SCCS 到现代系统

尽管今天没有人会直接使用 SCCS，但其思想通过 BitKeeper 影响了 Git 的设计。BitKeeper 在 2002 至 2005 年间为 Linux 内核开发提供版本控制，它直接继承自 SCCS 并使用了 weave 结构来跟踪变更。Git 从 BitKeeper 借鉴了许多核心理念，尽管最终采用了基于内容寻址的快照模型。

更有趣的是 weave 结构在当代的复兴。CRDT（无冲突复制数据类型）和 Pijul 版本控制系统采用了与 weave 惊人相似的数据结构。Pijul 基于 "补丁理论"，其内部表示同样使用交错的插入和删除标记来跟踪文本演变。这种表示方式使得冲突解决更加直观 —— 因为历史本身就是一系列可交换的补丁，而非严格的线性序列。

工程实践启示

对于需要实现增量同步的工程师，weave 结构提供了以下可落地的参考：

存储效率权衡：Weave 适合读多写少、历史访问模式均匀的场景。如果系统主要访问最新版本，反向增量（如 RCS）可能更合适；如果需要频繁重建任意历史状态，weave 的单遍扫描优势明显。

重叠块的处理：当数据结构需要表示相交的变更范围时，优先队列是必要的。简单的栈结构只能处理嵌套块，而优先队列配合版本号排序可以处理任意重叠模式。

激活集缓存：在 weave 的重建算法中，激活集的计算是主要的性能瓶颈。对于固定的版本依赖图，激活集可以预先计算并缓存，重建时只需查表即可。

差异算法选择：虽然 LCS 提供最优解，但对于交互式应用，Myers diff 的线性空间复杂度和 patience diff 对人类可读性的优化往往更具实用价值。

结语

Interleaved deltas 提醒我们，计算机科学中很少有真正 "过时" 的思想。SCCS 的 weave 结构在半个世纪后仍在以 CRDT 和 Pijul 的形式延续其生命力。对于设计增量同步系统的工程师而言，理解这种将时间维度编织进空间结构的技术，有助于在存储效率、访问性能和算法复杂度之间做出更明智的权衡。正如 Roman Kashitsyn 在其研究笔记中所言："Weaves always return"——weave 总会以某种形式回归。

参考来源

• Roman Kashitsyn, "Interleaved deltas", mmap(blog), 2026-05-22
• Marc J. Rochkind, "The Source Code Control System", IEEE Transactions on Software Engineering, 1975

systems