源碼解析：Git的第一個送出是什麼樣的？

前言

Git 是目前世界上被最廣泛使用的現代軟體版本管理系統（Version Control System）。Git 本身亦是一個成熟并處于活躍開發狀态的開源項目，今天驚人數量的軟體項目依賴 Git 進行版本管理，這些項目包括開源以及各種商業軟體。Git 在職業軟體開發者中擁有良好的聲譽，Git 目前支援絕大多數的作業系統以及 IDE（Integrated Development Environments）。

Git 最初是由 Linux 作業系統核心的創造者 Linus Torvalds 在 2005 年創造，Git 第一個可用版本是 Linus 花了兩周時間用C寫出來的。Git 第一個版本就實作了 Git 源碼自托管，一個月之内，Linux系統的源碼也已經由 Git 管理了！

Git 的第一個送出源碼僅有約1000行，但是已經實作了Git的基本設計原理，比如初始化倉庫、送出代碼、檢視代碼diff、讀取送出資訊等，Git 定義了三個區：工作區（workspace）、暫存區（index）、版本庫（commit history），也實作了三類重要的 Git 對象：blob、tree、commit。本文将從源碼上分析 Git 的第一個送出并挖掘背後優秀的設計原理。

編譯

擷取源碼

在Github上可以找到Git的倉庫鏡像：

https://github.com/git/git.git

# 擷取 git 源碼
$ git clone https://github.com/git/git.git

# 檢視第一個送出
$ git log --date-order --reverse
commit e83c5163316f89bfbde7d9ab23ca2e25604af290
Author: Linus Torvalds <[email protected]>
Date:   Thu Apr 7 15:13:13 2005 -0700

    Initial revision of "git", the information manager from hell

# 變更為第一個送出，指定commit-id
$ git reset --hard e83c5163316f89bfbde7d9ab23ca2e25604af290           

檔案結構

$ tree -h
.
├── [2.4K]  cache.h
├── [ 503]  cat-file.c                  # 檢視objects檔案
├── [4.0K]  commit-tree.c               # 送出tree
├── [1.2K]  init-db.c                   # 初始化倉庫
├── [ 970]  Makefile
├── [5.5K]  read-cache.c                # 讀取目前索引檔案内容
├── [8.2K]  README
├── [ 986]  read-tree.c                 # 讀取tree
├── [2.0K]  show-diff.c                 # 檢視diff内容
├── [5.3K]  update-cache.c              # 添加檔案或目錄
└── [1.4K]  write-tree.c                # 寫入到tree

# 統計代碼行數，總共1089行
$ find . "(" -name "*.c" -or -name "*.h" -or -name "Makefile" ")" -print | xargs wc -l
 ...
 1089 total           

編譯第一個送出的Git會有編譯問題，需要更改Makefile添加相關的依賴庫：

$ git diff ./Makefile
... 
-LIBS= -lssl
+LIBS= -lssl -lz -lcrypto
...           

編譯：

# 編譯
$ make           

隻支援在 linux 平台上編譯運作。

源碼分析

Write programs that do one thing and do it well.

——Unix philosophy

檢視編譯生成的可執行檔案，總共有7個：

指令使用過程：

init-db：初始化倉庫

指令說明

$ init-db           

運作流程

建立目錄：.dircache。
建立目錄：.dircache/objects。
在 .dircache/objects 中建立了從 00 ~ ff 共256個目錄。

.dircache/ 是Git的工作目錄，最新版本的Git工作目錄為 .git/ 。

運作示例

# 運作init-db初始化倉庫
$ init-db
defaulting to private storage area

# 檢視初始化後的目錄結構
$ tree . -a
.
└── .dircache                   # git工作目錄
    └── objects                 # objects檔案
        ├── 00
        ├── 01
        ├── 02
        ├── ......              # 省略
        ├── fe
        └── ff
258 directories, 0 files           

