[[426802]]

Naive Git

一起寫一個(gè)簡(jiǎn)單的Git吧!

前言

我與兩個(gè)師弟一起成立一個(gè) git org，主要是他們(我需要工作，劃水出主意做PM居多)做一些趣味使然的項(xiàng)目，PioneerIncubator[9]，這個(gè) git 是第三個(gè)項(xiàng)目，第一個(gè)項(xiàng)目是 betterGo，我好幾個(gè)月前就寫好初版了，就等他們做一些完善補(bǔ)充工作了，之后會(huì)單獨(dú)介紹。第二個(gè)項(xiàng)目是剛動(dòng)手，他們搜了一下，發(fā)現(xiàn)上年十月發(fā)現(xiàn)有人做了，那個(gè)項(xiàng)目還有500多star了。

Git的原理是怎么樣呢?

Git is a distributed version-control system for tracking changes in source code during software development.

各位讀者就算不了解git的原理，想必也會(huì)用三把斧 git add; git commit; git push，下面就簡(jiǎn)單說一下git是怎么做的版本管理的：跟蹤文件的變化，使用commit作為標(biāo)記，與遠(yuǎn)程服務(wù)器同步。

跟蹤文件變化

假如你來開發(fā)git這個(gè)工具，在初始化一個(gè)文件夾(repository)后，為了記錄之后可能的修改，你需要記錄當(dāng)前所有需要跟蹤的文件內(nèi)容，最簡(jiǎn)單的就是全部復(fù)制一份好了。

文件是否變化了?比較一下文件哈希好了。

Commit作標(biāo)記

顧言思義，就是將當(dāng)前的 repository 狀態(tài)存儲(chǔ)起來，作為commit。你可以通過 commit 恢復(fù)到任意狀態(tài)，git tag 本質(zhì)也只是給這個(gè) commit 一個(gè) tag(別名)，git branch 也是一樣。

恢復(fù)到某一個(gè) commit，就是將它所代表的 repository 狀態(tài)恢復(fù)起來，就是將文件全部?jī)?nèi)容以及當(dāng)前commit恢復(fù)到那個(gè)狀態(tài)。

與遠(yuǎn)程服務(wù)器同步

git說自己是分布式的版本管理系統(tǒng)，是因?yàn)榧偃鏏、B、C三個(gè)人一起合作，理論上每個(gè)人都有一份server的版本，而且可以獨(dú)立開發(fā)，解決沖突。

Git具體是怎么做的呢?

原理說完了，但commit的管理是要用東西來存儲(chǔ)讀取管理的，Git沒有用數(shù)據(jù)庫(kù)，直接將其內(nèi)容放到.git 文件夾里。

里面有什么內(nèi)容呢?

