在线午夜精品自拍小视频_无码av无码专区线_亚洲无码精品人妻_人人澡欧美一区

用 Node 實(shí)現(xiàn)一個(gè)簡(jiǎn)易 Git，了解一下存儲(chǔ)原理

以下文章來(lái)源于ELab團(tuán)隊(duì) ，作者ELab.yepeng

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

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

手把手教你理解輪子之 Git

現(xiàn)狀分析
來(lái)，我們克服一下恐懼，我們?yōu)槭裁磿?huì)覺(jué)得這個(gè)東西很復(fù)雜，因?yàn)樗娴暮軓?fù)雜，光是上層命令，就有各種各樣的用法，就算筆者也不敢說(shuō)真的能夠精通，關(guān)鍵是他的文檔 居然夠?qū)懸槐緯綪ro Git】[1]，還有王法嗎，還有法律嗎？

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

對(duì)于本文，其實(shí)你并不需要了解太多的東西，一點(diǎn)點(diǎn)的Git基本知識(shí)，一點(diǎn)點(diǎn)基本語(yǔ)言知識(shí)，一點(diǎn)點(diǎn)的shell知識(shí)，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
嗯，差不多，單純本地的倉(cāng)庫(kù) 我們要用到的命令是不是就這些，我們將在主要內(nèi)容分享完之后，再回到這里來(lái)理解這些命令。

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

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



├── COMMIT_EDITMSG  // 上一次提交的 msg
├── FETCH_HEAD // 遠(yuǎn)端的所有分支頭指針 hash
├── HEAD // 當(dāng)前頭指針
├── ORIG_HEAD //
├── config // 記錄一些配置和遠(yuǎn)端映射
├── description // 倉(cāng)庫(kù)描述
├── 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
對(duì)這些倉(cāng)庫(kù)分析完，突然發(fā)現(xiàn)，我們是不是只需要這一個(gè)目錄下的東西，就可以將一個(gè)repo的所有源信息拷貝。

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


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

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

"{type} {content.length}\0{content}"
OK，那我們來(lái)嘗試下生成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ù)庫(kù)的文件系統(tǒng)，通過(guò)sha1算法生成的hash作為key，對(duì)應(yīng)到我們的git的幾類對(duì)象，然后再去樹狀的尋址，最底層存儲(chǔ)的是我們的文件內(nèi)容。

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

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

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

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



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

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

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

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



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


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

author與對(duì)應(yīng)的時(shí)間點(diǎn)
commit的時(shí)候我們輸入的描述
這個(gè)commit所指向的tree
這個(gè)commit的parent 即父節(jié)點(diǎn)
git是以類似單向鏈表的形式將我們的一個(gè)個(gè)提交組織起來(lái)的，同時(shí)，同時(shí)一個(gè)節(jié)點(diǎn)至多有2個(gè)父節(jié)點(diǎn)。到此，其實(shí)整個(gè)git內(nèi)容存儲(chǔ)的結(jié)構(gòu)我們已經(jīng)捋清楚了。


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

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

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

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

實(shí)現(xiàn)
前期準(zhǔn)備
回想一下前面講的，我們需要的東西有些什么，sha1，這個(gè)可以用crypto， zlib，node中也帶了這個(gè)，可以通過(guò) require('zlib')拿到。

識(shí)別命令參數(shù)
首先，讓node環(huán)境能夠讀我們的一些命令，來(lái)干各種各樣的事情，通過(guò)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)行下一步，萬(wàn)事開頭難，先開個(gè)頭吧。使用我們的命令，初始化一個(gè)git倉(cāng)庫(kù)。

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ǔ)庫(kù)，接著就是把大象裝進(jìn)冰箱。

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

引入一些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'
}
來(lái)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的讀取blob對(duì)象的方法，比較簡(jiǎn)陋，還不支持對(duì)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)起來(lái)就很簡(jiǎn)單了，只需要調(diào)用現(xiàn)有的方法就行了。

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

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è)也簡(jiǎn)單的實(shí)現(xiàn)下，就是返回對(duì)應(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)搭起來(lái)了，需要的是commit 和tree將文件串聯(lián)起來(lái)，調(diào)用我們的cat-file試試，現(xiàn)在應(yīng)該對(duì)commit和blob的解析是正確的， 但是tree的content的解析似乎有些問(wèn)題，我們后面來(lái)看這個(gè)問(wèn)題，但是commit對(duì)象的content和 blob的content不太一樣。

內(nèi)容解析完善
剛剛我們粗略的實(shí)現(xiàn)了一下讀對(duì)象，能把內(nèi)容塊讀出來(lái)了。接著我們來(lái)完善他，以便更好的服務(wù)于我們的四種對(duì)象,先改寫下我們的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í)這里需要記錄長(zhǎng)度和真實(shí)長(zhǎng)度對(duì)比是否有錯(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對(duì)象實(shí)現(xiàn)起來(lái)很簡(jiǎn)單 就不在這里說(shuō)了。

Commit對(duì)象實(shí)現(xiàn)起來(lái)稍微復(fù)雜一點(diǎn)，我們需要解析commit對(duì)象中的一些鍵值對(duì)，將他們都記住，同時(shí)把commit內(nèi)容單獨(dú)存起來(lái)。一個(gè)commit對(duì)象存儲(chǔ)的東西，在上面我們已經(jīng)介紹過(guò)了，通過(guò)一個(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 相對(duì)來(lái)說(shuō)是我們解析起來(lái)最為復(fù)雜的一個(gè)對(duì)象，他不像前兩個(gè)一樣，能夠通過(guò)直接toString就能拿到正常的文本，我們直接去解析就行了。Tree Object本身其實(shí)就是一個(gè)二進(jìn)制對(duì)象，關(guān)鍵吧，他還有個(gè)誤導(dǎo)，差點(diǎn)給筆者都給帶偏了，他cat-file解析出來(lái)的文件，其實(shí)并不是他原本文件長(zhǎng)的樣子....，他做了一個(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ǔ)簡(jiǎn)單實(shí)現(xiàn)，其實(shí)到這里就完結(jié)了，大致流程能夠串起來(lái)了。
分支和ref：
分支名和ref其實(shí)也是鍵值對(duì)，分支名作為文件名存儲(chǔ)在ref目錄下，文件內(nèi)容則是一串sha1值，這串sha1值來(lái)自于commit 頭結(jié)點(diǎn)的hash值，我們可以通過(guò)這個(gè)commit 對(duì)象回溯到當(dāng)時(shí)的場(chǎng)景。

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

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

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

課后作業(yè)：

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

作者：ELab.yepeng

歡迎關(guān)注微信公眾號(hào) ：前端印象