Bloom Filters: Probabilistic Membership at Scale

Imagine an API that receives millions of requests for objects stored on disk. Most requested IDs do not exist, yet every miss still crosses the network, enters the database, and touches an index page before returning nothing. A small in-memory set could reject those requests, but storing every ID again may consume as much memory as the index it is meant to protect.

A Bloom filter solves a narrower problem with a useful compromise. It answers membership queries using a compact bit array and several hash-derived positions. A negative answer is definitive; a positive answer means only “possibly present.” By accepting a configurable number of false positives, the system can avoid almost all expensive lookups for absent keys while using only a few bits per known key.

That asymmetry makes Bloom filters valuable at scale, but it also makes them easy to misuse. Their guarantee depends on how they are sized, populated, deployed, and observed. This article develops the math, implements a practical TypeScript version, and shows where the structure belongs in cache and database request paths.

The one-sided membership guarantee #

A Bloom filter contains an array of $m$ bits, initially zero, and uses $k$ hash positions for each key. To insert a key, set all $k$ positions to one. To query it, inspect the same positions. If any position is zero, that key could not have been inserted under the filter’s assumptions. If every position is one, the key may be present, or other keys may have set those bits by coincidence.

This creates two distinct answers:

• Definitely absent: at least one required bit is zero, so the backing store can be skipped.
• Maybe present: every required bit is one, so the backing store must still decide.

Bloom filters do not produce false negatives only when several assumptions hold. Every key considered present must have been inserted. Writers and readers must canonicalize and encode keys identically. The bit array must not be cleared, corrupted, or replaced with an older snapshot. Ordinary Bloom filters must not delete by clearing bits, because a shared bit may represent many keys. Concurrent updates also need semantics that cannot lose bit-setting writes.

The insertion and query cost is $O(k)$, independent of the number of inserted keys. Space is $O(m)$ rather than proportional to the full byte length of all keys. The filter stores no key values, so it cannot enumerate members, return associated data, or explain which insertion caused a positive result.

Sizing the bit array and hash count #

The filter should be designed from two workload inputs: expected inserted items $n$ and acceptable false-positive probability $p$. After inserting $n$ items into $m$ bits with $k$ positions per item, the approximate false-positive probability is:

For fixed $m$ and $n$, the optimal number of hash positions is:

Solving for the required bit count gives:

Suppose a service expects ten million keys and permits a one-percent false-positive rate. The formulas require about 95.9 million bits, or roughly 11.4 MiB, and $k$ rounds to 7. At 0.1 percent, memory rises to about 17.1 MiB and the optimal $k$ becomes 10. That is usually still much smaller than retaining ten million strings plus hash-table overhead.

The expected count must be honest. A filter sized for one million items but filled with three million accumulates too many one bits, and its false-positive rate can become dramatically worse than its design target. Capacity planning should therefore include growth, rebuild frequency, and traffic skew. A filter per tenant or partition can prevent one hot population from saturating every other population, although very small filters have proportionally more metadata and management cost.

Production implementations rarely compute $k$ cryptographic hashes. Kirsch-Mitzenmacher double hashing derives positions as $h_1(x) + i h_2(x)$ for $i$ from zero to $k-1$. Two well-mixed base hashes are enough for Bloom-filter behavior while avoiding repeated encoding and expensive digest operations. Hash quality still matters: correlated or poorly distributed values invalidate the probability model.

A substantial TypeScript implementation #

The following implementation owns its sizing, validates parameters, uses a packed Uint8Array, and derives all positions from two 32-bit hashes. It also exposes utilization and an estimated current false-positive rate, which are useful for monitoring saturation.

