Bloom Filter

A database gets asked for user:48151. The key doesn't exist. How much work does it take to say so?

If every key sits in an in-memory HashSet, almost none, but the set holds every key in full. A hundred million 16-byte keys plus per-entry overhead is several gigabytes, for one table on one node. That's memory you wanted for caching actual data, and it grows with every key you add.

If the keys live only on disk, proving absence means reading the disk. A random read on a spinning disk is about 10 ms; on an SSD, about 100 µs. Both are roughly a thousand times slower than RAM, and a key that isn't there costs as much to look up as one that is. It's often worse: an LSM-tree database like Cassandra or RocksDB keeps data in many sorted files, so a missing key has to be checked in every one of thembefore the database can say “not found”.

Lots of real traffic is exactly this kind of lookup: “has this user already seen this post?”, “is this username taken?”, “does this row exist before I insert it?”. A Bloom filter is a small, fixed-size structure in RAM that answers most of these without touching the disk. It uses about 10 bits per key instead of the whole key, and pays for that by sometimes saying “maybe” when the honest answer is “no”.

Start with an array of m bits, all 0, and pick khash functions. To insert a key, hash it k ways and set those k bits to 1. To check a key, hash it the same k ways and look at those bits. If any of them is 0, the key was never inserted, because inserting it would have set that bit. If they're all 1, the key was probably inserted, or other keys happened to set every one of its bits.

insert(key):
  for i in 0 ..< k:
    bits[(a + i·b) mod m] = 1        // a, b = two hashes of key

mightContain(key):
  for i in 0 ..< k:
    if bits[(a + i·b) mod m] == 0:
      return false                   // definitely not present
  return true                        // maybe present — go check

Real filters rarely run k separate hash functions. They compute two hashes, a and b, and derive the rest as (a + i·b) mod m. Kirsch and Mitzenmacher showed in 2006 that this double hashing does as well as k independent hashes, and it's what the simulation does too. Here is a 32-bit filter with k = 3 after inserting 3 keys:

Three keys set 8 of 32 bits. Notice nothing in the array says which key set which bit, and nothing records the keys themselves. That is where both the space saving and every limitation below come from.

That asymmetry is the whole design. The filter sits in front of something slow and authoritative, and only ever makes the fast path faster. A false positive costs what the lookup would have cost without a filter. A false negative would return wrong data, which is why the structure can't allow one.

With n keys in m bits and k hashes, the chance a given bit is still 0 is about e^(−kn/m). An absent key gets through only if all k of its bits are 1:

p ≈ (1 − e^(−kn/m))^k          false positive rate
k_best = (m/n) · ln 2           ≈ 0.69 × bits per key
m = −n · ln p / (ln 2)²         bits needed for a target p

The best k is where each bit ends up 1 with probability one half. Fewer hashes and a fingerprint is too vague; more and the array fills up too fast. Once k is optimal, only bits per key matters:

Roughly 10 bits per key buys 1%, and each extra ~4.8 bits cuts it another tenfold. For 100,000,000 keys, a 1% filter needs about 120 MB and a 0.1% filter about 180 MB, against gigabytes for the keys themselves. The size depends on how many keys there are, not how long they are: a 200-byte URL costs the same 10 bits as a 4-byte integer.

One catch: m is fixed when the filter is built. Insert far more keys than planned and the rate climbs past anything you sized for, which is what “Saturate to 90%” shows. A filter can't be grown in place because it no longer knows its keys. You rebuild it from the source data, or stack a new, larger filter on top (a scalable Bloom filter).

To delete a key you'd clear its k bits. But any of those bits may also belong to other keys, and the filter has no record of which. Clear a shared bit and every key that relied on it now reads “definitely absent” while it's still stored: a false negative, the one error the filter promised never to make. The fuller the filter, the more bits are shared, so the more damage one delete does. The simulation's “Delete key attempt” picks the most-shared key on purpose so you can watch it happen.

A counting Bloom filterreplaces each bit with a small counter, usually 4 bits. Insert increments, delete decrements, and a slot counts as set while it's above 0. That makes deletes safe, as long as you only delete keys you actually inserted, for about four times the memory. A cuckoo filter gets deletion more cheaply by storing a short fingerprint per key instead of setting shared bits.

* Only if you never delete a key that wasn't inserted. Deleting a false positive removes some other key's fingerprint or count.

Use a HashSet when the keys fit comfortably in memory and you need exact answers. Use a Bloom filter when they don't, the set only grows (or is rebuilt periodically), and a false “maybe” costs one extra read. Reach for a cuckoo filter when you need deletes or want a low false positive rate in less space. A counting Bloom filter is the simplest way to add deletes to code that already uses a Bloom filter, if the 4× memory is affordable.

An LSM-tree database (Cassandra, RocksDB, LevelDB, HBase, ScyllaDB) buffers writes in memory, then flushes them to disk as an immutable, sorted file called an SSTable. Background compaction merges SSTables together, but at any moment a table is spread across many of them. A read has to find the newest version of the key, so it checks SSTables from newest to oldest until it finds one.

For a key that exists, that search stops early. For a key that doesn't, it checks every SSTable, each one at least an index lookup and usually a disk read. With 20 SSTables that's 20 reads to return nothing. This read amplification is the main cost of the LSM design, and negative lookups are its worst case.

So each SSTable is written with its own Bloom filter over the keys it contains, and those filters are kept in memory. A read checks each SSTable's filter first and only opens the files whose filter says “maybe”. At a 1% false positive rate, a miss across 20 SSTables costs 0.2 disk reads on average instead of 20.

Several details make this pairing work especially well:

• SSTables are immutable, so the filter never needs a delete. A deleted row is written as a new tombstone record, not removed from the old file. When compaction merges files, it writes a new SSTable and builds a fresh filter for it, so the delete problem above never comes up.
• The key count is known when the filter is built. Flush and compaction know exactly how many keys go into the new file, so every filter is sized correctly and never saturates.
• The rate is a per-table setting. Cassandra exposes it as bloom_filter_fp_chance(0.01 by default, 0.1 for leveled compaction, where a read touches fewer SSTables). RocksDB configures it as bits per key on the table's filter policy, commonly 10.
• Filter memory is the real budget.At 10 bits per key, a billion keys on a node is about 1.2 GB of filters. RocksDB's optimize_filters_for_hits skips the filter on the last level, which holds most of the data, for workloads where nearly every lookup is for a key that exists.

The simulation is this picture shrunk to one filter: the bottom row is the SSTables, and every “disk seeks prevented” is a file the database didn't have to open.

• CDN caches. Akamai found most URLs are requested exactly once. A Bloom filter of recently seen URLs lets the cache store an object only on its second request, which keeps one-hit wonders from evicting useful content.
• Bigtable and HBase. The same per-file trick as above, from the system that popularized the LSM design.
• Web browsers.Early versions of Chrome's Safe Browsing kept a Bloom filter of malicious URL prefixes locally and only asked Google's servers about URLs that matched.
• Distributed joins.Databases ship a Bloom filter of one side of a join to the nodes holding the other side, so they can drop rows that can't match before sending them over the network.

All of these use the same k-hashes-into-an-array idea as a hash table. The difference is that a Bloom filter drops the keys to save space, which is why it can say “definitely not” but never “definitely yes”.