阮一峰：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

這段提示說，遠程代碼庫一共有 4350078 個對象需要克隆。

這就叫"清點對象"（counting objects），Github 需要實時計算出來，需要克隆的對象總數。

這個過程非常慢，根據 Github 的披露，像 Linux kernel 這樣巨大的庫，清點一次需要 8 分鐘！也就是說，發出git clone命令后，會干等八分鐘，然后才會開始真正的數據傳輸。這當然是無法忍受的。Github 團隊一直想解決這個問題。

后來，他們終于發現了一種新的算法，現在清點一次只要 3 毫秒！

為了理解這個算法，你必須先知道，什么是 Git 的對象。簡單說，對象就是文件，最重要的對象有三種。

快照對象（Commit）
目錄對象（Directory）
文件對象（File）

每次提交代碼的時候，會生成一個 commit 對象，里面有對應的當前"目錄對象"的名字。"目錄對象"保存了代碼根目錄所含有的子目錄和文件信息。每一個子目錄就是另一個"目錄對象"，每一個文件則是"文件對象"，里面是具體的文件內容。

所以，"清點對象"就是清點各種 commit、目錄、文件等。git clone和git fetch操作都需要清點對象，因為需要知道，到底下載哪些對象文件。

清點對象的原始算法如下。

1. 列出本地所有分支最新的一個 commit
2. 列出遠程所有分支最新的一個 commit
3. 兩者進行比較，只要有不同，就意味著分支發生變動
4. 每一個發生變動的 commit，都清點其中具體變動的子目錄和文件
5. 追溯到當前 commit 的父節點，重復第四步，直至本地與遠程的歷史一致為止
6. 加總所有需要變動的對象

上面的過程說明，"清點對象"是一個文件遍歷算法，變動的對象會被一一清點到，這就意味著大量的文件讀操作。對于大型代碼庫來說，這個過程非常慢。

Github 團隊想到的新算法，是建立一個 Bitmap 索引，即為每一個 commit 生成一個二進制值。

打開本地 Github 倉庫的.git/objects/pack/目錄，你會看到一個索引文件和一個數據文件，它們就是 Bitmap。簡單說，這兩個文件索引了當前代碼庫的所有對象，然后使用一個二進制值代表這些對象。有多少個對象，這個二進制值就有多少位。它的第n位，就代表數據文件里面的第n個對象。

每個 commit 都會有一個對應的二進制值，表示當前快照包含的所有對象。這些對象對應的二進制位都為1，其他二進制位都為0。

這樣做的好處是，不用讀取 commit 對象，只要讀取這個二進制值，就會知道當前 commit 包含了哪些節點。更妙的是，兩個二進制值只要做一次 XOR 運算，就會知道哪些位（即哪些對象）發生了變動。而且，因為新的對象總是添加到現有二進制位的后面，所以只要讀取多出來的那些位，就知道當前 commit 比上一次 commit 多出了哪些對象。

這樣一來，"清點對象"就變成了二進制值的比較運算，因此速度極快。進一步的介紹，請參看官方文檔《Bitmap 的解釋》，《Bitmap 的格式》。

目前，Github 的生產環境已經部署了這套算法，用戶再也不用為了清點對象，而苦苦等待了。而且，Github 團隊還把它合并進了 Git，這意味著，從此所有 Git 實現都可以使用 Bitmap 功能了，因此將來肯定還會有更多好玩的用法出現。