前言

本文試圖理解 git 的原理，重寫部分 git 命令，從最底層的幾個命令開始，聽起來很離譜，做起來也很離譜，但是真正去做了，發現，誒，好像沒有那麼離譜。

俗話說得好（我也不知道哪裏來的俗話，maybe 我自己說的），理解一個東西最好的方法就是實現它。git 作爲我們每天都需要去打交道的一個東西，瞭解它和熟悉怎麼去使用它也是我們每個人的必要技能。

現狀分析

來，我們克服一下恐懼，我們爲什麼會覺得這個東西很複雜，因爲它真的很複雜，光是上層命令，就有各種各樣的用法，就算筆者也不敢說真的能夠精通，關鍵是他的文檔 居然夠寫一本書【Pro Git】[1]，還有王法嗎，還有法律嗎？

不過再仔細想想，我們需要了解這麼多的特性嗎，我們每天日常使用的也就是幾個命令，我們是不是隻需要了解他的底層機制和那幾個命令就行了？好像沒那麼可怕了？OK，我們進入正題。

對於本文，其實你並不需要了解太多的東西，一點點的 Git 基本知識，一點點基本語言知識，一點點的 shell 知識，OK，條件具備了，我們可以開始愉快的玩耍了。

首先我們例舉一下，我們需要用到的本地命令有些啥

• git add

• git commit

• git checkout

• git rm

• git init

• git log

• git reflog

• git show-ref

• git merge

• git rebase

• git cat-file

• git hash-object

• git ls-tree

• git tag

嗯，差不多，單純本地的倉庫 我們要用到的命令是不是就這些，我們將在主要內容分享完之後，再回到這裏來理解這些命令。

GIT 底層結構

不知道大家有沒有好奇過這些東西，這些玩意都是啥？我們如何靠這個目錄下的文件來管理我們各種各樣奇奇怪怪的提交，而且還能回溯呢？

GIT 目錄

先來看一下目錄結構：

├── COMMIT_EDITMSG  // 上一次提交的 msg
├── FETCH_HEAD // 遠端的所有分支頭指針 hash
├── HEAD // 當前頭指針
├── ORIG_HEAD // 
├── config // 記錄一些配置和遠端映射
├── description // 倉庫描述
├── hooks // commit lint規則 husky植入
│   ├── applypatch-msg
│   ├── applypatch-msg.sample
│   ├── commit-msg
│   ├── commit-msg.sample
│   ├── fsmonitor-watchman.sample
│   ├── post-applypatch
│   ├── post-checkout
│   ├── post-commit
│   ├── post-merge
│   ├── post-receive
│   ├── post-rewrite
│   ├── post-update
│   ├── post-update.sample
│   ├── pre-applypatch
│   ├── pre-applypatch.sample
│   ├── pre-auto-gc
│   ├── pre-commit
│   ├── pre-commit.sample
│   ├── pre-merge-commit
│   ├── pre-merge-commit.sample
│   ├── pre-push
│   ├── pre-push.sample
│   ├── pre-rebase
│   ├── pre-rebase.sample
│   ├── pre-receive
│   ├── pre-receive.sample
│   ├── prepare-commit-msg
│   ├── prepare-commit-msg.sample
│   ├── push-to-checkout
│   ├── push-to-checkout.sample
│   ├── sendemail-validate
│   ├── update
│   └── update.sample
├── index // 暫存區
├── info
│   ├── exclude
│   └── refs
├── logs // 顧名思義，記錄我們的git log
│   ├── HEAD
│   └── refs
├── objects // git 存儲的我們的文件
│   
├── lost-found //一些懸空的文件
│   ├── commit
│   └── other
├── packed-refs 打包好的指針頭
└── refs // 所有的hash
    ├── heads
    ├── remotes
    └── tags

對這些倉庫分析完，突然發現，我們是不是隻需要這一個目錄下的東西，就可以將一個 repo 的所有源信息拷貝。

記住我們剛剛所講的東西，這個目錄的一些結構，這對理解我們後面的命令和底層存儲幫助很大，我們將在後面部分深入介紹。

GIT Hash

首先 git 中的對象，我們一共有 4 種 type，分別是 commit / tree / blob / tag。

我們先需要摸清楚 git 算 hash 的規則，我們一共有四種對象 type，這四個 type 一定是要附帶到我們 sha1 加密後的 hash 裏面的，還有一些文本附加信息，整體的規則如下。

"{type} {content.length}\0{content}"

OK，那我們來嘗試下生成 hash 值，看看我們生成的，和 git 生成的 是否一致。

echo -n "hello,world" | git hash-object --stdin

const crypto = require('crypto'),
const sha1 = crypto.createHash('sha1');
sha1.update("blob 11\0hello,world");
console.log(sha1.digest('hex'));

