System Design (High-Level Design) Module 14 – Search, geospatial and probabilistic data structures
HyperLogLog, Count-Min and heavy hitters
How HyperLogLog counts distinct users and Count-Min counts frequent items in kilobytes, how sketches merge across servers, and how to find heavy hitters.
What you will learn
- Count distinct items with HyperLogLog and state the error that comes with its memory
- Estimate frequencies with Count-Min and find the heavy hitters of a stream
- Merge sketches across machines and time windows
- Decide where an approximate count is acceptable and where only an exact one will do
Before you start
What you’ll learn · Before you start
What you will learn
- Count distinct items with HyperLogLog and state the error that comes with its memory
- Estimate frequencies with Count-Min and find the heavy hitters of a stream
- Merge sketches across machines and time windows
- Decide where an approximate count is acceptable and where only an exact one will do
Before you start
On this page
Counting gets hard when the counts must be distinct or per item and the stream holds billions of events. How many different people opened a page today? Which songs were played most in the last minute? Exact answers keep every distinct item, so their memory grows with the data: 100 million user ids of 16 bytes are 1.6 GB before any overhead. sketch (data summary): A small, fixed-size summary of a stream that answers one question, such as how many distinct items it held or how often an item occurred, with a stated error instead of an exact answer. keep a small, fixed state instead and answer with a stated error. HyperLogLog estimates how many distinct items a stream holds. Count-Min estimates how often each item occurred. A Count-Min sketch with a short list of candidates finds the heavy hitters, the few items that make up a large share of the stream.
What a sketch keeps instead of the items
HyperLogLog hashes every item and looks at where the first 1 bit of the hash falls. A hash that starts with k zeros turns up about once in 2^k distinct items, so the longest run of zeros hints at how many there were. One hint is noisy, so HyperLogLog splits the hashes over m register (HyperLogLog): One of the m small counters of a HyperLogLog. The first bits of an item's hash choose the register, and it keeps the largest rank, one plus the leading zeros, seen among the rest of the bits. by their first bits, keeps the largest rank seen in each, and combines all m into one estimate with a typical error of 1.04 ÷ √m (Flajolet et al.). Redis’s HyperLogLog uses at most 12 KB and reports a standard error (of an estimate): The typical size of an estimate's error over many runs, its root mean square. For HyperLogLog it is about 1.04 divided by the square root of the number of registers. of 0.81 % (Redis, HyperLogLog).
A Count-Min sketch keeps d rows of w counters. Every event adds 1 to one counter in each row, chosen by that row’s hash, and an item’s estimate is the smallest of its d counters. Collisions only add other items’ counts, so a Count-Min sketch never undercounts; it can overcount, by an amount bounded by a small share of all events.
Heavy hitters are the items whose counts stand out, such as the top songs of a minute. To find heavy hitters, keep a short list of candidates beside a Count-Min sketch and update each candidate’s estimate as events arrive.
Two sketches, one hash
Text description of the diagram
The diagram starts with a stream of events, such as user ids, song ids or URLs. Each event is hashed to 64 bits, and the hash feeds two sketches, shown one above the other in a box labelled "Two sketches fed by the same hashes".
- HyperLogLog, which answers "how many distinct items?": the first bits of the hash pick one of m registers; the register keeps the largest rank seen, where the rank is 1 plus the number of leading zeros in the other bits; the estimate comes from all m registers, with a typical error of 1.04 divided by the square root of m.
- Count-Min, which answers "how often has each item occurred?": it has d rows of w counters, and each event adds 1 to one counter in each row; the estimate for an item is the smallest of its d counters, which is never below the true count.
Sketches also merge, which is what makes them work across servers and days: two HyperLogLogs of the same size merge by keeping the larger value of each register. Follow one day of visitors through the HyperLogLog half of the figure:
The drawing shows the whole scene; its 7 steps are listed below.
Every step as text
- Day 1. 40,000 events reach the sketch, four visits from each of 10,000 users. Nothing about the users is stored, only 1,024 small registers, all 0 at the start.
- Hash. Each user id is hashed to 64 bits that look random. The same user always gives the same bits, which is what lets repeat visits disappear later.
- Pick a register. The first 10 bits pick one of 1,024 registers, so each register hears from about 10 of the day's 10,000 users.
- Rank. The rank is 1 plus the number of zeros before the first 1 in the other 54 bits. Half of all hashes have rank 1, a quarter rank 2, and only 1 in 2^k has rank k.
- Keep the larger. A register keeps the largest rank it has seen. A user's second, third and fourth visits give the same hash and the same rank, so they change nothing, and the loop goes on with the next event.
- Estimate. The estimate combines all 1,024 registers into one number. Day 1 comes out at 9,782 for its 10,000 users, 2.2 % low, inside the typical error of 3.25 %.
- Merge. Day 2's sketch merges in by keeping the larger value of each register. The merged sketch says 16,498 for the 16,000 users of both days, and nobody who came on both days counts twice.
The program counts two days of visitors in 1,024 registers each, 768 bytes at 6 bits a register, and merges the days:
Python 3.14 · main.py
M64 = 0xFFFFFFFFFFFFFFFF
P = 10
M = 1 << P
def mix64(x: int) -> int:
x = (x + 0x9E3779B97F4A7C15) & M64
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & M64
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & M64
return x ^ (x >> 31)
def add(registers: list[int], user: int) -> None:
# First P bits: the register. Rank: 1 + leading zeros of the rest.
h = mix64(user)
rank = (64 - P) - (h & ((1 << (64 - P)) - 1)).bit_length() + 1
i = h >> (64 - P)
registers[i] = max(registers[i], rank)
def estimate(registers: list[int]) -> float:
total = 0.0
for r in registers:
total += 2.0**-r
return 0.7213 / (1 + 1.079 / M) * M * M / total
def report(label: str, registers: list[int], exact: int) -> None:
est = estimate(registers)
error = (est / exact - 1) * 100
print(f"{label}: {exact} distinct users, estimate {est:.0f} ({error:+.1f}%)")
sketches: list[list[int]] = []
everyone: set[int] = set()
for day in range(2):
registers, users = [0] * M, set()
for i in range(40_000):
user = 6_000 * day + i * 7_919 % 10_000 # 10,000 users a day, 4 visits each
add(registers, user)
users.add(user)
report(f"day {day + 1}", registers, len(users))
sketches.append(registers)
everyone |= users
report("both days merged", [max(a, b) for a, b in zip(*sketches)], len(everyone))In Python: Python's integers never overflow, so every product is masked back to 64 bits with & M64, and bit_length gives the position of the highest 1 bit directly.
Recorded with CPython 3.14.8 on macOS 26 arm64. It runs in your browser with Pyodide 314.0.7 (CPython 3.14.2). To run it yourself: python3 main.py
JavaScript Node 24 · main.mjs
const M64 = (1n << 64n) - 1n;
const P = 10;
const M = 1 << P;
function mix64(id) {
let x = (BigInt(id) + 0x9e3779b97f4a7c15n) & M64;
x = ((x ^ (x >> 30n)) * 0xbf58476d1ce4e5b9n) & M64;
x = ((x ^ (x >> 27n)) * 0x94d049bb133111ebn) & M64;
return x ^ (x >> 31n);
}
function add(registers, user) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
const h = mix64(user);
const rest = h & ((1n << BigInt(64 - P)) - 1n);
const rank = 64 - P - (rest === 0n ? 0 : rest.toString(2).length) + 1;
const i = Number(h >> BigInt(64 - P));
registers[i] = Math.max(registers[i], rank);
}
function estimate(registers) {
let total = 0;
for (const r of registers) total += 2 ** -r;
return ((0.7213 / (1 + 1.079 / M)) * M * M) / total;
}
function report(label, registers, exact) {
const est = estimate(registers);
const error = (est / exact - 1) * 100;
const sign = error >= 0 ? "+" : "";
console.log(
`${label}: ${exact} distinct users, estimate ${est.toFixed(0)} (${sign}${error.toFixed(1)}%)`,
);
}
const sketches = [];
const everyone = new Set();
for (let day = 0; day < 2; day++) {
const registers = new Array(M).fill(0);
const users = new Set();
for (let i = 0; i < 40_000; i++) {
const user = 6_000 * day + ((i * 7_919) % 10_000); // 10,000 users a day, 4 visits each
add(registers, user);
users.add(user);
}
report(`day ${day + 1}`, registers, users.size);
sketches.push(registers);
for (const user of users) everyone.add(user);
}
const merged = sketches[0].map((r, i) => Math.max(r, sketches[1][i]));
report("both days merged", merged, everyone.size);In JavaScript: A Number holds only 53 bits exactly, so the hash is a BigInt; BigInt has no leading-zero count, so the length of its binary text gives the bit length.
Recorded with Node.js 24.21.0 LTS (V8 13.6) on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0). To run it yourself: node main.mjs
Java 25 LTS · Main.java
import java.util.HashSet;
import java.util.Locale;
import java.util.Set;
public class Main {
static final int P = 10;
static final int M = 1 << P;
static long mix64(long x) {
x += 0x9E3779B97F4A7C15L;
x = (x ^ (x >>> 30)) * 0xBF58476D1CE4E5B9L;
x = (x ^ (x >>> 27)) * 0x94D049BB133111EBL;
return x ^ (x >>> 31);
}
static void add(int[] registers, int user) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
long h = mix64(user);
long rest = h & ((1L << (64 - P)) - 1);
int rank = (64 - P) - (64 - Long.numberOfLeadingZeros(rest)) + 1;
int i = (int) (h >>> (64 - P));
registers[i] = Math.max(registers[i], rank);
}
static double estimate(int[] registers) {
double total = 0.0;
for (int r : registers) {
total += Math.pow(2.0, -r);
}
return 0.7213 / (1 + 1.079 / M) * M * M / total;
}
static void report(String label, int[] registers, int exact) {
double est = estimate(registers);
double error = (est / exact - 1) * 100;
System.out.printf("%s: %d distinct users, estimate %.0f (%+.1f%%)%n", label, exact, est, error);
}
public static void main(String[] args) {
Locale.setDefault(Locale.ROOT);
int[][] sketches = new int[2][M];
Set<Integer> everyone = new HashSet<>();
for (int day = 0; day < 2; day++) {
Set<Integer> users = new HashSet<>();
for (int i = 0; i < 40_000; i++) {
int user = 6_000 * day + i * 7_919 % 10_000; // 10,000 users a day, 4 visits each
add(sketches[day], user);
users.add(user);
}
report("day " + (day + 1), sketches[day], users.size());
everyone.addAll(users);
}
int[] merged = new int[M];
for (int i = 0; i < M; i++) {
merged[i] = Math.max(sketches[0][i], sketches[1][i]);
}
report("both days merged", merged, everyone.size());
}
}In Java: Long.numberOfLeadingZeros counts the zeros of the 64-bit value, and >>> shifts in zeros where >> would copy the sign bit of the long.
Recorded with OpenJDK 25.0.4.1 LTS (Eclipse Temurin) on macOS 26 arm64. It runs in your browser with a TeaVM 0.16.0 build in QuickJS (quickjs-emscripten 0.32.0). To run it yourself: java Main.java
C++23 · main.cpp
#include <algorithm>
#include <array>
#include <bit>
#include <cmath>
#include <cstdint>
#include <format>
#include <print>
#include <string>
#include <unordered_set>
constexpr int P = 10;
constexpr int M = 1 << P;
using Sketch = std::array<int, M>;
std::uint64_t mix64(std::uint64_t x) {
x += 0x9E3779B97F4A7C15ULL;
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
return x ^ (x >> 31);
}
void add(Sketch ®isters, int user) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
const std::uint64_t h = mix64(static_cast<std::uint64_t>(user));
const std::uint64_t rest = h & ((1ULL << (64 - P)) - 1);
const int rank = (64 - P) - static_cast<int>(std::bit_width(rest)) + 1;
int &r = registers[h >> (64 - P)];
r = std::max(r, rank);
}
double estimate(const Sketch ®isters) {
double total = 0.0;
for (const int r : registers) {
total += std::ldexp(1.0, -r);
}
return 0.7213 / (1 + 1.079 / M) * M * M / total;
}
void report(const std::string &label, const Sketch ®isters,
std::size_t exact) {
const double est = estimate(registers);
const double error = (est / static_cast<double>(exact) - 1) * 100;
std::println("{}: {} distinct users, estimate {:.0f} ({:+.1f}%)", label,
exact, est, error);
}
int main() {
std::array<Sketch, 2> sketches{};
std::unordered_set<int> everyone;
for (int day = 0; day < 2; day++) {
std::unordered_set<int> users;
for (int i = 0; i < 40'000; i++) {
const int user =
6'000 * day + i * 7'919 % 10'000; // 10,000 users a day, 4 visits each
add(sketches[day], user);
users.insert(user);
}
report(std::format("day {}", day + 1), sketches[day], users.size());
everyone.insert(users.begin(), users.end());
}
Sketch merged{};
std::ranges::transform(sketches[0], sketches[1], merged.begin(),
[](int a, int b) { return std::max(a, b); });
report("both days merged", merged, everyone.size());
}In C++: std::bit_width, new in C++20, is the number of bits a value needs, and std::array keeps each sketch's 1,024 registers in one block of memory.
Recorded with Apple clang 21.0.0 (C++23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang++ -std=c++23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.cpp -o main && ./main
C# 14 · .NET 10 · app.cs
using System.Globalization;
using System.Numerics;
CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;
const int P = 10;
const int M = 1 << P;
var sketches = new int[2][];
var everyone = new HashSet<int>();
for (var day = 0; day < 2; day++)
{
sketches[day] = new int[M];
var users = new HashSet<int>();
for (var i = 0; i < 40_000; i++)
{
var user = 6_000 * day + i * 7_919 % 10_000; // 10,000 users a day, 4 visits each
Add(sketches[day], user);
users.Add(user);
}
Report($"day {day + 1}", sketches[day], users.Count);
everyone.UnionWith(users);
}
Report("both days merged", sketches[0].Zip(sketches[1], Math.Max).ToArray(), everyone.Count);
static ulong Mix64(ulong x)
{
x += 0x9E3779B97F4A7C15;
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9;
x = (x ^ (x >> 27)) * 0x94D049BB133111EB;
return x ^ (x >> 31);
}
static void Add(int[] registers, int user)
{
// First P bits: the register. Rank: 1 + leading zeros of the rest.
var h = Mix64((ulong)user);
var rest = h & ((1UL << (64 - P)) - 1);
var rank = (64 - P) - (64 - BitOperations.LeadingZeroCount(rest)) + 1;
var i = (int)(h >> (64 - P));
registers[i] = Math.Max(registers[i], rank);
}
static double Estimate(int[] registers)
{
var total = 0.0;
foreach (var r in registers)
{
total += Math.Pow(2, -r);
}
return 0.7213 / (1 + 1.079 / M) * M * M / total;
}
static void Report(string label, int[] registers, int exact)
{
var est = Estimate(registers);
var error = (est / exact - 1) * 100;
Console.WriteLine($"{label}: {exact} distinct users, estimate {est:F0} ({error:+0.0;-0.0}%)");
}In C#: BitOperations.LeadingZeroCount counts the leading zeros of a ulong, and Zip with Math.Max merges the two days' sketches register by register.
Recorded with C# 14 on .NET 10.0.12 (SDK 10.0.401) on macOS 26 arm64. It runs in your browser with the .NET runtime for WebAssembly 10.0.12. To run it yourself: dotnet run app.cs
C23 · main.c
#include <math.h>
#include <stdint.h>
#include <stdio.h>
enum { P = 10, M = 1 << P, USERS = 16000 };
static uint64_t mix64(uint64_t x) {
x += 0x9E3779B97F4A7C15u;
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9u;
x = (x ^ (x >> 27)) * 0x94D049BB133111EBu;
return x ^ (x >> 31);
}
static void add(int registers[M], int user) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
const uint64_t h = mix64((uint64_t)user);
uint64_t rest = h & ((UINT64_C(1) << (64 - P)) - 1);
int bit_length = 0;
for (; rest > 0; rest >>= 1) {
bit_length++;
}
const int rank = (64 - P) - bit_length + 1;
const int i = (int)(h >> (64 - P));
if (rank > registers[i]) {
registers[i] = rank;
}
}
static double estimate(const int registers[M]) {
double total = 0.0;
for (int i = 0; i < M; i++) {
total += ldexp(1.0, -registers[i]);
}
return 0.7213 / (1 + 1.079 / M) * M * M / total;
}
static void report(const char *label, const int registers[M], int exact) {
const double est = estimate(registers);
const double error = (est / exact - 1) * 100;
printf("%s: %d distinct users, estimate %.0f (%+.1f%%)\n", label, exact, est,
error);
}
int main(void) {
static int sketches[2][M];
static bool seen[2][USERS];
for (int day = 0; day < 2; day++) {
int distinct = 0;
for (int i = 0; i < 40000; i++) {
const int user =
6000 * day + i * 7919 % 10000; // 10,000 users a day, 4 visits each
add(sketches[day], user);
distinct += !seen[day][user];
seen[day][user] = true;
}
char label[16];
snprintf(label, sizeof label, "day %d", day + 1);
report(label, sketches[day], distinct);
}
int merged[M];
int everyone = 0;
for (int i = 0; i < M; i++) {
merged[i] =
sketches[0][i] > sketches[1][i] ? sketches[0][i] : sketches[1][i];
}
for (int u = 0; u < USERS; u++) {
everyone += seen[0][u] || seen[1][u];
}
report("both days merged", merged, everyone);
return 0;
}In C: C's standard library has no set, so a bool array of 16,000 marks the users seen each day, and a short loop finds the bit length the other languages get from a library call.
Recorded with Apple clang 21.0.0 (C23) and GCC 16.2.0 on macOS 26 arm64. It runs in your browser with Clang in WebAssembly (YoWASP) 22.0.0-git20542-10. To run it yourself: clang -std=c23 -O2 -Wall -Wextra -Werror -pedantic -fsanitize=address,undefined main.c -o main && ./main
PHP 8.5 · main.php
<?php
declare(strict_types=1);
const P = 10;
const M = 1 << P;
/** The low 64 bits of $a * $b, in 16-bit digits: an int product that overflows becomes a float. */
function mul64(int $a, int $b): int
{
[$result, $carry] = [0, 0];
for ($k = 0; $k < 4; $k++) {
$sum = $carry;
for ($i = 0; $i <= $k; $i++) {
$sum += (($a >> (16 * $i)) & 0xFFFF) * (($b >> (16 * ($k - $i))) & 0xFFFF);
}
$result |= ($sum & 0xFFFF) << (16 * $k);
$carry = $sum >> 16;
}
return $result;
}
function shr(int $x, int $n): int
{
return ($x >> $n) & (PHP_INT_MAX >> ($n - 1));
}
function mix64(int $id): int
{
$x = $id + ((0x9E3779B9 << 32) | 0x7F4A7C15);
$x = mul64($x ^ shr($x, 30), (0xBF58476D << 32) | 0x1CE4E5B9);
$x = mul64($x ^ shr($x, 27), (0x94D049BB << 32) | 0x133111EB);
return $x ^ shr($x, 31);
}
/** @param list<int> $registers */
function add(array &$registers, int $user): void
{
// First P bits: the register. Rank: 1 + leading zeros of the rest.
$h = mix64($user);
$rest = $h & ((1 << (64 - P)) - 1);
$rank = (64 - P) - ($rest === 0 ? 0 : strlen(decbin($rest))) + 1;
$i = shr($h, 64 - P);
$registers[$i] = max($registers[$i], $rank);
}
/** @param list<int> $registers */
function report(string $label, array $registers, int $exact): void
{
$total = 0.0;
foreach ($registers as $r) {
$total += 2 ** -$r;
}
$est = 0.7213 / (1 + 1.079 / M) * M * M / $total;
$error = ($est / $exact - 1) * 100;
printf("%s: %d distinct users, estimate %.0F (%+.1F%%)\n", $label, $exact, $est, $error);
}
if (PHP_INT_SIZE < 8) {
fwrite(STDERR, "This program needs 64-bit integers.\n");
exit(1);
}
[$sketches, $everyone] = [[], []];
for ($day = 0; $day < 2; $day++) {
[$registers, $users] = [array_fill(0, M, 0), []];
for ($i = 0; $i < 40_000; $i++) {
$user = 6_000 * $day + $i * 7_919 % 10_000; // 10,000 users a day, 4 visits each
add($registers, $user);
$users[$user] = true;
}
report('day ' . ($day + 1), $registers, count($users));
$sketches[] = $registers;
$everyone += $users;
}
report('both days merged', array_map(max(...), $sketches[0], $sketches[1]), count($everyone));In PHP: PHP has no unsigned 64-bit integer, so mul64 multiplies in 16-bit digits; the ids are small, so adding SplitMix64's constant cannot overflow, and decbin gives the bit length. The browser's PHP has 32-bit integers, too narrow for these hashes, so it stops there at once and its tab shows the recorded output.
Recorded with PHP 8.5.11 (CLI) on macOS 26 arm64. To run it yourself: php main.php
Rust 1.99 · main.rs
use std::collections::HashSet;
const P: u32 = 10;
const M: usize = 1 << P;
fn mix64(mut x: u64) -> u64 {
x = x.wrapping_add(0x9E37_79B9_7F4A_7C15);
x = (x ^ (x >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
x = (x ^ (x >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
x ^ (x >> 31)
}
fn add(registers: &mut [u32], user: u64) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
let h = mix64(user);
let rest = h & ((1 << (64 - P)) - 1);
let rank = (64 - P) - (64 - rest.leading_zeros()) + 1;
let i = (h >> (64 - P)) as usize;
registers[i] = registers[i].max(rank);
}
fn estimate(registers: &[u32]) -> f64 {
let total: f64 = registers.iter().map(|&r| 0.5f64.powi(r as i32)).sum();
let m = M as f64;
0.7213 / (1.0 + 1.079 / m) * m * m / total
}
fn report(label: &str, registers: &[u32], exact: usize) {
let est = estimate(registers);
let error = (est / exact as f64 - 1.0) * 100.0;
println!("{label}: {exact} distinct users, estimate {est:.0} ({error:+.1}%)");
}
fn main() {
let mut sketches = [[0u32; M]; 2];
let mut everyone = HashSet::new();
for day in 0..2 {
let mut users = HashSet::new();
for i in 0..40_000u64 {
// 10,000 users a day, 4 visits each
let user = 6_000 * day as u64 + i * 7_919 % 10_000;
add(&mut sketches[day], user);
users.insert(user);
}
report(&format!("day {}", day + 1), &sketches[day], users.len());
everyone.extend(users);
}
let merged: Vec<u32> = sketches[0]
.iter()
.zip(&sketches[1])
.map(|(a, b)| *a.max(b))
.collect();
report("both days merged", &merged, everyone.len());
}In Rust: wrapping_add and wrapping_mul make the 64-bit wrap-around explicit, where a plain + or * would stop a debug build, and leading_zeros counts on the u64 itself.
Recorded with rustc 1.99.0 (edition 2024) on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: rustc --edition 2024 -O main.rs && ./main
TypeScript 6.0 · main.ts
const M64 = (1n << 64n) - 1n;
const P = 10;
const M = 1 << P;
function mix64(id: number): bigint {
let x = (BigInt(id) + 0x9e3779b97f4a7c15n) & M64;
x = ((x ^ (x >> 30n)) * 0xbf58476d1ce4e5b9n) & M64;
x = ((x ^ (x >> 27n)) * 0x94d049bb133111ebn) & M64;
return x ^ (x >> 31n);
}
function add(registers: number[], user: number): void {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
const h = mix64(user);
const rest = h & ((1n << BigInt(64 - P)) - 1n);
const rank = 64 - P - (rest === 0n ? 0 : rest.toString(2).length) + 1;
const i = Number(h >> BigInt(64 - P));
registers[i] = Math.max(registers[i], rank);
}
function estimate(registers: number[]): number {
let total = 0;
for (const r of registers) total += 2 ** -r;
return ((0.7213 / (1 + 1.079 / M)) * M * M) / total;
}
function report(label: string, registers: number[], exact: number): void {
const est = estimate(registers);
const error = (est / exact - 1) * 100;
const sign = error >= 0 ? "+" : "";
console.log(
`${label}: ${exact} distinct users, estimate ${est.toFixed(0)} (${sign}${error.toFixed(1)}%)`,
);
}
const sketches: number[][] = [];
const everyone = new Set<number>();
for (let day = 0; day < 2; day++) {
const registers: number[] = new Array<number>(M).fill(0);
const users = new Set<number>();
for (let i = 0; i < 40_000; i++) {
const user = 6_000 * day + ((i * 7_919) % 10_000); // 10,000 users a day, 4 visits each
add(registers, user);
users.add(user);
}
report(`day ${day + 1}`, registers, users.size);
sketches.push(registers);
for (const user of users) everyone.add(user);
}
const merged = sketches[0].map((r, i) => Math.max(r, sketches[1][i]));
report("both days merged", merged, everyone.size);In TypeScript: The hash is a bigint, because a number holds only 53 bits exactly; its bit length comes from toString(2), as bigint has no leading-zero count.
Recorded with TypeScript 6.0.3 (strict), run by Node.js 24.21.0 on macOS 26 arm64. It runs in your browser with QuickJS (quickjs-emscripten 0.32.0) after Sucrase 3.35.1. To run it yourself: npx -p typescript@6.0.3 tsc --noEmit --strict main.ts && node main.ts
Go 1.27 · main.go
package main
import (
"fmt"
"math"
"math/bits"
)
const p = 10
func mix64(x uint64) uint64 {
x += 0x9E3779B97F4A7C15
x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9
x = (x ^ (x >> 27)) * 0x94D049BB133111EB
return x ^ (x >> 31)
}
func add(registers []int, user int) {
// First p bits: the register. Rank: 1 + leading zeros of the rest.
h := mix64(uint64(user))
rank := (64 - p) - bits.Len64(h&(1<<(64-p)-1)) + 1
i := h >> (64 - p)
registers[i] = max(registers[i], rank)
}
func estimate(registers []int) float64 {
total := 0.0
for _, r := range registers {
total += math.Ldexp(1, -r)
}
m := float64(len(registers))
return 0.7213 / (1 + 1.079/m) * m * m / total
}
func report(label string, registers []int, exact int) {
est := estimate(registers)
errPct := (est/float64(exact) - 1) * 100
fmt.Printf("%s: %d distinct users, estimate %.0f (%+.1f%%)\n", label, exact, est, errPct)
}
func main() {
var sketches [2][]int
everyone := map[int]bool{}
for day := range 2 {
sketches[day] = make([]int, 1<<p)
users := map[int]bool{}
for i := range 40_000 {
user := 6_000*day + i*7_919%10_000 // 10,000 users a day, 4 visits each
add(sketches[day], user)
users[user] = true
everyone[user] = true
}
report(fmt.Sprintf("day %d", day+1), sketches[day], len(users))
}
merged := make([]int, 1<<p)
for i := range merged {
merged[i] = max(sketches[0][i], sketches[1][i])
}
report("both days merged", merged, len(everyone))
}In Go: bits.Len64 is the bit length. The estimate reads m from len(registers), because Go works out expressions of constants exactly, which would round differently from the other languages.
Recorded with Go 1.27.1 on macOS 26 arm64. It runs in your browser with the Go compiler in WebAssembly 1.27.1. To run it yourself: go run main.go
Swift 6.4 · main.swift
let p = 10
let m = 1 << p
func mix64(_ id: Int) -> UInt64 {
var x = UInt64(id) &+ 0x9E37_79B9_7F4A_7C15
x = (x ^ (x >> 30)) &* 0xBF58_476D_1CE4_E5B9
x = (x ^ (x >> 27)) &* 0x94D0_49BB_1331_11EB
return x ^ (x >> 31)
}
func add(_ registers: inout [Int], _ user: Int) {
// First p bits: the register. Rank: 1 + leading zeros of the rest.
let h = mix64(user)
let rest = h & ((1 << UInt64(64 - p)) - 1)
let rank = (64 - p) - (64 - rest.leadingZeroBitCount) + 1
let i = Int(h >> UInt64(64 - p))
registers[i] = max(registers[i], rank)
}
func estimate(_ registers: [Int]) -> Double {
var total = 0.0
for r in registers { total += Double(sign: .plus, exponent: -r, significand: 1) }
let size = Double(m)
return 0.7213 / (1 + 1.079 / size) * size * size / total
}
func report(_ label: String, _ registers: [Int], _ exact: Int) {
let est = estimate(registers)
let tenths = Int(((est / Double(exact) - 1) * 1000).rounded())
let error = "\(tenths < 0 ? "-" : "+")\(abs(tenths) / 10).\(abs(tenths) % 10)"
print("\(label): \(exact) distinct users, estimate \(Int(est.rounded())) (\(error)%)")
}
var sketches: [[Int]] = []
var everyone = Set<Int>()
for day in 0..<2 {
var registers = [Int](repeating: 0, count: m)
var users = Set<Int>()
for i in 0..<40_000 {
let user = 6_000 * day + i * 7_919 % 10_000 // 10,000 users a day, 4 visits each
add(®isters, user)
users.insert(user)
}
report("day \(day + 1)", registers, users.count)
sketches.append(registers)
everyone.formUnion(users)
}
report("both days merged", zip(sketches[0], sketches[1]).map { max($0, $1) }, everyone.count)In Swift: &+ and &* are the wrapping operators, where plain + and * would stop the program on overflow; without Foundation, the one decimal of the error is rounded by hand.
Recorded with Apple Swift 6.4 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: swiftc -O main.swift -o main && ./main
Ruby 4.0 · main.rb
# frozen_string_literal: true
M64 = 0xFFFFFFFFFFFFFFFF
P = 10
M = 1 << P
def mix64(id)
x = (id + 0x9E3779B97F4A7C15) & M64
x = ((x ^ (x >> 30)) * 0xBF58476D1CE4E5B9) & M64
x = ((x ^ (x >> 27)) * 0x94D049BB133111EB) & M64
x ^ (x >> 31)
end
def add(registers, user)
# First P bits: the register. Rank: 1 + leading zeros of the rest.
h = mix64(user)
rank = 64 - P - (h & ((1 << (64 - P)) - 1)).bit_length + 1
i = h >> (64 - P)
registers[i] = [registers[i], rank].max
end
def estimate(registers)
total = 0.0
registers.each { |r| total += 2.0**-r }
0.7213 / (1 + (1.079 / M)) * M * M / total
end
def report(label, registers, exact)
est = estimate(registers)
error = ((est / exact) - 1) * 100
puts format('%<label>s: %<exact>d distinct users, estimate %<est>.0f (%<error>+.1f%%)',
label:, exact:, est:, error:)
end
sketches = []
everyone = Set.new
2.times do |day|
registers = Array.new(M, 0)
users = Set.new
40_000.times do |i|
user = (6_000 * day) + (i * 7_919 % 10_000) # 10,000 users a day, 4 visits each
add(registers, user)
users << user
end
report("day #{day + 1}", registers, users.size)
sketches << registers
everyone.merge(users)
end
report('both days merged', sketches[0].zip(sketches[1]).map(&:max), everyone.size)In Ruby: Ruby's integers grow without limit, so every product is masked back to 64 bits, and Integer#bit_length gives the bit length; Set needs no require since Ruby 3.2.
Recorded with CRuby 4.0.7 on macOS 26 arm64. It runs in your browser with ruby.wasm 2.10.1 (Ruby 4.0.0). To run it yourself: ruby main.rb
Kotlin 2.4 · Main.kt
import kotlin.math.abs
import kotlin.math.roundToInt
import kotlin.math.roundToLong
const val P = 10
const val M = 1 shl P
fun mix64(id: Int): ULong {
var x = id.toULong() + 0x9E3779B97F4A7C15uL
x = (x xor (x shr 30)) * 0xBF58476D1CE4E5B9uL
x = (x xor (x shr 27)) * 0x94D049BB133111EBuL
return x xor (x shr 31)
}
fun add(
registers: IntArray,
user: Int,
) {
// First P bits: the register. Rank: 1 + leading zeros of the rest.
val h = mix64(user)
val rest = h and ((1uL shl (64 - P)) - 1uL)
val rank = (64 - P) - (64 - rest.countLeadingZeroBits()) + 1
val i = (h shr (64 - P)).toInt()
registers[i] = maxOf(registers[i], rank)
}
fun estimate(registers: IntArray): Double {
var total = 0.0
for (r in registers) total += 1.0 / (1L shl r)
return 0.7213 / (1 + 1.079 / M) * M * M / total
}
fun report(
label: String,
registers: IntArray,
exact: Int,
) {
val est = estimate(registers)
val tenths = ((est / exact - 1) * 1000).roundToInt()
val error = (if (tenths < 0) "-" else "+") + "${abs(tenths) / 10}.${abs(tenths) % 10}"
println("$label: $exact distinct users, estimate ${est.roundToLong()} ($error%)")
}
fun main() {
val sketches = List(2) { IntArray(M) }
val everyone = mutableSetOf<Int>()
for (day in 0 until 2) {
val users = mutableSetOf<Int>()
for (i in 0 until 40_000) {
val user = 6_000 * day + i * 7_919 % 10_000 // 10,000 users a day, 4 visits each
add(sketches[day], user)
users += user
}
report("day ${day + 1}", sketches[day], users.size)
everyone += users
}
val merged = IntArray(M) { maxOf(sketches[0][it], sketches[1][it]) }
report("both days merged", merged, everyone.size)
}In Kotlin: ULong arithmetic wraps around and countLeadingZeroBits counts on the ULong itself; String.format exists only on the JVM, so the error is rounded to tenths by hand.
Recorded with Kotlin 2.4.20 on Java 25.0.4.1 on macOS 26 arm64. It runs in your browser with a WebAssembly build on the WASI runner (browser_wasi_shim 0.4.2). To run it yourself: kotlinc Main.kt -include-runtime -d main.jar && java -jar main.jar
Dart 3.13 · main.dart
import 'dart:math';
const p = 10;
const m = 1 << p;
int mix64(int id) {
var x = id + 0x9E3779B97F4A7C15;
x = (x ^ (x >>> 30)) * 0xBF58476D1CE4E5B9;
x = (x ^ (x >>> 27)) * 0x94D049BB133111EB;
return x ^ (x >>> 31);
}
void add(List<int> registers, int user) {
// First p bits: the register. Rank: 1 + leading zeros of the rest.
final h = mix64(user);
final rank = (64 - p) - (h & ((1 << (64 - p)) - 1)).bitLength + 1;
final i = h >>> (64 - p);
registers[i] = max(registers[i], rank);
}
double estimate(List<int> registers) {
var total = 0.0;
for (final r in registers) {
total += 1 / (1 << r);
}
return 0.7213 / (1 + 1.079 / m) * m * m / total;
}
void report(String label, List<int> registers, int exact) {
final est = estimate(registers);
final error = (est / exact - 1) * 100;
final sign = error >= 0 ? '+' : '';
print(
'$label: $exact distinct users, estimate ${est.toStringAsFixed(0)} '
'($sign${error.toStringAsFixed(1)}%)',
);
}
void main() {
final sketches = <List<int>>[];
final everyone = <int>{};
for (var day = 0; day < 2; day++) {
final registers = List.filled(m, 0);
final users = <int>{};
for (var i = 0; i < 40000; i++) {
final user =
6000 * day + i * 7919 % 10000; // 10,000 users a day, 4 visits each
add(registers, user);
users.add(user);
}
report('day ${day + 1}', registers, users.length);
sketches.add(registers);
everyone.addAll(users);
}
final merged = [
for (var i = 0; i < m; i++) max(sketches[0][i], sketches[1][i]),
];
report('both days merged', merged, everyone.length);
}In Dart: Dart's int has 64 bits on the VM and in WebAssembly and its products wrap around; bitLength gives the number of bits, and >>> shifts in zeros.
Recorded with Dart 3.13.5 on macOS 26 arm64. It runs in your browser with a WebAssembly build by dart2wasm 3.13.5. To run it yourself: dart run main.dart
What every language printed
day 1: 10000 distinct users, estimate 9782 (-2.2%) day 2: 10000 distinct users, estimate 10347 (+3.5%) both days merged: 16000 distinct users, estimate 16498 (+3.1%)
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. Runs on this device: a JavaScript build of this program (about 66 KB), made when the page was built. The first run also downloads the JavaScript runner (about 0.6 MB), which is kept for the next runs. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 152 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a .NET build of this program (about 3 KB), made when the page was built. The first run also downloads .NET (about 3.6 MB), which is kept for the next runs. Edit runs your changes in the browser: the first edited run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads .NET (about 8.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 9 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device, in your browser. The first run downloads the C and C++ compiler (about 29.1 MB), which is kept for the next runs. It is best on a computer. Runs on this device: a WebAssembly build of this program (about 39 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads the JavaScript runner (about 0.9 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 717 KB), made when the page was built. Edit runs your changes in the browser: the first edited run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device, in your browser. The first run downloads the Go compiler (about 18.7 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 1.7 MB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device, in your browser. The first run downloads Ruby (about 10.2 MB), which is kept for the next runs. Runs on this device: a WebAssembly build of this program (about 190 KB), made when the page was built. To change the code, copy it and run it with the command below. Runs on this device: a WebAssembly build of this program (about 12 KB), made when the page was built. To change the code, copy it and run it with the command below.Your run, in this browser
Each day has 10,000 distinct users among 40,000 events, and the estimates are 2.2 % below and 3.5 % above the exact counts: the first inside the typical error of 3.25 % for 1,024 registers, the second just beyond it. The merged sketch says 16,498 for 16,000 distinct users over both days, while an exact set of their 8-byte ids takes 128,000 bytes. Two relatives matter in practice: HyperLogLog++ adds a 64-bit hash, a correction for small counts and a compact encoding for small sketches, and a t-digest summarises numbers so that percentiles such as p99 (99th percentile): The latency within which 99 % of requests finish, so the slowest 1 % take longer. Tail latency is read from such high percentiles, because an average hides the slowest requests. More in “Latency, throughput and percentiles” can be read from it. Next, write the register-by-register merge yourself.
Exercise · Easy · Python
Merge two HyperLogLog sketches
hll.py holds a HyperLogLog with 1,024 registers: add records an item and estimate returns the number of distinct items seen. Write merge(a, b), which returns a new sketch that counts every item of both sketches, as if all their items had been added to one sketch.
- Each register of the result is the larger of the two registers at the same position.
- Sketches with different numbers of registers cannot be merged: raise
ValueError. - Do not change
aorb.
Merging is what lets each server, or each day, keep its own sketch: the tests check that merging Monday's and Tuesday's sketches gives exactly the sketch of both days' visitors, with the visitors of both days counted once.
Starter code · hll.py
import math
M64 = 0xFFFFFFFFFFFFFFFF
P = 10
M = 1 << P # 1,024 registers
def hash64(text):
h = 0xCBF29CE484222325
for byte in text.encode():
h = ((h ^ byte) * 0x100000001B3) & M64
h = ((h ^ (h >> 30)) * 0xBF58476D1CE4E5B9) & M64
h = ((h ^ (h >> 27)) * 0x94D049BB133111EB) & M64
return h ^ (h >> 31)
def new_sketch():
return [0] * M
def add(registers, item):
"""Record an item: its register keeps the largest rank seen."""
h = hash64(item)
rest = h & ((1 << (64 - P)) - 1)
rank = (64 - P) - rest.bit_length() + 1
i = h >> (64 - P)
registers[i] = max(registers[i], rank)
def estimate(registers):
m = len(registers)
raw = 0.7213 / (1 + 1.079 / m) * m * m / sum(2.0 ** -r for r in registers)
zeros = registers.count(0)
return m * math.log(m / zeros) if raw <= 2.5 * m and zeros else raw
def merge(a, b):
"""A new sketch that counts every item of both: the larger value of each register. Raise ValueError if the
sketches have different numbers of registers. Do not change a or b."""
# Replace this line with your code.
return []The sample tests · test_hll.py
from hll import add, estimate, merge, new_sketch
def sketch_of(items):
s = new_sketch()
for item in items:
add(s, item)
return s
def test_register_by_register():
"""each register keeps the larger of the two values"""
assert merge([0, 3, 1, 0], [2, 1, 1, 0]) == [2, 3, 1, 0]
def test_inputs_are_not_changed():
"""merging returns a new sketch"""
a, b = [0, 3, 1, 0], [2, 1, 1, 0]
merge(a, b)
assert a == [0, 3, 1, 0] and b == [2, 1, 1, 0]
def test_union_of_two_days():
"""the merge of two days' sketches is exactly the sketch of all their items"""
monday = [f"member:{i}" for i in range(0, 6_000)]
tuesday = [f"member:{i}" for i in range(4_000, 9_000)]
assert merge(sketch_of(monday), sketch_of(tuesday)) == sketch_of(monday + tuesday)
def test_duplicates_do_not_count_twice():
"""merging a sketch with itself changes nothing, so repeated users are not counted twice"""
s = sketch_of(f"member:{i}" for i in range(3_000))
assert merge(s, s) == s
assert round(estimate(merge(s, s))) == round(estimate(s))
def test_sizes_must_match():
"""sketches with different numbers of registers cannot be merged"""
try:
merge([0] * 1024, [0] * 512)
except ValueError:
return
raise AssertionError("merge accepted sketches of 1,024 and 512 registers")
def test_merged_estimate():
"""two overlapping groups of 10,000 members: the merged sketch estimates the 15,000 people in either group"""
a = sketch_of(f"member:{i}" for i in range(10_000))
b = sketch_of(f"member:{i}" for i in range(5_000, 15_000))
assert [round(estimate(a)), round(estimate(b))] == [10207, 9655]
assert round(estimate(merge(a, b))) == 14962A hint
Check len(a) != len(b) first and raise ValueError(...). Then build the result with a list comprehension over zip(a, b) that keeps the larger value of each pair.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide): nothing is sent to mysmartcopilot.com. The first run downloads Python (about 13.5 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Checkpoint
Check: What HyperLogLog and Count-Min keep
HyperLogLog’s error at four sizes, measured against its formula Pro: opens with a Pro, Premium or Ultimate pass
In this part:
- Merging sketches across machines and time windows
- Count-Min: the error bound, with numbers
- Heavy hitters: a Count-Min sketch and a short candidate list
- Where an approximate answer is the wrong answer
- Practise: check yourself
- Interview questions
- Product wants the number of unique users per page per day, per week and per month for 1 million pages. Exact sets would cost too much. Design it with HyperLogLog and give the memory and the error.
- Show the 100 most-played songs of every minute from 2 million plays a second spread over 50 servers. Design the counting, and state the error you are willing to accept.
- A teammate proposes counting API calls per customer with a Count-Min sketch, because exact counters for 2 million customers seem expensive. The counts will be used for billing. What do you say, and what would you build instead?
- Key takeaways
3 diagrams · 2 runnable examples (Python) · 3 interview answers · about 41 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Terms in this lesson
- Count-Min sketch
- A sketch of d rows of w counters: every event adds 1 to one counter in each row, and an item's estimate is the smallest of its counters, which is never below its true count.
- heavy hitter
- An item that makes up a large share of a stream, such as one of the most played songs of a minute, found with a Count-Min sketch and a short list of candidates.
- register (HyperLogLog)
- One of the m small counters of a HyperLogLog. The first bits of an item's hash choose the register, and it keeps the largest rank, one plus the leading zeros, seen among the rest of the bits.
- sketch (data summary)
- A small, fixed-size summary of a stream that answers one question, such as how many distinct items it held or how often an item occurred, with a stated error instead of an exact answer.
- standard error (of an estimate)
- The typical size of an estimate's error over many runs, its root mean square. For HyperLogLog it is about 1.04 divided by the square root of the number of registers.
- t-digest
- A summary of a stream of numbers from which percentiles such as the p99 can be read without keeping every value.
References
- HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (Flajolet, Fusy, Gandouet and Meunier) (Discrete Mathematics and Theoretical Computer Science, AofA proceedings (INRIA copy))
- HyperLogLog in Practice: Algorithmic Engineering of a State of the Art Cardinality Estimation Algorithm (Google Research (EDBT))
- An improved data stream summary: the count-min sketch and its applications (Cormode and Muthukrishnan) (Journal of Algorithms (Elsevier))
- Redis documentation: HyperLogLog (Redis)
- Redis documentation: Count-min sketch (Redis)
- Redis documentation: Top-K (Redis)
- Redis documentation: t-digest (Redis)
- Computing Extremely Accurate Quantiles Using t-Digests (Dunning and Ertl) (arXiv)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress