Bloom Filters, HyperLogLog & Count-Min Sketch

In one line

When exact answers are too big or too slow, probabilistic structures give almost-right answers in tiny memory: 'definitely not present' (Bloom filter), 'about 48 million unique visitors' (HyperLogLog), 'roughly how often' (Count-Min Sketch).

0/8 · 0%

Think of it like this

A nightclub bouncer with a list of banned faces that he only half-remembers. If he's never seen you, you're DEFINITELY not banned and walk straight in. If you look familiar, he checks the full list. He's occasionally wrong about 'familiar', never wrong about 'never seen'. That's a Bloom filter.

Key ideas

01
BLOOM FILTER: a bit array plus k hash functions. Adding an item sets k bits; checking tests those k bits. All set → 'possibly present' (could be a false positive); any bit unset → 'definitely not present' (no false negatives). About 10 bits per item gives ~1% false positives. Uses: skip disk reads for keys that don't exist (LSM trees, Cassandra), 'has this URL been crawled?' (web crawler), avoiding cache penetration by queries for non-existent keys. Items can't be removed (a counting Bloom filter or cuckoo filter can).
02
HYPERLOGLOG: counts DISTINCT items (unique users, unique IPs) with about 0.8% error using ~12 KB, regardless of whether there are a thousand or a billion items. Redis has it built in (PFADD, PFCOUNT), and sketches from different servers or days can be merged.
03
COUNT-MIN SKETCH: estimates how many times each item occurred (frequencies) in fixed memory, overestimating slightly, never underestimating. Combined with a small heap it finds HEAVY HITTERS / top-K (trending hashtags, top searched products, abusive IPs) over huge streams.
04
The pattern: trade a small, bounded error for enormous memory and speed savings. Always state the error bound, and keep the exact data elsewhere if you ever need the precise answer (billing must be exact; 'trending' doesn't).

Java / Spring map

→
Guava's BloomFilter.create(Funnels.stringFunnel(UTF_8), 10_000_000, 0.01) builds a filter for 10 M items at 1% false positives (~12 MB); Redis BF.ADD/BF.EXISTS (Redis Stack/8) and PFADD/PFCOUNT provide shared versions.

Code & diagrams

Bloom filter in actionjava

BloomFilter<String> seen = BloomFilter.create(
    Funnels.stringFunnel(StandardCharsets.UTF_8), 50_000_000, 0.01);   // 50M URLs, 1% FP, ~60 MB

void crawl(String url) {
  if (seen.mightContain(url)) return;   // probably crawled already (1% chance we skip a new one)
  seen.put(url);
  fetchQueue.add(url);                   // definitely new → crawl it
}

Explain without notes

Why can a Bloom filter produce false positives but never false negatives?

Practice

Count unique daily visitors per page for 10 million pages without storing every visitor ID. What do you use and how much memory?

Trade-offs

↔
Probabilistic structures give bounded-error answers in tiny memory; they can't list the items or give exact counts, so they fit analytics, deduplication hints, and caching, not money.

Run it in production

You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:

Stateful · Redis & caching patterns

Cache-aside with a stampede lock, TTLs, rate limiting, and sessions in Redis.

Completion checklist

I can explain Bloom filter false positives
I know when HyperLogLog and Count-Min Sketch apply

Back to phase

Command Palette