HyperLogLog and Count-Min Sketch: A System Design Guide

If you remember five things

The whole topic in one glance. Everything below is the defense of these five.

Different questions. HLL answers "how many distinct," Count-Min Sketch answers "how often is this one." Pick the structure from the question, not from habit.
Flat memory. HLL counts 100M uniques in about 12 KB. CMS uses a fixed grid no matter how many distinct items you feed it. Both stay flat as data grows.
Bounded error, stated in numbers. HLL is roughly 2 percent two-sided. CMS never undercounts, it only overcounts, and you set how much with the grid size.
Mergeable. Compute a sketch per shard, ship the tiny sketches, merge them. You move kilobytes, not terabytes, and the global answer keeps its error bound.
Refuse them when the number is disputed. Billing, legal, and compliance counts must be exact. Forcing a sketch there is the judgment failure that fails you.

1The core idea#

Start with the one sentence everything else hangs off.

Both are probabilistic data structures.
You trade a small, bounded amount of accuracy for an enormous saving in memory.
Internalize that trade and you can reason about every detail below.

HyperLogLog (HLL) answers one question: how many distinct items have I seen?

Think unique daily active users, unique IPs hitting an endpoint, unique search terms.
The exact way to do this is a hash set, and a hash set grows with every new item.
Count 100 million uniques with a set: even at a lean 16 bytes per entry that is 1.6 GB, and in a real language with object overhead it is closer to 5 to 8 GB.
HLL answers the same question in about 12 kilobytes with roughly 2 percent error.
That is a compression ratio around 100,000 to 1 against the lean estimate. Not a typo.

Count-Min Sketch (CMS) answers a different question: how many times have I seen this specific item?

Frequency, not cardinality.
Think "how many times did this URL get requested," "how many clicks did this ad get," "which search queries are trending."
The exact version is a hash map from item to counter, which again grows with the number of distinct items.
CMS uses a fixed-size grid of counters no matter how many distinct items you throw at it.

The mental model I keep in my head:

HLL is a crowd estimator. You do not count every face, you read a statistical signature of the crowd and infer the size.
CMS is a set of tally sheets where many items share a line. You take the smallest tally when lines disagree, because collisions only ever add noise, never remove it.

The property that makes both worth the trouble

Both are mergeable, and that matters more than people expect. Compute an HLL on each of 50 shards, ship the tiny sketches to one place, union them, and you get the global unique count. No raw data leaves the shard, and you move 50 times 12 KB (about 600 KB) instead of terabytes of raw events.

2How it works#

HyperLogLog#

Start with the coin-flip intuition, because it makes the rest obvious.

If I flipped a fair coin a bunch of times and the longest run of heads I ever saw was 10, you would guess I flipped it around 2^10 (about a thousand) times.
Rare patterns imply many trials. That is the whole engine.

HLL applies this to hashes:

Hash every incoming item to a uniform bitstring.
A hash that starts with many leading zeros is rare, so seeing one hints you have processed a lot of distinct items.
Track only the single longest run of leading zeros and your estimate is wildly noisy, so HLL splits the hash.
The first few bits pick one of m registers (say 16,384 of them, which is 2^14, so the first 14 bits select the register).
The rest of the bits feed the leading-zeros count for that register. Each register keeps the max run it has seen.
At query time you combine all registers with a harmonic mean, which tames outliers, and you get the cardinality.

The accuracy and footprint, with the arithmetic shown:

More registers means tighter accuracy. The standard error is about 1.04 divided by the square root of m.
With 16,384 registers: 1.04 / sqrt(16384) = 1.04 / 128, roughly 0.8 percent error.
Footprint: 16,384 registers times 6 bits each is 98,304 bits, which is 12,288 bytes (about 12 KB).
Same item hashed twice lands in the same register and changes nothing. That is exactly why duplicates do not inflate the count.

Count-Min Sketch#

CMS is a 2D grid of counters:

d rows, w columns, with a different hash function per row.
To record one occurrence: hash the item once per row, and increment the counter at that column in each row.
To ask "how many times have I seen X": hash it the same way, read the d counters, and return the smallest one.

Why the minimum, and why that is the safe choice:

