本文將系統(tǒng)分享 Git 底層知識(shí)：對(duì)象生命周期變化，底層數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)包文件結(jié)構(gòu)，數(shù)據(jù)包文件索引，以及詳細(xì)分析對(duì)象查詢流程和算法。

狀態(tài)模型

上圖描述了 git 對(duì)象的在不同的生命周期中不同的存儲(chǔ)位置，通過不同的 git 命令改變 git 對(duì)象的存儲(chǔ)生命周期。

工作區(qū) （workspace）

就是我們當(dāng)前工作空間，也就是我們當(dāng)前能在本地文件夾下面看到的文件結(jié)構(gòu)。初始化工作空間或者工作空間 clean 的時(shí)候，文件內(nèi)容和 index 暫存區(qū)是一致的，隨著修改，工作區(qū)文件在沒有 add 到暫存區(qū)時(shí)候，工作區(qū)將和暫存區(qū)是不一致的。

暫存區(qū) （index）

老版本概念也叫 Cache 區(qū)，就是文件暫時(shí)存放的地方，所有暫時(shí)存放在暫存區(qū)中的文件將隨著一個(gè) commit 一起提交到 local repository 此時(shí) local repository 里面文件將完全被暫存區(qū)所取代。暫存區(qū)是 git 架構(gòu)設(shè)計(jì)中非常重要和難理解的一部分。

本地倉(cāng)庫(kù) （local repository）

git 是分布式版本控制系統(tǒng)，和其他版本控制系統(tǒng)不同的是他可以完全去中心化工作，你可以不用和中央服務(wù)器 （remote server） 進(jìn)行通信，在本地即可進(jìn)行全部離線操作，包括 log，history，commit，diff 等等。完成離線操作最核心是因?yàn)?git 有一個(gè)幾乎和遠(yuǎn)程一樣的本地倉(cāng)庫(kù)，所有本地離線操作都可以在本地完成，等需要的時(shí)候再和遠(yuǎn)程服務(wù)進(jìn)行交互。

遠(yuǎn)程倉(cāng)庫(kù) （remote repository）

中心化倉(cāng)庫(kù)，所有人共享，本地倉(cāng)庫(kù)會(huì)需要和遠(yuǎn)程倉(cāng)庫(kù)進(jìn)行交互，也就能將其他所有人內(nèi)容更新到本地倉(cāng)庫(kù)把自己內(nèi)容上傳分享給其他人。結(jié)構(gòu)大體和本地倉(cāng)庫(kù)一樣。

文件在不同的操作下可能處于不同的 git 生命周期，下面看看一個(gè)文件變化的例子。

文件變化

對(duì)象模型

倉(cāng)庫(kù)結(jié)構(gòu)

git 分布式的一個(gè)重要體現(xiàn)是 git 在本地是有一個(gè)完整的 git 倉(cāng)庫(kù)也就是 .git 文件目錄，通過這個(gè)倉(cāng)庫(kù)，git 就可以完全離線化操作。在這個(gè)本地化的倉(cāng)庫(kù)中存儲(chǔ)了 git 所有的模型對(duì)象。下面是 git 倉(cāng)庫(kù)的 tree 和相關(guān)說明：

git 主要有四個(gè)對(duì)象，分別是 Blob，Tree， Commit， Tag 他們都用 SHA-1 進(jìn)行命名。

你可以用 git cat-file -t 查看每個(gè) SHA-1 的類型，用 git cat-file -p 查看每個(gè)對(duì)象的內(nèi)容和簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。git cat-file 是 git 的瑞士軍刀，是底層核心命令。

Blob 對(duì)象

只用于存儲(chǔ)單個(gè)文件內(nèi)容，一般都是二進(jìn)制的數(shù)據(jù)文件，不包含任何其他文件信息，比如不包含文件名和其他元數(shù)據(jù)。

Tree 對(duì)象

對(duì)應(yīng)文件系統(tǒng)的目錄結(jié)構(gòu)，里面主要有：子目錄 （tree），文件列表 （blob），文件類型以及一些數(shù)據(jù)文件權(quán)限模型等。

