Bloom Filters, Count-Min Sketch, and HyperLogLog: Probabilistic Data Structures for Production Systems

Every system design decision eventually runs into a wall where the exact answer is too expensive. You want to know whether a user has already seen a notification, but storing every seen ID at scale costs hundreds of gigabytes. You want to count unique visitors per day, but keeping a full set of visitor IDs in memory means your analytics layer consumes as much RAM as your database.

Probabilistic data structures solve this by trading a bounded, configurable error rate for dramatic reductions in memory and lookup latency. The three covered here are the most practically useful: Bloom filters for membership testing, Count-Min Sketch for frequency estimation, and HyperLogLog for cardinality estimation. Each has well-understood mathematical error bounds. Knowing how they work internally is what lets you tune them correctly and reason about failure modes.

Bloom Filters

How It Works

A Bloom filter is a bit array of size m, initially all zeros. You choose k hash functions, each mapping an input to a position in [0, m).

Insert: For element x, compute h1(x) through hk(x) and set those k bits to 1.

Query: Check those same k positions. If all are 1, the element is “probably in” the set. If any is 0, it is definitely not in the set.

False positives occur when all k positions happen to be set by prior insertions of other elements. False negatives cannot occur: insertion always sets bits; queries check those exact bits.

class BloomFilter {
  private readonly bits: Uint8Array;
  private readonly m: number;
  private readonly k: number;

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

  add(item: string): void {
    for (let i = 0; i < this.k; i++) {
      const pos = this.hash(item, i) % this.m;
      this.bits[Math.floor(pos / 8)] |= 1 << pos % 8;
    }
  }

  has(item: string): boolean {
    for (let i = 0; i < this.k; i++) {
      const pos = this.hash(item, i) % this.m;
      if ((this.bits[Math.floor(pos / 8)] & (1 << pos % 8)) === 0) return false;
    }
    return true;
  }

  // Double hashing avoids needing k independent hash functions
  private hash(item: string, seed: number): number {
    const h1 = this.fnv1a(item);
    const h2 = this.fnv1a(item + "\0" + seed);
    return Math.abs(h1 + seed * h2);
  }

  private fnv1a(input: string): number {
    let hash = 2166136261;
    for (let i = 0; i < input.length; i++) {
      hash ^= input.charCodeAt(i);
      hash = (hash * 16777619) >>> 0;
    }
    return hash;
  }
}

Tuning

Given expected item count n and target false positive rate p:

m = -(n * ln(p)) / (ln(2))^2
k = (m / n) * ln(2)

For 1 million items at 1% false positive rate: m is roughly 9.6 million bits (1.2 MB) and k is 7. Dropping to 0.1% costs about 50% more memory. Halving the false positive rate means 50% more memory, roughly.

The most common production mistake: sizing for n and ignoring growth. At 2x expected capacity, expect roughly 4x the configured false positive rate. Either cap inserts and rotate filters on a schedule, or monitor the insertion count and alert before degradation.

Production Use Cases

Notification deduplication: Check a per-user Bloom filter before sending a push notification. If has(notificationId) returns true, skip. Fall back to the database only on a positive result, then add to the filter after a confirmed send. A 1% false positive rate means 1% of notifications get incorrectly skipped. Tune to your business tolerance.

Cache pre-check: A Bloom filter of all cached keys lets you skip a cache round trip on guaranteed misses. A negative result means certain miss; go directly to the database. A positive result still requires the cache lookup due to false positives.

Message pipeline deduplication: At-least-once delivery produces duplicates. A Bloom filter at the consumer side handles the common case cheaply, falling back to an exact check only on positives.

Count-Min Sketch

How It Works

A Count-Min Sketch is a 2D array of counters with d rows and w columns. Each row has its own hash function mapping elements to [0, w).

Update: For element x with count c, for each row i, increment sketch[i][hash_i(x)] by c.

Query: Return min(sketch[i][hash_i(x)]) over all rows. Collisions can only inflate counts, never deflate them, so the minimum across rows is the best estimate.

class CountMinSketch {
  private readonly table: number[][];
  private readonly d: number;
  private readonly w: number;
  private readonly seeds: number[];

  constructor(epsilon: number, delta: number) {
    // w = ceil(e / epsilon), d = ceil(ln(1 / delta))
    this.w = Math.ceil(Math.E / epsilon);
    this.d = Math.ceil(Math.log(1 / delta));
    this.seeds = Array.from({ length: this.d }, (_, i) => i * 2654435761);
    this.table = Array.from({ length: this.d }, () => new Array(this.w).fill(0));
  }

