Count Billions in 12 Kilobytes

A video streaming site with 500 million viewers a day needs to know: how many unique visitors did we reach this month? The obvious approach stores every visitor ID in a set. A month of data = 2.5 billion unique IDs × 8 bytes each = 20 gigabytes. One line of a company dashboard now occupies a server’s entire memory budget.

The breakthrough: trade 1% accuracy for a fixed 12 KB footprint, regardless of cardinality.

The Naive Approach: Why Exact Counting Dies

Storing every unique visitor ID works perfectly until scale hits:

def count_unique(visitor_ids):
    return len(set(visitor_ids))  # O(1) lookup, O(N) space

For 1 billion visitors over a month:

• 8 bytes per ID (typical UUID or long integer)
• 1 billion × 8 = 8 gigabytes of RAM
• Growth is linear with cardinality; no escape

This approach breaks in three ways: memory exhaustion, distributed merge failure (combining counts across data centers means re-storing all IDs), and query latency (set operations are CPU-friendly but memory I/O eventually saturates). Web-scale companies hit this wall within weeks of launch.

HyperLogLog: The Probabilistic Breakthrough

HyperLogLog (Flajolet et al., 2007) inverts the problem. Instead of storing IDs, it stores only the distribution of a statistical property: the leading-zero count in hashed values.

The key insight: if a hash function produces a random bit string, observing N leading zeros is extraordinarily rare (probability 1 in 2^N). Seeing many distinct items with leading zeros implies you’ve hashed billions of times.

Think of it like sampling: if you flip a coin and get heads 10 times in a row, you probably flipped it far more than 10 times total. Similarly, a hash with 20 leading zeros implies the algorithm has seen roughly 2^20 distinct items.

This trade-off is brutal in its efficiency:

How It Works: The Mechanism

HyperLogLog operates in four steps:

1. Hash every value

   Apply a cryptographic hash (SHA-1, MD5) to each incoming item. For a visitor ID like user_7429814, compute its binary hash.

2. Extract leading-zero count

   Count the number of leading zero bits in the hash output. For example:

   • Hash 0x7c2a... in binary = 0111110... → 2 leading zeros
   • Hash 0xc8f9... in binary = 1100... → 0 leading zeros
   • Hash 0x002e... in binary = 00000000... → 8 leading zeros

   Leading zeros are rare: roughly 1 in 2^k values have k leading zeros.

3. Update register buckets

   Use the first 14 bits of the hash to select one of 16,384 registers (14 KB total). Update that register with the maximum leading-zero count seen so far for its bucket. This step is critical: tracking the maximum across billions of hashes requires only a single byte per register.

4. Calculate the harmonic mean

   The cardinality estimate is:

   E = α × (2^14)^2 / (sum of 2^(-register_i))

   where α ≈ 0.7213 (a calibration constant) and register_i is the stored leading-zero count for bucket i. The harmonic mean formula captures the probabilistic structure of the algorithm—it yields an unbiased estimate with about ±1% error.

Step by step: how the leading-zeros trick becomes a cardinality counter.

Memory Efficiency: The Numbers

The fixed footprint is the algorithm’s superpower:

• 16,384 registers × 1 byte per register = 16 KB (for the counter)
• Auxiliary data (calibration constants, merge buffers) ≈ 1–2 KB
• Total ≈ 12–16 KB per HyperLogLog instance

Compare to exact cardinality:

• 1 million unique items: 8 MB (set) vs. 12 KB (HyperLogLog) = ~650× smaller
• 1 billion unique items: 8 GB (set) vs. 12 KB (HyperLogLog) = ~650,000× smaller

Memory doesn’t grow. Ever. You can count the entire internet’s daily unique visitors and pay only 12 KB, accepting 1% error.

Merging and Distributed Counting

One counter becomes many. Imagine you run analytics across 100 regional servers, each tracking visitor counts locally:

# Each server maintains its own HyperLogLog
server_1_hll = HyperLogLog()
server_2_hll = HyperLogLog()
server_100_hll = HyperLogLog()

# Merge: take element-wise maximum of registers
global_hll = merge(server_1_hll, ..., server_100_hll)
# Merge cost: O(1) per bucket

Merging two HyperLogLog instances is trivial: compare each of the 16,384 register pairs and keep the maximum. The resulting HyperLogLog estimates the union cardinality with the same ~1% error. This is impossible with exact-count sets (you’d have to rehash all items across all servers).

This design is why Redis and streaming platforms use HyperLogLog for global unique-user tracking—it scales horizontally with negligible overhead.

Trade-Offs: When NOT to Use HyperLogLog

HyperLogLog excels at scale but breaks down in three scenarios:

Real-World Deployments

Redis: The PFADD and PFCOUNT commands implement HyperLogLog. Twitter uses it for tracking daily active users; Stripe uses it for fraud-ring detection (unique card fingerprints across millions of transactions).

Google Analytics: Uniqueness estimates in real-time dashboards rely on HyperLogLog’s speed and memory efficiency. For 2 billion daily sessions, storing exact counts would require petabyte-scale infrastructure.

Bloom Filters + HyperLogLog: Combine the two for approximate set membership + cardinality. A Bloom filter answers “is this item in the set?” (with false positives); HyperLogLog answers “how many unique items have we seen?” Together they enable space-efficient streaming deduplication.

The Deeper Math (For the Curious)

The algorithm’s error bound comes from the standard error of the harmonic-mean estimator:

Standard Error ≈ 1.04 / sqrt(m)

where m is the number of registers (16,384 in standard HyperLogLog). This gives a typical error of:

1.04 / sqrt(16384) ≈ 0.0081 ≈ 0.81%

By adding a bias-correction term for small and large cardinalities, practical implementations achieve ±1% error across the full range (1 to 2^64 unique items). The trade-off is proven: no way to get this compression without accepting probabilistic error.

Takeaway

HyperLogLog solves cardinality estimation by treating it as a statistical inference problem rather than an enumeration problem. Instead of storing data, it stores a fingerprint of the leading-zero distribution—a distribution that encodes cardinality probabilistically. The result: a fixed 12 KB counter that scales from millions to billions of unique items with 1% error and mergeable distributed instances.

For any system tracking uniqueness at scale, HyperLogLog is the answer to “how do you avoid gigabytes of storage?”