Skip to content
Tutorials Center
My learning

Topics

Lesson 43 of 65 ยท Core Algorithms and Data Structures for Design

Counting at Scale: HyperLogLog and Count-Min

Count unique visitors and heavy hitters with tiny memory: HyperLogLog for distinct counts and Count-Min Sketch for frequencies, with runnable Python implementations.

Counting sounds trivial until the numbers are huge. How many distinct users visited your site today? How many times was each of 100 million URLs requested? An exact answer needs memory proportional to the number of distinct items: a set of 500 million user IDs takes gigabytes, and merging such sets across servers is expensive.

Probabilistic data structures (sketches) trade a small, controlled error for a tiny, fixed amount of memory. This lesson covers two you should know for system design: HyperLogLog for counting distinct elements and Count-Min Sketch for estimating how often each element occurs. Both are used in Redis, databases, network monitoring and analytics pipelines. They are siblings of the Bloom filter, which answers membership.

Counting distinct items: the idea behind HyperLogLog

Flip a fair coin repeatedly until you see heads; the number of tails before it is your result. Getting 10 tails in a row is rare (probability 1 in about 1,000), so if someone tells you their longest run was 10, they probably tried around a thousand times.

HyperLogLog (HLL) uses this trick on hashes. Hash each item to a uniformly random bit string. The count of leading zeros in the hash is like the run of tails. If the maximum leading zeros you have seen is r, then you have probably seen about 2^r distinct items. Duplicates hash to the same value, so they never change the maximum, which is why it counts distinct items.

One maximum is very noisy, so HLL splits items into m registers using the first bits of the hash, keeps the maximum per register, and combines the registers with a harmonic mean. The standard error is about 1.04 / sqrt(m): with 16,384 registers (12 KB in Redis) it is roughly 0.8 percent, whether you count a thousand items or a billion.

Python HyperLogLog from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error stays within a few percent while the true count grows a thousandfold, and the memory never changes.

Merging: the superpower

Two HLL sketches built with the same parameters can be merged by taking the maximum of each register pair. The result equals the sketch of the union of both streams. That makes HLL ideal for distributed systems: every server counts its own traffic, and a central job merges small sketches instead of moving user IDs around.

Python Daily uniques per server, merged into one total

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Adding the three local counts overcounts users who visited several servers; merging the sketches counts each user once.

Counting frequencies: Count-Min Sketch

A different question: how many times did item x occur? Which are the most frequent items ("heavy hitters")? An exact counter per item needs a dictionary with one entry per distinct item.

A Count-Min Sketch (CMS) is a small 2D array of counters with d rows and w columns, plus one hash function per row.

  • Add an item: in each row, hash the item to a column and increment that counter.
  • Estimate an item: compute its column in each row and take the minimum of those d counters.

Collisions only ever add extra counts, so every counter is at least the true count, and the minimum across independent rows is the least contaminated. The estimate is therefore never too low, but can be too high: it overestimates, never underestimates. With width w = ceil(e/ฮต) and depth d = ceil(ln(1/ฮด)), the error is at most ฮต times the total count with probability at least 1-ฮด.

Python Count-Min Sketch on a skewed stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Heavy hitters are estimated well because their counts dwarf the noise, while rare items may be inflated by collisions. For finding the top items you combine a CMS with a small heap or use the Space-Saving algorithm, which tracks only k candidates (covered in Tries and Top-K).

Choosing a sketch

Question Structure Error type Mergeable
Is x in the set? Bloom filter False positives only Yes (bitwise OR)
How many distinct items? HyperLogLog Relative error about 1/sqrt(m) Yes (max)
How often did x occur? Count-Min Sketch Overestimates only Yes (add tables)
Which items are most frequent? Count-Min plus heap, or Space-Saving Approximate ranks Mostly

Using them in a design

  • Unique visitors per page per day: one HLL per page and day; Redis offers PFADD, PFCOUNT and PFMERGE for this. Weekly uniques come from merging seven daily sketches, which is impossible with plain counters.
  • Trending hashtags and top searches: a CMS per time window feeds a top-k tracker.
  • Network and abuse detection: estimate packets per source IP with fixed memory to spot heavy senders.
  • Rate limiting at huge scale: approximate per-key counters (see Retries, Timeouts and Dead Letter Queues for why protecting dependencies matters).
  • Database query planners: HLL estimates column cardinality to choose join orders.

Sketches are for estimates. Do not use them for billing, inventory or anything that must be exact. Tell product owners the error bound, for example "unique visitors, plus or minus 1%".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does HyperLogLog estimate?

    HLL estimates cardinality, the count of unique elements, using leading-zero statistics of hashes.
  2. 2. Why can two HyperLogLog sketches be merged to count a union?

    Each register stores a maximum, and the max of maxima equals the maximum over the union, so overlap is not double counted.
  3. 3. A Count-Min Sketch estimate can be:

    Collisions only add to counters, so the minimum over rows is an upper bound on the true count.
  4. 4. Which is NOT a good use of a sketch?

    Billing needs exact counts. Sketches are approximate and are best for analytics and monitoring.

Summary

  • Exact counting needs memory proportional to distinct items; sketches use small fixed memory with bounded error.
  • HyperLogLog estimates distinct counts from the longest run of leading zeros across many registers, with about 1/sqrt(m) error.
  • HLL sketches merge by register-wise maximum, which suits distributed counting.
  • Count-Min Sketch estimates frequencies by taking the minimum across hashed counter rows: it overestimates, never underestimates.
  • Use sketches for analytics and monitoring, not for exact accounting.

Next: Geospatial Indexing