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

Question

考虑这个简单的Python代码，这表明一个非常简单的版本控制设计一dictonary：

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) 

注意，通过使用历史列表，你可以重构它曾经存在过的任何状态下的电流字典。我认为这是一个“前向构建”（因为缺乏更好的术语），因为构建当前字典必须从头开始并处理整个历史列表。我认为这是最明显和直接的方法。

正如我所听说的，早期版本控制系统使用这种“前向构建”过程，但它们并不是最佳的，因为大多数用户都关心构建的最新版本。而且，当用户只关心看到最新版本时，用户不希望下载整个历史记录。

那么我的问题是，在版本控制系统中存储历史还有哪些其他方法？也许可以使用“倒退建造”？这可能允许用户只下载最近的修订版而不需要整个历史记录。我还用seen几种不同的格式来存储历史记录，即：变更集，快照和补丁。变更集，快照和补丁之间有什么区别？

在现代流行版本控件中，他们如何存储历史以及各种设计的优点？

Answer 1

你提到存储（文件）这3种方法-history：

1. 补丁：一个补丁（通常是文本，但二进制补丁也是可以的）两个文件之间的差异表示。它是unix命令的输出diff并且可以通过unix命令补丁应用。很多版本控制系统使用补丁来存储文件的历史记录（例如，SVN，CVS，GIT ..）。有时候这些补丁在技术上被称为“德尔塔”，如希腊字母"Δ"描述了两件事的区别。
2. 变更集：变更集是一个术语，用于将“属于一起”的变更结合到单个实体中的不同文件中。并非所有版本控制系统都支持更改集（最值得注意的CVS和SourceSafe）。开发人员正在使用变更集来避免构建破损（例如：在一个文件中更改方法的签名，在第二个文件中更改调用，您需要同时执行两个更改才能运行该程序，否则会出现错误）。 See also here for the difference between changeset and patch。
3. 快照：是此文件/文件系统状态的完整副本到这个时间点。它们通常很大，它们的使用取决于性能特征。快照始终是多余的修补程序的列表，但是更快地获取信息，有时版本的系统的混合或组合补丁和快照

Subversion使用向前三角洲在FSFS版本库（又名补丁）和落后三角洲在BDB存储库中。 注意，这些实现具有不同的性能特征：

• 向前三角洲是快承诺，但在结账慢（因为 “当前”版本必须重构）

• 落后三角洲是快检查出来，但慢于提交新 增量必须构建，构建新的当前和重写前面的“当前”作为一帮三角洲

另请注意，FSFS使用"skipping delta"算法，该算法可以最小化跳转以重建特定版本。但是，这种跳过增量并不像mercurials快照那样大小优化;它只需最小化构建完整版本所需的“修订”数量，而不考虑整体大小。

这里小ASCII技术的文件的（从说明书复制），用9个版本：

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

其中“0 < - 1”意思是对于修订版1增量碱是修订0

对于N个修订，跳转数最多为log（N）。

另外FSFS上的一个非常漂亮的效果是，旧版本将只写一次，在此之后，他们将只能通过进一步的行动来阅读。 这就是为什么Subversion版本库非常稳定：只要硬盘上没有硬件故障，即使上次提交发生了一些损坏，您也应该能够获得工作存储库：您仍旧拥有所有旧版本。

在BDB后端，您不断重写当前版本的checkins/commits，这使得这个过程容易出现数据损坏。另外，由于您仅将全文存储在当前版本中，因此在提交时破坏数据可能会破坏历史记录的绝大部分内容。

Answer 2

我认为颠覆做了一些反向构建的尝试。但我可以更好地解释我所知道的：水银快照。

Mercurial使用前向构建方案。但为了使每个修订版本都可以轻松重建，还有重新同步点：每次重建修订所需的所有delta的大小都大于全文的两倍时，就会存储全文本（压缩的快照），并且所有后续的增量都是相对于这个新快照计算的。

这意味着您不需要阅读超过文本大小的3倍来检索任何修订。

你可以找到更多的细节in the Hg Book。

Answer 3

作为一个更一般的答案，您需要区分来自DVCS（Distributed VCS, like Git or Mercurial）的CVCS（集中式VCS，如CVS，SVN，Perforce，ClearCase，...）。
他们涉及different workflows and usage。

特别是，CVCS 客户和服务器之间的数据交换会比用DVCS

这就是为什么三角洲是（推动或拉动全部回购时真正需要增量）更重要对于CVCS中的大多数操作来说非常重要，这对于DVCS中的某些操作和不同原因而言是非常重要的。

三角洲在埃里克库描述了两本书：

• Source Control HOWTO，章Chapter 4: Repositories：

库=文件系统*时间

树是文件夹层次结构和文件。三角洲是两棵树之间的差异。理论上，这两棵树不需要关联。然而，在实践中，我们计算它们之间差异的唯一原因是因为其中一个来源于另一个。一些开发人员从树N开始并做了一个或多个更改，导致树N + 1。

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

德尔塔检测很重要（请参阅this thread）：正向德尔塔或反向德尔塔。

一些SCM工具使用某种妥协设计。在一种方法中，我们不是只存储一棵完整的树，而是将其他所有的树表示为一个三角洲，我们在这条路上洒了几棵满树。

您可以在Eric Raymond's Understanding Version-Control Systems中看到“旧”VCS的演变。

• Version Control by Example，Chapter 12. DVCS Internals：

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

不要忘记，三角洲管理也有对代表史上创造了Directed Acyclic Graphs (DAGs)的影响（参见“Arrows direction in ProGit book”和inconvenient behind DAG）。

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

• 混帐： “Is the git binary diff algorithm (delta storage) standardized?”
• 水银： “Mercurial: Repository Structure”
• 准确性的（它结合了两者的方法）： “Veracity: DAGs and Data”

Veracity支持两个种的DAG：

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

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

这最后点说明第三（第四？）代VCS必须应对的不仅是文件（树）也数据库分布（出于各种目的）