Git儲存原理及部分實現

手把手教你理解輪子之git

當年他陳刀仔，能用20塊贏到 3700萬，今天我盧.....

Sry，串臺了

當年他linus 能用兩個星期寫完Git， 今天我葉某人.... (好吧，當場給linus跪下)

前言

本文試圖理解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 .

引用文件：

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

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

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

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