如下圖輸出：

詳細(xì)解釋如下：

Commit 對(duì)象

是一次修改的集合，當(dāng)前所有修改的文件的一個(gè)集合，可以類比一批操作的“事務(wù)”。是修改過的文件集的一個(gè)快照，隨著一次 commit 操作，修改過的文件將會(huì)被提交到 local repository 中。通過 commit 對(duì)象，在版本化中可以檢索出每次修改內(nèi)容，是版本化的基石。

→ git cat-file -t fbf9e415f77008b780b40805a9bb996b37a6ad2ccommit→ git cat-file -p fbf9e415f77008b780b40805a9bb996b37a6ad2ctree bd31831c26409eac7a79609592919e9dcd1a76f2parent d62cf8ef977082319d8d8a0cf5150dfa1573c2b7author xxx 1502331401 +0800committer xxx 1502331401 +0800修復(fù)增量bug

詳細(xì)解釋如下：

Tag 對(duì)象

tag 是一個(gè)“固化的分支”，一旦打上 tag 之后，這個(gè) tag 代表的內(nèi)容將永遠(yuǎn)不可變，因?yàn)?tag 只會(huì)關(guān)聯(lián)當(dāng)時(shí)版本庫(kù)中最后一個(gè) commit 對(duì)象。

分支的話，隨著不斷的提交，內(nèi)容會(huì)不斷的改變，因?yàn)榉种е赶虻淖詈笠粋€(gè) commit 不斷改變。所以一般應(yīng)用或者軟件版本的發(fā)布一般用 tag。

git 的 Tag 類型有兩種：

1 lightweight （輕量級(jí)）

創(chuàng)建方式：

git tag tagName

這種方式創(chuàng)建的 Tag，git 底層不會(huì)創(chuàng)建一個(gè)真正意義上的 tag 對(duì)象，而是直接指向一個(gè) commit 對(duì)象，此時(shí)如果使用 git cat-file -t tagName 會(huì)返回一個(gè) commit。

→ git cat-file -t v4commit→ git cat-file -p v4tree ceab4f96440655b0ff1a783316c95450fa1fb436parent 7f23c9ca70ce64fc58e8c7507c990c6c6a201d3dauthor 與水 1506224164 +0800committer 與水 1506224164 +0800

rawtest2

2 annotated （含附注）

創(chuàng)建方式：

git tag -a tagName -m‘’

這種方式創(chuàng)建的標(biāo)簽，git 底層會(huì)創(chuàng)建一個(gè) tag 對(duì)象，tag 對(duì)象會(huì)包含相關(guān)的 commit 信息和 tagger 等額外信息，此時(shí)如果使用 git cat-file -t tagname會(huì)返回一個(gè) tag。

→ git cat-file -t v3tag→ git cat-file -p v3object d5d55a49c337d36e16dd4b05bfca3816d8bf6de8 //commit 對(duì)象SHA-1type committag v3tagger xxx 1506230900 +0800

與水測(cè)試標(biāo)注型tag

總結(jié)：所有對(duì)象模型之間的關(guān)系大致如下：

存儲(chǔ)模型

概念

git 區(qū)別與其他 vcs 系統(tǒng)的一個(gè)最主要原因之一是：git 對(duì)文件版本管理和其他 vcs 系統(tǒng)對(duì)文件版本的實(shí)現(xiàn)理念完成不一樣。這也就是 git 版本管理為什么如此強(qiáng)大的最核心的地方。

Svn 等其他的 VCS 對(duì)文件版本的理念是以文件為水平維度，記錄每個(gè)文件在每個(gè)版本下的 delta 改變。

Git 對(duì)文件版本的管理理念卻是以每次提交為一次快照，提交時(shí)對(duì)所有文件做一次全量快照，然后存儲(chǔ)快照引用。