. 
  |-- HEAD //指向branch、tag (ref: refs/heads/devbranch) 
  |-- index 
  |-- objects 
  |   |-- 05 
  |   |   `-- 76fac355dd17e39fd2671b010e36299f713b4d 
  |   |-- 0c 
  |   |   `-- 819c497e4eca8e08422e61adec781cc91d125d 
  |   |-- fe 
  |   |   `-- 897108953cc224f417551031beacc396b11fb0 
  |   |-- fe 
  |   |   `-- 897108953cc224f417551031beacc396b11fb0 
  |   |-- info 
  |   
  `-- refs 
      |-- heads //各個(gè)branch的heads 
      |   `-- master //此分支最新的commit id 
      |   `-- devBranch // checkout -b branch就會(huì)生成的branch 
      `-- tags 
          `-- v0.1 

各位再結(jié)合

下面我展開講講：

• HEAD: 指向branch或者tag，標(biāo)記當(dāng)前是在哪個(gè)分支或者tag上;
• index：TODO
• objects：記錄文件的內(nèi)容，每個(gè)文件夾名稱是該object的sha1值的前兩位，文件夾下的文件名稱是sha1值的后18位;(tips:sha1算法，是一種加密算法，會(huì)計(jì)算當(dāng)前內(nèi)容的哈希值，作為object的文件名，得到的哈希值是一個(gè)用十六進(jìn)制數(shù)字組成的字符串(長(zhǎng)度為40))
• refs
• heads: heads 里的就是各個(gè)分支的 HEAD 分別指向哪個(gè) commit id;簡(jiǎn)單說，就是 各個(gè)branch分別最新的commit是什么，這樣子 git checkout branch 就可以切換到對(duì)的地方
• tags: 同理，這個(gè)文件夾里存的都是各個(gè)tag

那么，新建一個(gè)branch的時(shí)候，只要在 refs/heads 文件夾里新建branch 名字的文件，并將當(dāng)前commit id存進(jìn)去即可;

新建一個(gè)commit時(shí)，只要根據(jù) HEAD 文件，找到當(dāng)前的 branch或者tag 是什么，修改里面的內(nèi)容即可。

有點(diǎn)不好懂?咱給出一個(gè)git的實(shí)例，默認(rèn)在一個(gè)文件夾執(zhí)行 git init 后，添加一個(gè)文件并 commit 的信息, commit id為 017aa3d7851e8bbff78a697566b5f827b183483c：

$ cat .git/HEAD 
ref: refs/heads/master 
$ cat .git/refs/heads/master 
017aa3d7851e8bbff78a697566b5f827b183483c 

如上，HEAD 指向了master，而 master 的commit id正是剛剛commit的id。

存儲(chǔ)讀取解決了，那么commit怎么組織呢?

將當(dāng)前的 repository 狀態(tài)存儲(chǔ)起來，作為commit。你可以通過 commit 恢復(fù)到任意狀態(tài)，git tag 本質(zhì)也只是給這個(gè) commit 一個(gè) tag(別名)，git branch 也是一樣。

恢復(fù)到某一個(gè) commit，就是將它所代表的 repository 狀態(tài)恢復(fù)起來，就是將文件全部?jī)?nèi)容以及當(dāng)前commit恢復(fù)到那個(gè)狀態(tài)。

上面說了，管理文件夾(repository)狀態(tài)，但是文件夾是可以嵌套的，與文件不一樣，需要有這層級(jí)關(guān)系，同時(shí)也要存文件內(nèi)容，怎么做來區(qū)分呢?

我們可以引入以下概念：

• Tree：代表文件夾，因?yàn)?git init 時(shí)，就是把當(dāng)前文件夾./ 作為項(xiàng)目來管理，那么接下來所有要追蹤的項(xiàng)目無非就是./ 里的文件或者文件夾而已;
•  Blob：文件，Tree里可以包含它;

關(guān)系如下圖：

給點(diǎn)我們寫的數(shù)據(jù)結(jié)構(gòu)代碼你看看，要注意的是，tree 可以擁有 blob 或者 tree，所以用了 union;parent 與 next 作為鏈表使用，作為文件夾目錄管理;

struct tree_entry_list { 
    struct tree_entry_list *next; 
    union { 
        struct tree *tree; 
        struct blob *blob; 
    } item; 
    struct tree_entry_list *parent; 
}; 
 
struct tree { 
    struct tree_entry_list *entries; 
}; 

而 commit 跟樹一樣，也是有層級(jí)的單鏈表，不過只有

struct commit { 
    struct commit *parents; 
    struct tree *tree; 
 
    char *commit_id[10]; 
    char *author; 
    char *committer; 
    char *changelog; 
}; 

一圖勝千言，看圖吧：

如上，有三個(gè)commit，先后順序?yàn)椋? -> 2 -> 3， 3是最新的。

• 畫圈的blob是文件內(nèi)容，代表這個(gè)文件在commit 1跟2都沒有變化，所以復(fù)用了同一個(gè);
• 畫正方形的，也是同一個(gè)文件，但是內(nèi)容有變化了，所以分別指向了不一樣的blob;
• tag 指向了commit 2;
• HEAD 跟 branch 都在最新的commit 3，新增了一個(gè)文件;

于是通過commit記錄變動(dòng)的內(nèi)容，就是可以從上而下的恢復(fù)所有有變更的文件。

如圖，checkout 到 v0.1的tag，就是找到此commit id，然后恢復(fù)commit下的tree的文件：

云風(fēng)的游戲資源倉(cāng)庫(kù)及升級(jí)發(fā)布

云風(fēng)參考過git的原理做過一個(gè)游戲資源倉(cāng)庫(kù)管理，我下面講一下它跟git的區(qū)別，他的文章[10]我覺得比較繞，沒有背景知識(shí)的人很難看明白。

背景

我們的引擎的一個(gè)重要特性就是，在 PC 上開發(fā)，在移動(dòng)設(shè)備上運(yùn)行調(diào)試。我們需要頻繁的將資源同步到設(shè)備上

程序以 c/s 結(jié)構(gòu)運(yùn)行時(shí)，在移動(dòng)設(shè)備上先建立一個(gè)空的鏡像倉(cāng)庫(kù)，同步 PC 端的資源倉(cāng)庫(kù)。運(yùn)行流程是這樣的：

首先在客戶端啟動(dòng)的時(shí)候，向服務(wù)器索取一個(gè)根索引的 hash ，在本地鏡像上設(shè)定根。

客戶端請(qǐng)求一個(gè)文件路徑時(shí)，從根開始尋找對(duì)應(yīng)的目錄索引文件，逐級(jí)查找。如果本地有所需的 hash 對(duì)象，就直接使用;否則向服務(wù)器請(qǐng)求，直到最后獲得目標(biāo)文件。api 的設(shè)計(jì)上，open 一個(gè)資源路徑，要么返回最終的文件，要么返回一個(gè) hash ，表示當(dāng)前還缺少這個(gè) hash 對(duì)象;這樣，可以通過網(wǎng)絡(luò)模塊請(qǐng)求這個(gè)對(duì)象;獲得該對(duì)象后，無須理會(huì)這個(gè)對(duì)象是什么，簡(jiǎn)單寫入鏡像倉(cāng)庫(kù)，然后重新前面的過程，再次請(qǐng)求未完成的路徑，最終就能打開所需的資源文件。

場(chǎng)景是：Client <- 他的游戲服務(wù)器 ，單向同步;

他是這樣子做的，客戶端的倉(cāng)庫(kù)是 key-value 的文件數(shù)據(jù)庫(kù)，key是文件的hash，value就是文件內(nèi)容;

同步時(shí)，會(huì)從根到具體hash全量同步文件下載到數(shù)據(jù)庫(kù);

假如客戶端使用資源時(shí)，發(fā)現(xiàn)缺乏這個(gè)文件，就用hash去服務(wù)器拉下來。

換言之，因?yàn)椴恍枰芾肀镜匕姹荆⑶彝降缴嫌?，所以無需在本地記錄全量的版本狀態(tài)

跟Git的區(qū)別：

場(chǎng)景是：Client <-> gitHub ，雙向同步;

git 需要本地組織commit，切換本地有但服務(wù)器沒有的版本(就是離線操作) ，同時(shí)還需要將變更同步到上游。

最后的建議

如果看完該文，讓你躍躍欲試的話，請(qǐng)不要用C寫，請(qǐng)不要用C寫，請(qǐng)不要用C寫。

從零開始寫過幾個(gè)大一點(diǎn)項(xiàng)目，每次都覺得用C寫項(xiàng)目太難受了，這次我寫 git commit 時(shí)，發(fā)現(xiàn)要讀寫文件，解析內(nèi)容，我發(fā)出了內(nèi)心的感嘆：

太難了，不是寫這個(gè)難，是C太難用了。。

想到我要遍歷這些文件，根據(jù)目錄得到tree的hash，然后還要update這棵樹，把tree跟commit還要blob反序列存到文件里，還要讀出來，之后還要組織鏈表操作，用C寫就覺得百般阻撓。。。

具體實(shí)現(xiàn)，git rebase，git merge等進(jìn)階內(nèi)容，就要等下一篇了。

本文轉(zhuǎn)載自微信公眾號(hào)「山盡寫東西的cache」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系山盡寫東西的cache公眾號(hào)。