Engineering Atlas › System Design Fundamentals

Counting unique items with HyperLogLog

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The intuition

Hash every item to a random bit string. Half of all hashes start with 1, a quarter with 01, an eighth with 001. If the longest run of leading zeros seen is 20, you have probably seen around 2^20 distinct values, and duplicates never change the answer. One observation is very noisy, so HLL splits the stream into many independent sub-streams and averages.

Registers

Choose a precision p and create m = 2^p registers. For each item:

  1. Hash it to 64 bits (32 is enough for modest cardinalities).
  2. Use the first p bits as the register index.
  3. In the remaining bits, compute the position of the first 1 bit (leading zeros plus one), called the rank.
  4. Set the register to the maximum of its current value and that rank.

Each register is a small number, at most about 64, so 6 bits per register suffice. With p = 14 that is 16,384 registers in 12 KB, the configuration Redis uses.

The estimate

HLL combines the registers with a harmonic mean, which resists outliers:

E = alpha * m^2 / sum(2^-register[j])

where alpha is a constant close to 0.72 that corrects a systematic bias. The relative standard error is about 1.04 / sqrt(m): 1.6 percent at p = 12, 0.81 percent at p = 14, 0.41 percent at p = 16. The original paper's headline example is counting well beyond 10^9 distinct items at about 2 percent error in 1.5 KB (Flajolet et al., 2007).

Small and large ranges

With few items, many registers are zero and the raw formula overestimates, so the original algorithm switches to linear counting: with V empty registers, the estimate is m * ln(m / V). Google's HLL++, which most libraries implement, adds empirical bias correction, a 64-bit hash so large counts do not saturate, and a sparse encoding for small sketches (Heule et al., EDBT 2013).

Newer estimators replace those patches with one formula. Otmar Ertl's 2017 estimator removes the small- and large-range bias from theory rather than from empirical tables (Ertl), and current Redis computes PFCOUNT with it instead of linear counting (Redis source). Ertl's UltraLogLog (2024) keeps mergeability and constant-time inserts but needs 24 to 28 percent less space than HLL for the same accuracy (PVLDB), so "HLL" is no longer the last word in distinct counting.

Merge, union, intersection

Two sketches with the same p and hash function merge by taking the element-wise maximum of registers. The result is exactly the sketch you would have built from the combined stream, so the union of daily sketches gives a weekly count with no extra error. Intersection must be estimated as |A| + |B| - |A union B|; when the overlap is small relative to the sets, the subtraction of two large noisy numbers produces a huge relative error. A maximum-likelihood method gets better intersection estimates from the same registers, but small overlaps of large sets stay noisy.

Sketches with different precision can still be combined by folding the finer one down to the smaller p. BigQuery does this automatically: merging a precision-14 and a precision-15 sketch returns precision 14 (BigQuery docs). Sketches built with different hash functions cannot be combined at all.

Down the stack

Layer 1The contract

The estimate has relative standard error about 1.04 / sqrt(m). That is a statistical statement: about 68 percent of estimates fall within one standard error and 95 percent within two, not a hard bound. Merging two sketches with the same precision and hash is lossless. The result depends only on the set of distinct items, not their order or multiplicity. Nothing about individual items can be recovered.

Layer 2The mechanism

Redis stores a HyperLogLog as an ordinary string, so GET and SET serialise it (Redis docs). A 16-byte header holds the magic HYLL, an encoding byte (dense or sparse), and a cached cardinality whose top bit marks it stale. The dense form packs 16,384 6-bit registers into 12,288 bytes. The sparse form is run-length encoded with three opcodes: ZERO (one byte, up to 64 empty registers), XZERO (two bytes, up to 16,384), and VAL (one byte, a value up to 32 repeated up to 4 times); any register above 32 forces the dense form. Redis also converts to dense when the sparse form, header included, exceeds hll-sparse-max-bytes, 3,000 by default (redis.conf). Items are hashed with 64-bit MurmurHash2 (MurmurHash64A). PFCOUNT returns the cached value if nothing changed since the last count.

