HyperLogLog architecture, in depth: registers, sparse encoding, estimators and merge in production

The idea in one paragraph, and the numbers that follow from it

Hash each item to a uniformly random 64-bit value. Use the first p bits to pick one of m = 2^p registers, and in the remaining bits find the position of the first 1 bit, called the rank. A rank of k happens with probability 2^-k, so a register that has seen rank 20 has probably seen around a million distinct hashes routed to it. Each register keeps only the maximum rank it has seen. The estimate combines all registers with a harmonic mean, E = α_m · m² / Σ 2^-M[j], where α_m is roughly 0.7213 / (1 + 1.079/m) for m of 128 or more. Duplicates hash identically and so cannot raise any register: that is why the structure counts distinct items.

The relative standard error is about 1.04/√m, and a rank never exceeds 64 − p + 1, so 6 bits per register are enough for a 64-bit hash. Those two facts give the whole sizing table:

Each extra bit of precision doubles memory and cuts error by √2. About 95% of estimates land within two standard errors, so a p = 14 sketch usually reports 1,000,000 as 984,000 to 1,016,000. Choose p from the error your consumers can tolerate, not from habit.

The architecture: five components

A production HLL has five parts, and each one has a decision that is easy to get wrong.

• Canonicalisation and hashing turn an item into 64 uniform bits. The hash function, its seed and the exact bytes fed to it are part of the sketch format.
• Bit split decides which bits index the register and which feed the rank. Implementations differ: the example below uses the top p bits, while Redis uses the low 14 bits. Both are correct; they are not compatible.
• Register store holds the maxima, sparse for small sets and dense for large ones.
• Merge and serialisation move sketches between processes and storage.
• Estimator turns registers into a number, with corrections at the small end of the range.

Hashing and canonicalisation

Everything HLL promises rests on the hash behaving like a random function over your inputs. Use a well-mixed 64-bit hash such as MurmurHash64A, xxHash64 or a truncated BLAKE2; avoid language default hash functions, which are often seeded per process (so two workers disagree) or weak on short integer keys. With a 32-bit hash the original paper needed a large-range correction as the count approached 2³² because collisions became common; with 64 bits that correction is unnecessary at any cardinality you will meet.

The quieter failure is canonicalisation. User@Example.com, user@example.com and user@example.com are three distinct items to a hash. Decide once, in a shared library, how each field is normalised (case, whitespace, Unicode normalisation form, integer versus string encoding of ids) and version that decision alongside the hash. Hash user ids as integers in one service and as strings in another, and the sketches merge without error while double-counting every user.

Dense registers: packing 6-bit values

The dense form is an array of m registers, 6 bits each, packed across byte boundaries. Redis stores exactly this: 16,384 registers in 12,288 bytes after a 16-byte header. Packing is simple bit arithmetic, but the edge cases (a register straddling two bytes) are where hand-written implementations go wrong, so test it against a one-byte-per-register reference.

def get6(buf: bytearray, i: int) -> int:
    byte, off = divmod(i * 6, 8)
    v = buf[byte] >> off
    if off > 2:                              # register spills into the next byte
        v |= buf[byte + 1] << (8 - off)
    return v & 63

def set6(buf: bytearray, i: int, v: int) -> None:
    byte, off = divmod(i * 6, 8)
    buf[byte] = (buf[byte] & ~(63 << off) & 0xFF) | ((v << off) & 0xFF)
    if off > 2:
        hi_mask = 63 >> (8 - off)
        buf[byte + 1] = (buf[byte + 1] & ~hi_mask & 0xFF) | (v >> (8 - off))

Some libraries offer 4-, 6- and 8-bit register variants: 8 bits wastes a quarter of the space but makes every access a single byte load. The estimate is the same; only size and update cost change.

Sparse registers: why small sketches matter most

Most real sketch populations are dominated by small sets. If you keep one sketch per page, per campaign or per API key, the long tail sees tens of distinct items, and a 12 KB dense array to record 30 values is a 400-fold waste. Both major production designs therefore start sparse.

HLL++ (Heule, Nunkesser and Hall, 2013) keeps a sorted list of (index, rank) pairs, computed at a much higher precision p′ (25 in the paper), compressed with variable-length and difference encoding. While sparse, the higher precision makes small counts very accurate; when the list would outgrow the dense array, it converts to dense at the normal p, which is lossless because p′ indices fold down to p.

Redis uses a run-length encoding over the normal 16,384 registers with three opcodes: ZERO (one byte, 1 to 64 empty registers), XZERO (two bytes, up to 16,384 empty registers) and VAL (one byte, a value from 1 to 32 repeated 1 to 4 times). A fresh key is a single XZERO. It promotes to dense when the sparse form passes hll-sparse-max-bytes (3000 bytes by default) or when a register needs a value above 32, which VAL cannot express. Sparse updates cost more CPU, since an insert can split a run.

Estimators across the range

