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