One Hash Bloom Filters

Bloom filters are probabilistic data structures that efficiently answer whether a key exists in a set with minimal memory and computation, making them valuable for high-performance systems like databases. Bluesky uses bloom filters extensively in its backend to avoid millions of database queries per second, achieving roughly 99% hit rates that skip unnecessary disk lookups for operations like checking blocks and mutes. Traditional bloom filters use multiple hash functions, but the double hashing technique developed by Kirsch and Mitzenmacher in 2008 achieves similar false positive rates using just two hashes, further reducing computational overhead.