HyperLogLog Explained: Counting Billions of Unique Items with 12 KB

Scenario context

HyperLogLog estimates the number of distinct elements in a dataset using ~12 KB of memory regardless of cardinality — with ±0.81% error. The insight: if you hash every element to a random bit string, the maximum length of leading zeros you observe is statistically correlated with how many distinct hashes you have seen. Multiple registers stochastically average this observation to reduce variance. Redis ships HyperLo…

This walkthrough focuses on The Unique Visitor Problem at Google Analytics Scale.

Before making a design choice, clarify:

• Google Analytics must answer one of the most common questions in web analytics: how many unique visitors viewed this page today?
• Not total page views — distinct users.
• At Google scale, a popular page may receive hundreds of millions of views per day from tens of millions of distinct users.

Concepts in play: hash-tables-and-bloom-filters, caching, sorting-and-searching-algorithms, jvm-internals-and-garbage-collection

Stage 1 — The Intuition: Leading Zeros as a Cardinality Signal

• Before the full algorithm, understand the core intuition — the "bit trick" that makes HyperLogLog work.
• If you hash each element to a uniformly random bit string, the probability that a given hash starts with at least k leading zeros is: Why?
• Each bit of a random hash is independently 0 or 1 with equal probability.
• The probability that the first bit is 0 is 1/2.

Observable outcome: The probability that the first bit is 0 is 1/2.

Stage 2 — The Full Algorithm: m Registers + Harmonic Mean

• HyperLogLog replaces the single ρ max tracker with m independent registers — small counters, one per sub-stream — and averages their estimates.
• Step 1: Split Each Hash into a Routing Prefix and a Value For each element x , compute a 64-bit hash h(x) .
• Split it into: Routing prefix : the first b bits, where m = 2^b registers.
• For Redis's default of 4096 registers, b = 12 .

Observable outcome: For Redis's default of 4096 registers, b = 12 .

Stage 3 — Deep Dive: Internals, Math, and Performance

• The Internals: Memory Layout and Register Encoding Redis's HyperLogLog representation uses exactly 12,304 bytes (≈ 12 KB).
• The layout: 4096 registers × 6 bits per register = 24,576 bits = 3,072 bytes for the register array.
• Redis packs these into 6144 bytes with its specific dense encoding (two additional bytes per 3-byte group for alignment).
• A 16-byte header stores the magic bytes, encoding type, and a cached cardinality estimate.

Observable outcome: A 16-byte header stores the magic bytes, encoding type, and a cached cardinality estimate.

Stage 4 — Visualizing the HyperLogLog Estimation Pipeline

• The following diagram traces how a stream of user IDs flows through HyperLogLog's estimation pipeline — from hashing to register update to cardinality estimate.
• Each element routes to exactly one register based on its hash prefix, and the register stores the maximum leading-zero count ever observed.
• The harmonic mean across all registers combines 4096 independent sub-stream estimates into a single cardinality figure.
• No individual element is stored — only the register maximums.

Observable outcome: No individual element is stored — only the register maximums.

Stage 5 — Real Uses: Where HyperLogLog Powers Analytics at Scale

• Redis ships HyperLogLog as a native data type.
• Every PFADD call updates a 12 KB sketch; every PFCOUNT returns the estimated cardinality with ±0.81% error.
• Redis's implementation is the most widely deployed HyperLogLog in the industry.
• Google Analytics and Mixpanel.

Observable outcome: Google Analytics and Mixpanel.

Stage 6 — HyperLogLog in Java: Simulation and Guava Integration

• The following Java code demonstrates the leading-zeros intuition that underlies HyperLogLog — useful for understanding the algorithm before reaching for a production library.
• Usage example — unique visitor counting: Three scenarios where this matters: 1.
• Count how many distinct user IDs received each variant.
• Use one HyperLogLog per variant; compare estimates to ensure balanced exposure without storing every user ID.

Observable outcome: Use one HyperLogLog per variant; compare estimates to ensure balanced exposure without storing every user ID.

End-to-end outcome

After working through the stages, you should be able to explain:

• The 12 KB guarantee is absolute — not approximate.
• The memory cost of a HyperLogLog sketch in Redis is fixed at ~12 KB regardless of whether you have seen 10 or 10 billion distinct elements.
• HyperLogLog is the correct structure when you need to answer "how many distinct elements have I seen?" at any scale, with sub-1% error, in fixed memory.
• Core algorithm: hash each element → use top b bits as register index → count leading zeros in remaining bits → update register with the maximum seen.

Alternatives considered

Decision Guide: When HyperLogLog Is the Right Tool

The deciding question: Do you need to count distinct elements, not store or enumerate them?

Failure and degraded modes

Trade-offs and Failure Modes

• Detection: HyperLogLog cannot remove elements.
• User or operator impact: HyperLogLog cannot remove elements.