Every counter an item maps to is at least as large as that item's true count.
Other items hashing to the same cell can only push a counter higher, never lower.
So each row gives an overestimate, and the smallest overestimate is your tightest bound.
CMS never undercounts. It only overcounts, and you control how much with the grid dimensions.

The error bound, with concrete numbers:

With width w and depth d, the overestimate is at most e/w times the total stream count, with probability at least 1 - (1/2)^d.
Concretely, w = 2718 and d = 5 bounds the error at about 0.1 percent of total volume with 97 percent confidence.
That uses 2718 times 5 counters, roughly 54 KB at 4 bytes each.

flowchart LR A[Event stream] --> B[Hash the item] B --> C[HLL registers] B --> D[CMS counter grid] C --> E[Harmonic mean estimate] D --> F[Take min of rows] E --> G[(Unique count)] F --> H[(Item frequency)]

The common shape of both structures. One event stream, one hash step, then the two sketches answer two different questions off the same input. Notice the hash is shared but what each side does with the bits is completely different: HLL reads leading zeros, CMS reads column positions.

3A worked example with real numbers#

Make it concrete. Say I run a video site. Yesterday one popular video got 50 million plays from 12 million unique viewers, and I want two numbers: how many unique viewers, and how many plays came from my single busiest viewer (a bot I suspect is replaying).

Unique viewers with HLL.

I hash each viewer ID into an HLL with 16,384 registers.
By the end of the day the sketch is 12 KB on disk, full stop, whether I saw 12 million viewers or 120 million.
When I call PFCOUNT it returns something like 11,904,000 or 12,096,000: within 0.8 percent of the true 12 million.
The exact hash-set alternative would have held 12 million IDs, roughly 192 MB lean or near 1 GB with real overhead, per video per day.
Across 10,000 videos that is the difference between 120 MB of sketches and terabytes of sets.

Pause before you read on: CMS reports the suspected bot played 72,000 times. The true count is 40,000. Did CMS malfunction, and can you still trust it for a "flag anything over 10,000 plays" alert?

Reveal the answer

Nothing malfunctioned. CMS only overcounts, so 72,000 for a true 40,000 is expected noise from other viewers colliding into the same cells. For a "flag over 10,000" threshold this is exactly the direction of error you want: the reading is guaranteed to be at least the true count, so you can never miss a real spike. You might occasionally flag a borderline-innocent viewer, and you tighten `w` if that happens too often.

Busiest viewer with CMS.

I keep a CMS with w = 2718, d = 5. Every play increments 5 counters.
The true busiest viewer played 40,000 times. The total stream is 50 million events.
Worst-case overestimate is e/w times 50 million: about 2.718 / 2718 * 50,000,000, roughly 50,000.
So CMS might report the bot's count anywhere from the true 40,000 up to about 90,000, and crucially never below 40,000.
For "is this viewer way over a 10,000-play threshold," a reading that is guaranteed not to undercount is exactly what I want: I never miss the bot, I might occasionally flag a borderline-innocent one, and I tighten w if the false alarms bother me.

The merge payoff.

I run 50 edge servers. Each keeps its own 12 KB HLL for the day.
At midnight each ships its sketch to a central job: 50 times 12 KB is 600 KB of network traffic.
I union them into one HLL and get the global unique-viewer count, still inside 0.8 percent error.
I moved under a megabyte instead of 50 million raw event rows.

~100,000:1

The compression that justifies the whole tradeHLL holds 100M uniques in 12 KB against a lean 1.6 GB exact set. This single ratio is why you reach for a sketch at all. When it stops being this lopsided (small cardinalities, a handful of items), the sketch loses its reason to exist.

4Trade-offs#

The honest framing for an interview: you give up exactness and the ability to ask certain questions, in exchange for memory that stays flat as data grows.

What HLL cannot do:

Tell you which items it saw. It only knows how many distinct ones.
Delete an item.
Answer "was user 123 in this set."
Stay accurate at small cardinalities, unless you use the sparse representation trick (which most good implementations do automatically).

What CMS cannot do:

List the top items by itself. It can only answer "how often is X" when you already have X in hand.
Decrement safely in the basic version, so sliding windows need conservative variants or a ring of sketches.
Stay precise for rare items when the error is additive and scales with total stream volume. A few monster-frequency items inflate everyone else's estimate.
In practice you pair it with a small heap of candidate heavy hitters to recover the "top items" question.

