國慶節就到，一起寫一個Linux初版的Git吧
Naive Git
一起寫一個簡單的Git吧!
前言
我與兩個師弟一起成立一個 git org，主要是他們(我需要工作，劃水出主意做PM居多)做一些趣味使然的項目，PioneerIncubator[9]，這個 git 是第三個項目，第一個項目是 betterGo，我好幾個月前就寫好初版了，就等他們做一些完善補充工作了，之后會單獨介紹。第二個項目是剛動手，他們搜了一下，發現上年十月發現有人做了，那個項目還有500多star了。
Git的原理是怎么樣呢?
Git is a distributed version-control system for tracking changes in source code during software development.
各位讀者就算不了解git的原理，想必也會用三把斧 git add; git commit; git push，下面就簡單說一下git是怎么做的版本管理的：跟蹤文件的變化，使用commit作為標記，與遠程服務器同步。
跟蹤文件變化
假如你來開發git這個工具，在初始化一個文件夾(repository)后，為了記錄之后可能的修改，你需要記錄當前所有需要跟蹤的文件內容，最簡單的就是全部復制一份好了。
文件是否變化了?比較一下文件哈希好了。
Commit作標記
顧言思義，就是將當前的 repository 狀態存儲起來，作為commit。你可以通過 commit 恢復到任意狀態，git tag 本質也只是給這個 commit 一個 tag(別名)，git branch 也是一樣。
恢復到某一個 commit，就是將它所代表的 repository 狀態恢復起來，就是將文件全部內容以及當前commit恢復到那個狀態。
與遠程服務器同步
git說自己是分布式的版本管理系統，是因為假如A、B、C三個人一起合作，理論上每個人都有一份server的版本，而且可以獨立開發，解決沖突。
Git具體是怎么做的呢?
原理說完了，但commit的管理是要用東西來存儲讀取管理的，Git沒有用數據庫，直接將其內容放到.git 文件夾里。
里面有什么內容呢?
- .
- |-- HEAD //指向branch、tag (ref: refs/heads/devbranch)
- |-- index
- |-- objects
- | |-- 05
- | | `-- 76fac355dd17e39fd2671b010e36299f713b4d
- | |-- 0c
- | | `-- 819c497e4eca8e08422e61adec781cc91d125d
- | |-- fe
- | | `-- 897108953cc224f417551031beacc396b11fb0
- | |-- fe
- | | `-- 897108953cc224f417551031beacc396b11fb0
- | |-- info
- |
- `-- refs
- |-- heads //各個branch的heads
- | `-- master //此分支最新的commit id
- | `-- devBranch // checkout -b branch就會生成的branch
- `-- tags
- `-- v0.1
各位再結合
下面我展開講講：
- HEAD: 指向branch或者tag，標記當前是在哪個分支或者tag上;
- index：TODO
- objects：記錄文件的內容，每個文件夾名稱是該object的sha1值的前兩位，文件夾下的文件名稱是sha1值的后18位;(tips:sha1算法，是一種加密算法，會計算當前內容的哈希值，作為object的文件名，得到的哈希值是一個用十六進制數字組成的字符串(長度為40))
- refs
- heads: heads 里的就是各個分支的 HEAD 分別指向哪個 commit id;簡單說，就是 各個branch分別最新的commit是什么，這樣子 git checkout branch 就可以切換到對的地方
- tags: 同理，這個文件夾里存的都是各個tag
那么，新建一個branch的時候，只要在 refs/heads 文件夾里新建branch 名字的文件，并將當前commit id存進去即可;
新建一個commit時，只要根據 HEAD 文件，找到當前的 branch或者tag 是什么，修改里面的內容即可。
有點不好懂?咱給出一個git的實例，默認在一個文件夾執行 git init 后，添加一個文件并 commit 的信息, commit id為 017aa3d7851e8bbff78a697566b5f827b183483c：
- $ cat .git/HEAD
- ref: refs/heads/master
- $ cat .git/refs/heads/master
- 017aa3d7851e8bbff78a697566b5f827b183483c
如上，HEAD 指向了master，而 master 的commit id正是剛剛commit的id。
存儲讀取解決了，那么commit怎么組織呢?
將當前的 repository 狀態存儲起來，作為commit。你可以通過 commit 恢復到任意狀態，git tag 本質也只是給這個 commit 一個 tag(別名)，git branch 也是一樣。
恢復到某一個 commit，就是將它所代表的 repository 狀態恢復起來，就是將文件全部內容以及當前commit恢復到那個狀態。
上面說了，管理文件夾(repository)狀態，但是文件夾是可以嵌套的，與文件不一樣，需要有這層級關系，同時也要存文件內容，怎么做來區分呢?
我們可以引入以下概念：
- Tree：代表文件夾，因為 git init 時，就是把當前文件夾./ 作為項目來管理，那么接下來所有要追蹤的項目無非就是./ 里的文件或者文件夾而已;
- Blob：文件，Tree里可以包含它;
關系如下圖：
給點我們寫的數據結構代碼你看看，要注意的是，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 跟樹一樣，也是有層級的單鏈表，不過只有
- struct commit {
- struct commit *parents;
- struct tree *tree;
- char *commit_id[10];
- char *author;
- char *committer;
- char *changelog;
- };
一圖勝千言，看圖吧：
如上，有三個commit，先后順序為：1 -> 2 -> 3， 3是最新的。
- 畫圈的blob是文件內容，代表這個文件在commit 1跟2都沒有變化，所以復用了同一個;
- 畫正方形的，也是同一個文件，但是內容有變化了，所以分別指向了不一樣的blob;
- tag 指向了commit 2;
- HEAD 跟 branch 都在最新的commit 3，新增了一個文件;
于是通過commit記錄變動的內容，就是可以從上而下的恢復所有有變更的文件。
如圖，checkout 到 v0.1的tag，就是找到此commit id，然后恢復commit下的tree的文件：
云風的游戲資源倉庫及升級發布
云風參考過git的原理做過一個游戲資源倉庫管理，我下面講一下它跟git的區別，他的文章[10]我覺得比較繞，沒有背景知識的人很難看明白。
背景
我們的引擎的一個重要特性就是，在 PC 上開發，在移動設備上運行調試。我們需要頻繁的將資源同步到設備上
程序以 c/s 結構運行時，在移動設備上先建立一個空的鏡像倉庫，同步 PC 端的資源倉庫。運行流程是這樣的：
首先在客戶端啟動的時候，向服務器索取一個根索引的 hash ，在本地鏡像上設定根。
客戶端請求一個文件路徑時，從根開始尋找對應的目錄索引文件，逐級查找。如果本地有所需的 hash 對象，就直接使用;否則向服務器請求，直到最后獲得目標文件。api 的設計上，open 一個資源路徑，要么返回最終的文件，要么返回一個 hash ，表示當前還缺少這個 hash 對象;這樣，可以通過網絡模塊請求這個對象;獲得該對象后，無須理會這個對象是什么，簡單寫入鏡像倉庫，然后重新前面的過程，再次請求未完成的路徑，最終就能打開所需的資源文件。
場景是：Client <- 他的游戲服務器 ，單向同步;
他是這樣子做的，客戶端的倉庫是 key-value 的文件數據庫，key是文件的hash，value就是文件內容;
同步時，會從根到具體hash全量同步文件下載到數據庫;
假如客戶端使用資源時，發現缺乏這個文件，就用hash去服務器拉下來。
換言之，因為不需要管理本地版本，并且同步到上游，所以無需在本地記錄全量的版本狀態
跟Git的區別：
場景是：Client <-> gitHub ，雙向同步;
git 需要本地組織commit，切換本地有但服務器沒有的版本(就是離線操作) ，同時還需要將變更同步到上游。
最后的建議
如果看完該文，讓你躍躍欲試的話，請不要用C寫，請不要用C寫，請不要用C寫。
從零開始寫過幾個大一點項目，每次都覺得用C寫項目太難受了，這次我寫 git commit 時，發現要讀寫文件，解析內容，我發出了內心的感嘆：
太難了，不是寫這個難，是C太難用了。。
想到我要遍歷這些文件，根據目錄得到tree的hash，然后還要update這棵樹，把tree跟commit還要blob反序列存到文件里，還要讀出來，之后還要組織鏈表操作，用C寫就覺得百般阻撓。。。
具體實現，git rebase，git merge等進階內容，就要等下一篇了。
本文轉載自微信公眾號「山盡寫東西的cache」，可以通過以下二維碼關注。轉載本文請聯系山盡寫東西的cache公眾號。