  update(item: string, count = 1): void {
    for (let i = 0; i < this.d; i++) {
      const col = this.hash(item, this.seeds[i]) % this.w;
      this.table[i][col] += count;
    }
  }

  estimate(item: string): number {
    let min = Infinity;
    for (let i = 0; i < this.d; i++) {
      const col = this.hash(item, this.seeds[i]) % this.w;
      min = Math.min(min, this.table[i][col]);
    }
    return min;
  }

  private hash(item: string, seed: number): number {
    let h = seed;
    for (let i = 0; i < item.length; i++) {
      h = Math.imul(h ^ item.charCodeAt(i), 0x9e3779b9);
      h ^= h >>> 16;
    }
    return Math.abs(h);
  }
}

Error Bounds

The estimate exceeds the true count by at most epsilon * N with probability at least 1 - delta, where N is total stream weight. For 0.1% error with 99% confidence: w = ceil(2.718 / 0.001) = 2719, d = ceil(ln(100)) ≈ 5. That is 13,595 counters total. For a stream of 100 million events, the worst-case over-estimate for any element is 100,000.

Production Use Cases

Sliding window rate limiting: Two sketches per key (current window and previous). Weight the previous window by the remaining fraction of the current period to get a smooth sliding window count.

class SketchRateLimiter {
  private current: CountMinSketch;
  private previous: CountMinSketch;
  private windowStart: number;
  private readonly windowMs: number;

  constructor(epsilon: number, delta: number, windowMs: number) {
    this.current = new CountMinSketch(epsilon, delta);
    this.previous = new CountMinSketch(epsilon, delta);
    this.windowStart = Date.now();
    this.windowMs = windowMs;
  }

  isAllowed(key: string, limit: number): boolean {
    this.rotateIfNeeded();
    const elapsed = Date.now() - this.windowStart;
    const weight = 1 - elapsed / this.windowMs;
    const estimate =
      this.current.estimate(key) +
      Math.floor(this.previous.estimate(key) * weight);
    if (estimate >= limit) return false;
    this.current.update(key);
    return true;
  }

  private rotateIfNeeded(): void {
    if (Date.now() - this.windowStart >= this.windowMs) {
      this.previous = this.current;
      this.current = new CountMinSketch(0.001, 0.01);
      this.windowStart = Date.now();
    }
  }
}

Top-k heavy hitters: Pair a Count-Min Sketch with a min-heap of size k. After each update, check if the estimated frequency belongs in the top-k and evict the minimum if so. This gives approximate top-k without tracking every distinct element.

Analytics event counting: Count clicks or feature usage per user in constant memory. The sketch uses d * w counters regardless of user count.

HyperLogLog

How It Works

The algorithm exploits a property of uniform hash functions: in a stream of uniformly distributed values, the probability of a value starting with at least k leading zeros is 2^(-k). If the maximum run of leading zeros observed is k, the stream likely contains around 2^k distinct elements.

This single-register estimate has high variance. HyperLogLog reduces variance by splitting elements across m = 2^b registers using the first b bits of each hash as a bucket index, then taking the harmonic mean across all registers with a bias correction.

class HyperLogLog {
  private readonly m: number;
  private readonly b: number;
  private readonly registers: Uint8Array;
  private readonly alphaMM: number;

  constructor(b: number) {
    if (b < 4 || b > 16) throw new Error("b must be between 4 and 16");
    this.b = b;
    this.m = 1 << b;
    this.registers = new Uint8Array(this.m);
    const alpha = b >= 6
      ? 0.7213 / (1 + 1.079 / this.m)
      : b === 5 ? 0.697 : 0.673;
    this.alphaMM = alpha * this.m * this.m;
  }

  add(item: string): void {
    const hash = this.hash32(item);
    const index = hash >>> (32 - this.b);
    const w = (hash << this.b) | ((1 << this.b) - 1);
    const rank = Math.clz32(w) + 1;
    this.registers[index] = Math.max(this.registers[index], rank);
  }

  estimate(): number {
    let sum = 0;
    for (let i = 0; i < this.m; i++) sum += Math.pow(2, -this.registers[i]);
    let e = this.alphaMM / sum;

    // Small range correction
    if (e <= 2.5 * this.m) {
      const zeros = this.registers.filter(r => r === 0).length;
      if (zeros > 0) e = this.m * Math.log(this.m / zeros);
    }
    // Large range correction
    if (e > (1 / 30) * 4294967296) {
      e = -4294967296 * Math.log(1 - e / 4294967296);
    }
    return Math.round(e);
  }

  merge(other: HyperLogLog): void {
    if (this.m !== other.m) throw new Error("Precision mismatch");
    for (let i = 0; i < this.m; i++) {
      this.registers[i] = Math.max(this.registers[i], other.registers[i]);
    }
  }

  private hash32(input: string): number {
    let h1 = 0xdeadbeef, h2 = 0x41c6ce57;
    for (let i = 0; i < input.length; i++) {
      const c = input.charCodeAt(i);
      h1 = Math.imul(h1 ^ c, 0x9e3779b9);
      h2 = Math.imul(h2 ^ c, 0x5f4a7c15);
    }
    return (h1 ^ h2) >>> 0;
  }
}

Tuning Precision

The standard error is 1.04 / sqrt(m):

b	Registers	Memory	Standard Error
10	1,024	~1 KB	3.25%
12	4,096	~4 KB	1.63%
14	16,384	~16 KB	0.81%
16	65,536	~64 KB	0.41%

b = 14 is the right default for most analytics use cases. The mergeability is what makes HLL practical at scale: maintain per-shard HLLs, merge at query time. A month of daily HLLs for 10,000 properties at b = 12 is 30 × 10,000 × 4 KB = 1.2 GB, versus the gigabytes required for exact sets. For weekly or monthly uniques, merge the daily registers with element-wise max.

Redis Integration

All three structures work with Redis, enabling shared state across service instances without each process maintaining its own copy.

import { createClient } from "redis";

const redis = createClient();
await redis.connect();

// Bloom filter (requires Redis Stack or RedisBloom module)
await redis.bf.add("seen:user:123", "notif:abc");
const exists = await redis.bf.exists("seen:user:123", "notif:xyz");

// Count-Min Sketch
await redis.cms.initByProb("req-counts", 0.001, 0.01);
await redis.cms.incrBy("req-counts", [{ item: "10.0.0.1", increment: 1 }]);
const [count] = await redis.cms.query("req-counts", "10.0.0.1");

// HyperLogLog (built into every Redis version, no module needed)
await redis.pfAdd("visitors:2026-03-24", "user:456");
const unique = await redis.pfCount("visitors:2026-03-24");

// Weekly unique count by merging daily keys
const weekly = await redis.pfCount(
  "visitors:2026-03-18", "visitors:2026-03-19",
  "visitors:2026-03-20", "visitors:2026-03-21",
  "visitors:2026-03-22", "visitors:2026-03-23",
  "visitors:2026-03-24"
);

PFADD and PFCOUNT are built into every Redis version. Bloom filters and Count-Min Sketch require Redis Stack. If your managed Redis does not support modules, run the structures in application memory and checkpoint to durable storage periodically.

Tradeoffs

Structure	Memory	Error Type	Error Bound	Deletions	Merge
Bloom Filter	O(n) bits	False positives only	Configurable p	No	Yes (bitwise OR)
Count-Min Sketch	O(d x w) counters	Over-counts only	epsilon x N, confidence 1 - delta	No	Yes (element-wise sum)
HyperLogLog	O(2^b) bytes	Relative error	1.04 / sqrt(m)	No	Yes (register max)
Exact hash set	O(n)	None	None	Yes	Yes
Exact counter map	O(n)	None	None	Yes	Yes

The no-deletion constraint catches teams off guard. Bloom filter bits are shared across elements, so clearing a bit might create false negatives for others. For deletion support, use a Counting Bloom Filter: replace each bit with a 4-bit counter, increment on insert, decrement on delete. Memory cost is 4x, but deletions work correctly.

Production Considerations

Filter rotation: Bloom filter false positive rate degrades as fill factor grows. Run two filters in parallel (current and previous). Insert into both, query both, and retire the older one on a schedule. This bounds fill factor regardless of insert volume.

Persistence: These structures reset on process restart. Serialize to durable storage between restarts if your use case requires correctness across deployments. A Bloom filter serializes to m/8 bytes; a Count-Min Sketch to d * w * sizeof(counter).

Monitoring: Track insertion count against n for Bloom filters and alert at 150% fill. For Count-Min Sketch, track total stream weight to compute the absolute error ceiling. For HyperLogLog, the error is a fixed relative rate; anomalous cardinality spikes usually point to upstream data problems, not sketch issues.

Hash function choice: MurmurHash3 and xxHash are solid defaults. FNV-1a is simpler and fast enough for most workloads. Never use MD5 or SHA-1 here.

The Core Insight

These are not approximation hacks. They are the correct engineering choice when the acceptable error rate is well-defined and exact computation is prohibitive. The key discipline is making the error bound explicit: document what false positive rate or over-estimation percentage your system can tolerate, configure the structure to meet it, and monitor that it stays within bounds as traffic changes.

Simple enough to implement from scratch in a few hours. That exercise is worth doing, because you will understand the failure modes before they hit you in production.