Skip to content

HyperLogLog (HLL)

1. What is it? (2-3 lines)

HyperLogLog (HLL) is a probabilistic cardinality estimation algorithm used to count unique elements (distinct values) in massive datasets using a tiny, fixed memory footprint (~12KB in Redis for billions of items) with a standard error of ~0.81%.

2. Why does it exist?

Counting unique items (SELECT COUNT(DISTINCT user_id)) across billions of events requires storing every unique value in a Hash Set or Bitmap, consuming gigabytes/terabytes of memory. HyperLogLog uses probabilistic mathematics to estimate unique counts using a constant 12KB memory array regardless of dataset size.

3. Where is it used?

  • Redis: PFADD, PFCOUNT, PFMERGE commands (used for Daily Active User - DAU metrics).
  • Data Warehouses & Search: Snowflake (HLL), Google BigQuery (APPROX_COUNT_DISTINCT), AWS Athena / Presto, Elasticsearch.
  • Analytics Platforms: Google Analytics, Mixpanel, Amplitude for unique visitor counting.

4. How does it work? (simple flow)

  1. Mathematical Intuition (Coin Flips): If you flip a coin and get 5 consecutive heads (\(00001\)), you estimate you flipped roughly \(2^5 = 32\) times. HLL observes the number of leading zeros in hashed binary values.
  2. Hash & Leading Zeros:
  3. Hash incoming value to a uniform 64-bit binary integer.
  4. Use the first \(p\) bits to select a register (bucket index \(m = 2^p\)).
  5. Count the number of leading zeros \(\rho\) in the remaining bits.
  6. Register Update: Update register M[bucket] = max(M[bucket], rho).
  7. Harmonic Mean Estimation: HLL computes the Harmonic Mean across all \(m\) registers to normalize outliers and estimates total unique cardinality \(E = \alpha_m m^2 \cdot \left( \sum_{j=1}^m 2^{-M[j]} \right)^{-1}\).

5. Advantages

  • Unmatched memory efficiency: Counts billions of unique items in a fixed 12KB register memory.
  • Standard error is small and mathematically bounded (\(\approx 1.04 / \sqrt{m} \approx 0.81\%\) for 16,384 registers).
  • Supports fast parallel merging across nodes (PFMERGE) for multi-region aggregated DAU metrics.

6. Limitations

  • Approximate Estimate Only: Cannot return exact counts; always subject to ~0.81% statistical error.
  • No Item Extraction: Cannot retrieve or list the actual unique elements stored in the HLL.

7. Common interview questions (10)

  1. How does HyperLogLog count 1 billion unique users in 12KB of memory in Redis?
  2. What is the mathematical intuition behind counting leading zeros in binary hashes?
  3. Why does HyperLogLog use the Harmonic Mean instead of Geometric or Arithmetic Mean across registers?
  4. How does PFMERGE combine HyperLogLog registers from 30 daily keys into a single Monthly Active User (MAU) metric?
  5. How does HyperLogLog compare to Bitmaps (SETBIT) in Redis for DAU tracking?
  6. At what dataset scale does a Bitmap become more memory-expensive than a 12KB HyperLogLog?
  7. What is the standard error formula for HyperLogLog with \(m\) registers?
  8. How does Presto / BigQuery APPROX_COUNT_DISTINCT speed up SQL analytics queries?
  9. Can you remove an item from a HyperLogLog? Why or why not?
  10. How does LogLog evolve into HyperLogLog and HyperLogLog++?

8. Common misconceptions

  • Misconception: HyperLogLog stores user IDs. Fact: HLL stores only max leading zero counts in an array of tiny byte registers; raw user IDs are never stored.
  • Misconception: HLL memory grows as unique user count increases. Fact: Redis HLL memory is strictly capped at a maximum of 12KB regardless of whether you count 100 users or 10 billion users.

10. 30-second cheat sheet

  • Purpose: Estimate Unique Cardinality (COUNT(DISTINCT)) in \(O(1)\) constant memory (~12KB).
  • Core Math: Hashes item \(\to\) Counts leading zeros \(\to\) Applies Harmonic Mean across registers.
  • Accuracy: Fixed ~0.81% error rate for 16,384 registers (\(m=2^{14}\)).
  • Redis Commands: PFADD key user123, PFCOUNT key, PFMERGE mau_key dau_day1 dau_day2.