export type BloomFilterStats = {
  bitSize: number;
  hashCount: number;
  setBits: number;
  fillRatio: number;
  estimatedFalsePositiveRate: number;
};

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

  constructor(expectedItems: number, falsePositiveRate: number) {
    if (!Number.isInteger(expectedItems) || expectedItems <= 0) {
      throw new RangeError('expectedItems must be a positive integer');
    }
    if (!(falsePositiveRate > 0 && falsePositiveRate < 1)) {
      throw new RangeError('falsePositiveRate must be between 0 and 1');
    }

    const rawBitSize =
      (-expectedItems * Math.log(falsePositiveRate)) /
      Math.LN2 ** 2;

    this.bitSize = Math.ceil(rawBitSize);
    this.hashCount = Math.max(
      1,
      Math.round((this.bitSize / expectedItems) * Math.LN2),
    );
    this.bits = new Uint8Array(Math.ceil(this.bitSize / 8));
  }

  add(value: string): void {
    for (const bitIndex of this.positions(value)) {
      const byteIndex = Math.floor(bitIndex / 8);
      const mask = 1 << (bitIndex % 8);
      this.bits[byteIndex]! |= mask;
    }
  }

  has(value: string): boolean {
    for (const bitIndex of this.positions(value)) {
      const byteIndex = Math.floor(bitIndex / 8);
      const mask = 1 << (bitIndex % 8);
      if ((this.bits[byteIndex]! & mask) === 0) {
        return false;
      }
    }
    return true;
  }

  stats(): BloomFilterStats {
    let setBits = 0;
    for (const byte of this.bits) {
      let remaining = byte;
      while (remaining !== 0) {
        remaining &= remaining - 1;
        setBits += 1;
      }
    }

    const fillRatio = setBits / this.bitSize;
    return {
      bitSize: this.bitSize,
      hashCount: this.hashCount,
      setBits,
      fillRatio,
      estimatedFalsePositiveRate: fillRatio ** this.hashCount,
    };
  }

  private *positions(value: string): Generator<number> {
    const bytes = new TextEncoder().encode(value);
    const first = BloomFilter.hash32(bytes, 0x811c9dc5);
    const second = BloomFilter.hash32(bytes, 0x9e3779b9) | 1;

    for (let index = 0; index < this.hashCount; index += 1) {
      const combined =
        (first + Math.imul(index, second) + Math.imul(index, index)) >>> 0;
      yield combined % this.bitSize;
    }
  }

  private static hash32(bytes: Uint8Array, seed: number): number {
    let hash = seed >>> 0;
    for (const byte of bytes) {
      hash ^= byte;
      hash = Math.imul(hash, 0x01000193);
    }

    hash ^= hash >>> 16;
    hash = Math.imul(hash, 0x85ebca6b);
    hash ^= hash >>> 13;
    hash = Math.imul(hash, 0xc2b2ae35);
    return (hash ^ (hash >>> 16)) >>> 0;
  }
}

Packed bytes keep the allocation close to the mathematical size; a JavaScript boolean[] would carry substantial per-element overhead. TextEncoder defines UTF-8 bytes consistently, while the two fixed seeds make the result deterministic across processes. The second hash is forced odd so it cannot collapse to zero and repeatedly select one position. The quadratic term helps avoid short cycles when m has inconvenient factors.

This class is suitable for a single JavaScript execution context. Sharing mutable bytes across workers requires atomic bitwise updates, and distributing the filter requires a versioned serialization format containing bitSize, hashCount, hash algorithm, seeds, and key-encoding rules. Changing any of those parameters creates a different filter even when the byte array has the same length.

Placing the filter in a real request path #

The most common use is protecting a slower authoritative store. The filter is advisory: it can bypass work after a negative answer, but it cannot satisfy a positive answer by itself.

For cache penetration, insert every valid object ID into the filter. Requests for random nonexistent IDs stop before the cache and database. A “maybe” proceeds normally; if the cache misses, the database remains authoritative. This differs from negative caching, which stores recent misses and can serve them directly for a TTL. The two techniques can coexist: the Bloom filter rejects broad never-seen traffic, while a negative cache absorbs repeated false positives or recently deleted keys.

Databases and storage engines use Bloom filters at finer granularity. An LSM-tree table can maintain a filter for each immutable SSTable. Before reading a block or file, the engine checks whether that file might contain the key. A negative result skips I/O; a positive result searches the real index. Partitioned filters improve locality because only the relevant filter block must be loaded.

