背景

Linux 作為最大也是最成功的開源項目，吸引了全球程序員的貢獻，到目前為止，共有兩萬多名開發者給 Linux Kernel 提交過代碼。令人驚訝的是，在項目的前十年(1991 ~ 2002)中，Linus 作為項目管理員并沒有借助任何配置管理工具，而是以手工方式通過 patch 來合并大家提交的代碼。倒不是說 Linus 喜歡手工處理，而是因為他對于軟件配置管理工具(SCM)非常挑剔，無論是商用的 clearcase 還是開源的 cvs、svn 等都不能入他的法眼。在他看來，一個能夠滿足 Linux 內核項目開發使用的版本控制系統需要滿足幾個條件：1) 快 2)支持多分支場景（幾千個分支并行開發場景） 3) 分布式 4) 能夠支持大型項目。直到2002年，Linus 終于找到了一款基本滿足他要求的工具——BitKeeper, 而 BitKeeper 是商業工具，他們愿意給 Linux 社區免費使用，但是需要保證遵守不得進行反編譯等條款。BitKeeper 提供的默認接口顯然不能滿足社區用戶的全部需要，一位社區開發者反編譯 BitKeeper 并利用了未公開接口，這讓 BitKeeper 公司撤回了免費使用的 License。不得已，Linus 利用假期十天時間，實現一款 DVCS —— Git，并推送給社區開發者們使用。

設計

Git 已經成為全球軟件開發者的標配，關于 Git 的介紹和用法不需多說，我今天想要談談 Git 的內部實現。不過在看本文之前，我先給大家提一個問題：如果是你來設計 git（或者重新設計 git），你打算怎么設計？第一個版本發布準備實現哪些功能？看完本文，再對照自己的想法做個比較。歡迎留言討論。

學習 Git 的內部實現，最好的辦法是看 Linus 最初的代碼提交，checkout 出 git 項目的第一次提交節點，可以看到代碼庫中只有幾個文件：一個 README，一個構建腳本Makefile，剩下幾個 C 源文件。這次 commit 的備注寫的也非常特別：Initial revision of "git", the information manager from hell.

commite83c5163316f89bfbde7d9ab23ca2e25604af290 Author:LinusTorvalds Date:ThuApr715132005-0700 Initialrevisionof"git",theinformationmanagerfromhell

在 README 中，Linus 詳細描述了 Git 的設計思路。看似復雜的 Git 工作，在 Linus 的設計里，只有兩種對象抽象：1) 對象數據庫("object database")；2) 當前目錄緩存("current directory cache")。

Git 的本質就是一系列的文件對象集合，代碼文件是對象、文件目錄樹是對象、commit 也是對象。這些文件對象的名稱即內容的 SHA1 值，SHA1 哈希算法的值為40位。Linus 將前二位作為文件夾、后38位作為文件名。大家可以在 .git 目錄里的 objects 里看到有很多兩位字母/數字名稱的目錄，里面存儲了很多38位hash值名稱的文件，這就是 Git 的所有信息。Linus 在設計對象的數據結構時按照 <標簽ascii碼表示>(blob/tree/commit) + <空格> + <長度ascii碼表示> + <> + <二進制數據內容> 來定義，大家可以用 xxd 命令看下 objects 目錄里的對象文件(需 zlib 解壓)，比如一個 tree 對象文件內容如下：

00000000: 7472 6565 2033 3700 3130 3036 3434 2068 tree 37.100644 h 00000010: 656c 6c6f 2e74 7874 0027 0c61 1ee7 2c56 ello.txt.'.a..,V 00000020: 7bc1 b2ab ec4c bc34 5bab 9f15 ba {....L.4[....

對象有三種：BLOB、TREE、CHANGESET。

BLOB: 即二進制對象，這就是 Git 存儲的文件，Git 不像某些 VCS （如 SVN）那樣存儲變更 delta 信息，而是存儲文件在每一個版本的完全信息。比如先提交了一份 hello.c 進入了 Git 庫，會生成一個 BLOB 文件完整記錄 hello.c 的內容；對 hello.c 修改后，再提交 commit，會再生成一個新的 BLOB 文件記錄修改后的 hello.c 全部內容。Linus 在設計時，BLOB 中僅記錄文件的內容，而不包含文件名、文件屬性等元數據信息，這些信息被記錄在第二種對象 TREE 里。

TREE: 目錄樹對象。在 Linus 的設計里 TREE 對象就是一個時間切片中的目錄樹信息抽象，包含了文件名、文件屬性及BLOB對象的SHA1值信息，但沒有歷史信息。這樣的設計好處是可以快速比較兩個歷史記錄的 TREE 對象，不能讀取內容，而根據 SHA1 值顯示一致和差異的文件。另外，由于 TREE 上記錄文件名及屬性信息，對于修改文件屬性或修改文件名、移動目錄而不修改文件內容的情況，可以復用 BLOB 對象，節省存儲資源。而 Git 在后來的開發演進中又優化了 TREE 的設計，變成了某一時間點文件夾信息的抽象，TREE 包含其子目錄的 TREE 的對象信息（SHA1）。這樣，對于目錄結構很復雜或層級較深的 Git庫 可以節約存儲資源。歷史信息被記錄在第三種對象 CHANGESET 里。

