System designDeep dive3 min

Bloom filters

Answer have I seen this before? in a few bytes per item, with no false no's: a no is always right, a yes is right almost always.

1 · The idea

A row of bits and a few hash functions

Keep an array of m bits, all zero, and pick k hash functions. To add an item, hash it k ways and set those bits. To check an item, look at the same k bits: if any is zero, the item was never added. If all are one, it probably was: other items may have set those bits.

  1. Add "alice".

    Hashes point at bits 2, 7 and 11: set them.

  2. Add "bob".

    Bits 4, 7 and 13: set them (7 is already set).

  3. Check "carol".

    Bits 2, 9, 13: bit 9 is zero, so carol was definitely never added.

  4. Check "dave".

    Bits 4, 11, 13: all set, by alice and bob. The filter says maybe, and it's wrong: a false positive.

2 · The trade

More bits per item, fewer false positives

With the best number of hash functions (about 0.7 × bits per item), the false-positive rate falls fast as you give each item more bits. About 10 bits per item gives 1%, whatever the items are: URLs, ids or whole documents.

05105101520Bits per itemFalse positives (%)≈1%

A billion ids at 1% fit in about 1.2 GB. The ids themselves might take 16 GB or more.

3 · Where they're used

Skip expensive lookups that would find nothing

SystemQuestion the filter answers
Databases built on LSM trees (Cassandra, RocksDB)Could this file on disk hold the key? A *no* skips a disk read
CachesDoes this id exist at all? A *no* stops lookups for keys that don't exist
Web crawlersHave we already fetched this URL?
Sign-up formsIs this password in a list of leaked ones? Check locally before a slower exact check

4 · The limits

No deleting, and plan the size up front

You can't remove an item: clearing its bits might clear someone else's. A counting Bloom filter keeps small counters instead of bits to allow it, at several times the memory. And the false-positive rate climbs as you add items past the size you planned for, so size for the final count, or rebuild.

A Bloom filter in a few lines

typescript
class Bloom {
  private bits: Uint8Array;
  constructor(private m: number, private k: number) {
    this.bits = new Uint8Array(Math.ceil(m / 8));
  }
  private *positions(item: string) {
    const h1 = hash(item, 1), h2 = hash(item, 2);
    for (let i = 0; i < this.k; i++) yield (h1 + i * h2) % this.m; // double hashing
  }
  add(item: string) {
    for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
  }
  mightContain(item: string) {
    for (const p of this.positions(item)) if (!(this.bits[p >> 3] & (1 << (p & 7)))) return false;
    return true;
  }
}

Check yourself

3 questions

1. A Bloom filter says an item is not in the set. How sure can you be?
2. About how many bits per item give a 1% false-positive rate?
3. Why can't a plain Bloom filter delete an item?

Takeaways

Remember this

  • A no is certain, a yes is probable.
  • About 10 bits per item gives about 1% false positives.
  • Use one to skip lookups that would find nothing: disk reads, cache misses, repeat work.
  • No deletes without counters, and size it for the final item count.