Part 2 · 1 chapters · ~8 min

Bloom Filters, HyperLogLog and Count-Min Sketches

Trading exactness for memory, Bloom filters (bits per item, hash count, false-positive maths), cuckoo filters with deletion, HyperLogLog for distinct counts (measured in Redis), count-min sketches for heavy hitters, merging sketches across machines, and production uses.

Small memory, bounded error

code

// a Bloom filter in a few lines: m bits, k hashes (double hashing from one digest)
class Bloom {
  bits: Uint8Array; constructor(public m: number, public k: number) { this.bits = new Uint8Array(Math.ceil(m / 8)); }
  private idx(s: string) { const h = createHash('sha256').update(s).digest(); const a = h.readUInt32BE(0), b = h.readUInt32BE(4);
    return Array.from({ length: this.k }, (_, i) => (a + i * b) % this.m); }
  add(s: string) { for (const i of this.idx(s)) this.bits[i >> 3] |= 1 << (i & 7); }
  has(s: string) { return this.idx(s).every(i => this.bits[i >> 3] & (1 << (i & 7))); }   // false = definitely absent
}
// sizing: m = -n ln(p) / (ln 2)^2, k = (m/n) ln 2 → n = 1M, p = 1%: m ≈ 9.6M bits (1.2 MB), k ≈ 7

// measured in Redis 8.6.2: PFADD 1,000,000 distinct ids → PFCOUNT 1,003,993 (0.40% error), MEMORY USAGE 14,384 bytes

Mergeable: HyperLogLogs and count-min sketches from different servers can be merged (PFMERGE), so each node counts locally and a central job combines them: daily active users across regions without moving raw ids.

APPROXIMATE STRUCTURES, MEASURED AND TYPICAL

memory needed to answer a question about 1,000,000 items

swipe the figure sideways, or tap expand for full screen

1/5

exact

Storing a million ids exactly needs at least about 11 MB here, and more with data structure overhead.

exact answers cost memory~11 MB for a million ids