最新版本Git使用 git init . 初始化倉庫，而且初始化工作目錄為 .git/，初始化後，.git/ 目錄中的檔案和功能也非常豐富，包括 .git/HEAD、.git/refs/ 、.git/info/ 等，以及很多的 hooks 示例：.git/hooks/**.sample。

update-cache：添加檔案或目錄

update-cache 主要是把工作區的修改檔案送出到暫存區。工作區、暫存區等說明見下文【設計原理】 。

指令使用

$ update-cache <file> ...           

讀取并解析索引檔案 ：.dircache/index。

周遊多個檔案，讀取并生成變更檔案資訊（檔案名稱、檔案内容sha1值、日期、大小等），寫入到索引檔案中。

周遊多個檔案，讀取并壓縮變更檔案，存儲到objects檔案中，該檔案為blob對象。

如果是剛初始化的倉庫，會自動建立索引檔案。索引檔案說明見下文【設計原理 - 索引檔案】。blob對象的檔案格式及說明見下文【設計原理 - blob對象】。sha1值說明見下文【設計原理 - 雜湊演算法】。

運作示例

# 新增README.md檔案
$ echo "hello git" > README.md

# 送出
$ update-cache README.md

# 檢視索引檔案
$ hexdump -C .dircache/index
00000000  43 52 49 44 01 00 00 00  01 00 00 00 af a4 fc 8e  |CRID............|
00000010  5e 34 9d dd 31 8b 4c 8e  15 ca 32 05 5a e9 a4 c8  |^4..1.L...2.Z...|
00000020  af bd 4c 5f bf fb 41 37  af bd 4c 5f bf fb 41 37  |..L_..A7..L_..A7|
00000030  00 03 01 00 91 16 d2 04  b4 81 00 00 ee 03 00 00  |................|
00000040  ee 03 00 00 0a 00 00 00  bb 12 25 52 ab 7b 40 20  |..........%R.{@ |
00000050  b5 f6 12 cc 3b bd d5 b4  3d 1f d3 a8 09 00 52 45  |....;...=.....RE|
00000060  41 44 4d 45 2e 6d 64 00                           |ADME.md.|
00000068


# 檢視objects内容，sha1值從索引檔案中擷取
$ cat-file bb122552ab7b4020b5f612cc3bbdd5b43d1fd3a8
temp_git_file_61uTTP: blob
$ cat ./temp_git_file_RwpU8b
hello git
           

cat-file：檢視objects檔案内容

cat-file 根據sha1值檢視暫存區中的objects檔案内容。cat-file 是一個輔助工具，在正常的開發工作流中一般不會使用到。

$ cat-file <sha1>           

根據入參sha1值定位objects檔案，比如 .dircache/objects/46/4b392e2c8c7d2d13d90e6916e6d41defe8bb6a

讀取該objects檔案内容，解壓得到真實資料。

寫入到臨時檔案 temp_git_file_XXXXXX（随機不重複檔案）。

objects内容為壓縮格式，基于zlib壓縮算法，objects說明見【設計原理 - objects 檔案】。

# cat-file 會把内容讀取到temp_git_file_rLcGKX
$ cat-file 82f8604c3652fa5762899b5ff73eb37bef2da795
temp_git_file_tBTXFM: blob

# 檢視 temp_git_file_tBTXFM 檔案内容
$ cat ./temp_git_file_tBTXFM 
hello git!           

show-diff：檢視diff内容

檢視工作區和暫存區中的檔案差異。

$ show-diff           

讀取并解析索引檔案：.dircache/index。

循環周遊變更檔案資訊，比較工作區中的檔案資訊和索引檔案中記錄的檔案資訊差異。

無差異，顯示 : ok。

有差異，調用 diff 指令輸出差異内容。

# 建立檔案并送出到暫存區
$ echo "hello git!" > README.md
$ update-cache README.md

# 目前無差異
$ show-diff
README.md: ok

# 更改README.md
$ echo "hello world!" > README.md

# 檢視diff
$ show-diff
README.md:  82f8604c3652fa5762899b5ff73eb37bef2da795
--- -   2020-08-31 17:33:50.047881667 +0800
+++ README.md   2020-08-31 17:33:47.827740680 +0800
@@ -1 +1 @@
-hello git!
+hello world!
           

write-tree：寫入到tree

write-tree 作用将儲存在索引檔案中的多個objects對象歸并到一個類型為tree的objects檔案中，該檔案即Git中重要的對象：tree。

$ write-tree           

循環周遊變更檔案資訊，按照指定格式編排變更檔案資訊及内容。

壓縮并存儲到objects檔案中，該object檔案為tree對象。

tree對象的檔案格式及相關說明見下文【設計原理 - tree對象】。

# 送出
$ write-tree
c771b3ab2fe3b7e43099290d3e99a3e8c414ec72

# 檢視objects内容
$ cat-file  c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
temp_git_file_r90ft5: tree
$ cat ./temp_git_file_r90ft5
100664 README.md��`L6R�Wb��_�>�{�-��           

read-tree：讀取tree

read-tree 讀取并解析指定sha1值的tree對象，輸出變更檔案的資訊。

$ read-tree <sha1>           

運作步驟

解析sha1值。

讀取對應sha1值的object對象。

輸出變更檔案的屬性、路徑、sha1值。

# 送出
$ write-tree
c771b3ab2fe3b7e43099290d3e99a3e8c414ec72

# 讀取tree對象
$ read-tree  c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
100664 README.md (82f8604c3652fa5762899b5ff73eb37bef2da795)           

commit-tree：送出tree

commit-tree 把本地變更送出到版本庫裡，具體是基于一個tree對象的sha1值建立一個commit對象。

$ commit-tree <sha1> [-p <sha1>]* < changelog           

參數解析。

擷取使用者名稱、使用者郵件、送出日期。

寫入tree資訊。

寫入parent資訊。

寫入author、commiter資訊。

寫入comments（注釋）。

壓縮并存儲到objects檔案中，該object檔案為commit對象。

commit對象的檔案格式及說明見下文【設計原理 - commit對象】。

# 寫入到tree
$ write-tree 
c771b3ab2fe3b7e43099290d3e99a3e8c414ec72

# 送出tree
$ echo "first commit" > changelog
$ commit-tree c771b3ab2fe3b7e43099290d3e99a3e8c414ec72 < changelog
Committing initial tree c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
7ea820bd363e24f5daa5de8028d77d88260503d9

# 檢視commit對象内容
$ cat-file 7ea820bd363e24f5daa5de8028d77d88260503d9
temp_git_file_CIfJsg: commit
$ cat temp_git_file_CIfJsg
tree c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
author Xiaowen Xia <chenan.xxw@aos-hw09> Tue Sep  1 10:56:16 2020
committer Xiaowen Xia <chenan.xxw@aos-hw09> Tue Sep  1 10:56:16 2020

first commit           

設計原理

Write programs to work together.

與傳統的集中式版本控制系統（CVCS）相反，Git 從一開始就設計成了去中心化的分布式系統，每個開發者本地工作區都是一個完整的版本庫，擁有本地的代碼倉庫。另外，Git 的設計初衷是為了讓更多的開發者一起開發軟體。

該版本 Git 定義了三種對象：

blob 對象：儲存着檔案快照。

tree 對象：記錄着目錄結構和 blob 對象索引。

commit 對象：包含着指向前述 tree 對象的指針和所有送出資訊。

三種對象互相之間的關系如下：

另外，Git 也定義了三個區，工作區（workspace），暫存區（index）和版本庫（commit history）：

• 工作區（workspace）：我們直接修改代碼的地方。
• 暫存區（index）：資料暫時存放的區域，用于在工作區和版本庫之間進行資料交流。
• 版本庫（commit history）：存放已經送出的資料。

每個可執行檔案的具體分工是：init-db 用來建立一個初始化倉庫，update-cache 會将 工作區 的變更寫到 索引檔案 （index）中，write-tree 會将之前的所有變更整理成 tree 對象，commit-tree 會将 指定的 tree 對象寫到本地版本庫中。另外，show-diff 用來檢視 工作區 和 暫存區 中的檔案差異，read-tree 用來讀取 tree對象 的資訊。

由此可以繪制一個簡單的Git開發工作流：

objects 檔案

objects檔案是載體，用來存儲Git中的3個重要對象：blob、tree、commit。

objects檔案的存儲目錄預設為.dircache/objects，也可以通過環境變量： SHA1_FILE_DIRECTORY 指定。檔案路徑和名稱根據sha1值決定，取sha1值的第一個位元組的hex值為目錄，其他位元組的hex值為名稱，比如sha1值為：

0277ec89d7ba8c46a16d86f219b21cfe09a611e1

的對象檔案存儲路徑為：

.dircache/objects/02/77ec89d7ba8c46a16d86f219b21cfe09a611e1

為了節約存儲，同時也能存儲多個資訊，objects檔案内容都是經過 zlib 壓縮過的。objects檔案的格式由 + + <要存儲的内容> 組成，其中 可以是"blob"（blob對象）、"tree"（tree對象）、"commit"（commit對象）。

使用 cat-file 可以檢視object檔案是什麼類型的對象。

.dircache/objects 目錄結構如下：

$ tree .git/objects
.git/objects
├── 02
│   └── 77ec89d7ba8c46a16d86f219b21cfe09a611e1
├── ......                                          # 省略
├── be
│   ├── adb5bac00c74c97da7f471905ab0da8b50229c
│   └── ee7b5e8ab6ae1c0c1f3cfa2c4643aacdb30b9b
├── ......                                          # 省略
├── c9
│   └── f6098f3ba06cf96e1248e9f39270883ba0e82e
├── ......                                          # 省略
├── cf
│   ├── 631abbf3c4cec0911cb60cc307f3dce4f7a000
│   └── 9e478ab3fc98680684cc7090e84644363a4054
├── ......                                          # 省略
└── ff           

問：為什麼 .dircache/objects/ 目錄下面要以sha1值前一個位元組的hex值作為子目錄？

blob 對象

運作 update-cache 會生成 blob 對象。

blob 對象用于存儲變更檔案内容，其實就代表一個變更檔案快照。blob 對象由 + + 拼裝并壓縮：

使用 cat-file 檢視 blob 對象内容：

# 檢視 blob 對象内容
$ cat-file 82f8604c3652fa5762899b5ff73eb37bef2da795temp_git_file_tBTXFM: blob

$ cat ./temp_git_file_tBTXFM 
hello git!           

tree 對象

運作 write-tree 會生成 tree 對象。

tree 對象用于存儲多個送出檔案的資訊。tree 對象由 + + 檔案模式 + 檔案名稱 + 檔案sha1值 拼裝并壓縮：

檔案sha1值 使用binary格式存儲，占用20位元組。

使用 cat-file 檢視 tree 對象内容：

# 檢視 tree 對象内容
$ cat-file  c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
temp_git_file_r90ft5: tree

$ cat ./temp_git_file_r90ft5
100664 README.md��`L6R�Wb��_�>�{�-��           

檔案sha1值 使用binary格式存儲，是以列印的時候會有亂碼。

commit 對象

運作 commit-tree 會生成 commit 對象。

commit 對象存儲一次送出的資訊，包括所在的tree資訊，parent資訊以及送出的作者等資訊。commit 對象由 + + + * + + + 拼裝并壓縮：

tree sha1值 和 parent sha1值 使用hex字元串格式存儲，占用40位元組。

使用 cat-file 檢視 commit 對象内容：

# 檢視 commit 對象内容
$ cat-file 7ea820bd363e24f5daa5de8028d77d88260503d9
temp_git_file_CIfJsg: commit

$ cat temp_git_file_CIfJsg
tree c771b3ab2fe3b7e43099290d3e99a3e8c414ec72
author Xiaowen Xia <chenan.xxw@aos-hw09> Tue Sep  1 10:56:16 2020
committer Xiaowen Xia <chenan.xxw@aos-hw09> Tue Sep  1 10:56:16 2020

first commit           

索引檔案

索引檔案預設路徑為：.dircache/index。索引檔案用來存儲變更檔案的相關資訊，當運作 update-cache 時會添加變更檔案的資訊到索引檔案中。

同時也有一個叫 .dircache/index.lock 的檔案，該檔案存在時表示目前工作區被鎖定，無法進行送出操作。

使用 hexdump 指令可以檢視到索引檔案内容：

$ hexdump -C .dircache/index 
00000000  43 52 49 44 01 00 00 00  01 00 00 00 ae 73 c4 f2  |CRID.........s..|
00000010  ce 32 c9 6f 13 20 0d 56  9c e8 cf 0d d3 75 10 c8  |.2.o. .V.....u..|
00000020  94 ad 4c 5f f4 5c 42 06  94 ad 4c 5f f4 5c 42 06  |..L_.\B...L_.\B.|
00000030  00 03 01 00 91 16 d2 04  b4 81 00 00 ee 03 00 00  |................|
00000040  ee 03 00 00 0b 00 00 00  a3 f4 a0 66 c5 46 39 78  |...........f.F9x|
00000050  1e 30 19 a3 20 42 e3 82  84 ee 31 54 09 00 52 45  |.0.. B....1T..RE|
00000060  41 44 4d 45 2e 6d 64 00                           |ADME.md.|           

.dircache/index 索引檔案使用二進制存儲相關内容，該檔案由 檔案頭 + 變更檔案資訊 組成：

檔案頭大小為32位元組，一個變更檔案資訊大小至少是63位元組。其中：檔案頭中的sha1值由整個索引檔案内容（檔案頭 + 變更檔案資訊）計算得到的。變更檔案資訊的sha1值由變更檔案内容（壓縮後）計算得到的。

雜湊演算法

該 Git 版本中使用的雜湊演算法為 sha1算法 ，代碼中使用的是 OpenSSL 庫中提供的sha1算法。

目前 Git 已經有了新的選擇：sha256算法 ，且目前正在做 sha1 到 sha256 的遷移。

#include <openssl/sha.h>

static int verify_hdr(struct cache_header *hdr, unsigned long size)
{
  SHA_CTX c;
  unsigned char sha1[20];
        /* 省略 */
  /* 計算索引檔案頭sha1值 */
  SHA1_Init(&c);
  SHA1_Update(&c, hdr, offsetof(struct cache_header, sha1));
  SHA1_Update(&c, hdr+1, size - sizeof(*hdr));
  SHA1_Final(sha1, &c);
  /* 省略 */
  return 0;
}
           

