One Hash Bloom Filters
This article explains the technical utility of Bloom filters, a probabilistic data structure used to optimize database lookups by reducing disk I/O. The author demonstrates how they are used in high-performance systems like Bluesky to scale efficiently.
Why it matters
Bloom filters are a fundamental building block for modern high-scale distributed systems, allowing developers to manage massive datasets with minimal memory overhead.
Note: as always, all my public writing is written by hand by me.
A bloom filter is a probabilistic data structure that allows you to quickly and cheaply answer the question "is key X in this set?" with either "definitely not" or "probably" .
You pick a false positive rate that is acceptable for your workload and hardware, add keys to the set, and check for their existence later on.
Bloom filters use a small amount of memory compared to the cardinality of the set, and are computationally very cheap. For these reasons, they're frequently used in high performance data systems.
For example, a database might keep an in-memory bloom filter and check it before actually going to disk when looking up rows. This saves substantial amounts of very slow disk IO.
Get smarter about the news
Sign up free for a feed built around what you actually care about, Dive Deeper research on any story, and the full text of every article.
Create free accountAlready have an account? Sign in