如何存儲和計算版本控制歷史記錄？

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必須應對的不僅是文件（樹）也數據庫分佈（出於各種目的）