京公网安备11010502063487号服务端怎么在几十毫秒里算出该给 clone 的人发哪些对象?答案是 reachability bitmap。这篇生成 .bitmap,再用 Python 解码 EWAH 压缩位图:四张类型位图、164 张提交位图,并与 git rev-list --objects 逐个对账。
$ ls .git/objects/pack; git count-objects -v | grep -E "^(in-pack|packs)"; git rev-list --objects --all | wc -l
pack-bb7adb7a19a6dc6a176a76fcf3bfee194af1f212.idx
pack-bb7adb7a19a6dc6a176a76fcf3bfee194af1f212.pack
pack-bb7adb7a19a6dc6a176a76fcf3bfee194af1f212.rev
in-pack: 30000
packs: 1
300006000 个提交的线性历史,每次改一个文件,共 30,000 个对象(6000 commit、18,000 tree、6000 blob),git gc 之后是一个 pack,没有 bitmap。
$ git rev-list --objects --count HEAD 30000 耗时 32.8 ms
“从某个提交出发,能到达哪些对象”需要遍历 commit 和 tree,仓库大时很慢。服务端每次 fetch / clone 都要回答这个问题。不用 bitmap 时,本例数 30,000 个可达对象要 32.8 ms。
$ git repack -adbq; ls -l .git/objects/pack/*.bitmap | awk '{print $5, $9}' | sed "s#.git/objects/pack/##"
149820 pack-bb7adb7a19a6dc6a176a76fcf3bfee194af1f212.bitmap
$ git rev-list --use-bitmap-index --objects --count HEAD
30000
耗时 12.5 ms(没有 bitmap 时 32.8 ms,快 2.6 倍)reachability bitmap 为一部分提交预先存下“可达对象集合”:pack 里每个对象一位,1 表示可达。之后集合运算(并、差)变成位运算,不再需要遍历。本例同样的统计降到 12.5 ms,快 2.6 倍。
签名 b'BITM' 版本 1 选项 0x0005 位图化的提交数 164 0000 42 49 54 4d 00 01 00 05 00 00 00 a4 bb 7a db 7a BITM.........z.z 0010 19 a6 dc 6a 17 6a 76 fc f3 bf ee 19 4a f1 f2 12 ...j.jv.....J... …(共 149820 字节) 头部里记的 pack 校验和 bb7adb7a19a6dc6a176a76fcf3bfee194af1f212 pack 文件最后 20 字节 bb7adb7a19a6dc6a176a76fcf3bfee194af1f212 一致: True 选项位: FULL_DAG, HASH_CACHE
.bitmap 以签名 BITM、版本、选项、位图化的提交数、配对 pack 的校验和开头。6000 个提交里只给 164 个存了位图,约 2.7%;其余的提交从最近的位图出发再走几步。
commit 位图:共 6,000 位,其中 6,000 位为 1 tree 位图:共 30,000 位,其中 18,000 位为 1 blob 位图:共 29,640 位,其中 6,000 位为 1 tag 位图:共 0 位,其中 0 位为 1 四类相加 = 30,000;pack 里的对象数 = 30,000
头部后面是 commit / tree / blob / tag 四张类型位图,每个对象一位;位图用 EWAH 压缩(连续的全 0 或全 1 的 64 位字合并成一个游程)。四类 1 的个数相加正好等于 pack 里的对象数。
共解出 164 张;xor_offset 非 0 的有 110 张 entry 里的 object_pos 是提交在 .idx(按 hash 排序)里的下标;位图里的第 n 位对应 pack 里按偏移排序的第 n 个对象 第 0 张:提交 a41517eeba… xor_offset=0 位图里 1 的个数 30,000 git rev-list --objects 数出 30,000 集合完全一致: True 第 82 张:提交 1af1790bea… xor_offset=1 位图里 1 的个数 29,590 git rev-list --objects 数出 29,590 集合完全一致: True 第 163 张:提交 d997d58abf… xor_offset=0 位图里 1 的个数 85 git rev-list --objects 数出 85 集合完全一致: True 每 10 张抽查一张(共 17 张),集合不一致的: 0 HEAD 对应第 0 张
每个被选中的提交有一张可达对象位图,相邻的提交位图可以用 XOR 差分(xor_offset)存储。entry 里的 object_pos 是提交在 .idx(hash 排序)里的下标,而位图的第 n 位对应 pack 里按偏移排序的第 n 个对象——实验里用两种顺序分别映射才得到与 git 完全一致的结果。
git pack-objects --revs --stdout(相当于整库 clone,打包 HEAD 可达的全部对象):不用 bitmap 63.3 ms,用 bitmap 21.4 ms
git 服务端为 clone 打包时需要知道“该发哪些对象”,位图让它不必遍历。本例整库打包 63.3 → 21.4 ms;仓库越大,遍历越慢,差别越明显。