Bloom Filters: “Have I Seen This?” in Tiny Memory
What this episode covers
A Bloom filter answers “have I seen this item before?” with just a row of 0/1 cells and a few hash functions. Inserting an item lights up a handful of cells; if even one of an item’s cells is dark at query time, you can be certain it was never inserted.
The price is false positives: when every cell is lit it can only say “maybe”, but it never misses an item that was inserted. This episode shows how false positives appear, then lets you drag the number of cells m and the number of hash functions k to find the balance between memory and accuracy.
Prerequisites
- Hash Tables: Trading Space for Time Coming soon
Where it is used in the real world
- Cassandra Before reading, it asks each on-disk file’s Bloom filter; a “definitely not here” answer skips that file and saves many disk reads.
- HBase Every store file gets a Bloom filter, so looking up a row only opens the files that might contain it.
- RocksDB The LSM storage engine keeps Bloom filters for the files at each level, so keys that do not exist barely touch the disk.
Watch next
- LSM Trees: Turning Random Writes into Sequential Ones Coming soon
Episode 3
This is episode 3 of the “Data Structures and Algorithms” series (13 planned).