HyperLogLog
On the roadmap:Staff Engineer · step 2: Approximate answers at scale
Estimate how many different items you have seen using about a kilobyte, however many there are. Duplicates are free.
In plain words
If you flip a fair coin, ten heads in a row is rare, so seeing a run like that suggests you flipped a lot of coins. A HyperLogLog does this with hash bits: it remembers the rarest pattern it has seen in each of many small groups, and turns that into a count of different items.
Why it matters
Counting different items exactly means remembering all of them. HyperLogLog uses a fixed, tiny amount of memory, adds an item in constant time, ignores repeats, and can be merged, so 'how many unique visitors?' is cheap at any scale.
Where you meet it
- Redis: PFADD and PFCOUNT, using at most 12 KB with a standard error of about 0.81%
- Analytics databases that offer approximate distinct counts
- Counting unique visitors, searches or devices without storing them
You will be able to
- Explain why a long run of leading zeros hints at how many items there were
- Merge counts from different machines without counting anything twice
- Say what error to expect for a given number of registers
In interviews
Appears in 'count unique visitors' and 'design a view counter', often as the answer when exact counting is too big.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Hash each item and use the first bits to pick a register
- Each register remembers the longest run of leading zeros it has seen
- An estimate from the harmonic mean of the registers, with a small-count correction
- merge() that keeps the larger value in each register
function hash32(s: string): number {
let h = 0x811c9dc5;
for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
return h >>> 0;
}
export class HyperLogLog {
readonly m: number; // the number of registers
readonly registers: Uint8Array; // each remembers the longest run of leading zeros it has seen, plus one
/** p: the first p bits of a hash pick a register, so there are 2^p registers. Typical error is about 1.04 / sqrt(2^p). */
constructor(readonly p = 10) {
this.m = 1 << p;
this.registers = new Uint8Array(this.m);
}
add(item: string): void {
const h = hash32(item);
const index = h >>> (32 - this.p); // the first p bits choose a register
const rest = (h << this.p) >>> 0; // the remaining bits
const rank = rest === 0 ? 32 - this.p + 1 : Math.clz32(rest) + 1; // where the first 1 bit is
if (rank > this.registers[index]) this.registers[index] = rank;
}
/** Estimated number of different items added. */
count(): number {
const alpha = this.m === 16 ? 0.673 : this.m === 32 ? 0.697 : this.m === 64 ? 0.709 : 0.7213 / (1 + 1.079 / this.m);
let sum = 0, zeros = 0;
for (const r of this.registers) { sum += 2 ** -r; if (r === 0) zeros++; }
const raw = (alpha * this.m * this.m) / sum;
// while few registers are used, counting the empty ones is more accurate
return raw <= 2.5 * this.m && zeros > 0 ? Math.round(this.m * Math.log(this.m / zeros)) : Math.round(raw);
}
/** Fold another sketch in: the result counts the union of both. */
merge(other: HyperLogLog): void {
for (let i = 0; i < this.m; i++) this.registers[i] = Math.max(this.registers[i], other.registers[i]);
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints hyperloglog ok when everything passes. You need Node.js installed.
mkdir hyperloglog && cd hyperloglog
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Redis keeps its HyperLogLog in at most 12 KB with a standard error of about 0.81%, and offers commands to add, count and merge.
- Improved versions such as HyperLogLog++ correct the bias at small and large counts and use 64-bit hashes, so very large counts stay accurate.
- Registers are often stored in a compact sparse form while few are in use, so small counts cost even less memory.
- Because a merge is just the larger value in each register, daily sketches can be combined into weekly or monthly counts.
Ways to count different items
| What it answers | Memory | Accuracy | Pick it when | |
|---|---|---|---|---|
| HyperLogLog | How many different items? | About 1 KB to 12 KB | Typically 1 to 3% off | You need big unique counts cheaply |
| Hash set | Exactly which items, and how many | Grows with the items | Exact | The set is small enough to keep |
| Bloom filter | Have I seen this item? | A few bits per item | Can say yes wrongly | You need membership, not a count |
| Count-Min sketch | How often was this item seen? | Fixed and small | Can be too high | You need per-item counts |
| Bitmap (linear counting) | How many different items? | About a bit per item | Good while counts are small | The range of counts is small |
What it cannot do
It gives an estimate, not the truth
Expect a few percent error. It is not suitable when you need an exact number, such as for billing.
It cannot say who was counted
Items are not stored, so you cannot list them, check one, or remove one.
Small counts need a correction
With few items most registers are empty, so the lab switches to counting the empty registers.
Quality depends on the hash
A weak hash with patterns skews every register and the error grows.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Change p and measure how the error follows 1.04 divided by the square root of the registers
- Add the correction for very large counts that hash collisions cause
- Count the different users per day, then merge seven days into a weekly count