HyperLogLog

The problem: unique visitors, per link, per day

Owners want "unique visitors" for each link: not clicks, but distinct people (by a hashed visitor ID). The exact way keeps a set of IDs per link per day. A popular link with 2 million visitors needs 2 million IDs, around 32 MB at 16 bytes each, and Snip has millions of links and wants weekly and monthly uniques too. Uniques also don't add up: Monday's visitors plus Tuesday's double-count everyone who came both days, so each period needs its own set.

The idea: rare events tell you how many tries there were

Flip a coin until it comes up heads. If someone tells you the longest run of tails they saw was 10, they probably flipped around 2¹⁰ times: a run that long is rare, so it took many attempts to see one.

HyperLogLog applies this to hashes. Hash each visitor ID to a random-looking number and look at the leading zero bits. About half of hashes start with a 1, a quarter with 01, an eighth with 001. Seeing a hash that starts with 20 zeros suggests about 2²⁰ distinct items, and crucially, seeing the same visitor again gives the same hash, so duplicates change nothing.

One maximum is noisy, so HyperLogLog splits the hashes into m buckets (registers) using the first few bits, records the longest run of zeros per bucket, and combines them with a harmonic mean, which isn't thrown off by one lucky bucket. The error falls as buckets are added: the standard error is about 1.04 / √m.

Try it

From the lab: at precision 10 (1,024 registers, 768 bytes), a million visitors are estimated within about 3%, against about 15 MB for the exact set. At precision 14 (16,384 registers, 12 KB) the error is a fraction of a percent. At precision 4 (16 registers) it's off by about 20%. The memory doesn't grow with the number of visitors at all.

Merging: the property that makes it useful

The union of two HyperLogLogs is the register-by-register maximum, with no loss of accuracy. So Snip keeps one sketch per link per hour, and:

• Daily uniques = merge 24 hourly sketches. Weekly = merge 7 daily ones. No raw IDs needed.
• Each app server can keep its own sketch, and a central job merges them.
• Overlapping visitors are handled correctly: the lab's merge, with half the visitors in both days, estimates the union, not the sum.

What you can't do is subtract or intersect reliably: "visitors on Monday who didn't come back on Tuesday" needs other techniques.

A small implementation

export class HyperLogLog {
  readonly m: number;
  readonly registers: Uint8Array;

  constructor(readonly p = 14) {
    this.m = 1 << p; // 2^p registers
    this.registers = new Uint8Array(this.m);
  }

  add(item: string) {
    const h = hash32(item); // any well-mixed 32-bit hash
    const idx = h >>> (32 - this.p); // first p bits pick a register
    const rest = (h << this.p) >>> 0; // remaining bits
    const rank = rest === 0 ? 32 - this.p + 1 : Math.clz32(rest) + 1; // position of the first 1-bit
    if (rank > this.registers[idx]) this.registers[idx] = rank;
  }

  count(): number {
    let sum = 0;
    let zeros = 0;
    for (const r of this.registers) {
      sum += 2 ** -r;
      if (r === 0) zeros++;
    }
    const alpha = 0.7213 / (1 + 1.079 / this.m);
    const estimate = (alpha * this.m * this.m) / sum;
    // Small counts: many registers still empty, so count those instead (linear counting).
    if (estimate <= 2.5 * this.m && zeros > 0) return this.m * Math.log(this.m / zeros);
    return estimate;
  }

  /** The union of two sketches is the register-by-register maximum. */
  merge(other: HyperLogLog) {
    for (let i = 0; i < this.m; i++) this.registers[i] = Math.max(this.registers[i], other.registers[i]);
  }
}

Tested at precision 14: counts from 100 to a million, each added twice, came within 0.7%; over 20 runs of 100,000 the root-mean-square error was 0.70%, against the theoretical 0.81%; merging two sketches of 60,000 visitors with 30,000 in common estimated 90,640 for a true 90,000. Production versions use a 64-bit hash, so very large counts don't suffer hash collisions, and Google's HyperLogLog++ adds a sparse mode for small counts and bias correction.

Use the one you have

Redis has it built in: PFADD visitors:x7Kp:2026-11-04 <visitor-id>, PFCOUNT, PFMERGE. Each uses at most 12 KB with a 0.81% standard error. Most analytics databases offer an approximate distinct count based on HyperLogLog too.

Recap

Interview questions