Github 的清点对象算法

使用 Github 的时候,你有没有见过下面的提示?

这段提示说,远程代码库一共有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功能了,因此将来肯定还会有更多好玩的用法出现。

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-08-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

有趣的算法(四)——一致性Hash算法模拟redis集群

有趣的算法(四)——一致性Hash算法模拟redis集群 (原创内容,转载请注明来源,谢谢) 一、概述 redis的集群,对key存储在哪个服务器的问题上,采...

38770
来自专栏Jerry的SAP技术分享

用代码判断当前系统是否支持某个版本的feature

JDK9已经出来有一段时间了,因此很多流行的Java应用纷纷增添了对JDK9乃至JDK10的支持,比如Tomcat。

14520
来自专栏人人都是极客

环形缓冲区的实现

队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。

39040
来自专栏前端杂货铺

[译] Cookbook of QUnit

本篇文章是QUnit的简介,可以作为很好的入门教程。文章原址 介绍 自动化测试时软件开发过程中必不可少的一部分,而单元测试则是自动化测试的最为基本的一块,软件的...

310110
来自专栏HansBug's Lab

关于使用lazytag的线段树两种查询方式的比较研究

说到线段树,想来大家并不陌生——最基本的思路就是将其规划成块,然后只要每次修改时维护一下即可。 但是尤其是涉及到区间修改时,lazytag的使用往往能够对于程序...

33070
来自专栏同步博客

memcached分布式缓存

  memcached虽然称为“分布式”缓存服务器,但服务器端并没有“分布式”功能。Memcache集群主机不能够相互通信传输数据,它的“分布式”是基于客户端的...

15810
来自专栏用户画像

Python 使用正则表达式进行MongoDB条件查询

db.VideoProfile.find( {_id: { $regex: /^1_[0-9]{5,}$/} } ).count()

10220
来自专栏跟着阿笨一起玩NET

T4模板语法

T4,即4个T开头的英文字母组合:Text Template Transformation Toolkit。

15610
来自专栏DOTNET

ASP.NET MVC编程——模型

1 ViewModel 是一种专门提供给View使用的模型,使用ViewModel的理由是实体或领域模型所包含的属性比View使用的多或少,这种情况下实体或领域...

33780
来自专栏小李刀刀的专栏

在ASP中实现UNIX时间戳

  在康盛创想发布UC以后,我曾经尝试为其编写ASP把版本的客户端类库,过程中发现了几个问题,首当其冲的当然是服务器端不支持非php平台的接口,这个问题直接导致...

43160

扫码关注云+社区

领取腾讯云代金券