linkjob-notes

Counting distinct items sounds trivial until you have a billion events per day. Storing every user ID in a set to count unique visitors costs gigabytes. HyperLogLog (HLL) does it in about 12 KB with roughly 0.8 percent error.

The core intuition

Hash every item to a random-looking bit string. In random bits, a run of k leading zeros shows up about once every 2^k items. So if the longest run of leading zeros you have seen is 20, you have probably seen around a million distinct items. Duplicates hash to the same value, so they never change the answer. That is why HLL counts distinct items.

Why many buckets

One “longest run” estimate is very noisy. HLL uses the first few bits of the hash to pick one of m buckets (for example 16,384) and tracks the max run per bucket. It then combines the buckets with a harmonic mean, which dampens outliers. More buckets means lower error: the standard error is about 1.04 / sqrt(m).

Properties that make it useful

  • Mergeable: the union of two HLLs is just the per-bucket maximum. You can count daily uniques per server and merge them into weekly uniques without reprocessing raw data.
  • Fixed memory: size depends on m, not on how many items you add.
  • No deletes: you cannot remove an item. If you need that, look at other sketches.

Where you meet it

Redis has PFADD and PFCOUNT. BigQuery, Snowflake, and Presto expose APPROXCOUNTDISTINCT. Analytics pipelines use HLL for unique users, unique IPs, and cardinality checks on columns.

In an interview

If a system design question asks for “unique viewers per video,” mentioning HLL with its error bound and mergeability is a quick way to show depth. For practicing how to explain trade-offs like this clearly, see AI interview copilot (I help build Linkjob AI).