Probabilistic Data Structures#

Q: What is a Bloom filter?

A Bloom filter is a bit array plus k hash functions. It tells you definitely not in the set or probably in the set, with a tunable false positive rate but no false negatives.

Q: What is HyperLogLog used for?

HyperLogLog estimates the number of distinct elements in a stream with around 1 percent error using only a few kilobytes, no matter how many billions of events you feed it.

Q: Bloom filter vs Cuckoo filter?

Cuckoo filters support delete and use less space at the same false positive rate, at the cost of a more complex insert. Bloom filters are simpler and lock-free to update.

Q: What does Count-Min Sketch do?

Count-Min Sketch estimates how often each item appears in a stream using a small 2D array, ideal for top-K and heavy-hitter detection over high-volume event streams.

Q: When should I use a probabilistic structure?

Use them when exact answers cost too much memory or compute and a small bounded error is acceptable, like caching layers, analytics counters, and anti-spam pre-filters.

Problem statement (interviewer prompt)

You need to know membership ("have we seen this URL?"), frequency ("top hashtags right now"), and cardinality ("unique users today") on streams of billions of events with only megabytes of memory. Pick the right probabilistic structure for each and explain the trade-offs.

flowchart LR
  K[Key / event]
  BF[Bloom Filter<br/>membership]
  CMS[Count-Min Sketch<br/>frequency]
  HLL[HyperLogLog<br/>cardinality]
  TD[t-digest / KLL<br/>quantiles]
  CK[Cuckoo Filter<br/>membership + delete]
  K --> BF
  K --> CMS
  K --> HLL
  K --> TD
  K --> CK

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class K,BF,CMS,HLL,TD,CK service;

Trade exact answers for huge memory savings + O(1) updates.

Bloom filter diagram showing three hash functions mapping set elements x, y, z to a bit array — Bloom filter: three hash functions map each element to bit positions; a set-bit collision means possible membership (false positive). Source: David Eppstein, Wikimedia Commons (Public Domain)

flowchart TB
  subgraph BF[Bloom Filter]
    BFW[Insert: set k bits via k hashes]
    BFR[Query: all k bits set?<br/>false positive possible, no false negative]
    BFP["Params: m bits, n items<br/>FPR ≈ (1 - e^{-kn/m})^k"]
    BFV[Variants: Counting, Scalable, Partitioned]
  end

  subgraph CKF[Cuckoo Filter]
    CFW[Insert with fingerprint<br/>+ alt bucket]
    CFD[Delete supported]
    CFP[Better cache locality<br/>than Bloom for high load]
  end

  subgraph CMS[Count-Min Sketch]
    CMW[Insert: ++ in d rows]
    CMR[Query: min over rows<br/>overestimate only]
    CMP["Params: d hashes, w width<br/>ε ≈ e/w, δ ≈ e^{-d}"]
    CMU[Use: heavy hitters,<br/>top-k, frequency]
  end

  subgraph HLL[HyperLogLog]
    HLLW[Bucket via hash prefix<br/>track max trailing zeros]
    HLLR[Cardinality estimate<br/>via harmonic mean]
    HLLP[2^14 bytes ≈ 16 KB<br/>0.81% std err]
    HLLM[Mergeable across shards]
  end

  subgraph QT[Quantiles: t-digest, KLL, GK]
    QTW[Cluster ranks into centroids]
    QTR[Query p50/p95/p99]
    QTM[Mergeable]
  end

  subgraph MinHash[MinHash / SimHash / LSH]
    SHJ[Jaccard / cosine similarity<br/>at scale]
    LSH[Locality-sensitive hashing<br/>for near-neighbor search]
  end

  subgraph TD[Top-K]
    SS[Space-Saving]
    HK[Misra-Gries Heavy Keepers]
  end

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class BFW,BFR,BFP,BFV,CFD,CFP,CMW,CMR,CMP,CMU,HLLR,HLLP,HLLM,QTW,QTR,QTM,SHJ,LSH,SS,HK service;
    class CFW,HLLW storage;

Bloom filter math#

m bits, n items, k hash functions.
Optimal k ≈ (m/n)·ln 2.
FPR ≈ (1 - e^{-kn/m})^k ≈ (1 - e^{-k·n/m})^k.
For FPR 1% with n=1B: m ≈ 9.6 bn bits ≈ 1.2 GB.

When to use each#

Need	Pick
"have we seen this URL?"	Bloom / Cuckoo
"what are top hashtags?"	Count-Min + heap, or Space-Saving
"how many unique users today?"	HyperLogLog
"p99 latency over 1B events"	t-digest / KLL
"near-duplicate detection"	MinHash + LSH (or SimHash)
"set difference between replicas"	Invertible Bloom Filter

Pitfalls#

Bloom: cannot delete (use Counting Bloom or Cuckoo).
CMS: overestimates; pair with reservoir sampling for confidence.
HLL: bad at small cardinalities (n < ~12·m); use sparse repr.
All assume good hash functions (Murmur, xxHash); avoid identity hashes.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`HLD`	Probabilistic data structures	Bloom, HLL, Count-Min, MinHash, t-digest	probabilistic-data-structures

Quick reference#

Why they exist#

Sometimes "approximately correct, with O(1) memory" beats "exact, with O(N) memory" - by orders of magnitude. Cache invalidation, analytics, anti-abuse, log dedup all benefit.

Where they show up in this repo#

Web Crawler - Bloom filter for seen URLs.
Distributed Cache - Bloom filter for cache penetration.
Rate Limiter - Count-Min for hot keys.
Real-time Analytics / Trending - HLL for unique counts, CMS+heap for top-K.
Spam / Abuse - MinHash/LSH for near-dup content.
Distributed Counter - HLL & CMS for views/likes at scale.

Reservoir & sampling#

Reservoir sampling: uniform random sample of N from a stream of unknown length.
Weighted reservoir for biased sampling.

Tuning rules of thumb#

Bloom 10 bits/key → 1% FPR.
CMS width = e/ε, depth = ln(1/δ); for ε=0.01, δ=0.01 → 272 × 5 = 1.4k cells.
HLL m=2^14 → 1.62/√m = 0.81% std err.

Refs#

Cormode, Muthukrishnan: "An improved data stream summary: the Count-Min Sketch."
Flajolet et al.: "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm."
Bonomi et al.: "Cuckoo filter."
Mitzenmacher, Upfal: Probability and Computing (textbook).
Apache DataSketches library docs.

FAQ#

What is a Bloom filter?#

A Bloom filter is a bit array plus k hash functions. It tells you definitely not in the set or probably in the set, with a tunable false positive rate but no false negatives.

What is HyperLogLog used for?#

HyperLogLog estimates the number of distinct elements in a stream with around 1 percent error using only a few kilobytes, no matter how many billions of events you feed it.

Bloom filter vs Cuckoo filter?#