BigQuery exposes the same idea through HLL_COUNT.INIT, HLL_COUNT.MERGE, and HLL_COUNT.EXTRACT, storing HLL++ sketches as bytes columns with precision from 10 to 24, default 15. Defaults differ between engines: Presto's APPROX_DISTINCT defaults to about 2.3 percent standard error and is exact below 256 items thanks to its sparse layout (Meta), while Redis gives 0.81 percent. Two dashboards that both say "unique users" can disagree by more than either team's error budget.

Layer 3The machine

An add is one hash of the input (roughly 10 to 30 ns for a short key), one count-leading-zeros instruction (LZCNT on x86, CLZ on ARM), and a read-modify-write of a 6-bit field that may straddle two bytes. The whole dense sketch, 12 KB, fits in a 32 to 48 KB L1 data cache, so updates are a few nanoseconds once warm.

Counting is the heavier operation: summing 2^-register over 16,384 registers with a precomputed table takes on the order of 10 to 50 us, which is why Redis caches the result. Merging is a byte-wise maximum, which vectorises well. On the network, a dense sketch is 12 KB; most sparse sketches are a few hundred bytes, which matters when millions are shipped between services.

Why it's built this way

  1. Exact distinct counting needs memory proportional to the number of distinct items, so the sketch accepts error in exchange for constant space.
  2. The longest run of leading zeros needs only log log n bits to store, which is where the name comes from.
  3. One such observation is very noisy, so the stream is split into m registers and combined, with error falling as 1 / sqrt(m).
  4. Most real sets are small, so implementations add sparse encodings and small-range corrections instead of always paying for 12 KB.

Diagram

flowchart LR
    X["Item"] --> H["64-bit hash"]
    H --> I["First p bits: register index j"]
    H --> R["Rest: rank = leading zeros + 1"]
    I --> U["register[j] = max(register[j], rank)"]
    R --> U
    U --> E["Harmonic mean of 2^register"]
    E --> C{"Many empty registers?"}
    C -->|yes| L["Linear counting"]
    C -->|no| A["Bias-corrected HLL estimate"]

Worked example

An ad platform reports unique users per campaign, per country, per day. There are 20,000 active campaigns and 60 countries, about 1.2 million (campaign, country) pairs each day, from 8 billion impression events.

Exact counting needs a set of user IDs per pair: about 1 GB for one 30-million-user campaign-day, and daily numbers cannot be added into weekly uniques because users repeat across days.

With HLL at p = 14, each pair costs 12 KB dense, or a few hundred bytes sparse, about 4 GB per day in the warehouse. A 30-day count for one campaign merges 1,800 sketches (30 days by 60 countries) in a few milliseconds, with 0.8 percent standard error.

The trade surfaces when the sales team asks "how many users saw both campaign A and campaign B?". If A reached 10 million users, B reached 8 million, and the overlap is 50,000, inclusion-exclusion subtracts two numbers each uncertain by about 80,000. The answer is meaningless. That question needs a different sketch (Theta or KMV sketches handle set operations better) or an exact join on sampled data.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
HyperLogLog (HLL++)Fixed tiny memory, mergeable, about 1 percent errorNo membership or listing, poor intersectionsDistinct counts over large, partitioned data
Exact set or COUNT(DISTINCT)Exact, supports any queryMemory grows with cardinality, not mergeable across periodsSmall cardinalities or billing-grade numbers
Theta / KMV sketchesUnions, intersections, and differencesLarger than HLL for the same errorOverlap and set-difference questions
Roaring bitmaps of user IDsExact, fast set algebraNeeds dense integer IDs, more memoryAudience building and segmentation

Pitfalls in production

Leadership lens

Check yourself

  1. Why does adding the same item a million times not change an HLL estimate?

    Show answer

    The item always hashes to the same register and rank, and the register keeps a maximum, so repeats cannot change any register.

  2. Why is a harmonic mean used to combine registers instead of an arithmetic mean?

    Show answer

    Register values contribute as powers of two, so one unusually large register would dominate an arithmetic mean; the harmonic mean downweights those outliers.

  3. Doubling the registers from 16,384 to 32,768 improves error from 0.81 percent to what, and why only that much?

    Show answer

    About 0.57 percent, because error scales as 1.04 / sqrt(m), so doubling memory improves accuracy by only a factor of the square root of two.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →