Some questions are asked millions of times a day and almost always have the answer "no". Is this username taken? Has this user already seen this video in their recommendations? Is this URL on the malware list? Does this SSTable on disk contain this key?

Answering them with a database lookup works until it does not: every signup form keystroke becomes a query, and most of those queries return nothing. A Bloom filter is a tiny, probabilistic data structure that answers "definitely not" or "probably yes" in constant time from memory, so you only pay for the expensive lookup when the answer might be yes.

The problem: lookups that mostly miss

Here is the naive username check behind a signup form:

async function isUsernameTaken(db: Db, username: string) {
  const row = await db.query("SELECT 1 FROM users WHERE username = $1", [username.toLowerCase()]);
  return row.length > 0;
}

With an index this is fast for one request. Now put it behind an input that checks availability as the user types, for a site with hundreds of millions of accounts and a signup spike after a marketing campaign. The database spends most of its time proving that nguyenvana1997x does not exist.

A cache does not help much either. Caching misses means storing every name anyone ever typed. You want a structure that is small enough to keep in memory on every app server and can rule out most names without asking anyone.

How a Bloom filter works

A Bloom filter is a bit array of m bits, all zero at the start, and k independent hash functions that each map a key to a position in the array.

  • Add a key: hash it with all k functions and set those k bits to 1.
  • Check a key: hash it the same way. If any of the k bits is 0, the key was definitely never added. If all are 1, the key was probably added: those bits might have been set by other keys.

That asymmetry is the whole point:

  • No false negatives. If you added a key, all its bits are 1 forever, so the filter never says "no" to something it has seen.
  • Some false positives. A key you never added can land on bits that other keys happened to set. You control how often with the size of the array and the number of hash functions.
  • No deletes in the basic version. Clearing a bit could erase evidence of another key. Counting Bloom filters or Cuckoo filters fix that at the cost of more memory.

For the signup form, this means: if the filter says "no", the name is free and you never touch the database. If it says "probably", you do the real lookup, which happens only for names that are taken plus a small percentage of false positives.

Sizing the filter

For n expected keys and a target false positive rate p, the optimal sizes are:

  • bits: m = -n · ln(p) / (ln 2)²
  • hash functions: k = (m / n) · ln 2

In practice that is about 9.6 bits per key for a 1% false positive rate and 14.4 bits per key for 0.1%, regardless of how long the keys are. A billion usernames at 1% fits in about 1.2 GB; a hundred million fits in about 120 MB. Storing the names themselves would take many times that.

A TypeScript implementation

The trick that makes k hash functions cheap is double hashing: compute two base hashes once and derive the rest as h1 + i · h2. Kirsch and Mitzenmacher showed this keeps the false positive rate of truly independent hashes.

// FNV-1a, 32-bit. Fast, decent distribution, no dependencies.
function fnv1a(input: string, seed = 0x811c9dc5): number {
  let hash = seed;
  for (let i = 0; i < input.length; i++) {
    hash ^= input.charCodeAt(i);
    hash = Math.imul(hash, 0x01000193);
  }
  return hash >>> 0;
}

export class BloomFilter {
  readonly size: number;
  readonly hashCount: number;
  private readonly bits: Uint8Array;

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

  private *positions(key: string) {
    const h1 = fnv1a(key);
    const h2 = (fnv1a(key, 0x9747b28c) | 1) >>> 0; // odd and unsigned: `|` returns a signed int
    for (let i = 0; i < this.hashCount; i++) {
      yield (h1 + i * h2) % this.size;
    }
  }

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

  mightContain(key: string): boolean {
    for (const pos of this.positions(key)) {
      if ((this.bits[pos >>> 3]! & (1 << (pos & 7))) === 0) return false;
    }
    return true;
  }

  get bytes() {
    return this.bits.byteLength;
  }
}

Let us check that it behaves as promised: add 100,000 keys, then test 100,000 keys that were never added.

const filter = new BloomFilter(100_000, 0.01);
for (let i = 0; i < 100_000; i++) filter.add(`user-${i}`);

let missed = 0;
for (let i = 0; i < 100_000; i++) if (!filter.mightContain(`user-${i}`)) missed++;

let falsePositives = 0;
for (let i = 0; i < 100_000; i++) if (filter.mightContain(`visitor-${i}`)) falsePositives++;

console.log({ bytes: filter.bytes, hashCount: filter.hashCount, missed, falsePositiveRate: falsePositives / 100_000 });
// { bytes: 119814, hashCount: 7, missed: 0, falsePositiveRate: 0.00518 }

About 117 KB for 100,000 keys, zero misses, and a false positive rate under the 1% target. The exact rate varies with the hash function and the key set, so measure it on keys that look like yours.

One bug is worth calling out because it is easy to write: x | 1 in JavaScript returns a signed 32-bit integer. Without the >>> 0, about half of all h2 values are negative, positions go negative, and the filter starts returning false negatives, which is the one thing a Bloom filter must never do. A test like the one above catches it immediately.

Using it in the signup flow

The filter sits in front of the database, not instead of it:

export class UsernameChecker {
  constructor(
    private readonly filter: BloomFilter,
    private readonly db: Db,
  ) {}

  async isTaken(raw: string): Promise<boolean> {
    const username = raw.trim().toLowerCase();
    if (!this.filter.mightContain(username)) return false; // definitely free, no query
    return isUsernameTaken(this.db, username); // taken, or a false positive
  }

  markTaken(username: string) {
    this.filter.add(username.trim().toLowerCase());
  }
}

Two operational details matter more than the code:

  • Keep the filter in sync. Call markTaken after a successful signup, and rebuild the filter periodically from the database (or from a change stream) so new instances start with all names.
  • The database still enforces uniqueness. The filter is an optimisation for the read path. A unique index is what stops two people registering the same name at the same moment.

If many app servers need the same filter, keep one copy in Redis with the RedisBloom module (BF.ADD, BF.EXISTS) instead of building it in every process.

Where Bloom filters show up

  • Databases and storage engines. LSM-tree stores such as Cassandra, RocksDB, LevelDB and HBase keep a Bloom filter per SSTable, so a read skips files that cannot contain the key. This is the most widespread use by far.
  • Caches. CDNs and caches use them to avoid caching "one-hit wonders": only cache an object the second time it is requested.
  • Cache penetration. Requests for IDs that cannot exist (negative, random, scraped from old links) miss the cache every time and land on the database. A filter of every real ID in front of the cache rejects them in memory, which also blunts a cheap denial-of-service trick.
  • Show-once features. Ads, onboarding tips or "what's new" banners that each user should see at most once. A filter per campaign answers "already shown to this user?" without a lookup; a false positive only means one user misses one impression.
  • Recommendation and feeds. Filtering out items a user has already seen without storing the full history per user.
  • Security. Checking passwords against a breached-password list, or URLs against a blocklist, before doing an exact lookup.
  • Distributed joins and sync. Sending a compact filter instead of a full key set to find what the other side is missing.

Trade-offs and pitfalls

  1. Undersizing. The false positive rate climbs quickly once you add more keys than you planned for. Size for the number of keys you expect in a year, not today, or use a scalable Bloom filter that adds layers as it fills.
  2. Expecting deletes. Removing a user does not remove their bits. Either accept the stale "probably" (the database check handles it) or use a counting filter or a Cuckoo filter.
  3. Bad hashing. Weak or correlated hash functions concentrate bits and inflate false positives. Use a well-tested non-cryptographic hash (FNV, Murmur3, xxHash) with double hashing.
  4. Adding hash functions to fix false positives. More hashes help only up to the optimum k = (m / n) · ln 2. Past that, every key sets more bits, the array fills faster and the false positive rate goes up. The real lever is bits per key: make m bigger.
  5. Mixing hash implementations. Every service that writes or reads a shared filter must use exactly the same hash functions and seeds. A Go writer and a Node.js reader with different hash libraries will disagree on every bit position.
  6. Normalising differently on write and read. Lowercase, trim and Unicode-normalise in exactly one function, or the filter will say "definitely not" to a name that exists in another spelling.
  7. Using it where you need certainty. A Bloom filter can never tell you a key definitely exists. Anything that must be exact still needs the real lookup.

Exercises

  1. Change the target false positive rate to 0.1% and 10% in the test above. Plot bytes against the measured rate.
  2. Add 200,000 keys to a filter sized for 100,000 and measure the false positive rate. How much worse is it?
  3. Extend BloomFilter with toBuffer() and static fromBuffer() so a filter can be built in a batch job and loaded by app servers at startup.
  4. Implement a counting Bloom filter with 4-bit counters and a remove() method. What does it cost in memory compared to the bit version?