CHANGESET: 即 Commit 對象。一個 CHANGESET 對象中記錄了該次提交的 TREE 對象信息（SHA1），以及提交者(committer)、提交備注(commit message)等信息。跟其他SCM（軟件配置管理）工具所不同的是，Git 的 CHANGESET 對象不記錄文件重命名和屬性修改操作，也不會記錄文件修改的 Delta 信息等，CHANGESET 中會記錄父節點 CHANGESET 對象的 SHA1 值，通過比較本節點和父節點的 TREE 信息來獲取差異。Linus 在設計 CHANGESET 父節點時允許一個節點最多有 16 個父節點，雖然超過兩個父節點的合并是很奇怪的事情，但實際上，Git 是支持超過兩個分支的多頭合并的。

Linus 在三種對象的設計解釋后著重闡述了可信(TRUST)：雖然 Git 在設計上沒有涉及可信的范疇，但 Git 作為配置管理工具是可以做到可信的。原因是所有的對象都以SHA1編碼（Google 實現 SHA1 碰撞攻擊是后話，且 Git 社區也準備使用更高可靠性的 SHA256 編碼來代替），而簽入對象的過程可信靠簽名工具保證，如 GPG 工具等。

理解了Git 的三種基本對象，那么對于 Linus 對于 Git 初始設計的“對象數據庫”和“當前目錄緩存”這兩層抽象就很好理解了。加上原本的工作目錄，Git 有三層抽象，如下圖示：一個是當前工作區(Working Directory)，也就是我們查看/編寫代碼的地方，一個是 Git 倉庫(Repository),即 Linus 說的對象數據庫，我們在 Git 倉看到的 .git 文件夾中存儲的內容，Linus 在第一版設計時命名為 .dircache，在這兩個存儲抽象中還有一層中間的緩存區（Staging Area），即 .git/index 里存儲的信息，我們在執行 git add 命令時，便是將當前修改加入到了緩存區。

Linus 解釋了“當前目錄緩存”的設計，該緩存就是一個二進制文件，內容結構很像 TREE 對象，與 TREE 對象不同的是 index 不會再包含嵌套 index 對象，即當前修改目錄樹內容都在一個 index 文件里。這樣設計有兩個好處：1. 能夠快速的復原緩存的完整內容，即使不小心把當前工作區的文件刪除了，也可以從緩存中恢復所有文件；2. 能夠快速找出緩存中和當前工作區內容不一致的文件。

實現

Linus 在 Git 的第一次代碼提交里便完成了 Git 的最基礎功能，并可以編譯使用。代碼極為簡潔，加上 Makefile 一共只有 848 行。感興趣的同事可以通過上一段所述方法 checkout Git 最早的 commit 上手編譯玩玩，只要有 Linux 環境即可。因為依賴庫版本的問題，需要對原始 Makefile 腳本做些小修改。Git 第一個版本依賴 openssl 和 zlib 兩個庫，需要手工安裝這兩個開發庫。在 ubuntu 上執行：sudo apt install libssl-dev libz-dev ；然后修改 makefile 在 LIBS= -lssl 行 中的 -lssl 改成 -lcrypto 并增加 -lz ；最后執行 make，忽略編譯告警，會發現編出了7個可執行程序文件：init-db, update-cache, write-tree, commit-tree, cat-file, show-diff 和 read-tree.

下面分別簡要介紹下這些可執行程序的實現：

init-db: 初始化一個 git 本地倉庫，這也就是我們現在每次初始化建立 git 庫式敲擊的 git init 命令。只不過一開始 Linus 建立的 倉庫及 cache 文件夾名稱叫 .dircache, 而不是我們現在所熟知的 .git 文件夾。

update-cache: 輸入文件路徑，將該文件（或多個文件）加入緩沖區中。具體實現是：校驗路徑合法性，然后將文件計算 SHA1值，將文件內容加上 blob 頭信息進行 zlib 壓縮后寫入到對象數據庫(.dircache/objects)中；最后將文件路徑、文件屬性及 blob sha1 值更新到 .dircache/index 緩存文件中。

write-tree: 將緩存的目錄樹信息生成 TREE 對象，并寫入對象數據庫中。TREE 對象的數據結構為：'tree ' + 長度 + + 文件樹列表。文件樹列表中按照 文件屬性 + 文件名 + + SHA1 值結構存儲。寫入對象成功后，返回該 TREE 對象的 SHA1 值。

commit-tree: 將 TREE 對象信息生成 commit 節點對象并提交到版本歷史中。具體實現是輸入要提交的 TREE 對象 SHA1 值，并選擇輸入父 commit 節點（最多 16個），commit 對象信息中包含 TREE、父節點、committer 及作者的 name、email及日期信息，最后寫入新的 commit 節點對象文件，并返回 commit 節點的 SHA1 值。

cat-file: 由于所有的對象文件都經過 zlib 壓縮，因此想要查看文件內容的話需要使用這個工具來解壓生成臨時文件，以便查看對象文件的內容。

