Supercharging the Git Commit Graph IV: Bloom Filters

This post introduces the application of Bloom filters to accelerate file history calls in Visual Studio Team Services (VSTS) Git. It explains how Bloom filters, as probabilistic sets, can provide a 'definitely not' or 'probably in the set' answer, allowing VSTS to avoid walking Git trees when a path has definitely not changed between commits. The post details the mechanics of Bloom filters, their implementation for file history by creating a filter per commit based on changed paths, and the observed speedups (up to 6x-20x) with minimal storage overhead. It also discusses the potential for extending the Git commit-graph feature to use Bloom filters.