一起寫一個 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 等進階內容，就要等下一篇了。

工作去了 ；P

References

[9] PioneerIncubator: https://github.com/PioneerIncubator
[10] 他的文章: https://blog.codingnow.com/2018/08/asset_repo.html

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/aNvIDhsDkRhpGDnPKxA8lw

猜你喜歡