close

大廠技術堅持周更精選好文

手把手教你理解輪子之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//commitlint規則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//顧名思義，記錄我們的gitlog│├──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"|githash-object--stdinconstcrypto=require('crypto'),constsha1=crypto.createHash('sha1');sha1.update("blob11\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的解析，我們能夠獲得輸入的參數

enumCommandEnum{Add='add',Init='init',...}constchooseCommand=(command:CommandEnum)=>{switch(command){caseCommandEnum.Add:returnadd();caseCommandEnum.Init:returninit();...default:break;}console.log("暫不支持此命令")}chooseCommand(process.argv[2]asCommandEnum);init

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

constinit=()=>{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=0filemode=truebare=falselogallrefupdates=trueignorecase=trueprecomposeunicode=true`);fs.writeFileSync('.git/description','');}寫入和讀取

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

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

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

importfsfrom'fs';importzlibfrom'zlib';importcryptofrom'crypto';exportenumGitObjectType{Commit='commit',Tree='tree',Blob='blob',Tag='tag'}

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

exportconstreadObject=(sha1='f8eb512de72634ca12328d85f70b696414473914')=>{constdata=fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);consta=zlib.inflateSync(data).toString('utf8');consttypeIndex=a.indexOf('');constlengthIndex=a.indexOf(`\0`);constobjType=a.substring(0,typeIndex);constlength=a.substring(typeIndex+1,lengthIndex);constcontent=a.substring(lengthIndex+1);//console.log(a);return{objType,length,content};}

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

exportconstcreateObject=(obj:GitObject)=>{constdata=obj.serialize();constsha1=crypto.createHash('sha1');sha1.update(data);constname=sha1.digest("hex");constzipData=zlib.deflateSync(data);console.log(name);constdirName=`.git/objects/${name.substring(0,2)}`fs.existsSync(dirName)&&fs.mkdirSync(dirName);fs.writeFileSync(`.git/objects/${name.substring(0,2)}/${name.substring(2)}`,zipData)returnname;}

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

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

exportconstcatFile=()=>{consttype=process.argv[3];constsha1=process.argv[4];constres=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值就行了

exportconsthashObject=()=>{constpath=process.argv[3];constdata=fs.readFileSync(path);constsha1=crypto.createHash('sha1');sha1.update(data);constname=sha1.digest("hex");console.log(name);}

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

內容解析完善

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

readObjectexportconstreadObject=(sha1:string)=>{constdata=fs.readFileSync(`.git/objects/${sha1.substring(0,2)}/${sha1.substring(2)}`);constbuf=zlib.inflateSync(data)consta=buf.toString('utf8');consttypeIndex=a.indexOf('');constlengthIndex=a.indexOf(`\0`);//console.log(a);constobjType=a.substring(0,typeIndex);//去掉校驗，其實這裡需要記錄長度和真實長度對比是否有錯//constlength=a.substring(typeIndex+1,lengthIndex);letobj;if(objType===GitObjectType.Blob){obj=newGitBlob(a.substring(lengthIndex+1));}if(objType===GitObjectType.Commit){obj=newGitCommit(a.substring(lengthIndex+1))}if(objType===GitObjectType.Tree){obj=newGitTree(buf.slice(lengthIndex+1))}returnobj;}

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

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

Commit objectclassGitCommitextendsGitObject{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))returnthis.data;}recursiveParse=(data:string,map?:any):any=>{if(!map){map=newMap();}constspace=data.indexOf('');constnl=data.indexOf(`\n`);console.log(space,nl);if(space<0||nl<space){map.set("content",data);returnmap;}constkey=data.substring(0,space);letend=0;while(true){end=data.indexOf(`\n`,end+1)if(data[end+1]!=='')break;}constvalue=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)}constrestData=data.substring(end+1);returnthis.recursiveParse(restData,map);}}Tree Object解析

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

classGitTreeextendsGitObject{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)=>{constx=data.indexOf('',start);if(x<0){returnstart+21;}constmode=data.slice(start,x).toString('ascii');//consttype=consty=data.indexOf(`\x00`,x)if(y<0){returnx+21};constpath=data.slice(x+1,y).toString('ascii');constsha1=data.slice(y+1,y+21).toString('hex');console.log(mode,path,sha1);returny+21;}deserialize=()=>{constbuffer=this.data;letpos=0;letmax=buffer.length;while(pos<max){pos=this.parseTreeOneLine(buffer,pos);}returnthis.data;}}我們的底層基礎簡單實現，其實到這裡就完結了，大致流程能夠串起來了。分支和ref：

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

log與reflog

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

暫存區：

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

後語

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

課後作業：

git 的gc問題
底層命令來實現我們日常調用的上層命令效果
怎麼去實現一個遠程的git中心服務器，遠程的命令怎麼關聯？
補充實現一個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團隊收貨大廠一手好文章~

我們來自字節跳動，是旗下大力教育前端部門，負責字節跳動教育全線產品前端開發工作。

我們圍繞產品品質提升、開發效率、創意與前沿技術等方向沉澱與傳播專業知識及案例，為業界貢獻經驗價值。包括但不限於性能監控、組件庫、多端技術、Serverless、可視化搭建、音視頻、人工智能、產品設計與營銷等內容。

歡迎感興趣的同學在評論區或使用內推碼內推到作者部門拍磚哦 🤪

字節跳動校/社招投遞鏈接: https://job.toutiao.com/

內推碼：BVJNBUG

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 鑽石舞台 的頭像
    鑽石舞台

    鑽石舞台

    鑽石舞台 發表在 痞客邦 留言(0) 人氣()