使用 Bloom Filters 更快找到 Git 文件历史
本文讨论了一种能够加速查找与某个文件相关的所有 git log 的优化：使用 Bloom Filters。
Git Commit 的数据结构是一颗哈希树。树节点是文件快照，树的边是文件目录。
这种数据结构决定了 checkout 某个版本的数据方便，但是检索历史将要遍历很长的提交历史才行。 鉴于这颗树还与目录成绩长度有关，嵌套深的时候查起来很费力：
Bloom Filters 是一个 probabilistic set. 这个 set 就是一些比特位组成的开关，每次设置完之后我们查询问题可以得到两个答案：绝对不可能 / 可能. 如果我们能够得到前一个答案，意味着我们可以不用再深入检查了，只需要检查那些 可能 的case 是不是 true 即可。
一些工程上的小观察：
- 如果文件有变更，提交的父亲目录也会变更
- VSTS 对路径名长度设置为 512，因为路径名长度符合对数正态分布, 512 以上就比较少见了
- 大部分提交都很小
- 实测 false positive 概率只有 1%，意味着这个算法用上去速度能加快 99 倍
