Probabilistic Data Structures: HyperLogLog & Count-Min Sketch

1. The Problem & Why It Matters

In modern web applications, distributed systems, and real-time streaming engines, two questions arise constantly:

1. Cardinality Estimation (Count-Distinct): “How many unique daily active users (DAUs) visited our site today?”
2. Frequency Estimation (Heavy Hitters): “Which IP addresses are making the most API requests right now to detect DDoS attacks?”

The naive approach stores every seen identifier in a Hash Set or Hash Map:

• Tracking 100 million unique 64-bit user IDs in a hash set requires: $$10^8\times (8\text{ bytes key}+16\text{ bytes pointer overhead})\approx 2.4\text{ GB RAM}$$
• If you need to compute distinct users across 1,000 dimensions (per country, per device type, per campaign), memory balloons into terabytes of RAM.
• Distributed sets cannot be unioned without massive network bandwidth transfers.

When an approximate answer with a small, mathematically bounded error margin (e.g. $\pm 1\%$) is acceptable, Probabilistic Data Structures provide near-miraculous efficiency:

• HyperLogLog (HLL) estimates billions of unique elements with 0.81% standard error using only 12 KB of memory.
• Count-Min Sketch (CMS) counts frequencies of billions of streaming events in fixed sub-megabyte memory with strict mathematical error bounds.

2. Intuitive Mental Model

The HyperLogLog Coin-Flip Intuition

Imagine a person flips a fair coin repeatedly and tells you: “My longest run of consecutive heads was 10 heads in a row.”

• Probability of seeing 10 heads in a single attempt: $$P(\text{10 heads})={\left(\frac{1}{2}\right)}^{10}=\frac{1}{1024}$$
• You can deduce with high probability that this person flipped coins roughly $1,000$ times. If someone tells you their longest run was 30 heads, they must have flipped coins roughly $2^{30}\approx 1\text{ billion}$ times!
• HyperLogLog applies this principle to uniform 64-bit hashes: the number of leading zeros in the hash represents consecutive coin flips.

The Count-Min Sketch Room Allocation Intuition

Imagine counting attendees wearing different colored shirts in a stadium with 5 doors. Each attendee picks 3 random rooms based on their name. If a room has 15 people in it, you know there cannot possibly be more than 15 people wearing that specific shirt. By taking the minimum count across all 3 rooms, you isolate the true count from random crowd overlaps.

SYSTEM ARCHITECTURE BLUEPRINTDATA STRUCTURES

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 3

1. hash64(element) → 64-bit Binary String & m = 2^p Registers (M_0 to M_m-1)

Establishes the ingress and structural boundary across hash64(element) → 64-bit Binary String & m = 2^p Registers (M_0 to M_m-1): [0110] [0000 0001 1011 0100 ... 1001]; p=4 bits: Register Index (Bucket 6) | 60 bits: Leading Zeros Count ρ = 7.

Architectural Invariant: p=4 bits: Register Index (Bucket 6) | 60 bits: Leading Zeros Count ρ = 7.

ARCHITECTURAL FLOW · STEP 2 OF 3

2. Harmonic Mean Raw Estimate Formula & Mathematical Error Guarantees

Coordinates core data-plane execution and state transitions through Harmonic Mean Raw Estimate Formula & Mathematical Error Guarantees: E = &#945;_m * m^2 * [ &#931; (2^(-M[j])) ]^(-1); Standard error &#963; &#8776; 1.04 / &#8730;m; For m = 16,384 registers (p=14): Memory = 12 KB in Redis! Estimates billions of unique items with < 0.81% error.

Architectural Invariant: Guarantees: true_count &#8804; estimate &#8804; true_count + &#949; * N.

ARCHITECTURAL FLOW · STEP 3 OF 3

3. 18 & h3(x)

Enforces durability, state convergence, and output verification across 18 & h3(x): Count(x) = min(14, 18, 11) = 11.

Architectural Invariant: Count(x) = min(14, 18, 11) = 11.

3. Architectural Mechanisms & Concrete Topologies

3.1 HyperLogLog (HLL) Architecture

HyperLogLog partitions elements into $m=2^p$ registers:

1. Hash input element $x$ with a uniform 64-bit hash function: $h(x)$.
2. Use the first $p$ bits as the register index: $j=h(x{)}_{[\mathrm{0..}p-1]}$.
3. Count the number of leading zeros in the remaining $64-p$ bits, plus 1: $\rho (w)$.
4. Update register $M[j]$: $$M[j]=\max (M[j],\rho (w))$$

3.2 Count-Min Sketch (CMS) Architecture

A 2D array of counters of depth $d$ (rows) and width $w$ (columns), with $d$ independent pairwise hash functions $\{h_1,h_2,\dots ,h_d\}$:

• Update($x,c$): For each row $i\in [\mathrm{1..}d]$: $$\text{Table}[i,h_i(x)]\leftarrow \text{Table}[i,h_i(x)]+c$$
• Query($x$): Return the minimum value: $${\hat{a}}_x=\underset{1\le i\le d}{\min }\text{Table}[i,h_i(x)]$$

4. Formal Mathematical Derivations

4.1 HyperLogLog Harmonic Mean & Standard Error

The raw cardinality estimator $E$ uses the harmonic mean of $2^{M[j]}$ across all $m$ registers:

where ${\alpha }_m$ is a bias-correction constant: $${\alpha }_m={\left(m{\int }_0^{\infty }{\left({\log }_2\left(\frac{2+u}{1+u}\right)\right)}^{m}du\right)}^{-1}$$ For $m\ge 128$: $${\alpha }_m\approx \frac{0.7213}{1+\frac{1.079}{m}}$$

Theoretical Standard Error: $$\sigma =\frac{1.04}{\sqrt{m}}=\frac{1.04}{\sqrt{2^p}}$$

For $p=14$ ($m=2^{14}=16,384$ registers, as used in Redis): $$\sigma \approx \frac{1.04}{\sqrt{16,384}}=\frac{1.04}{128}=0.008125(0.8125\%)$$ With a 64-bit hash and $p=14$ prefix bits, the remaining suffix has $64-14=50$ bits, so $\rho (w)\in \{1,2,\dots ,51\}$ (plus 0 for an empty register $=52$ states), requiring $\lceil {\log }_2(52)\rceil =6\text{ bits}$ per register: $$\text{Register Memory}=16,384\times 6\text{ bits}=98,304\text{ bits}=12,288\text{ bytes}=12\text{ KiB}$$ (Redis prepends a 16-byte HYLL header, bringing a dense Redis HyperLogLog object to exactly $12,304\text{ bytes}$.)

4.2 Count-Min Sketch Error Bounds

Assume a non-negative stream (cash-register / strict turnstile model where every update satisfies $c\ge 0$, and total stream $L_1$ mass is $N={\sum }_i{a}_i$) and $d$ pairwise-independent hash functions. Given additive error factor $\epsilon$ and failure probability $\delta$, we dimension the matrix:

The Guarantees (derived via Markov’s inequality on per-row expected collision noise $\mathbb{E}[{\text{noise}}_i]\le \frac{N-a_x}{w}\le \frac{\epsilon N}{e}$, so $P({\text{noise}}_i>\epsilon N)<\frac{1}{e}$, and across $d$ independent rows $P({\min }_i{\text{noise}}_i>\epsilon N)<e^{-d}\le \delta$):

1. One-Sided Lower Bound: ${\hat{a}}_x\ge a_x$ (never underestimates when all updates $c\ge 0$).
2. Probabilistic Upper Bound: With probability at least $1-\delta$: $${\hat{a}}_x\le a_x+\epsilon \cdot N$$

Worked Sizing Example: For $\epsilon =0.001$ (additive error $\le 0.1\%$ of total stream events $N$) and $\delta =0.001$ ($99.9\%$ confidence):

• $w=\lceil 2.71828/0.001\rceil =2,719$ columns; $d=\lceil \ln (1000)\rceil =7$ rows.
• Using 32-bit (4-byte) unsigned counters: $2,719\times 7\times 4\text{ bytes}=76,132\text{ bytes}\approx 74.3\text{ KiB}$—fixed memory whether $N$ is $10^7$ or $10^9$ events.

5. Edge Cases, Failure Modes & Distributed Anomalies

5.1 Small Cardinality Bias in HLL

When $E<\frac{5}{2}m$, many registers remain zero. The raw harmonic mean formula overestimates cardinality. The Fix (Linear Counting Fallback): Count the number of empty registers $V={\sum }_{j=0}^{m-1}\mathbb{I}(M[j]==0)$. If $V>0$: $$E_{\text{corrected}}=m\ln \left(\frac{m}{V}\right)$$

5.2 Mergeability: The Ultimate Distributed Superpower

Both HyperLogLog and Count-Min Sketch are monoids under point-wise maximum/addition!

• To compute unique users across 10 distributed Cassandra nodes: each node computes its local 12 KB HLL sketch. The coordinator fetches ten 12 KB buffers ($120\text{ KB}$ network transfer) and merges them: $$M_{\text{merged}}[j]=\max (M_1[j],M_2[j],\dots ,M_{10}[j])$$ The merged sketch has the exact same accuracy as if all data had been processed on a single machine!

6. Open-Source Architectural Studies

6.1 Redis: PFADD, PFCOUNT, PFMERGE

Redis implements HyperLogLog natively. An HLL structure begins in sparse representation (run-length encoded bytes for low cardinality). When memory exceeds 3 KB, Redis converts it to the dense representation of 16,384 6-bit registers, capped permanently at 12 KB.

6.2 Apache Pinot & ClickHouse: Approximate Aggregations

ClickHouse uses uniqCombined64 (a hybrid HyperLogLog variant) to compute SELECT count(DISTINCT user_id) over billions of rows in milliseconds, scanning memory orders of magnitude faster than exact SQL hash sets.

7. Production Incident Post-Mortem (War Stories)

The Billion-Key Redis OOM Blackout

Context: An ad-tracking service counted daily unique cookie clicks per advertiser campaign using Redis SADD campaign:123:cookies <cookie_id>. The Incident: During a global marketing event, campaigns tracked 45 million unique cookies each. Redis memory surged from 14 GB to 128 GB within 3 hours, triggering the Linux OOM killer (kill -9 redis-server). The Remediation: Replaced SADD / SCARD with Redis HyperLogLog PFADD / PFCOUNT. Memory dropped from 128 GB to 85 MB (a $1,500\times$ memory reduction), while distinct reporting error remained below 0.8%.

8. Production-Grade TypeScript Simulation: HyperLogLog & Count-Min Sketch

/**
 * Production Probabilistic Simulation: HyperLogLog & Count-Min Sketch
 * Browser- & Server-portable (uses standard Uint8Array / TextEncoder, zero Node globals).
 */

export class HyperLogLogSimulator {
  private readonly p: number;
  private readonly m: number;
  private readonly registers: Uint8Array;
  private readonly alphaMM: number;
  private readonly encoder = new TextEncoder();

  constructor(p = 12) {
    this.p = p;
    this.m = 1 << p;
    this.registers = new Uint8Array(this.m);

    const alpha = 0.7213 / (1 + 1.079 / this.m);
    this.alphaMM = alpha * this.m * this.m;
  }

  private hash64(key: string): bigint {
    // 64-bit FNV-1a followed by MurmurHash3 fmix64 avalanche finalizer
    let hash = 0xcbf29ce484222325n;
    const fnvPrime = 0x100000001b3n;
    const mask64 = 0xffffffffffffffffn;
    const bytes = this.encoder.encode(key);

    for (let i = 0; i < bytes.length; i++) {
      hash ^= BigInt(bytes[i]);
      hash = (hash * fnvPrime) & mask64;
    }

    // fmix64 finalizer ensures uniform entropy across upper register-index bits
    hash ^= hash >> 33n;
    hash = (hash * 0xff51afd7ed558ccdn) & mask64;
    hash ^= hash >> 33n;
    hash = (hash * 0xc4ceb9fe1a85ec53n) & mask64;
    hash ^= hash >> 33n;
    return hash;
  }

  public add(element: string): void {
    const hash = this.hash64(element);
    const registerIndex = Number(hash >> BigInt(64 - this.p));
    const remainingBits = (hash << BigInt(this.p)) & 0xffffffffffffffffn;
    const maxRank = 64 - this.p + 1;

    // rho(w): 1-based position of first 1-bit in remaining (64 - p) suffix bits
    let rank = 1;
    let mask = 0x8000000000000000n;
    while ((remainingBits & mask) === 0n && rank < maxRank) {
      rank++;
      mask >>= 1n;
    }

    if (rank > this.registers[registerIndex]) {
      this.registers[registerIndex] = rank;
    }
  }

  public count(): number {
    let sum = 0;
    let emptyRegisters = 0;

    for (let i = 0; i < this.m; i++) {
      const val = this.registers[i];
      sum += Math.pow(2, -val);
      if (val === 0) emptyRegisters++;
    }

    let estimate = this.alphaMM / sum;

    // Small cardinality bias correction (Linear Counting)
    if (estimate <= 2.5 * this.m && emptyRegisters > 0) {
      estimate = this.m * Math.log(this.m / emptyRegisters);
    }
    return Math.round(estimate);
  }
}

export class CountMinSketchSimulator {
  private readonly width: number;
  private readonly depth: number;
  private readonly table: Int32Array[];

  constructor(width = 500, depth = 5) {
    this.width = width;
    this.depth = depth;
    this.table = Array.from({ length: depth }, () => new Int32Array(width));
  }

  private hash(key: string, seed: number): number {
    let h = seed >>> 0;
    for (let i = 0; i < key.length; i++) {
      h = Math.imul(h ^ key.charCodeAt(i), 0x5bd1e995) >>> 0;
    }
    h ^= h >>> 13;
    h = Math.imul(h, 0x5bd1e995) >>> 0;
    h ^= h >>> 15;
    return (h >>> 0) % this.width;
  }

  public add(key: string, count = 1): void {
    for (let row = 0; row < this.depth; row++) {
      const col = this.hash(key, row * 0x9e3779b1 + 17);
      this.table[row][col] += count;
    }
  }

  public addConservative(key: string, count = 1): void {
    const targetValue = this.estimate(key) + count;
    for (let row = 0; row < this.depth; row++) {
      const col = this.hash(key, row * 0x9e3779b1 + 17);
      if (this.table[row][col] < targetValue) {
        this.table[row][col] = targetValue;
      }
    }
  }

  public estimate(key: string): number {
    let minCount = Infinity;
    for (let row = 0; row < this.depth; row++) {
      const col = this.hash(key, row * 0x9e3779b1 + 17);
      minCount = Math.min(minCount, this.table[row][col]);
    }
    return minCount;
  }
}

export function runProbabilisticExperiment(): void {
  console.log("=== 1. HyperLogLog Cardinality Verification ===");
  const hll = new HyperLogLogSimulator(12); // m=4096, theoretical sigma = 1.04 / 64 = 1.625%
  const TRUE_DISTINCT = 20000;

  for (let i = 0; i < TRUE_DISTINCT; i++) {
    hll.add(`user_${i}`);
  }

  const estimated = hll.count();
  const errorPercent = (Math.abs(estimated - TRUE_DISTINCT) / TRUE_DISTINCT) * 100;
  console.log(`True Distinct: ${TRUE_DISTINCT} | HLL Estimated: ${estimated} | Error: ${errorPercent.toFixed(2)}%`);

  console.log("=== 2. Count-Min Sketch (Standard vs. Conservative Update) ===");
  const standardCms = new CountMinSketchSimulator(256, 5);
  const conservativeCms = new CountMinSketchSimulator(256, 5);

  standardCms.add("ip_192.168.1.1", 450);
  conservativeCms.addConservative("ip_192.168.1.1", 450);

  for (let i = 0; i < 5000; i++) {
    const noiseKey = `ip_noise_${i % 400}`;
    standardCms.add(noiseKey, 1);
    conservativeCms.addConservative(noiseKey, 1);
  }

  console.log(
    `Heavy Hitter True: 450 | Standard CMS: ${standardCms.estimate("ip_192.168.1.1")} | Conservative CMS: ${conservativeCms.estimate("ip_192.168.1.1")}`
  );
}

runProbabilisticExperiment();

9. Operational Checklist, Failure Runbooks & Sizing Rules

When to Use Probabilistic Data Structures

• Use HyperLogLog: When counting unique entities (DAU/MAU, IP addresses, search queries) where $\pm 1\%$ accuracy is acceptable and dataset exceeds $10^5$–$10^6$ items.
• Use Count-Min Sketch: For point frequency estimation, DDoS heavy-hitter tracking (paired with a bounded Top-K Min-Heap), and frequency-aware cache admission (W-TinyLFU).
• Never Use Probabilistic Structures: For financial accounting balances, exact billing ledgers, inventory deductions, or security revocation lists where exactness is mandatory.

10. Design Alternatives & Trade-offs Matrix

11. Guided Applied System Design Exercises & Debugging Drills

Drill 1: Distributed HLL Union across Edge PoPs

Your CDN operates 50 edge Points of Presence (PoPs) globally. Each PoP logs 100 million HTTP requests daily.

1. Prove why transmitting raw user IP sets to central servers requires gigabytes of bandwidth, whereas transmitting local 12 KiB HLL sketches requires only $50\times 12\text{ KiB}=600\text{ KiB}$ total.
2. Write the register-wise max merge algorithm to compute the global unique user count from the 50 regional sketches, and state what breaks if two PoPs used different hash seeds or precision parameters $p$.

Drill 2: Top-K Heavy Hitters with CMS & Min-Heap

Design a real-time DDoS mitigation engine that identifies the top 100 IP addresses generating traffic over a 10 Gbps network link.

1. Combine a Count-Min Sketch (which stores no keys) with an in-memory Min-Heap of size $K=100$ keyed by estimated frequency.
2. Outline how you prevent stale historical spikes from dominating continuous long-lived windows using tumbling dual-sketch rotation or exponential counter halving.

12. Authoritative References & Version Context

• Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Conference on Analysis of Algorithms (AofA ‘07), DMTCS Proceedings, pp. 127–146. https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
• Heule, S., Nunkesser, M., & Hall, A. (2013). HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm. Proceedings of EDBT 2013 (Google). https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/
• Cormode, G., & Muthukrishnan, S. (2005). An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms, 55(1), pp. 58–75. https://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf
• Estan, C., & Varghese, G. (2002). New Directions in Traffic Measurement and Accounting (Conservative Update). ACM SIGCOMM ‘02. https://dl.acm.org/doi/10.1145/633025.633056
• Redis Official Documentation (Redis 7.x baseline). HyperLogLog (PFADD, PFCOUNT, PFMERGE) Sparse/Dense 12 KiB Representation. https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglog/