如何存储和计算版本控制历史记录？

Question

考虑这个简单的python代码,它演示了一个非常简单的版本控制设计:

def build_current(history):
    current = {}
    for action, key, value in history:
        assert action in ('set', 'del')
        if action == 'set':
            current[key] = value
        elif action == 'del':
            del current[key]
    return current

history = []
history.append(('set', '1', 'one'))
history.append(('set', '2', 'two'))
history.append(('set', '3', 'three'))
print build_current(history)
history.append(('del', '2', None))
history.append(('set', '1', 'uno'))
history.append(('set', '4', 'four'))
print build_current(history)
for action, key, value in history:
    if key == '2':
        print '(%s, %s, %s)' % (action, key, value)

请注意,通过使用历史列表,您可以在曾经存在的任何状态下重建当前字典.我认为这是一个"前向构建"(缺少一个更好的术语)因为要构建当前字典,必须从头开始并处理整个历史列表.我认为这是最明显和最直接的方法.

正如我所听到的,早期版本控制系统使用了这种"前向构建"过程,但它们并不是最佳的,因为大多数用户更关心构建的最新版本.此外,当用户只关心查看最新版本时,他们不想下载整个历史记录.

那么我的问题是,在版本控制系统中存储历史记录还有哪些其他方法？也许可以使用"向后构建"？这可能允许用户仅下载最近的修订版而不需要整个历史记录.我还看到了一些用于存储历史记录的不同格式,即:变更集,快照和补丁.变更集,快照和补丁之间有什么区别？

在现有的流行版本控件中,它们如何存储它们的历史以及它们各种设计的优点是什么？

Answer 1

你提到了这三种存储方法(文件) - 历史:

1. 补丁:补丁是(通常是文本的,但二进制补丁也是可能的)表示两个文件之间的差异.它是unix命令diff的输出,可以通过unix命令patch应用.许多版本控制系统都使用补丁来存储文件的历史记录(例如SVN,CVS,GIT ..).有时,这些补丁在技术上被称为"delta",希腊字母"Δ"描述了两件事的差异.
2. changeset:变更集是将"属于一起"的变更组合到单个实体中的不同文件的术语.并非所有版本控制系统都支持变更集(最值得注意的是CVS和SourceSafe).开发人员使用变更集来避免破坏的构建(例如:在一个文件中更改方法的签名,在第二个文件中更改调用.您需要进行两个更改才能运行程序,否则会出错). 另请参见此处了解变更集和补丁之间的区别.
3. 快照:此文件/文件系统状态的完整副本到此时间点.它们通常非常大,其使用取决于性能特征.快照始终是补丁列表的冗余,但要更快地检索信息,有时版本控制系统会混合或组合补丁和快照

Subversion 在FSFS存储库中使用前向增量(也称为补丁),在BDB存储库中使用后向增量.请注意,这些实现具有不同的性能特征:

• 前进增量快速提交,但结账速度慢(因为必须重建"当前"版本)

• 后退增量快速检出但提交速度慢,因为必须构造新的增量以构造新的当前并将前一个"当前"重写为一堆增量

另请注意,FSFS使用"跳过增量"算法,该算法可最大限度地减少重建特定版本的跳转.然而,这个跳过的delta不是像mercurials快照一样的大小优化; 它只是最小化了构建完整版本所需的"修订"数量,无论总体大小如何.

这里是一个包含9个版本的文件的小ascii艺术(从规范中复制):

0 <- 1    2 <- 3    4 <- 5    6 <- 7
0 <------ 2         4 <------ 6
0 <---------------- 4
0 <------------------------------------ 8 <- 9

其中"0 < - 1"表示修订版1的delta基础是修订版0.

N个版本的跳转次数最多为log(N).

此外,对FSFS的一个非常好的影响是旧版本只会被写入一次,之后它们只能通过进一步的操作来读取.这就是为什么subversion存储库非常稳定的原因:只要你的硬盘上没有硬件故障,即使上次提交中发生了一些损坏,你也应该能够获得一个工作存储库:你仍然拥有所有较旧的版本.

在BDB Backend中,您不断在checkins/commits上重写当前版本,这使得此过程容易出现数据损坏.此外,当您仅将全文存储在当前版本中时,在提交时损坏数据可能会破坏历史记录的大部分内容.

Answer 2

我认为颠覆在向后构建方面做了一些尝试.但我可以解释一下我所知道的更多:Mercurial快照.

Mercurial使用正向构建方案.但是为了能够轻松地重建每个修订版本,有重新同步点:每次重建修订版本所需的所有增量大小都大于全文的两倍时,将存储全文本版本(压缩快照),相对于此新快照计算所有后续增量.

这意味着您永远不需要读取超过文本大小3倍的内容来检索任何修订版本.

您可以在Hg Book中找到更多详细信息.

Answer 3

作为更通用的答案，您需要将 CVCS（集中式 VCS，如 CVS、SVN、Perforce、ClearCase 等）与 DVCS（分布式 VCS，如 Git 或 Mercurial）区分开来。
它们涉及不同的工作流程和用法。

特别是，CVCS客户端与其服务器之间的数据交换将比 DVCS 更重要（在推送或拉动所有 repo 时确实需要增量）

这就是为什么 delta 对于 CVCS 中的大多数操作非常重要，仅对某些操作和 DVCS 中的不同原因很重要。

Eric Sink 在两本书中描述了 Delta：

• 源代码控制 HOWTO，第 4 章：存储库：

存储库 = 文件系统 * 时间

树是文件夹和文件的层次结构。delta 是两棵树之间的差异。理论上，这两棵树不需要关联。然而，在实践中，我们计算它们之间差异的唯一原因是因为它们中的一个是从另一个派生出来的。一些开发人员从树 N 开始并进行了一项或多项更改，结果是树 N+1。

我们可以将 delta 视为一组变化。事实上，许多 SCM 工具正是为了这个目的使用术语“变更集”。变更集只是表示两棵树之间差异的变更列表。

增量感很重要（请参阅此线程）：正向增量或反向增量。

一些 SCM 工具使用某种折衷设计。在一种方法中，我们不是只存储一棵完整的树并将其他每一棵树表示为增量，而是沿途撒上更多的完整树。

您可以在Eric Raymond 的《理解版本控制系统》中看到“旧”VCS 的演变。

• 版本控制示例，第 12 章。 DVCS 内部：

许多现代版本控制工具使用二进制文件增量来存储存储库。
一种流行的文件增量算法称为vcdiff。
它输出已更改的字节范围列表。这意味着它可以处理任何类型的文件，二进制或文本。作为附带的好处，vcdiff 算法同时压缩数据。

不要忘记，delta 管理也对为表示历史而创建的有向无环图 (DAG)产生影响（请参阅“ ProGit 书中的箭头方向”和DAG 背后的不便）。

你可以找到具体有关三角洲管理：

• Git：“ git binary diff 算法（增量存储）是否标准化？ ”
• Mercurial：“ Mercurial：存储库结构”
• 真实性（结合了两种方法）：“真实性：DAG 和数据”

Veracity 支持两种 DAG：

• 树 DAG 保留来自文件系统的目录结构的版本历史记录。DAG 的每个节点代表整个树的一个版本。

• 数据库（或“db”）DAG 保存数据库的版本历史或记录列表。DAG 的每个节点代表整个数据库的一种状态。

最后一点说明第三（第四？）代 VCS 不仅必须处理文件（树）的分发，还必须处理数据库（用于各种目的）的分发