$ 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
操作都需要清點對象,因為需要知道,到底下載哪些對象文件。
清點對象的原始算法如下。
上面的過程說明,"清點對象"是一個文件遍歷算法,變動的對象會被一一清點到,這就意味著大量的文件讀操作。對於大型代碼庫來說,這個過程非常慢。
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 功能了,因此將來肯定還會有更多好玩的用法出現。
GitHub 教程系列文章:
通過GitHub創建個人技術博客圖文詳解 http://www.linuxidc.com/Linux/2015-02/114121.htm
GitHub 使用教程圖文詳解 http://www.linuxidc.com/Linux/2014-09/106230.htm
Git 標簽管理詳解 http://www.linuxidc.com/Linux/2014-09/106231.htm
Git 分支管理詳解 http://www.linuxidc.com/Linux/2014-09/106232.htm
Git 遠程倉庫詳解 http://www.linuxidc.com/Linux/2014-09/106233.htm
Git 本地倉庫(Repository)詳解 http://www.linuxidc.com/Linux/2014-09/106234.htm
Git 服務器搭建與客戶端安裝 http://www.linuxidc.com/Linux/2014-05/101830.htm
Git 概述 http://www.linuxidc.com/Linux/2014-05/101829.htm
分享實用的GitHub 使用教程 http://www.linuxidc.com/Linux/2014-04/100556.htm
GitHub 的詳細介紹:請點這裡
GitHub 的下載地址:請點這裡