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

12 投票

3 回答

2563 浏览

提问于 2025-04-17 10:02

考虑一下这段简单的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)

注意，通过使用历史列表，你可以将当前的字典恢复到它曾经存在的任何状态。我把这个过程称为“向前构建”（因为找不到更好的词），因为要构建当前的字典，必须从头开始，处理整个历史列表。我认为这是最明显、最直接的方法。

我听说，早期的版本控制系统使用的就是这种“向前构建”的方式，但这并不是最优的，因为大多数用户更关心最近的版本。而且，用户不想在只关心最新版本的时候下载整个历史记录。

那么，我的问题是，版本控制系统还有哪些其他存储历史记录的方法呢？也许可以使用“向后构建”？这样可能让用户只下载最近的修订，而不需要整个历史。我还看到了一些不同的历史存储格式，比如：变更集、快照和补丁。这些变更集、快照和补丁之间有什么区别呢？

在现代流行的版本控制工具中，它们是如何存储历史记录的，各自的设计有什么优点呢？

版本控制版本控制系统变更集历史记录补丁快照向前构建向后构建

3 个回答

作为一个更通用的回答，你需要区分一下CVCS（集中式版本控制系统，比如CVS、SVN、Perforce、ClearCase等）和DVCS（分布式版本控制系统，比如Git或Mercurial）。
它们在工作流程和使用方式上是不同的。

特别是，CVCS的客户端和服务器之间的数据交换比DVCS更重要（因为DVCS在推送或拉取整个仓库时确实需要增量数据）。

这就是为什么在CVCS中，增量数据对大多数操作非常重要，而在DVCS中，增量数据只对某些操作和不同的原因重要。

增量数据在Eric Sink的两本书中有描述：

源代码控制指南，第4章：仓库：

仓库 = 文件系统 * 时间

树是文件夹和文件的层级结构。增量数据是两棵树之间的差异。从理论上讲，这两棵树不需要有关系。然而，实际上，我们计算它们之间的差异的唯一原因是因为其中一棵树是从另一棵树派生出来的。某个开发者从树N开始，进行了一个或多个更改，得到了树N+1。

我们可以把增量数据看作是一组更改。实际上，许多源代码管理工具使用“更改集”这个术语来表示这个概念。更改集只是表达两棵树之间差异的更改列表。

增量数据的意义很重要（见这个讨论）：前向增量或反向增量。

一些源代码管理工具使用某种折中设计。在一种方法中，不仅仅存储一棵完整的树，而是将其他树表示为增量数据，我们在过程中还会存储一些完整的树。

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

通过示例学习版本控制，第12章：DVCS内部结构：

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

别忘了，增量数据管理也会影响有向无环图（DAG），这些图用来表示历史（见“ProGit书中的箭头方向”以及DAG背后的不便）。

你可以找到关于增量数据管理的具体信息：

Veracity支持两种类型的DAG：

树DAG保持文件系统目录结构的版本历史。DAG的每个节点代表整个树的一个版本。
数据库（或“db”）DAG保持数据库或记录列表的版本历史。DAG的每个节点代表完整数据库的一个状态。

最后一点说明了第三（第四？）代版本控制系统必须处理的不仅仅是文件（树）的分发，还有数据库（用于各种目的）。

回答于 2025-04-17 由 Python大师

分享举报

我觉得Subversion在向后构建方面做了一些尝试。不过我可以更好地解释我知道的内容：那就是Mercurial的快照。

Mercurial使用的是向前构建的方式。为了让每个版本都能方便地重建，它设定了一些重新同步的点：每当重建一个版本所需的所有增量（也就是变化的部分）的大小超过完整文本的两倍时，就会存储一个完整的文本版本（压缩的快照），之后的所有增量都是相对于这个新快照来计算的。

这意味着你在获取任何版本时，最多只需要读取三倍于文本大小的数据。

你可以在Hg Book中找到更多详细信息。

回答于 2025-04-17 由 Python大师

分享举报

你提到了这三种存储（文件）历史的方法：

补丁（patch）：补丁是两个文件之间差异的表示，通常是文本形式，但也可以是二进制形式。它是通过unix命令diff生成的输出，可以用unix命令patch来应用。很多版本控制系统都使用补丁来存储文件的历史（比如SVN、CVS、GIT等）。有时候，这些补丁在技术上被称为“增量”（delta），这个词源于希腊字母"Δ"，用来描述两个事物之间的差异。
变更集（changeset）：变更集是一个术语，用来将“属于同一组”的不同文件的更改组合成一个整体。并不是所有的版本控制系统都支持变更集（最著名的如CVS和SourceSafe）。开发者使用变更集来避免构建失败（例如：在一个文件中改变一个方法的签名，在第二个文件中改变对这个方法的调用。你需要同时做这两个更改才能运行程序，否则会出错）。这里可以查看变更集和补丁之间的区别。
快照（snapshots）：快照是某个时间点上文件或文件系统状态的完整副本。它们通常比较大，使用时要考虑性能特点。快照通常是冗余的，和一系列补丁相比，但为了更快地获取信息，有时版本控制系统会将补丁和快照混合或结合使用。

Subversion在FSFS库中使用前向增量（forward deltas）（也就是补丁），在BDB库中使用后向增量（backward deltas）。请注意，这些实现的性能特点是不同的：

前向增量在提交时很快，但在检出时较慢，因为需要重建“当前”版本。
后向增量在检出时很快，但在提交时较慢，因为需要构建新的增量来生成新的当前版本，并将之前的“当前”版本重写为一系列增量。

另外，FSFS使用了一种“跳过增量（skipping delta）”算法，这样可以减少重建特定版本时的跳跃次数。不过，这种跳过增量并没有像Mercurial的快照那样进行大小优化；它只是最小化了构建完整版本所需的“修订”数量，而不管整体大小。

这里有一个小的ASCII艺术图（复制自规范），表示一个有9个修订的文件：

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

其中“0 <- 1”意味着修订1的增量基准是修订0。

跳跃的次数最多是log(N)，其中N是修订的数量。

另外，FSFS的一个很好的效果是，较旧的修订只会被写入一次，之后只会通过进一步的操作来读取。这就是为什么Subversion库非常稳定：只要你的硬盘没有硬件故障，即使最近的提交出现了一些损坏，你也应该能够获得一个可用的库，因为你仍然拥有所有较旧的修订。

在BDB后端，你在检查或提交时需要不断重写当前修订，这使得这个过程容易出现数据损坏。而且，由于你只在当前修订中存储完整文本，提交时如果数据损坏，很可能会破坏你历史的大部分内容。

回答于 2025-04-17 由 Python大师

分享举报

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

3 个回答

撰写回答