Bloom Filters — Algorithmics

A database with a billion keys spread over a hundred files on disk. A lookup for a key that does not exist reads all hundred files to prove it.

You want to skip the files that certainly do not contain it. Keeping a hash set of every key in memory would cost tens of gigabytes.

The trade

A Bloom filter answers set membership in about 10 bits per item — not 10 bytes, 10 bits — regardless of how big the items are.

The catch is that it can be wrong in exactly one direction:

“Not present” — always true. No false negatives, ever.
“Present” — probably true. Some percentage of the time it is lying.

That asymmetry is what makes it useful. A definite no lets you skip work; an uncertain yes just means you do the work you would have done anyway.

How it works

A bit array, all zeros, and $k$ hash functions.

Insert — hash the item $k$ ways, set those $k$ bits to 1.

Query — hash the item $k$ ways. If any of those bits is 0, the item was definitely never inserted. If all $k$ are 1, it probably was — or other items happened to set all of them.

class BloomFilter {
  private bits: Uint8Array;

  add(key: string) {
    for (let i = 0; i < this.k; i += 1) this.set(this.hash(key, i));
  }

  mightContain(key: string): boolean {
    for (let i = 0; i < this.k; i += 1) {
      if (!this.get(this.hash(key, i))) return false;   // certain
    }
    return true;                                        // probable
  }
}

Sizing it

Three numbers interact, and the arithmetic is worth playing with:

bits per item 10hash functions (k) 7items stored 1,000,000

false positive rate: 0.82%
memory: 1.3 MB
best k for this size: 7

k is optimal for this bit budget. Note what does not appear anywhere: the size of the items. A filter over a million 4 kB documents costs the same as one over a million integers.

p \approx \left(1 - e^{-kn/m}\right)^{k} \qquad k_{\text{best}} = \frac{m}{n}\ln 2 \approx 0.693 \times \frac{m}{n}

The rule of thumb worth remembering: about 10 bits per item gives roughly 1% false positives. For a billion items that is 1.2 GB — against tens of gigabytes for the real keys.

Where it is used

LSM-tree databases — Cassandra, RocksDB, LevelDB, HBase. One filter per SSTable, so a read consults only the files that might contain the key. Without this, LSM reads would be unusable.

CDN edge caches. Deciding whether an object is worth caching on first request, so one-hit-wonders do not evict popular objects.

Chrome’s Safe Browsing used one for malicious URLs — a definite “not malicious” avoids a network call, and a maybe triggers a real check. Exactly the asymmetry the structure provides.

Distributed joins. Send a filter of your keys instead of the keys; the other side ships back only rows that might match.