git 本質是一種類 kv 數據庫的文件系統，通過 sha1 算法生成的 hash 作爲 key，對應到我們的 git 的幾類對象，然後再去樹狀的尋址，最底層存儲的是我們的文件內容。

講到這了，衍生一下關於 git 使用 sha1 的目的以及前幾年 google 碰撞 sha1 算法導致的 sha1 算法不安全的問題，git 使用 sha1 進行 hash 的目的，更多的是爲了驗證文件完整性 防損壞等目的，同時 linus 本人以及 stackoverflow 上對這個問題也有一些討論和回覆，大家可以移步觀看。

stackoverflow 的討論 [2] linus 針對 google sha1 碰撞的郵件 [3]

生成 hash 的算法我們介紹完事了，那接下來就是根據 hash 去找東西了，前文提到了，git 一共存在四種對象，我們分別對四種對象以及內容尋址進行介紹。

GIT 對象

blob

這是最底層的對象，記錄的是文件內容，對，僅僅是文件內容，通過我們上面計算 hash 的方式可以看出來，不管文件名怎麼變化，我們所對應的那塊內容沒有改變，hash 值就不會改變，找到的永遠會是那個 blob。

這也是爲什麼 git 是用來管理代碼以及各種類型的文本的一種好方式，而不是用來管理 word/pdf （誤）。

在純文本類型文件管理中，git 只需要保存 diff 就行了，而如果我們代碼中全是二進制文件，那簡直是回溯噩夢，可能真實資源就兩個 pdf，一個 word 文件，但是版本太多，一個 git 倉庫大小几個 g 也不是不可能。

OK，這裏可能有些同學要問了，那我如果真的需要存儲很多頻繁變動的二進制文件，比如多媒體資源 / psd 啥的， 那我需要怎麼搞？好的，家人們，上鍊接。Git LFS（Large file storage）[4] 一句話介紹，把我們的大文件變成文件指針存儲在對象中，再去 lfs 拉取對應文件。

tree

剛剛我們說了，blob 對象是純粹的內容，有些不對勁，我們內容需要索引，我怎麼去找到他？這一節的標題叫做 tree，對，他就是以樹狀結構來進行組織的，隨便點開一個 objects 下面的文件 cat-file 看看。

可以看出來，我們整個對象的組織形式就是一棵多叉樹。通過樹級層級一層一層尋址，最後找到我們的內容塊。整體的組織形式就是下圖。

commit

現在還有另一個問題，不過我們其實上面的演示已經解釋了一部分這個問題了， 一個 commit 對應的信息其中只有幾種，

• author 與對應的時間點

• commit 的時候我們輸入的描述

• 這個 commit 所指向的 tree

• 這個 commit 的 parent 即父節點

git 是以類似單向鏈表的形式將我們的一個個提交組織起來的，同時，同時一個節點至多有 2 個父節點。到此，其實整個 git 內容存儲的結構我們已經捋清楚了。

tag

最後簡單介紹下，最後一種對象，tag 是對某個 commit 的描述，其實也是一種 commit。

小結

總結一下我們以上說的內容，我們可以得到 git 的一個設計思路，git 記錄的是一個 a → b 過程的鏈表，通過鏈表，我們可以逐步回溯到 a，在此之下呢，採用了一種多叉樹形結構對我們的 hash 值進行分層記錄，最底層，通過我們的 hash 值進行索引，對應到一個個壓縮後的二進制 objects。這就是整個 git 的結構設計。還有一些 git 對於查找效率的優化手段，壓縮手段。

對以上內容瞭解了之後，關於我們的分支本質上，其實也是對應一個 commit，只是多了一個 ref 指向這個 commit 而已，是不是對 git 整個清晰多了。

這裏留給大家一個課後問題吧，git 的 gc 怎麼去實現的， 整個完整過程是啥樣的，由於這些內容並不是本文的核心內容，就不在這裏展開了。

實現

前期準備

回想一下前面講的，我們需要的東西有些什麼，sha1，這個可以用crypto， zlib，node 中也帶了這個，可以通過 require('zlib')拿到。

識別命令參數

首先，讓 node 環境能夠讀我們的一些命令，來幹各種各樣的事情，通過 process 的解析，我們能夠獲得輸入的參數

enum CommandEnum{
  Add= 'add',
  Init = 'init',
  ...
}
const chooseCommand = (command:CommandEnum) => {
  
  switch(command){
    case CommandEnum.Add:
      return add();
    case CommandEnum.Init:
      return init();
    ...
    default:
      break;
  }
  console.log("暫不支持此命令")
}

chooseCommand(process.argv[2] as CommandEnum);

init

okk，我們現在進行下一步，萬事開頭難，先開個頭吧。使用我們的命令，初始化一個 git 倉庫。