Git 在存儲(chǔ)層，如果文件數(shù)據(jù)沒有改變的文件，Git 只是存儲(chǔ)指向源文件的一個(gè)引用，并不會(huì)直接多次存儲(chǔ)文件，這一點(diǎn)可以在 pack 文件中看見。

如下圖所示：

存儲(chǔ)

隨著需求和功能的不斷復(fù)雜，git 版本的不斷更新，但是主要的存儲(chǔ)模型還是大致不變。如下圖所示：

檢索模型

→ cd .git/objects/→ ls03 28 7f ce d0 d5 e6 f9 info pack

git 的對(duì)象有兩種：

一種是松散對(duì)象，就是在如上 .git/objects 的文件夾 03 28 7f ce d0 d5 e6 f9等，這些文件夾只有 2 個(gè)字符開頭，其實(shí)就是每個(gè)文件 SHA-1 值的前 2 個(gè)字母，最多有 #OXFF 256 個(gè)文件夾。

一種是打包壓縮對(duì)象，打包壓縮之后的對(duì)象主要存在的是 pack 文件中，主要用于文件在網(wǎng)絡(luò)上傳輸，減少網(wǎng)絡(luò)消耗。

為了節(jié)省存儲(chǔ)空間，可以手動(dòng)觸發(fā)打包壓縮操作 （git gc），將松散對(duì)象打包成 pack 文件對(duì)象。也可以將 pack 文件解壓縮成松散對(duì)象 （git unpack-objects）

→ cd pack→ lspack-efbf3149604d24e6ea427b025da0c59245b2c2ea.idx pack-efbf3149604d24e6ea427b025da0c59245b2c2ea.pack

為了加快 pack 文件的檢索效率，git 基于 pack 文件會(huì)生成相應(yīng)的索引 idx 文件。

pack 文件

pack 文件設(shè)計(jì)非常精密和巧妙，本著降低文件大小，減少文件傳輸，降低網(wǎng)絡(luò)開銷和安全傳輸?shù)脑瓌t設(shè)計(jì)的。

pack 文件設(shè)計(jì)的概圖如下：

pack 文件主要有三部分組成，Header， Body， Trailer

Header 部分主要 4-byte “PACK”， 4-byte “版本號(hào)”， 4-byte “Object 條目數(shù)”。

Body 部分主要是一個(gè)個(gè) Git 對(duì)象依次存儲(chǔ)，存儲(chǔ)位置在 idx 索引文件中記錄改對(duì)象在 pack 文件中的偏移量 offset。

Trailer 部分主要是所有 Objects 的名 （SHA-1）的校驗(yàn)和，為了安全可靠的文件傳輸。

下面我們看具體的 pack 文件：

從上圖可知：通過 idx 索引文件在 pack 文件中定位到對(duì)象之后，對(duì)象的結(jié)構(gòu)主要 Header 和 Data 兩部分。

1 Header 部分

Header 中首 8-bits：1-bit 是 MSB，接著的 3-bits 表示的是當(dāng)前對(duì)象類型，主要有 6種存儲(chǔ)類型，接著的 4-bits 是用于表示該 Object 展開的 （length） 大小的一部分，只是一部分，完整的大小取決于MSB和接下來的多個(gè) bits，完整算法如下：

如果 8-bits 中第一位是 1，表示下一個(gè)字節(jié)還是 header 的一部分，用于表示該對(duì)象展開的大小。

如果 8-bits 中第一位是 0，表示從下一個(gè)字節(jié)開始，將是數(shù)據(jù) Data 文件。

如果對(duì)象類型是 OBJ_OFS_DELTA 類型， 表示的是 Delta 存儲(chǔ)，當(dāng)前 git 對(duì)象只是存儲(chǔ)了增量部分，對(duì)于基本的部分將由接下來的可變長(zhǎng)度的字節(jié)數(shù)用于表示 base object 的距離當(dāng)前對(duì)象的偏移量，接下來的可變字節(jié)也是用 1-bit MSB 表示下一個(gè)字節(jié)是否是可變長(zhǎng)度的組成部分。對(duì)偏移量取負(fù)數(shù)，就可知 base 對(duì)象在當(dāng)前對(duì)象的前面多少字節(jié)。

