Github 的清点对象算法

作者: 阮一峰

日期: 2015年9月30日

珠峰培训

使用 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 clonegit 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功能了,因此将来肯定还会有更多好玩的用法出现。

(完)

一灯学堂

优达学城

留言(18条)

简单说就是把一个在线运算编程一个离线运算,并且选用了效率最高的二进制处理。

原理懂了,就像windows里的缩略图索引文件一样,这个Bitmap文件就是闲时有备急时用嘛。话说峰哥的网速真杠杠的:8.70 MiB/s

这是最新的技术么? 意味着想要使用这个新的技术的话,需要更新git?

请教一下:文中流程图用的是什么软件作的?

引用Wop的发言:

请教一下:文中流程图用的是什么软件作的?

我猜是53 Paper

github还真是良心

但是老版本的git没有这个功能,就没有这个Bitmap文件,就没有办法比对,那么老版本的性能依然不好?

我也很想知道这篇博客的配图是用什么做的?

配图引用自:http://githubengineering.com/counting-objects/

引用Lyeec的发言:

这是最新的技术么? 意味着想要使用这个新的技术的话,需要更新git?

Git 2.0+ release 就有了。

另外,counting object 应该算是集成进Git的功能,而非GitHub的(只不过是由GitHub的人实现),所以标题建议改成:Git的清点对象算法。

>>The bitmap-index patchset [2] finally shipped in the much anticipated Git 2.0 release, and now Git network operations from most major Git hosts are enjoying the overhaul.

bitmap patch 集成进Git 2.0,count object 也应该是Git而非GitHub的功能(只不过由GitHub的人实现),所以建议标题改为:Git的对象清点算法

GitHub是好,但是就是在国内访问速度太慢,有什么好办法,可以速度变快些呢?

引用axiaoxin的发言:

配图引用自:http://githubengineering.com/counting-objects/

老师写文,也不标引用了?

编程珠玑中的bitmap。。。

每个commit都会有一个对应的二进制值,表示当前快照包含的所有对象。这些对象对应的二进制位都为1,其他二进制位都为0。

请问快照里面除了对象以外还有什么?不是所有都是对象吗?

想请教一下小书签的问题http://www.ruanyifeng.com/blog/2011/06/a_guide_for_writing_bookmarklet.html

怎么用书签获取网页源码 用alert弹出

引用游客的发言:

想请教一下小书签的问题http://www.ruanyifeng.com/blog/2011/06/a_guide_for_writing_bookmarklet.html

怎么用书签获取网页源码 用alert弹出

下面这行代码应该能满足你的要求:

javascript:(function(){var x;if(window.XMLHttpRequest){x=new 
XMLHttpRequest();}else{x=new ActiveXObject("Microsoft.XMLHTTP");}x.onreadystatechange=function()
{if(this.readyState===4)
{alert(this.responseText);}};x.open('GET',location.href,true);x.send()})
();

引用HACK21的发言:

每个commit都会有一个对应的二进制值,表示当前快照包含的所有对象。这些对象对应的二进制位都为1,其他二进制位都为0。

请问快照里面除了对象以外还有什么?不是所有都是对象吗?

其实这个算法是为了方便的计算 可达性(reachable) 的。
对于给定的commit,如果packfile里第n位的对象是可达的,则bitmap里的第n位就是1,否则就是0

可以参考楼主最后贴的官方文档的解析。

我要发表看法

«-必填

«-必填,不公开

«-我信任你,不会填写广告链接