const init = ()=>{
  
  fs.mkdirSync('.git');
  fs.mkdirSync('.git/refs')
  fs.mkdirSync('.git/objects')
  fs.writeFileSync('.git/HEAD','ref: refs/heads/master')
  fs.writeFileSync('.git/config',`
        [core]
    repositoryformatversion = 0
    filemode = true
    bare = false
    logallrefupdates = true
    ignorecase = true
    precomposeunicode = true
`);
  fs.writeFileSync('.git/description','');
}

寫入和讀取

初始化完成了，我們有了一個存儲庫，接着就是把大象裝進冰箱。

剛剛我們在分享的過程中，不斷的用到兩個命令 git hash-object 和 git cat-file，這兩個命令，在我們日常工作中，其實不太會用到，他們兩幹嘛使的呢。Git 中存在兩個命令的概念，一個是底層命令 (Plumbing) ，另一個就是我們日常會使用到的上層命令 (Porcelain) ， 高層命令是基於底層命令的封裝，讓我們使用起來更爲方便。

引入一些 npm 包，定義一些結構體

import fs from 'fs';
import zlib from 'zlib';
import crypto from 'crypto';

export enum GitObjectType{
  Commit = 'commit',
  Tree = 'tree',
  Blob = 'blob',
  Tag = 'tag'
}

來實現一個簡單的讀取 blob 對象的方法，比較簡陋，還不支持對 content 進行解析，我們將在後續完善。

export const readObject = (sha1='f8eb512de72634ca12328d85f70b696414473914')=>{
  const data = fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);
  const a = zlib.inflateSync(data).toString('utf8');
  const typeIndex = a.indexOf(' ');
  const lengthIndex = a.indexOf(`\0`);

  const objType = a.substring(0,typeIndex);
  const length = a.substring(typeIndex +1,lengthIndex);
  const content = a.substring(lengthIndex+1);
  // console.log(a);
  return {objType,length,content};
}

ok， 有了讀之後，我們還需要往裏寫。

export const createObject = (obj:GitObject)=>{
  const data = obj.serialize();
  const sha1 = crypto.createHash('sha1');
  sha1.update(data);
  const name = sha1.digest("hex");
  const zipData = zlib.deflateSync(data);
  console.log(name);
  const dirName = `.git/objects/${name.substring(0,2)}` 
  fs.existsSync(dirName) && fs.mkdirSync(dirName);
  fs.writeFileSync(`.git/objects/${name.substring(0,2)}/${name.substring(2)}`,zipData)
  return name;
}

琢磨透了讀和寫的方法，我們的cat-file命令和hash-object命令實際上實現起來就很簡單了，只需要調用現有的方法就行了。

先是cat-file 對 hash 名的一個尋址，同時解壓縮對應的 objects，支持四個參數，分別返回不同的結果。我們直接讀對象就完事了嗷。

export const catFile = ()=>{
  const type = process.argv[3];
  const sha1 = process.argv[4];
  const res = readObject(sha1);
  if(type ==='-t'){
    console.log(res.type);
  }
  if(type==='-s'){
    console.log(res.length);
  }
  if(type === '-e'){
    console.log(!!res?.type)
  }
  if(type === '-p'){
    console.log(res.content)
  }
}

接着是hash-object, 這個也簡單的實現下，就是返回對應路徑的 hash 值就行了

export const hashObject = ()=>{
  const path = process.argv[3];
  const data = fs.readFileSync(path);
  const sha1 = crypto.createHash('sha1');
  sha1.update(data);
  const name = sha1.digest("hex");
  console.log(name);
  }

現在我們基本結構已經搭起來了，需要的是 commit 和 tree 將文件串聯起來，調用我們的cat-file試試，現在應該對 commit 和 blob 的解析是正確的， 但是 tree 的 content 的解析似乎有些問題，我們後面來看這個問題，但是 commit 對象的 content 和 blob 的 content 不太一樣。

內容解析完善

剛剛我們粗略的實現了一下讀對象，能把內容塊讀出來了。接着我們來完善他，以便更好的服務於我們的四種對象, 先改寫下我們的 readObject。

readObject

export const readObject = (sha1: string)=>{
  const data = fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);
  const buf = zlib.inflateSync(data)
  const a = buf.toString('utf8');
  const typeIndex = a.indexOf(' ');

  const lengthIndex = a.indexOf(`\0`);
  // console.log(a);
  const objType = a.substring(0,typeIndex);
  // 去掉校驗， 其實這裏需要記錄長度和真實長度對比是否有錯
  // const length = a.substring(typeIndex +1,lengthIndex);
  let obj;
  if(objType===GitObjectType.Blob){
    obj = new GitBlob(a.substring(lengthIndex+1));
  }
  if(objType===GitObjectType.Commit){
    obj = new GitCommit(a.substring(lengthIndex+1))
  }
  if(objType===GitObjectType.Tree){
    obj = new GitTree(buf.slice(lengthIndex+1))
  }
  return obj;
}