Dimension	HyperLogLog	Count-Min Sketch	Exact (hash set or map)
Question	How many unique	How often per item	Both, exactly
Memory	~12 KB, flat	Fixed grid, flat	Grows with distinct items
Error	~1 percent, two-sided	One-sided overcount	None
Mergeable	Yes, union	Yes, add grids	Expensive
Can delete	No	Only conservative variants	Yes
Can enumerate items	No	No	Yes
100M uniques footprint	12 KB	n/a	1.6 to 8 GB

The decision rule I want to hear in the room:

If an approximate answer off by 1 to 2 percent is fine for the business, and the exact answer costs gigabytes or a heavy scan, use the sketch.
If someone will dispute a billing number or a legal count, do not use a sketch.
Nobody wants to explain to finance why the invoice is "probably right within 2 percent."

A sketch is a bet that nobody will ever audit the number. Make that bet on purpose, not by accident.

5Where it is used#

Real systems lean on these heavily, and naming them in an interview lands well.

HLL in the wild:

Redis ships it natively as PFADD and PFCOUNT, capped at 12 KB per key. I have used it for "unique viewers per video per day" where storing full sets was a non-starter.
Presto and the old Redshift both expose approximate distinct-count functions backed by HLL, because COUNT(DISTINCT ...) over a trillion rows is brutal and most dashboards do not need the exact number.
BigQuery has it too, as APPROX_COUNT_DISTINCT.

CMS in the wild:

Network telemetry, for detecting heavy-hitter flows.
Ad systems, for click and impression frequency.
Stream processors like the ones built on Apache Flink or Spark, for trending-item detection.
Database query planners, estimating how many rows a value will match so the optimizer picks a join order.

The pattern that ties them together:

High-volume stream, you need an aggregate answer fast and cheap, and a small error is acceptable.
If that describes the problem, a sketch is probably the right tool.
Concrete example: a real-time dashboard counting unique users per minute per country. Keep one HLL per country, 195 countries at 12 KB each is about 2.3 MB, merge for regional totals, and the whole thing fits in memory on a single box.

6Common pitfalls and gotchas#

Using the wrong tool for the question.

The most common mistake I see.
HLL counts uniques, CMS counts frequencies.
Propose HLL to find the top 10 trending queries and you are wrong: HLL cannot rank anything.
Mixing these up reads as "I memorized the names but not the shapes."

Forgetting the one-sided error on CMS.

Candidates often say CMS "might be off." Be precise: it never undercounts, it only overcounts.
That property is why you can use it for thresholds like "alert if this item exceeds 1000 hits": a false positive on the alert is possible, but a missed real spike is not.

Assuming you can merge sketches with different parameters.

You can union two HLLs only if they have the same register count.
You can add two CMS grids only if they share dimensions and hash functions.
Pick your parameters once at the start. Changing them later means recomputing everything from raw data, which is often impossible if the raw data is gone.

Ignoring the small-range problem in HLL.

Plain HLL is inaccurate for low cardinalities.
Mature implementations switch to a sparse exact representation under a threshold and only flip to the register array when the set grows.
Roll your own and skip this, and your unique counts for low-traffic buckets will be embarrassing.

Hash quality.

Both structures assume uniform, independent hashing. A weak or biased hash wrecks the math.
Use a solid non-cryptographic hash from the murmur or xxhash families.
Do not reuse the same hash across what should be independent CMS rows.

Treating the error as worst case everywhere.

CMS error scales with total stream volume. In a stream dominated by a few giant items, counts for rare items get swamped.
If you need accurate tail frequencies, CMS is the wrong choice. Look at conservative-update variants or a different structure entirely.

Red flag that fails you here

Forcing a probabilistic structure onto a problem that demands exactness. If I ask for a billing total or a compliance count and you reach for HLL to save memory, you have failed the judgment check, and judgment is what the whole interview measures. The correct move is to refuse the sketch out loud and keep the exact path.

7How it shows up in interviews#

Interviewers reach for these when the problem has the word "unique" or "top" plus a huge scale.

Classic prompts: a unique-visitor counter for a site with billions of hits, trending topics, a rate limiter or heavy-hitter detector, analytics for an ad platform.

What we probe, and what separates a pass from a fail:

Do you pick the right structure for the question?

Uniques to HLL, frequencies to CMS.
A strong candidate says this in one sentence and moves on.
A weak one reaches for a hash set and only mentions memory when pushed.

Can you state the cost and the error?

Weak answer: "It's approximate and saves space, so we'd use HyperLogLog for the unique count."

No numbers, and numbers are the whole point of mentioning a sketch.

Strong answer: "HLL gives me unique counts at about 12 KB per key with 1 to 2 percent error. For 12 million viewers it lands within roughly 100,000 of the truth, versus near a gigabyte for an exact set. And it's mergeable across shards, so I aggregate 50 sketches by moving 600 KB instead of the raw events."

The difference is not polish. The weak answer could come from someone who read a blog title. The strong one proves you reasoned about the actual footprint and the actual error on this problem.

From the interviewer's chair

I am not testing whether you can recite "HyperLogLog." I am testing whether you volunteer the limits before I ask. A candidate who says "HLL can't tell me which users, so if product later wants retention cohorts I'll keep the raw events too" has shown me they think past the happy path. That one sentence moves you up a level.

Can you combine structures?

A great trending-topics answer is CMS for frequency plus a small heap holding candidate heavy hitters, maybe with an HLL alongside for unique-author counts.
Composing two sketches to answer a layered question is a senior move.

The trap I set:

I ask for exact billing or compliance counts.
The right response is to refuse the sketch: "These are approximate, so for anything auditable I'd keep the exact path and use sketches only for the live dashboard."
Candidates who try to force a probabilistic structure onto a problem that demands exactness fail the judgment check.

Follow-ups the interviewer will ask (and your answers)

"Can you delete a user from an HLL when they ask to be forgotten?"

No. HLL has no delete, because registers only ever hold a max run of leading zeros and you cannot know which items contributed. If deletion or right-to-be-forgotten matters, you need the raw events or a structure that supports removal. This is a real reason to keep raw data alongside the sketch for a retention window.

"Why take the minimum across CMS rows instead of the average?"

Because every row is an overestimate (collisions only add), so the true count sits at or below every counter. The minimum is the tightest upper bound that is still guaranteed to be at least the truth. Averaging would pull the estimate below some counters and break the one-sided no-undercount guarantee, which is the property you actually rely on for thresholds.

"How do you merge sketches computed on 50 different shards?"

HLL: union register-by-register, taking the max run in each register position, which only works if every shard used the same register count. CMS: add the grids cell-by-cell, which only works if they share width, depth, and hash functions. You freeze these parameters at the start precisely so the merge is valid later.

"The business wants the top 10 trending queries. Is HLL the tool?"

No, HLL cannot rank. Use CMS for per-item frequency plus a bounded min-heap of candidate heavy hitters: on each update, check the item's CMS estimate against the heap's smallest and swap if it is larger. That pair gives you an approximate top-K cheaply. Add an HLL per topic if you also want unique authors.

"Your CMS says a rare item has 500 hits but you know it had 3. What happened?"

Additive error from a high-volume stream. CMS error scales with total stream count, so a few monster items inflate every cell and swamp the true counts of rare items. If accurate tail frequencies matter, CMS is the wrong structure. Reach for conservative-update CMS or a count-sketch variant, or accept that CMS is only trustworthy for the heavy hitters.

What you can now explain in the room

Why HLL answers "how many unique" and CMS answers "how often," and how to pick from the question.
How HLL turns leading-zero runs across 16,384 registers into a cardinality at about 0.8 percent error.
Why CMS takes the minimum across rows, and why that guarantees it never undercounts.
The real footprint numbers: 12 KB for 100M uniques versus 1.6 to 8 GB for an exact set.
Why both are mergeable, and how that turns a cross-shard count into kilobytes of network traffic.
When to refuse a sketch entirely: anything billed, audited, or legally disputed needs the exact path.

For a full worked example, see the System Design Question walkthrough on building a real-time trending-topics and unique-visitor pipeline.

← Previous

Geospatial Indexing: Geohash and Quadtrees

Merkle Trees

Get a prep plan built around your HyperLogLog and Count-Min Sketch interview

Tell us the role and your interview date. We will send back a dated, day by day plan. Free.

Thanks. Check your inbox, your HyperLogLog and Count-Min Sketch prep plan is on the way.