show-diff: 快速比較當前緩存與當前工作區的差異，因為文件的屬性信息（包括修改時間、長度等）也保存在緩存的數據結構中，因此可以快速比較文件是否有修改，并展示差異部分。

read-tree: 根據輸入的 TREE 對象 SHA1 值輸出打印 TREE 的內容信息。

這就是第一個可用版本的 Git 的全部七個子程序，可能用過 Git 的同事會說：這怎么跟我常用的 Git 命令不一樣呢？Git add, git commit 呢？是的，在最初的 Git 設計中是沒有我們這些平常所使用的 git 命令的。在 Git 的設計中，有兩種命令：分別是底層命令(Plumbing commands)和高層命令(Porcelain commands)。一開始，Linus 就設計了這些給開源社區黑客使用的符合 Unix KISS 原則的命令，因為黑客們本身就是動手高手，水管壞了就擼起袖子去修理，因此這些命令被稱為 plumbing commands. 后來接手 Git 的 Junio Hamano 覺得這些命令對于普通的用戶可不太友好，因此在此之上，封裝了更易于使用、接口更精美的高層命令，也就是我們今天每天使用的 git add, git commit 之類。Git add 就是封裝了 update-cache 命令，而 git commit 就是封裝了 write-tree, commit-tree 命令。關于底層命令的更詳細介紹，大家有興趣的話可以看 Pro Git 中的 Git Internals 章節。

具體的代碼實現在這里就不再細述，Linus 的代碼風格極為簡潔，能一行完成的絕不寫兩行。另外，對于 Linux API 的使用自然無人出其右，我印象最深的是有好多處使用 mmap 建立文件與內存的映射，省去了內存申請、文件讀寫等操作，提升了工具性能。正如一位同事說的：Linus 的代碼除了不滿足編程規范，其他好像真挑不出什么毛病。順便說一句，Linus 的縮進風格是 Tab 鍵（典故參見《制表符還是空格符，這是個問題》）。

啟示

Linus 在提交了第一個 git commit 后，并向社區發布了 git 工具。當時，社區中有位叫 Junio Hamano 的開發者覺得這個工具很有意思，便下載了代碼，結果發現一共才 1244 行代碼，這更令他驚奇也引發了極大的興趣。Junio 在郵件列表與 Linus 交流并幫助增加了 merge 等功能，而后持續打磨 git，最后 Junio 完全接手了 Git 的維護工作，Linus 則回去繼續維護 Linux Kernel 項目。

如果選歷史上最偉大的一次 Git 代碼提交，那一定是這 Git 工具項目本身的第一次代碼提交。這次代碼提交無疑是開創性的，如果說 Linux 項目促成了開源軟件的成功并改寫了軟件行業的格局，那么 Git 則是改變了全世界開發者的工作方式和寫作方式。在 Git 誕生后兩年，舊金山的一個小酒館里坐著三位年輕的程序員，決定要用 Git 做點什么，幾個月后，GitHub 上線。

回到文中開頭提到的問題，如果我來設計 Git 的話，估計還是會從已有工具經驗（如SVN使用）上來延伸設計，甚至在我最早接觸 Git 時候曾膚淺的認為 Git 就是 SVN + 分布式。正是了解了 Git 的內部原理乃至閱讀了 Git 的初始代碼后才感嘆其設計的精妙，Git 的初始設計和實現大概能給（開源）軟件產品如下啟發：

解決痛點問題：Git 的緣起便是 Linus 本人及 Linux 社區的訴求，而這些訴求推而廣之是項目協作開發（特別是跨地域項目）的共性訴求。Linus 解決了他本人遇到的痛點問題，順便達成了一項偉大的成就。

極簡設計：Linus 在設計 Git 工具時并沒有受傳統 SCM 工具的束縛，考慮文件差異、版本對比等，而是抽象了幾種基本對象就把 git 的設計思路給理清楚了。

MVP (minimum viable product, 最小可用產品)：這個概念大家都懂，但實際操作起來卻不容易。一個 MVP 的配置管理工具需要哪些功能？一般來說會想到代碼提交、歷史追溯、版本比較、分支合并等。但 Linus 卻將它拆解開來，快速實現了底層的基本功能，簡單到只有開源社區黑客才能用。但這就夠了，黑客們因此發現了它的價值，繼續給它添磚加瓦。

快速發布，快速迭代：這也是源于 Linux Kernel 的開發經驗；Linus 在實現了 Git MVP 后，便在 Linux 社區郵件列表中公布，并征求意見，迭代完善。

找到合適接班人：《大教堂與集市》中也有類似的觀點，它說的是：“如果你對一個項目失去了興趣，你最后的職責就是把它交給一個稱職的繼承者?！辈贿^ Linus 將 Git 交給 Junio 并不是因為失去了興趣，而是因為他發現在 Git 基礎架構建立好之后，Junio 比他更擅長于實現更豐富、對普通用戶界面更友好的功能，因此他就放心的將 Git 交給了 Junio. 為開源項目找到更合適的接班人，這既需要魄力也需要智慧。

原文標題：改變世界的一次代碼提交

文章出處：【微信公眾號：Linuxer】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq