手把手教你理解輪子之git

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

Sry，串臺(tái)了

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

前言

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

俗話說得好（我也不知道哪里來的俗話，maybe 我自己說的），理解一個(gè)東西最好的方法就是實(shí)現(xiàn)它。git作為我們每天都需要去打交道的一個(gè)東西，了解它和熟悉怎么去使用它也是我們每個(gè)人的必要技能。

現(xiàn)狀分析

來，我們克服一下恐懼，我們?yōu)槭裁磿?huì)覺得這個(gè)東西很復(fù)雜，因?yàn)樗娴暮軓?fù)雜，光是上層命令，就有各種各樣的用法，就算筆者也不敢說真的能夠精通，關(guān)鍵是他的文檔 居然夠?qū)懸槐緯?span style="font-weight: bold;color: #ffb11b;padding: 3px;">【Pro Git】^[1]，還有王法嗎，還有法律嗎？

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

對于本文，其實(shí)你并不需要了解太多的東西，一點(diǎn)點(diǎn)的Git基本知識，一點(diǎn)點(diǎn)基本語言知識，一點(diǎn)點(diǎn)的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

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

GIT底層結(jié)構(gòu)

不知道大家有沒有好奇過這些東西，這些玩意都是啥？我們?nèi)绾慰窟@個(gè)目錄下的文件來管理我們各種各樣奇奇怪怪的提交，而且還能回溯呢？

GIT目錄

先來看一下目錄結(jié)構(gòu)：

├── COMMIT_EDITMSG  // 上一次提交的 msg
├── FETCH_HEAD // 遠(yuǎn)端的所有分支頭指針 hash
├── HEAD // 當(dāng)前頭指針
├── ORIG_HEAD // 
├── config // 記錄一些配置和遠(yuǎn)端映射
├── description // 倉庫描述
├── hooks // commit lint規(guī)則 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 // 暫存區(qū)
├── info
│   ├── exclude
│   └── refs
├── logs // 顧名思義，記錄我們的git log
│   ├── HEAD
│   └── refs
├── objects // git 存儲(chǔ)的我們的文件
│   
├── lost-found //一些懸空的文件
│   ├── commit
│   └── other
├── packed-refs 打包好的指針頭
└── refs // 所有的hash
    ├── heads
    ├── remotes
    └── tags

對這些倉庫分析完，突然發(fā)現(xiàn)，我們是不是只需要這一個(gè)目錄下的東西，就可以將一個(gè)repo的所有源信息拷貝。

記住我們剛剛所講的東西，這個(gè)目錄的一些結(jié)構(gòu)，這對理解我們后面的命令和底層存儲(chǔ)幫助很大，我們將在后面部分深入介紹。

GIT Hash

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

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

"{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 本質(zhì)是一種類kv數(shù)據(jù)庫的文件系統(tǒng)，通過sha1算法生成的hash作為key，對應(yīng)到我們的git的幾類對象，然后再去樹狀的尋址，最底層存儲(chǔ)的是我們的文件內(nèi)容。

講到這了，衍生一下關(guān)于git使用sha1的目的以及前幾年google碰撞sha1算法導(dǎo)致的 sha1算法不安全的問題，git使用sha1進(jìn)行hash的目的，更多的是為了驗(yàn)證文件完整性 防損壞等目的，同時(shí)linus本人以及stackoverflow上對這個(gè)問題也有一些討論和回復(fù)，大家可以移步觀看。

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

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

GIT 對象

blob

這是最底層的對象，記錄的是文件內(nèi)容，對，僅僅是文件內(nèi)容，通過我們上面計(jì)算hash的方式可以看出來，不管文件名怎么變化，我們所對應(yīng)的那塊內(nèi)容沒有改變，hash值就不會(huì)改變，找到的永遠(yuǎn)會(huì)是那個(gè)blob。

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

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

OK，這里可能有些同學(xué)要問了，那我如果真的需要存儲(chǔ)很多頻繁變動(dòng)的二進(jìn)制文件，比如多媒體資源/ psd啥的， 那我需要怎么搞？好的，家人們，上鏈接。Git LFS（Large file storage）^[4]一句話介紹，把我們的大文件變成文件指針存儲(chǔ)在對象中，再去lfs拉取對應(yīng)文件。

tree

剛剛我們說了，blob對象是純粹的內(nèi)容，有些不對勁，我們內(nèi)容需要索引，我怎么去找到他？這一節(jié)的標(biāo)題叫做 tree，對，他就是以樹狀結(jié)構(gòu)來進(jìn)行組織的，隨便點(diǎn)開一個(gè)objects下面的文件cat-file看看。

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

commit

現(xiàn)在還有另一個(gè)問題，不過我們其實(shí)上面的演示已經(jīng)解釋了一部分這個(gè)問題了， 一個(gè)commit對應(yīng)的信息其中只有幾種，

• author與對應(yīng)的時(shí)間點(diǎn)
• commit的時(shí)候我們輸入的描述
• 這個(gè)commit所指向的tree
• 這個(gè)commit的parent 即父節(jié)點(diǎn)

git是以類似單向鏈表的形式將我們的一個(gè)個(gè)提交組織起來的，同時(shí)，同時(shí)一個(gè)節(jié)點(diǎn)至多有2個(gè)父節(jié)點(diǎn)。到此，其實(shí)整個(gè)git內(nèi)容存儲(chǔ)的結(jié)構(gòu)我們已經(jīng)捋清楚了。

tag

最后簡單介紹下，最后一種對象，tag是對某個(gè)commit的描述，其實(shí)也是一種commit。

小結(jié)

總結(jié)一下我們以上說的內(nèi)容，我們可以得到git的一個(gè)設(shè)計(jì)思路，git記錄的是一個(gè)a → b過程的鏈表，通過鏈表，我們可以逐步回溯到a，在此之下呢，采用了一種多叉樹形結(jié)構(gòu)對我們的hash值進(jìn)行分層記錄，最底層，通過我們的hash值進(jìn)行索引，對應(yīng)到一個(gè)個(gè)壓縮后的二進(jìn)制objects。這就是整個(gè)git的結(jié)構(gòu)設(shè)計(jì)。還有一些 git對于查找效率的優(yōu)化手段，壓縮手段。

對以上內(nèi)容了解了之后，關(guān)于我們的分支本質(zhì)上，其實(shí)也是對應(yīng)一個(gè)commit，只是多了一個(gè)ref指向這個(gè)commit而已，是不是對git整個(gè)清晰多了。

這里留給大家一個(gè)課后問題吧，git 的 gc怎么去實(shí)現(xiàn)的， 整個(gè)完整過程是啥樣的，由于這些內(nèi)容并不是本文的核心內(nèi)容，就不在這里展開了。

實(shí)現(xiàn)

前期準(zhǔn)備

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

識別命令參數(shù)

首先，讓node環(huán)境能夠讀我們的一些命令，來干各種各樣的事情，通過process的解析，我們能夠獲得輸入的參數(shù)

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，我們現(xiàn)在進(jìn)行下一步，萬事開頭難，先開個(gè)頭吧。使用我們的命令，初始化一個(gè)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','');
}

寫入和讀取

初始化完成了，我們有了一個(gè)存儲(chǔ)庫，接著就是把大象裝進(jìn)冰箱。

剛剛我們在分享的過程中，不斷的用到兩個(gè)命令 git hash-object 和 git cat-file，這兩個(gè)命令，在我們?nèi)粘９ぷ髦校鋵?shí)不太會(huì)用到，他們兩干嘛使的呢。Git 中存在兩個(gè)命令的概念，一個(gè)是底層命令(Plumbing) ，另一個(gè)就是我們?nèi)粘?huì)使用到的上層命令(Porcelain) ， 高層命令是基于底層命令的封裝，讓我們使用起來更為方便。

引入一些npm包，定義一些結(jié)構(gòu)體

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

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

來實(shí)現(xiàn)一個(gè)簡單的讀取blob對象的方法，比較簡陋，還不支持對content進(jìn)行解析，我們將在后續(xù)完善。

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命令實(shí)際上實(shí)現(xiàn)起來就很簡單了，只需要調(diào)用現(xiàn)有的方法就行了。

先是cat-file 對hash 名的一個(gè)尋址，同時(shí)解壓縮對應(yīng)的objects，支持四個(gè)參數(shù)，分別返回不同的結(jié)果。我們直接讀對象就完事了嗷。

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,這個(gè)也簡單的實(shí)現(xiàn)下，就是返回對應(yīng)路徑的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);
  }

現(xiàn)在我們基本結(jié)構(gòu)已經(jīng)搭起來了，需要的是commit 和tree將文件串聯(lián)起來，調(diào)用我們的cat-file試試，現(xiàn)在應(yīng)該對commit和blob的解析是正確的， 但是tree的content的解析似乎有些問題，我們后面來看這個(gè)問題，但是commit對象的content和 blob的content不太一樣。

內(nèi)容解析完善

剛剛我們粗略的實(shí)現(xiàn)了一下讀對象，能把內(nèi)容塊讀出來了。接著我們來完善他，以便更好的服務(wù)于我們的四種對象,先改寫下我們的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);
  // 去掉校驗(yàn)， 其實(shí)這里需要記錄長度和真實(shí)長度對比是否有錯(cuò)
  // 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對象實(shí)現(xiàn)起來很簡單 就不在這里說了。

Commit對象實(shí)現(xiàn)起來稍微復(fù)雜一點(diǎn)，我們需要解析commit對象中的一些鍵值對，將他們都記住，同時(shí)把commit內(nèi)容單獨(dú)存起來。一個(gè)commit對象存儲(chǔ)的東西，在上面我們已經(jīng)介紹過了，通過一個(gè)map將他存儲(chǔ)。

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 相對來說是我們解析起來最為復(fù)雜的一個(gè)對象，他不像前兩個(gè)一樣，能夠通過直接toString就能拿到正常的文本，我們直接去解析就行了。Tree Object本身其實(shí)就是一個(gè)二進(jìn)制對象，關(guān)鍵吧，他還有個(gè)誤導(dǎo)，差點(diǎn)給筆者都給帶偏了，他cat-file解析出來的文件，其實(shí)并不是他原本文件長的樣子....，他做了一個(gè)格式化，且修改了順序。

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;
  }
}

我們的底層基礎(chǔ)簡單實(shí)現(xiàn)，其實(shí)到這里就完結(jié)了，大致流程能夠串起來了。

分支和ref：

分支名和ref其實(shí)也是鍵值對，分支名作為文件名存儲(chǔ)在ref目錄下，文件內(nèi)容則是一串sha1值，這串sha1值來自于commit 頭結(jié)點(diǎn)的hash值，我們可以通過這個(gè)commit 對象回溯到當(dāng)時(shí)的場景。

log與reflog

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

暫存區(qū)：

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

后語

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

課后作業(yè)：

1. git 的gc問題
2. 底層命令來實(shí)現(xiàn)我們?nèi)粘Ｕ{(diào)用的上層命令效果
3. 怎么去實(shí)現(xiàn)一個(gè)遠(yuǎn)程的git中心服務(wù)器，遠(yuǎn)程的命令怎么關(guān)聯(lián)？
4. 補(bǔ)充實(shí)現(xiàn)一個(gè)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