如果對(duì)象類型是 OBJ_REF_DELTA 類型，表示的是 Delta 存儲(chǔ)，當(dāng)前 git 對(duì)象只是存儲(chǔ)了增量部分，對(duì)于基本的部分，用 20-bytes 存儲(chǔ) Base Object 的 SHA-1 。

2 Data 部分

是經(jīng)過 Zlib 壓縮過的數(shù)據(jù)。可能是全部數(shù)據(jù)，也有可能是 Delta 數(shù)據(jù)，具體看 Header 部分的存儲(chǔ)類型，如果是 OBJ_OFS_DELTA 或者 OBJ_REF_DELTA 此處存儲(chǔ)的就是增量 （Delta） 數(shù)據(jù)，此時(shí)如果要取得全量數(shù)據(jù)的話，需要遞歸的找到最 Base Object，然后 apply delta 數(shù)據(jù)，在 base object 基礎(chǔ)上進(jìn)行 apply delta 數(shù)據(jù)也是非常精妙的，此文暫不做介紹。

從上面可以很清晰知道 pack 文件格式，我們?cè)購(gòu)谋镜貍}(cāng)庫(kù)中一探究竟：

不是增量 delta 格式：

SHA-1 type size size-in-packfile offset-in-packfile

增量 delta 格式：

如 399334856af4ca4b49c0008a25b6a9f524e40350（SHA-1） 表示對(duì)象的 base object SHA-1 是 cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804，base 對(duì)象最大深度 （depth） 為 1，如果cb5a93c4cf9c0ee5b7153a3a35a4fac7a7584804 還有引用對(duì)象，則改變 depth 為 2。

pack Header 中最后 4-bytes 用于表示的 pack 文件中 objects 的數(shù)量，最多 2 的 32 次方個(gè)對(duì)象，所以一些大的工程中有多個(gè) pack 文件和多個(gè) idx 文件。

文件的 size （文件解壓縮后大小） 有什么用呢，這個(gè)是為了方便我們進(jìn)行解壓的時(shí)候，設(shè)置流的大小，也就是方便知道流有多大。這里 size 不是說明下一個(gè)文件的偏移量，偏移量都是來自索引文件，見下面 idx：

index 文件

由于 version1 比較簡(jiǎn)單，下面用 version2 為例子：

分層模式：Header，F(xiàn)anout，SHA，CRC，Offset，Big File Offset，Trailer。

Header 層

version2 的 Header 部分總共有 8-bytes，version 1 的 header 部分是沒有的，前 4-bytes 總是 255， 116， 79， 99 因?yàn)檫@個(gè)也是版本 1 的開頭四個(gè)字節(jié)，后面 4-bytes 用于表示的是版本號(hào)，在當(dāng)前就是 version 2。

Fanout 層

fanout 層是 git 的亮點(diǎn)設(shè)計(jì)，也叫 Fanout Table（扇表）。fanout 數(shù)組中存儲(chǔ)的是相關(guān)對(duì)象的數(shù)目，數(shù)組下標(biāo)是對(duì)應(yīng) 16 進(jìn)制數(shù)。fanout 最后一個(gè)存儲(chǔ)的是整個(gè) pack 文件中所有對(duì)象的總數(shù)量。Fanout Table 是整個(gè) git 檢索的核心，通過它我們可以快速進(jìn)行查詢，用于定位 SHA 層的數(shù)組起始 - 終止下標(biāo)，定位好 SHA 層范圍之后，就可以對(duì) SHA 層進(jìn)行二分查找了，而不用對(duì)所有對(duì)象進(jìn)行二分查找。