The raw harmonic-mean estimate is biased upwards when many registers are still zero. The original fix is linear counting: if E ≤ 2.5m and V registers are zero, report m · ln(m / V) instead, which treats the registers as a hash-bitmap. The switch point creates a visible bump in error around 2.5m. HLL++ replaced it with an empirically measured bias-correction table and a tuned threshold per precision. Otmar Ertl's 2017 estimator, which Redis uses, derives a formula over the histogram of register values that is accurate across the whole range with no switch and no tables. If you implement your own, the minimal correct version is:

import hashlib, math

def h64(item: str) -> int:
    d = hashlib.blake2b(item.encode("utf-8"), digest_size=8).digest()
    return int.from_bytes(d, "big")

class HLL:
    def __init__(self, p: int = 14):
        assert 4 <= p <= 18
        self.p, self.m = p, 1 << p
        self.reg = bytearray(self.m)         # 1 byte per register for clarity

    def add(self, item: str) -> None:
        x = h64(item)
        idx = x >> (64 - self.p)             # top p bits choose the register
        w = x & ((1 << (64 - self.p)) - 1)   # remaining 64-p bits
        rank = (64 - self.p) - w.bit_length() + 1
        if rank > self.reg[idx]:
            self.reg[idx] = rank

    def estimate(self) -> float:
        m = self.m
        alpha = 0.7213 / (1 + 1.079 / m)
        e = alpha * m * m / sum(2.0 ** -r for r in self.reg)
        zeros = self.reg.count(0)
        if e <= 2.5 * m and zeros:
            return m * math.log(m / zeros)   # linear counting for small sets
        return e

Estimation is O(m), so production systems cache it: Redis keeps the last cardinality in the header and marks it stale when a register changes.

Merge, folding and why intersections are dangerous

The union of two sketches is the register-wise maximum. Max is commutative, associative and idempotent, which is what makes HLL an architecture component rather than a curiosity: shards merge in any order, a retried merge cannot double-count, and per-minute sketches roll up into hours, days and months. The rule is strict: both sides must use the same hash, seed, canonicalisation and bit split. Precision can be reduced but never increased, because the index bits you drop become the top of the rank field:

    def fold(self, new_p: int) -> "HLL":
        d = self.p - new_p
        assert d >= 0, "cannot raise precision"
        out = HLL(new_p)
        for idx, r in enumerate(self.reg):
            if r == 0:
                continue
            hi, lo = idx >> d, idx & ((1 << d) - 1)
            new_rank = (d - lo.bit_length() + 1) if lo else d + r
            out.reg[hi] = max(out.reg[hi], new_rank)
        return out

    def merge(self, other: "HLL") -> None:
        if other.p != self.p:
            raise ValueError("fold the higher-precision sketch down first")
        self.reg = bytearray(max(a, b) for a, b in zip(self.reg, other.reg))

Intersections have no native operation. The usual workaround, |A ∩ B| = |A| + |B| − |A ∪ B|, subtracts large noisy numbers: if A and B each hold ten million items and share ten thousand, the union's 0.81% error is around 160,000, which swamps the answer entirely. If you need intersections, differences or Jaccard similarity, use a sketch built for them, such as a theta sketch or MinHash, and keep HLL for unions and counts.

Worked example: unique visitors per page, rolled up

A site with 50,000 pages wants daily, weekly and yearly unique visitors per page. Exact sets would need every visitor id per page per day. With HLL at p = 14, each page-day is one sketch. Fully dense, a year is 50,000 × 365 × 12,288 bytes, about 224 GB. But traffic is skewed: suppose 90% of page-days see under 200 visitors. In a sparse encoding those sketches are a few hundred bytes each, and the store shrinks to a small fraction of the dense figure, dominated by the popular pages that genuinely need 12 KB.

The weekly count for a page is the estimate of the merge of seven daily sketches, not the sum of seven daily estimates; summing counts a returning visitor seven times. The yearly count merges 365 sketches, and its error is still 0.81% of the yearly total, because merging does not accumulate error. What you cannot do is subtract: visitors who came this week but not last week is a set difference, and the inclusion-exclusion trap above applies.

Databases expose the same pattern: BigQuery's HLL_COUNT functions build and merge HLL++ sketches, and Impala uses an HLL-style estimate for the number of distinct values when computing table statistics, which is why Impala's NDV statistics are approximate by design.

Failure modes

Operational guidance and trade-offs

Treat the sketch as a data format, not an in-memory trick. Put a version, the precision and the hash identifier in a header, write a golden-file test that a sketch serialised by one service loads and merges correctly in every other, and alert on merge rejections. Pick precision per use: dashboards live happily with 1.6%, capacity planning with 0.8%, anything that bills a customer should not use HLL at all.

If you want to see why the exact alternative is expensive, hash tables explains the per-entry overhead that a distinct-count set pays, which is exactly what HLL avoids.

What to do next

1. Pick one shared HLL library per organisation and record its hash, seed, bit split and precision in a versioned sketch header.
2. Write the canonicalisation rules for each counted field and put them in the same library.
3. Choose p from the error your consumers can tolerate using the sizing table, and document it next to the metric.
4. Enable a sparse representation if most of your sketches are small; measure the size distribution first.
5. Store per-window sketches and answer longer ranges by merging, never by summing estimates.
6. Add a cross-service golden-file test for serialise, merge and estimate, and ban inclusion-exclusion intersections in code review.