總結與思考

Use software leverage to your advantage.

好的代碼不是寫出來的，是改出來的

Git 的第一個送出中，雖然實作了 Git 的分布式核心思想，以及三種對象，三個區等核心概念，但是 Git 的靈魂功能比如分支政策、遠端倉庫、日志系統、git hooks 等功能都是後面逐漸疊代出來的。

關于細節

問：為什麼 .dircache/objects/ 目錄下面要以 sha1 值前一個位元組的 hex 值作為子目錄？

答：ext3 檔案系統下，一個目錄下隻能有 32000 個一級子檔案，如果都把 objects 檔案存儲到一個 .git/objects/ 目錄裡，很大機率會達到上限。同時要是一個目錄下面子檔案太多，那檔案查找效率會降低很多。

關于代碼品質

Git 的第一次送出源碼，從代碼品質、資料結構上看其實并沒有多少參考價值，反而我還發現了很多可以優化的地方，比如：

• 異常處理不完善，經常出現段錯誤（SegmentFault）。
• 存在幾處記憶體洩漏的地方，比如 write-tree.c > main函數 > buffer記憶體塊 。
• 從索引檔案中讀取到的變更檔案資訊使用數組存儲，涉及到了比較多的申請釋放操作，性能上是有損失的，可以優化成連結清單存儲。

不過這些都不重要，重要的是 Git 的設計原理和思想。

招聘

如果你是一個懂代碼，愛 Git，有技術夢想的工程師，并想要和我們一起打造世界 NO.1 的代碼服務和産品，請聯系我吧！C/C++/Golang/Java 我們都要 (=´∀｀)人(´∀｀=)

If not now, when? If not me, who?

歡迎投遞履歷到郵箱：[email protected]

參考資料

Git官方網站：

https://git-scm.com

Git官方文檔中心：

https://git-scm.com/doc

Git官網的Git底層原理介紹：Git Internals - Git Objects

zlib 官方網站：

http://zlib.net

淺析Git存儲—對象、打封包件及打封包件索引

(

https://www.jianshu.com/p/923bf0485995)

深入了解Git - 一切皆commit

https://www.cnblogs.com/jasongrass/p/10582449.html)

深入了解Git - Git底層對象(

https://www.cnblogs.com/jasongrass/p/10582465.html)