Github 的清點(diǎn)對(duì)象算法
使用 Github 的時(shí)候，你有沒(méi)有見(jiàn)過(guò)下面的提示？
- $ git clone https://github.com/torvalds/linux
- Cloning into 'linux'...
- remote: Counting objects: 4350078, done.
- remote: Compressing objects: 100% (4677/4677), done.
- Receiving objects: 4% (191786/4350078), 78.19 MiB | 8.70 MiB/s
這段提示說(shuō)，遠(yuǎn)程代碼庫(kù)一共有4350078個(gè)對(duì)象需要克隆。
這就叫”清點(diǎn)對(duì)象”（counting objects），Github需要實(shí)時(shí)計(jì)算出來(lái)，需要克隆的對(duì)象總數(shù)。
這個(gè)過(guò)程非常慢，根據(jù)Github的披露，像Linux kernel這樣巨大的庫(kù)，清點(diǎn)一次需要8分鐘！也就是說(shuō)，發(fā)出git clone命令后，會(huì)干等八分鐘，然后才會(huì)開(kāi)始真正的數(shù)據(jù)傳輸。這當(dāng)然是無(wú)法忍受的。Github團(tuán)隊(duì)一直想解決這個(gè)問(wèn)題。
后來(lái)，他們終于發(fā)現(xiàn)了一種新的算法，現(xiàn)在清點(diǎn)一次只要3毫秒！
為了理解這個(gè)算法，你必須先知道，什么是Git的對(duì)象。簡(jiǎn)單說(shuō)，對(duì)象就是文件，最重要的對(duì)象有三種。
快照對(duì)象（Commit）
目錄對(duì)象（Directory）
文件對(duì)象（File）
每次提交代碼的時(shí)候，會(huì)生成一個(gè)commit對(duì)象，里面有對(duì)應(yīng)的當(dāng)前”目錄對(duì)象”的名字。”目錄對(duì)象”保存了代碼根目錄所含有的子目錄和文件信息。每一個(gè)子目錄就是另一個(gè)”目錄對(duì)象”，每一個(gè)文件則是”文件對(duì)象”，里面是具體的文件內(nèi)容。
所以，”清點(diǎn)對(duì)象”就是清點(diǎn)各種commit、目錄、文件等。git clone和git fetch操作都需要清點(diǎn)對(duì)象，因?yàn)樾枰?，到底下載哪些對(duì)象文件。
清點(diǎn)對(duì)象的原始算法如下。
列出本地所有分支***的一個(gè)commit
列出遠(yuǎn)程所有分支***的一個(gè)commit
兩者進(jìn)行比較，只要有不同，就意味著分支發(fā)生變動(dòng)
每一個(gè)發(fā)生變動(dòng)的commit，都清點(diǎn)其中具體變動(dòng)的子目錄和文件
追溯到當(dāng)前commit的父節(jié)點(diǎn)，重復(fù)第四步，直至本地與遠(yuǎn)程的歷史一致為止
加總所有需要變動(dòng)的對(duì)象
上面的過(guò)程說(shuō)明，”清點(diǎn)對(duì)象”是一個(gè)文件遍歷算法，變動(dòng)的對(duì)象會(huì)被一一清點(diǎn)到，這就意味著大量的文件讀操作。對(duì)于大型代碼庫(kù)來(lái)說(shuō)，這個(gè)過(guò)程非常慢。
Github團(tuán)隊(duì)想到的新算法，是建立一個(gè)Bitmap索引，即為每一個(gè)commit生成一個(gè)二進(jìn)制值。
打開(kāi)本地Github倉(cāng)庫(kù)的.git/objects/pack/目錄，你會(huì)看到一個(gè)索引文件和一個(gè)數(shù)據(jù)文件，它們就是Bitmap。簡(jiǎn)單說(shuō)，這兩個(gè)文件索引了當(dāng)前代碼庫(kù)的所有對(duì)象，然后使用一個(gè)二進(jìn)制值代表這些對(duì)象。有多少個(gè)對(duì)象，這個(gè)二進(jìn)制值就有多少位。它的第n位，就代表數(shù)據(jù)文件里面的第n個(gè)對(duì)象。
每個(gè)commit都會(huì)有一個(gè)對(duì)應(yīng)的二進(jìn)制值，表示當(dāng)前快照包含的所有對(duì)象。這些對(duì)象對(duì)應(yīng)的二進(jìn)制位都為1，其他二進(jìn)制位都為0。
這樣做的好處是，不用讀取commit對(duì)象，只要讀取這個(gè)二進(jìn)制值，就會(huì)知道當(dāng)前commit包含了哪些節(jié)點(diǎn)。更妙的是，兩個(gè)二進(jìn)制值只要做一次 XOR運(yùn)算，就會(huì)知道哪些位（即哪些對(duì)象）發(fā)生了變動(dòng)。而且，因?yàn)樾碌膶?duì)象總是添加到現(xiàn)有二進(jìn)制位的后面，所以只要讀取多出來(lái)的那些位，就知道當(dāng)前 commit比上一次commit多出了哪些對(duì)象。
這樣一來(lái)，”清點(diǎn)對(duì)象”就變成了二進(jìn)制值的比較運(yùn)算，因此速度極快。進(jìn)一步的介紹，請(qǐng)參看官方文檔《Bitmap的解釋》，《Bitmap的格式》。
目前，Github的生產(chǎn)環(huán)境已經(jīng)部署了這套算法，用戶再也不用為了清點(diǎn)對(duì)象，而苦苦等待了。而且，Github團(tuán)隊(duì)還把它合并進(jìn)了Git，這意味著，從此所有Git實(shí)現(xiàn)都可以使用Bitmap功能了，因此將來(lái)肯定還會(huì)有更多好玩的用法出現(xiàn)。
