Module 16 · Lesson 6 of 14Free

HyperLogLog: estimating unique counts with little memory

Level

Advanced

Topic

Analytics and counting at scale

Reading time

20 min

Kartly’s festival dashboard has processed 30 million product-view events today. The team wants unique customers, not views. Storing every customer ID for every audience breakdown is consuming the analytics workers’ memory.

How can you count unique customers without remembering who they are?

These are illustrative analytics numbers for Kartly’s many-services stage. Assume about 5 million distinct signed-in customers in this lesson’s daily stream.

Exact sets remember every customer

Start with a set of customer IDs. On each view, insert the customer’s ID. Read the set’s size for the exact distinct count.

The set must distinguish a new ID from one already present. Its storage therefore grows with the distinct audience, rather than the number of repeated views.

Suppose each customer ID occupies 16 bytes. Five million IDs need 80 MB just for their payload. This excludes the set’s indexing and allocation costs. Separate audience breakdowns can repeat that cost.

You can instead sort retained events and count changes between adjacent IDs. That moves work into a batch query and may use disk. It does not produce a continuously updated answer for free.

HyperLogLog, or HLL, is a sketch: a compact summary designed to answer a limited question. Here, that question is cardinality, meaning the number of distinct values.

The challenge is finding a summary that ignores repetition without retaining membership.

Rare patterns reveal audience size

Imagine hashing each customer ID into uniformly distributed bits. Use the same hash function every time.

For a fresh distinct ID, the chance of starting with a zero is one half. The chance of starting with four zeros is one in sixteen. Longer zero prefixes become progressively rarer.

Observing a rare prefix is evidence that you have seen many distinct IDs. It is not proof: the first customer could be unusually lucky.

Define the rank as the number of leading zeros plus one. A suffix beginning 1 has rank 1. A suffix beginning 001 has rank 3.

Remembering only the largest rank gives a noisy signal. HLL reduces that noise by splitting hashes among many registers, then combining their signals. Its update rule stores the maximum rank in the selected register. ^{1HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmPhilippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier, DMTCS Proceedings, Analysis of Algorithms, 2007}

For Kartly, this replaces “remember each customer” with “remember the strongest observation in each bucket”. Repeated observations cannot exceed their own previous maximum.

The remaining question is how one hash selects both a bucket and an observation without mixing those jobs.

Split the hash before measuring

Let the precision be p. Allocate m = 2^p registers, initially zero.

Use the first p hash bits as the register index. Measure the rank using only the remaining bits.

Here is a toy trace with four registers. The hash strings are invented for teaching, not actual customer hashes.

Notice the second row. A genuinely new customer does not necessarily change a register. HLL does not count changed registers as customers.

Also notice that bucket bits are excluded from the rank. Including them would make some buckets inherently more likely to have long zero prefixes.

With a finite suffix, define an all-zero suffix’s rank as its width plus one. This handles the boundary without searching beyond the available bits.

The register array now contains evidence about audience size. Turning that evidence into a number needs more than adding its entries.

Estimate from all the registers

The basic estimate combines registers through reciprocal powers:

Z = sum(2^(-M[j])) over all registers j
E = alpha_m × m² / Z

M[j] is a register value. alpha_m is a calibration factor. For register counts of at least 128, a common approximation is 0.7213 / (1 + 1.079/m).

This is the harmonic-mean construction behind HLL, rather than an arithmetic average of per-register size signals. It reduces the influence of unusually large observations. ^{1HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmPhilippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier, DMTCS Proceedings, Analysis of Algorithms, 2007}

You can see the difference without calculating a full estimate. A register at 3 contributes 1/8 to Z. Raising it to 20 reduces that contribution toward zero. It does not inject 2^20 directly into a sum.

Empty registers need another calculation

An empty array exposes a problem. Every term in Z equals one, yet the raw formula returns about 0.72 × m, not zero.

For small audiences, use the number of untouched registers, V:

E_small = m × ln(m / V)

This is linear counting. The educational implementation below uses it when the raw estimate is at most 2.5 × m and V is positive. ^{2HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation AlgorithmStefan Heule, Marc Nunkesser and Alexander Hall, EDBT, 2013}

Why does this help? Under uniform bucket selection, the expected untouched fraction after n distinct IDs is approximately exp(-n/m). Solving for n gives the formula above.

For the toy trace, two registers remain empty. That produces 4 × ln(4/2), or about 2.8. The actual distinct count is three. Four registers make the trace readable, not accurate.

A useful implementation therefore needs both an update rule and an estimator suited to its operating range.

Buy accuracy with more registers

For standard HLL, the asymptotic relative standard error is about 1.04 / sqrt(m) under the uniform-hashing model. This describes statistical spread, not a maximum error bound. ^{1HyperLogLog: the analysis of a near-optimal cardinality estimation algorithmPhilippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier, DMTCS Proceedings, Analysis of Algorithms, 2007}

Choose precision from the dashboard’s tolerance, then calculate its cost.

As an implementation reference, Redis documents up to 12 KB of HLL memory and a standard error of 0.81%. Do not assume every library uses its representation or estimator. ^{3HyperLogLogRedis, Redis documentation}

Even bounded memory per sketch can become expensive. The number of independently maintained audiences still matters.

Merge state instead of totals

Kartly already processes views across workers. Each worker can own a local sketch for a day and audience group.

A merger combines matching registers using maximum:

merged[j] = max(left[j], right[j])

For example, merging [0, 4, 3, 0] with [2, 1, 5, 0] produces [2, 4, 5, 0].