Blob 對象實現起來很簡單 就不在這裏說了。

Commit 對象實現起來稍微複雜一點，我們需要解析 commit 對象中的一些鍵值對，將他們都記住，同時把 commit 內容單獨存起來。一個 commit 對象存儲的東西，在上面我們已經介紹過了，通過一個 map 將他存儲。

Commit object

class GitCommit extends GitObject{
  type = GitObjectType.Commit;
  data = '';
  length = 0;
  content:any;
  map;
  constructor(data:string){
  super();
    if(data){
      this.data=data;
      this.length = data.length;
    }
  }
  serialize = ()=>{
    return `${this.type} ${this.length}\0${this.data}`;
  }
  deserialize= ()=>{
    console.log(this.recursiveParse(this.data))
    return this.data;
  }
  recursiveParse = (data:string,map?:any):any=>{
    if(!map){
        map = new Map();
    }
    const space = data.indexOf(' ');

    const nl = data.indexOf(`\n`);
    console.log(space,nl);
    if(space<0 || nl<space){
       map.set("content",data);
        return map;
    }
    const key = data.substring(0,space);

    let end =0;
    while(true){
        end = data.indexOf(`\n`,end+1)
        if(data[end+1] !== ' ') break;
    }
    const value = data.substring(space+1,end);
    if(key ==='parent'){
        map.has('parent') ? map.set(key+'1',value) : map.set(key,value);
    } else {
        map.set(key,value)
    }

    const restData = data.substring(end+1);
    return this.recursiveParse(restData,map);
  }
}

Tree Object 解析

Tree Object 相對來說是我們解析起來最爲複雜的一個對象，他不像前兩個一樣，能夠通過直接 toString 就能拿到正常的文本，我們直接去解析就行了。Tree Object 本身其實就是一個二進制對象，關鍵吧，他還有個誤導，差點給筆者都給帶偏了，他 cat-file 解析出來的文件，其實並不是他原本文件長的樣子....，他做了一個格式化，且修改了順序。

class GitTree extends GitObject{
  type = GitObjectType.Commit;
  data:Buffer = Buffer.from('');
  length = 0;
  constructor(data:Buffer){
  super();
    if(data){
      this.data=data;
      this.length = data.length;
      
    }
  }
  serialize = ()=>{
    return `${this.type} ${this.length}\0${this.data}`;
  }
  parseTreeOneLine = (data:Buffer,start:number)=>{
    const x = data.indexOf(' ',start);
    if(x<0){
      return start+21;
    }
    const mode = data.slice(start,x).toString('ascii');
    // const type = 
    const y = data.indexOf(`\x00`,x)
    if(y<0){return x+21};
    const path = data.slice(x+1,y).toString('ascii');
    const sha1 = data.slice(y+1,y+21).toString('hex');
    console.log(mode,path,sha1);
    return y+21;
  }
  deserialize= ()=>{
    const buffer = this.data;
    let pos = 0;
    let max = buffer.length;
   
    while(pos<max){
      pos = this.parseTreeOneLine(buffer,pos);
    }
    return this.data;
  }
}

我們的底層基礎簡單實現，其實到這裏就完結了，大致流程能夠串起來了。

分支和 ref：

分支名和 ref 其實也是鍵值對，分支名作爲文件名存儲在 ref 目錄下，文件內容則是一串 sha1 值，這串 sha1 值來自於 commit 頭結點的 hash 值，我們可以通過這個 commit 對象回溯到當時的場景。

log 與 reflog

單純的文本文件，記錄一些 commit 對象以及時間點等。大家可以下來再去研究研究。

暫存區：

不過大家可能會有問題，不對啊，我們平時提交不是還有 stage 的概念嗎，這一塊東西呢？確實，少了這一塊，不過這一塊也是 git 底層相對麻煩的一部分（數據處理太多 T_T)，所以我並不打算在這篇分享中去實現他，有興趣的同學可以參考這個鏈接 git index 結構 [5]。

後語

分享到這就差不多了，實現了部分的底層讀寫 api，其他的 api 就不一一實現了，有興趣可以下來實現。

課後作業：

1. git 的 gc 問題

2. 底層命令來實現我們日常調用的上層命令效果

3. 怎麼去實現一個遠程的 git 中心服務器，遠程的命令怎麼關聯？

4. 補充實現一個 git

最後的最後，作爲 linus 的腦殘粉，linus 的一句話，送給大家，talk is cheap, show me the code .

引用文檔：

https://www.open-open.com/lib/view/open1328069609436.html

http://gitlet.maryrosecook.com/docs/gitlet.html

https://git-scm.com/docs/git-add/zh_HANS-CN

https://wyag.thb.lt/#org947aee7

歡迎關注公衆號 ELab 團隊 收貨大廠一手好文章~

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