Bloom filters

The problem: an expensive "no"

Before Snip shortens a URL, it checks it against a blocklist of known phishing and malware sites: 50 million entries from a security feed, held by a separate blocklist service. Snip creates about 350 links a second at peak, and almost every URL is fine. So nearly every check is a network call whose answer is "no".

Keeping the whole list in each app server would avoid the call, but 50 million URLs averaging 80 bytes is about 4 GB per server. What Snip needs is something small that can say "definitely not on the list" for the clean URLs, and send only the rest to the service.

How a Bloom filter works

A Bloom filter is an array of m bits, all zero to start, and k hash functions.

• Add an item: hash it k ways, giving k positions, and set those bits to 1.
• Check an item: hash it the same k ways. If any of those bits is 0, the item was definitely never added. If all are 1, it was probably added, or its bits happen to have been set by other items.

So a Bloom filter has no false negatives (if it says no, the answer is no) and a tunable rate of false positives (it sometimes says maybe for an item that isn't there). For Snip that's exactly right: a false positive costs one unnecessary call to the blocklist service, which gives the real answer.

Sizing one

Two numbers decide the size: how many items you'll add (n) and the false positive rate you'll accept (p). The optimal size and number of hashes are:

bits  m = −n · ln(p) / (ln 2)²
hashes k = (m / n) · ln 2

That works out to roughly 10 bits per item for 1%, whatever the items are:

Each extra 5 bits per item cuts false positives about tenfold. For Snip's 50 million URLs at 1%: about 480 million bits, 60 MB, with 7 hashes. That fits comfortably in every app server, against 4 GB for the list itself.

A small implementation

Instead of k different hash functions, a standard trick derives all k positions from two hashes: position i is h1 + i·h2, wrapped to the array's size.

import { createHash } from "node:crypto";

export class BloomFilter {
  readonly m: number; // bits
  readonly k: number; // hashes per item
  private bits: Uint8Array;

  constructor(expectedItems: number, falsePositiveRate: number) {
    this.m = Math.ceil((-expectedItems * Math.log(falsePositiveRate)) / Math.LN2 ** 2);
    this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.LN2));
    this.bits = new Uint8Array(Math.ceil(this.m / 8));
  }

  private positions(item: string): number[] {
    const d = createHash("md5").update(item).digest();
    const h1 = d.readUInt32BE(0);
    const h2 = (d.readUInt32BE(4) | 1) >>> 0; // odd, and unsigned
    return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);
  }

  add(item: string) {
    for (const p of this.positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
  }

  /** false: definitely never added. true: probably added. */
  mightContain(item: string): boolean {
    return this.positions(item).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0);
  }
}

Tested with 200,000 items at a 1% target, it uses 240 KB, reports every added item, and says "maybe" for about 0.98% of items it never saw. (The >>> 0 matters: without it, | turns large hashes negative in JavaScript and positions go out of range.)

What Bloom filters can't do

• No deletes. Clearing an item's bits could clear bits other items share. Rebuild the filter from the source list instead (Snip rebuilds from the feed every hour and swaps it in), or use a counting Bloom filter or a cuckoo filter, which support removal at a cost in space.
• Fixed capacity. Add far more than n items and the false positive rate climbs steeply. Size for growth, and rebuild larger when needed.
• No listing. You can't get the items back out; it only answers "might this be in the set?"

Where they're used

The classic use is inside storage engines. An LSM-tree database (09.03 The LSM write and read path) keeps data in many sorted files, and a lookup for a key might otherwise read every one. A Bloom filter per file, held in memory, rules out the files that don't have the key, so most lookups read one file or none. Cassandra sets a false positive chance per table, 0.01 by default for most tables. Other uses: a web crawler skipping URLs it has already fetched (15.06 Design: a web crawler), a CDN declining to cache objects requested only once, and a cache rejecting lookups for keys that can't exist.

Snip at the end of Module 05

Snip's data no longer fits one machine, and nothing depends on a single counter or a single clock. Every request still reaches its data in one hop, because each query was matched to a shard key. The next module goes deep on the layer that answers most of Snip's traffic before any of this is touched: caching (06.01 Where caches live).

Recap

Interview questions