一文講透 Git 底層數(shù)據(jù)結(jié)構(gòu)和原理
本文將系統(tǒng)分享 Git 底層知識(shí)：對(duì)象生命周期變化，底層數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)包文件結(jié)構(gòu)，數(shù)據(jù)包文件索引，以及詳細(xì)分析對(duì)象查詢(xún)流程和算法。
狀態(tài)模型
?? 
上圖描述了 git 對(duì)象的在不同的生命周期中不同的存儲(chǔ)位置，通過(guò)不同的 git 命令改變 git 對(duì)象的存儲(chǔ)生命周期。
工作區(qū) (workspace)
就是我們當(dāng)前工作空間，也就是我們當(dāng)前能在本地文件夾下面看到的文件結(jié)構(gòu)。初始化工作空間或者工作空間 clean 的時(shí)候，文件內(nèi)容和 index 暫存區(qū)是一致的，隨著修改，工作區(qū)文件在沒(méi)有 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)行全部離線(xiàn)操作，包括 log，history，commit，diff 等等。完成離線(xiàn)操作最核心是因?yàn)?git 有一個(gè)幾乎和遠(yuǎn)程一樣的本地倉(cāng)庫(kù)，所有本地離線(xiàn)操作都可以在本地完成，等需要的時(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 文件目錄，通過(guò)這個(gè)倉(cāng)庫(kù)，git 就可以完全離線(xiàn)化操作。在這個(gè)本地化的倉(cāng)庫(kù)中存儲(chǔ)了 git 所有的模型對(duì)象。下面是 git 倉(cāng)庫(kù)的 tree 和相關(guān)說(shuō)明：
?? 
git 主要有四個(gè)對(duì)象，分別是 Blob，Tree， Commit， Tag 他們都用 SHA-1 進(jìn)行命名。
你可以用 git cat-file -t 查看每個(gè) SHA-1 的類(lèi)型，用 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)，文件類(lèi)型以及一些數(shù)據(jù)文件權(quán)限模型等。
如下圖輸出：
詳細(xì)解釋如下：
?? 
Commit 對(duì)象
是一次修改的集合，當(dāng)前所有修改的文件的一個(gè)集合，可以類(lèi)比一批操作的“事務(wù)”。是修改過(guò)的文件集的一個(gè)快照，隨著一次 commit 操作，修改過(guò)的文件將會(huì)被提交到 local repository 中。通過(guò) commit 對(duì)象，在版本化中可以檢索出每次修改內(nèi)容，是版本化的基石。
詳細(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ì)象。
分支的話(huà)，隨著不斷的提交，內(nèi)容會(huì)不斷的改變，因?yàn)榉种е赶虻淖詈笠粋€(gè) commit 不斷改變。所以一般應(yīng)用或者軟件版本的發(fā)布一般用 tag。
git 的 Tag 類(lèi)型有兩種：
1 lightweight (輕量級(jí))
創(chuàng)建方式：
這種方式創(chuàng)建的 Tag，git 底層不會(huì)創(chuàng)建一個(gè)真正意義上的 tag 對(duì)象，而是直接指向一個(gè) commit 對(duì)象，此時(shí)如果使用 git cat-file -t tagName 會(huì)返回一個(gè) commit。
2 annotated (含附注)
創(chuàng)建方式：
這種方式創(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。
總結(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ù)沒(méi)有改變的文件，Git 只是存儲(chǔ)指向源文件的一個(gè)引用，并不會(huì)直接多次存儲(chǔ)文件，這一點(diǎn)可以在 pack 文件中看見(jiàn)。
如下圖所示：
?? 
存儲(chǔ)
隨著需求和功能的不斷復(fù)雜，git 版本的不斷更新，但是主要的存儲(chǔ)模型還是大致不變。如下圖所示：
?? 
檢索模型
git 的對(duì)象有兩種：
一種是松散對(duì)象，就是在如上 .git/objects 的文件夾 03 28 7f ce d0 d5 e6 f9 等，這些文件夾只有 2 個(gè)字符開(kāi)頭，其實(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)
為了加快 pack 文件的檢索效率，git 基于 pack 文件會(huì)生成相應(yīng)的索引 idx 文件。
pack 文件
pack 文件設(shè)計(jì)非常精密和巧妙，本著降低文件大小，減少文件傳輸，降低網(wǎng)絡(luò)開(kāi)銷(xiāo)和安全傳輸?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 文件：
?? 
從上圖可知：通過(guò) idx 索引文件在 pack 文件中定位到對(duì)象之后，對(duì)象的結(jié)構(gòu)主要 Header 和 Data 兩部分。
1 Header 部分
Header 中首 8-bits：1-bit 是 MSB，接著的 3-bits 表示的是當(dāng)前對(duì)象類(lèi)型，主要有 6種存儲(chǔ)類(lèi)型，接著的 4-bits 是用于表示該 Object 展開(kāi)的 (length) 大小的一部分，只是一部分，完整的大小取決于MSB和接下來(lái)的多個(gè) bits，完整算法如下：
- 如果 8-bits 中第一位是 1，表示下一個(gè)字節(jié)還是 header 的一部分，用于表示該對(duì)象展開(kāi)的大小。
- 如果 8-bits 中第一位是 0，表示從下一個(gè)字節(jié)開(kāi)始，將是數(shù)據(jù) Data 文件。
- 如果對(duì)象類(lèi)型是 OBJ_OFS_DELTA 類(lèi)型, 表示的是 Delta 存儲(chǔ)，當(dāng)前 git 對(duì)象只是存儲(chǔ)了增量部分，對(duì)于基本的部分將由接下來(lái)的可變長(zhǎng)度的字節(jié)數(shù)用于表示 base object 的距離當(dāng)前對(duì)象的偏移量，接下來(lái)的可變字節(jié)也是用 1-bit MSB 表示下一個(gè)字節(jié)是否是可變長(zhǎng)度的組成部分。對(duì)偏移量取負(fù)數(shù)，就可知 base 對(duì)象在當(dāng)前對(duì)象的前面多少字節(jié)。
- 如果對(duì)象類(lèi)型是 OBJ_REF_DELTA 類(lèi)型，表示的是 Delta 存儲(chǔ)，當(dāng)前 git 對(duì)象只是存儲(chǔ)了增量部分，對(duì)于基本的部分，用 20-bytes 存儲(chǔ) Base Object 的 SHA-1 。
2 Data 部分
是經(jīng)過(guò) Zlib 壓縮過(guò)的數(shù)據(jù)。可能是全部數(shù)據(jù)，也有可能是 Delta 數(shù)據(jù)，具體看 Header 部分的存儲(chǔ)類(lèi)型，如果是 OBJ_OFS_DELTA 或者 OBJ_REF_DELTA 此處存儲(chǔ)的就是增量 (Delta) 數(shù)據(jù)，此時(shí)如果要取得全量數(shù)據(jù)的話(huà)，需要遞歸的找到最 Base Object，然后 apply delta 數(shù)據(jù)，在 base object 基礎(chǔ)上進(jìn)行 apply delta 數(shù)據(jù)也是非常精妙的，此文暫不做介紹。
從上面可以很清晰知道 pack 文件格式，我們?cè)購(gòu)谋镜貍}(cāng)庫(kù)中一探究竟：
不是增量 delta 格式：
增量 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 不是說(shuō)明下一個(gè)文件的偏移量，偏移量都是來(lái)自索引文件，見(jiàn)下面 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 部分是沒(méi)有的，前 4-bytes 總是 255, 116, 79, 99 因?yàn)檫@個(gè)也是版本 1 的開(kāi)頭四個(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 檢索的核心，通過(guò)它我們可以快速進(jìn)行查詢(xú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è)字符開(kāi)頭的文件數(shù)量，而且是逐層累加的，后面的數(shù)組數(shù)量是包含前面數(shù)組的數(shù)據(jù)的個(gè)數(shù)的一個(gè)累加。
?? 
舉例如下：
1)如果數(shù)組下標(biāo)為 0，且 Fanout[0] = 10 代表著 #0x00 開(kāi)頭的 SHA-1 值的總數(shù)為 10 個(gè)。
2) 如果數(shù)組下標(biāo)為 1，且 Fanout[1] = 15 代表著小于 #0x01 開(kāi)頭的 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 的排序，按照名稱(chēng)排序，按照名稱(chēng)進(jìn)行排序是為了用二分搜索進(jìn)行查找。每個(gè) SHA-1 值占 20-bytes。
CRC 層
由于文件打包主要解決網(wǎng)絡(luò)傳輸問(wèn)題，網(wǎng)絡(luò)傳輸?shù)臅r(shí)候必須通過(guò) crc 進(jìn)行校驗(yàn)，避免傳輸過(guò)程中的文件損壞。CRC 數(shù)組對(duì)應(yīng)的是每個(gè)對(duì)象的 CRC 校驗(yàn)和。
Offset 層
是由 4 byte 字節(jié)所組成，表示的是每個(gè) SHA-1 文件的偏移量，但是如果文件大于 2G 之后，4 byte 字節(jié)將無(wú)法表示，此時(shí)將：
4 byte 中的第一 bit 就是 MSB，如果是 1 表示的是文件的偏移量是放在第 6 層去存儲(chǔ)，此時(shí)剩下的 31-bits 將表示文件在 Big File Offset 中的偏移量，也就是圖中的，通過(guò) 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，可以通過(guò) offset 層最后 31 bits 決定在 big file offset 中的位置，big file offset 通過(guò) 8 bytes 來(lái)表示對(duì)象在 pack 文件中的位置，理論上可以表示 2 的 64 次方文件大小。
Trailer 層
包含的是 packfile checksum 和關(guān)聯(lián)的 idx 的 checksum。
索引流程
從上面的分層知道 git 設(shè)計(jì)的巧妙。git 索引文件偏移量的查詢(xún)流程如下：
?? 
查詢(xún)算法
通過(guò) idx 文件查詢(xún) SHA-1 對(duì)應(yīng)的偏移量：
?? 
在 pack 文件中通過(guò)偏移量找到對(duì)象：
如果是普通的存儲(chǔ)類(lèi)型。定位到的對(duì)象就是用 Zlib 壓縮之后的對(duì)象，直接解壓縮即可。
如果是 Delta 類(lèi)型需要 遞歸查出 Delta 的 Base 對(duì)象，然后再把 delta data 應(yīng)用到 base object 上(可參考 git-apply-delta)。
參考資料
git 大多資料主要介紹是 git 使用，很少系統(tǒng)去講解底層數(shù)據(jù)結(jié)構(gòu)和原理。本文通過(guò)多個(gè)開(kāi)源代碼入手，結(jié)合 git 文檔，參考相關(guān) git 開(kāi)發(fā)者或相關(guān)研究文章，git 郵件列表等。下面是我探究覺(jué)得比較可靠的資料文檔集。
參考文檔
??https://stackoverflow.com/questions/8198105/how-does-git-store-files??
??https://www.npmjs.com/package/git-apply-delta??
??https://git-scm.com/book/en/v2/Git-Internals-Packfiles??
??https://codewords.recurse.com/issues/three/unpacking-git-packfiles??
??http://shafiulazam.com/gitbook/7_the_packfile.html??
??http://wiki.jikexueyuan.com/project/git-community-book/packfile.html??
??http://documentup.com/skwp/git-workflows-book??
??http://www.runoob.com/git/git-workspace-index-repo.html??
??http://shafiulazam.com/gitbook/1_the_git_object_model.html??
??http://eagain.net/articles/git-for-computer-scientists/??
??https://www.kernel.org/pub/software/scm/git/docs/user-manual.html#object-details??
??https://stackoverflow.com/documentation/git/topics??
??https://stackoverflow.com/search?page=2&tab=Votes&q=user%3a1256452%20%5bgit%5d??
??http://git.oschina.net/progit/9-Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86.html#9.5-The-Refspec??
??https://codewords.recurse.com/issues/three/unpacking-git-packfiles??
??http://shafiulazam.com/gitbook/7_the_packfile.html??
??https://w.org/pub/software/scm/git/docs/user-manual.html#object-details??
git 源碼
sha1_file.c sha1_object_info_extended 讀取對(duì)象
sha1_file.c find_pack_entry_one 從索引中尋找
其他 git 源碼
go-git https://github.com/src-d/go-gitgit
go https://github.com/ChimeraCoder/gitgo
【本文為51CTO專(zhuān)欄作者“阿里巴巴官方技術(shù)”原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者】
