Bloom Filters: The Yes/No That Saves a Disk Seek

A read lands on a Cassandra node: SELECT * WHERE key = 'user:8f3a'. That key might live in any of a dozen immutable SSTable files on disk, each one a candidate that costs a random seek to check. Cassandra could dutifully seek into all of them and find nothing — the key was never written. Instead, before touching the disk, it asks a small in-memory structure one question per file: have you possibly seen this key? Eleven files answer “definitely not.” One says “maybe.” Cassandra seeks into that one file, and only that one.

That structure is a Bloom filter. It turned a dozen disk seeks into one, using a few kilobytes of RAM, by being willing to occasionally say “maybe” when the honest answer was “no.”

The intuition: a fingerprint smeared across a bit array

Imagine a long row of light switches, all off. To record that you’ve seen an item, you run it through k different hash functions; each picks one switch, and you flip those k switches on. That’s the entire “insert.”

To ask have I seen this item?, you hash it the same k ways and peek at those same k switches. If any of them is off, the item was never inserted — flipping is one-way, so a switch that should be on can’t have drifted off. That’s the ironclad “definitely not.” If all k are on, the item was probably inserted — but maybe those switches were flipped on by other items that happened to collide. That’s the “maybe.”

You never stored the items themselves — only the smudge they left on the bit array. That’s why a Bloom filter can summarize a billion keys in megabytes, and why it can never hand you a key back or delete one.

From here the members-only continuation builds the whole picture: the bit-array-and-double-hashing diagram, a complete Bloom filter in code, the sizing math (how many bits and hashes for your target false-positive rate), the hard limits and why deletion is impossible, where Cassandra, Chrome, and CDNs deploy it in production, and an interview corner with a design challenge and a quiz.