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就不一一實現了,有興趣可以下來實現。
課後作業:
-
git 的gc問題
-
底層命令來實現我們日常呼叫的上層命令效果
-
怎麼去實現一個遠端的git中心伺服器,遠端的命令怎麼關聯?
-
補充實現一個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
:heart: 謝謝支援
以上便是本次分享的全部內容,希望對你有所幫助^_^
喜歡的話別忘了 分享、點贊、收藏 三連哦~。
歡迎關注公眾號 ELab團隊 收貨大廠一手好文章~
我們來自位元組跳動,是旗下大力教育前端部門,負責位元組跳動教育全線產品前端開發工作。
我們圍繞產品品質提升、開發效率、創意與前沿技術等方向沉澱與傳播專業知識及案例,為業界貢獻經驗價值。包括但不限於效能監控、元件庫、多端技術、Serverless、視覺化搭建、音視訊、人工智慧、產品設計與營銷等內容。
歡迎感興趣的同學在評論區或使用內推碼內推到作者部門拍磚哦
位元組跳動校/社招投遞連結: http://job.toutia o.com/
內推碼: BVJNBUG
- 使用 WebAssembly 打造定製 JS Runtime
- 前端也要懂演算法,不會演算法也能微調一個 NLP 預訓練模型
- 聯機遊戲原理入門即入土 -- 入門篇
- Plasmo Framework:次世代的瀏覽器外掛開發框架
- 深入理解 Mocha 測試框架:從零實現一個 Mocha
- Single Source of Truth:XCode SwiftUI 的介面編輯的設計理念
- 深入理解 D3.js 視覺化庫之力導向圖原理與實現
- 淺析神經網路 Neural Networks
- Cutter - Web視訊剪輯工具原理淺析
- 你可能需要一個四捨五入的工具函式
- 淺析eslint原理
- 最小編譯器the-super-tiny-compiler
- Git儲存原理及部分實現
- 淺談短鏈的設計
- Web元件構建庫-Lit
- 使用Svelte開發Chrome Extension
- Web3.0開發入門
- vscode外掛原理淺析與實戰
- 深入淺出 Web Audio API
- 探祕HTTPS