Initialization is part of correctness. A service can build a filter from a consistent database snapshot, then consume changes committed after the snapshot position. Another pattern builds a new version in the background, catches it up from a log, and atomically swaps readers only after it is current. Starting with an empty filter and gradually filling it while using negative answers is unsafe because existing keys not yet loaded become false negatives.

Deletion, counting, and scalable variants #

Clearing a bit in a standard Bloom filter is invalid. If alice and bob share a position, deleting alice and clearing that bit makes bob appear absent. The simplest safe policy is to leave bits set after deletions. Deleted keys then become false positives, which cost an unnecessary backing lookup but preserve correctness. Periodic rebuilding removes that accumulated noise.

A counting Bloom filter replaces each bit with a small counter. Insert increments all selected counters; delete decrements them. A position is present when its counter is nonzero. This supports deletion only if insertions and deletions are balanced exactly: deleting a key that was never inserted, deleting twice, counter overflow, or lost events can create false negatives. Four-bit counters are common, but they use several times the memory of a bit filter.

A Cuckoo filter stores short fingerprints in buckets and can delete a matching fingerprint. It often offers competitive lookup speed and better space efficiency at low false-positive targets, though insertion can fail near its load limit and requires relocation logic. A stable Bloom filter continuously ages counters to keep bounded memory for an unbounded stream; in exchange, old items can disappear, so false negatives become an intentional feature. A scalable Bloom filter adds larger subfilters as capacity grows, assigning each a tighter error budget to keep the combined false-positive rate bounded.

Choose the variant from lifecycle semantics, not novelty. Append-only data or immutable files fit a standard Bloom filter. Frequent exact deletions may favor Cuckoo filters. Windowed stream deduplication may accept aging. If false negatives are unacceptable and update delivery is not trustworthy, an exact index or authoritative lookup is the better design.

Testing, monitoring, and operational limits #

Tests should verify invariants rather than expect a particular false positive for one hand-picked string. Insert a deterministic set and assert that every inserted value returns true. Query a large, disjoint deterministic set, calculate the observed false-positive ratio, and allow a statistically sensible tolerance above the target. Test Unicode, empty strings, long keys, duplicate insertion, invalid constructor inputs, and serialize/restore compatibility if persistence is added.

In production, record at least four measurements: filter-negative requests, filter-positive requests, backing-store misses after a positive result, and fill ratio. The empirical false-positive rate is:

This operational ratio depends on traffic, because real missing keys may repeat or be adversarial; it is not identical to sampling uniformly from the key universe. Still, a rising ratio or fill level is an excellent rebuild signal. Also track inserted-item estimates, filter version age, change-stream lag, rebuild duration, and checksum failures. Alert on consumers serving an older version than the writer’s safe watermark.

Bloom filters have hard limits. They save work only when negative lookups are common and the protected operation is expensive relative to hashing. They add latency when almost every lookup is present. They are poor authorization boundaries because positives are ambiguous and untrusted clients may search for false positives. They do not hide membership information, resist targeted hash-flooding automatically, or replace a database uniqueness constraint. A filter that occupies more memory than the hot exact index, or whose false positives still overload the database, has missed its purpose.

Takeaways #

• A standard Bloom filter can safely answer “definitely absent” and only “maybe present.”
• The no-false-negative guarantee requires complete population, stable encoding and hashing, monotonic bit updates, and current replicas.
• Size from expected cardinality and error budget; monitor fill ratio because exceeding capacity rapidly degrades accuracy.
• Double hashing makes $k$ positions practical, while a packed bit array keeps memory close to the theoretical requirement.
• Use the filter ahead of an authoritative cache, database, or immutable storage file, never as the source of truth.
• Do not clear bits for deletion; rebuild, count carefully, or choose a Cuckoo or other lifecycle-appropriate variant.
• Test inserted-key invariants and statistical error behavior, then monitor observed backing misses, lag, age, and saturation in production.

A Bloom filter is powerful precisely because it promises less than a set. Once the request path respects that limited promise, a few megabytes of bits can prevent enormous amounts of network, cache, and storage work without changing the truth maintained by the underlying system.