fanout 總共 256 個(gè)，剛好是十六進(jìn)制的 #0xFF。fanout 數(shù)組用 SHA 的前面 2 個(gè)字符作為下標(biāo)（對(duì)應(yīng) .git/objects 中的松散文件目錄名，將 16 進(jìn)制的目錄名轉(zhuǎn)換 10 進(jìn)制數(shù)字），里面值就是用這兩個(gè)字符開頭的文件數(shù)量，而且是逐層累加的，后面的數(shù)組數(shù)量是包含前面數(shù)組的數(shù)據(jù)的個(gè)數(shù)的一個(gè)累加。

舉例如下：

1）如果數(shù)組下標(biāo)為 0，且 Fanout［0］ = 10 代表著 #0x00 開頭的 SHA-1 值的總數(shù)為 10 個(gè)。

2） 如果數(shù)組下標(biāo)為 1，且 Fanout［1］ = 15 代表著小于 #0x01 開頭的 SHA-1 值的總數(shù)為 15 個(gè)，從 Fanout［0］ = 10 知 Fanout［1］ = （15-10）

為什么 git 設(shè)計(jì)上 Fanout［n］ 會(huì)累加 Fanout［n-1］ 的數(shù)量？這個(gè)主要是為了快速確定 SHA 層檢索的初始位置，而不用每次去把前面所有 fanout［。.n-1］ 數(shù)量進(jìn)行累加。

SHA 層

是所有對(duì)象的 SHA-1 的排序，按照名稱排序，按照名稱進(jìn)行排序是為了用二分搜索進(jìn)行查找。每個(gè) SHA-1 值占 20-bytes。

CRC 層

由于文件打包主要解決網(wǎng)絡(luò)傳輸問題，網(wǎng)絡(luò)傳輸?shù)臅r(shí)候必須通過 crc 進(jìn)行校驗(yàn)，避免傳輸過程中的文件損壞。CRC 數(shù)組對(duì)應(yīng)的是每個(gè)對(duì)象的 CRC 校驗(yàn)和。

Offset 層

是由 4 byte 字節(jié)所組成，表示的是每個(gè) SHA-1 文件的偏移量，但是如果文件大于 2G 之后，4 byte 字節(jié)將無法表示，此時(shí)將：

4 byte 中的第一 bit 就是 MSB，如果是 1 表示的是文件的偏移量是放在第 6 層去存儲(chǔ)，此時(shí)剩下的 31-bits 將表示文件在 Big File Offset 中的偏移量，也就是圖中的，通過 Big File Offset 層 就可以知道對(duì)象在 pack 中的 offset。

4 byte 中的第一 bit 就是 MSB，如果是 0 31-bits 表示的存儲(chǔ)對(duì)象在 packfile 中的文件偏移量，此時(shí)不涉及 Big File Offset 層

Big File Offset 層

用于存儲(chǔ)大于 2G 的文件的偏移量。如果文件大于 2G，可以通過 offset 層最后 31 bits 決定在 big file offset 中的位置，big file offset 通過 8 bytes 來表示對(duì)象在 pack 文件中的位置，理論上可以表示 2 的 64 次方文件大小。

Trailer 層

包含的是 packfile checksum 和關(guān)聯(lián)的 idx 的 checksum。

索引流程

從上面的分層知道 git 設(shè)計(jì)的巧妙。git 索引文件偏移量的查詢流程如下：

查詢算法

通過 idx 文件查詢 SHA-1 對(duì)應(yīng)的偏移量：

在 pack 文件中通過偏移量找到對(duì)象：

如果是普通的存儲(chǔ)類型。定位到的對(duì)象就是用 Zlib 壓縮之后的對(duì)象，直接解壓縮即可。

如果是 Delta 類型需要 遞歸查出 Delta 的 Base 對(duì)象，然后再把 delta data 應(yīng)用到 base object 上（可參考 git-apply-delta）。

git 大多資料主要介紹是 git 使用，很少系統(tǒng)去講解底層數(shù)據(jù)結(jié)構(gòu)和原理。本文通過多個(gè)開源代碼入手，結(jié)合 git 文檔，參考相關(guān) git 開發(fā)者或相關(guān)研究文章，git 郵件列表等。
編輯：hfy