This follows directly from the update rule. The maximum over two subsets equals the maximum over their union. A customer appearing on both workers contributes the same bucket and rank.

Do not add the workers’ estimated counts. That would count shared customers twice.

The write path is event → local register update → snapshot → union update. The read path is dashboard → stored union → estimate.

Repeated snapshots are harmless because taking a maximum twice changes nothing. Out-of-order snapshots cannot decrease a register. These properties simplify retry handling, but they do not make storage durable.

Compatibility is essential. Both workers must agree on identity encoding, hash function, hash width, precision and register conventions. Include these in a versioned sketch format and reject mismatches.

Mergeable sketches develops the broader pattern. Here, maximum is the exact merge operation for the chosen register representation.

Implement the register mechanism

These matching implementations belong inside each analytics worker. They use the first 64 bits of SHA-256 and one byte per register.

The input contract is canonical ASCII customer IDs such as u_41. Hash UTF-8 bytes identically in both languages. The TypeScript version targets Node.js with ES2020 BigInt support.

from hashlib import sha256
from math import log

class HLL:
    def __init__(self, p: int = 14) -> None:
        if not 7 <= p <= 18:
            raise ValueError("precision must be 7..18")
        self.p = p
        self.m = 1 << p
        self.registers = bytearray(self.m)

    def add(self, customer_id: str) -> None:
        x = int.from_bytes(
            sha256(customer_id.encode("utf-8")).digest()[:8], "big"
        )
        width = 64 - self.p
        index = x >> width
        suffix = x & ((1 << width) - 1)
        rank = width - suffix.bit_length() + 1
        self.registers[index] = max(self.registers[index], rank)

    def merge(self, other: "HLL") -> None:
        if self.p != other.p:
            raise ValueError("incompatible precision")
        for i, value in enumerate(other.registers):
            self.registers[i] = max(self.registers[i], value)

    def estimate(self) -> float:
        alpha = 0.7213 / (1 + 1.079 / self.m)
        raw = alpha * self.m**2 / sum(
            2.0 ** (-r) for r in self.registers
        )
        empty = self.registers.count(0)
        if empty and raw <= 2.5 * self.m:
            return self.m * log(self.m / empty)
        return raw

import { createHash } from "node:crypto";

class HLL {
  readonly m: number;
  readonly registers: Uint8Array;
  constructor(readonly p: number = 14) {
    if (!Number.isInteger(p) || p < 7 || p > 18)
      throw new Error("precision must be 7..18");
    this.m = 2 ** p;
    this.registers = new Uint8Array(this.m);
  }
  add(customerId: string): void {
    const x = createHash("sha256")
      .update(customerId, "utf8").digest().readBigUInt64BE(0);
    const width = 64 - this.p;
    const index = Number(x >> BigInt(width));
    const suffix = x & ((1n << BigInt(width)) - 1n);
    const bits = suffix === 0n ? 0 : suffix.toString(2).length;
    const rank = width - bits + 1;
    this.registers[index] = Math.max(this.registers[index]!, rank);
  }
  merge(other: HLL): void {
    if (this.p !== other.p) throw new Error("incompatible precision");
    for (let i = 0; i < this.m; i++)
      this.registers[i] = Math.max(this.registers[i]!, other.registers[i]!);
  }
  estimate(): number {
    let z = 0, empty = 0;
    for (const r of this.registers) {
      z += 2 ** -r;
      if (r === 0) empty++;
    }
    const raw = (0.7213 / (1 + 1.079 / this.m)) * this.m ** 2 / z;
    return empty > 0 && raw <= 2.5 * this.m
      ? this.m * Math.log(this.m / empty) : raw;
  }
}

These are teaching implementations, not wire-compatible Redis HLLs. Their merge check assumes every instance uses this same code and identity contract.

For fixed-width hashes and bounded-length IDs, each update uses constant work. Estimation and merging scan all registers, taking O(m) time. Storage is O(m) bytes here; the code does not pack six-bit values.

One worker must own each mutable instance. If two writers read an old register and then write different maxima, the smaller write could overwrite the larger. Use serialized updates, an atomic maximum, or independent worker sketches followed by merging.

The code explains the mechanism. Production use also needs recovery, bounded group counts and a validated estimator.

Bound groups and preserve recovery

Suppose this scenario tracks 10,000 active audience groups. Byte-per-register sketches at the chosen precision require about 156 MiB of register payload. That excludes keys, object overhead and replicas.

Set group-retention rules before accepting arbitrary campaign or product labels. Otherwise, small individual sketches can still exhaust memory.

Use one sketch per UTC day and campaign. Merge daily sketches for a longer period; do not sum daily unique counts. The earlier time-window aggregation lesson covers window assignment.

A late view updates its original day’s sketch while that day remains open for correction. After retention expires, either rebuild from retained events or report the excluded data.

Replay is safe for repeated identities. Missing identities remain missing until their events are processed.

Common mistakes

• Treating standard error as a promise. A reported difference near the expected error scale may be estimation noise.
• Expecting membership answers. Register collisions deliberately discard the evidence needed to list customers.
• Subtracting yesterday’s sketch. Maximum updates have no inverse; overwritten observations cannot be recovered.
• Hashing events instead of customers. A fresh event ID turns repeated views into distinct inputs.
• Using the sketch to enforce once-per-customer rules. Use exact state and safe retry handling for those decisions.

Where this shows up

• Design: an ad click aggregator: estimate distinct clickers alongside exact event totals.
• Design: a video platform like YouTube: estimate distinct viewers without keeping every viewer in dashboard state.

Kartly can now estimate audience size; next it needs to estimate how often each product appears without storing every product’s counter.

Check your understanding

Summary