Distributed Counters & Top-K Approximations

Answering top URLs and failure counts without storing 100M keys

A 1.2MB Bloom answers present or absent with 7 hashes, but the dashboard asks how many times. You see 100M events per hour and need top 100 URLs plus failure counts for one endpoint. An exact hash map costs gigabytes plus collection pressure. Probabilistic sketches, meaning tiny structures trading bounded error for kilobytes, cover dashboards, trending, and quota checks. Count-Min Sketch, meaning a depth-by-width counter table estimating per-key frequency with overestimates only, answers how-many; HyperLogLog, meaning a register array estimating distinct counts from hash rarity, answers how-many-distinct; SpaceSaving, meaning a bounded heap tracking frequent items with min-eviction, answers which-are-top.

Incrementing d counters per event and reading back the minimum

A single counter array collides different keys into shared cells, so one heavy key inflates innocent neighbors. Count-Min fixes this with depth d independent rows, meaning separate hash functions: update increments one cell per row, estimate takes the minimum across rows. Collisions only add, never subtract, so estimates overestimate or match truth but never undercount. Like a restaurant tallying orders on d separate sheets and trusting the smallest total for each dish, the minimum trims collision excess while preserving the true count underneath.

w = ceil(e / ε), d = ceil(ln(1/δ))  // ε error, 1-δ confidence
table[d][w] zeros
update(x): for i in 0..d-1: table[i][h_i(x)]++
estimate(x): min_i table[i][h_i(x)]  // min reduces overestimation from collisions

Example: epsilon 0.01 with delta 0.01 gives width 272 and depth 5 near 5KB of integers. Epsilon, meaning error as a fraction of total events N, and delta, meaning failure probability, literally size the table. Merge across shards by summing cell-wise, and pair with a heap for top-K by scoring candidates with sketch estimates rather than exact counts.

Turning 1% error at 99% confidence into a 5KB table by hand

Your dashboard promises error under 1% of total traffic at 99% confidence over 100M events hourly. Width equals ceil(e over epsilon) and depth equals ceil(ln(1 over delta)) with e near 2.718. Plugging epsilon 0.01 and delta 0.01 gives width 272 and depth 5, hence 272 times 5 times 4B near 5.4KB, with a guarantee that estimates sit within true plus epsilon times N. The bound is 1M here: fine for a 20M-hit URL, useless for a 50-hit tail key.

w = ceil(e / ε),  d = ceil(ln(1/δ))   (e ≈ 2.718)
Guarantee: estimate ≤ true + ε·N with probability ≥ 1−δ. Overestimates ONLY.

Worked: ε=0.01, δ=0.01, N=100M events
  w = ceil(2.718/0.01) = 272 columns,  d = ceil(ln 100) = 5 rows
  memory = 272 × 5 × 4B counters ≈ 5.4KB
  error bound: ≤ 0.01 × 100M = 1M; fine for a URL with 20M hits, useless for one with 50.
Tighter: ε=0.001 → w=2719, d=5 → ~54KB, bound ≤ 100k.
Looser: ε=0.05, δ=0.05 → w=55, d=3 → under 1KB for coarse trending.

The reading rule: sketches answer give-or-take epsilon-N. Brilliant for heavy hitters towering above noise, misleading for tail keys below the bound. State that before quoting any number.

Counting 50M distinct visitors in twelve kilobytes of rarity buckets

Count-Min counts per key but cannot count distinct keys. HyperLogLog, meaning a distinct-count estimator that hashes IDs and averages rarity across registers, covers daily active users and unique devices: hash each ID, index a register by the first p bits, record leading zeros of the remainder plus 1, and harmonically average rarity across registers. Rare hashes imply large sets. With m equal to 2 to the p registers, error sigma near 1.04 over sqrt(m), so p 14 with 16,384 registers near 12KB gives 0.8%.

HLL sketch: m = 2^p registers (p=14 → 16,384 registers × 6 bits ≈ 12KB)
  add(x): i = first p bits of hash(x) (register index)
          r = leading zeros of remaining bits + 1
          reg[i] = max(reg[i], r)
  estimate ≈ alpha × m² / Σ 2^{-reg[i]}   (harmonic mean of rarities)
Error: σ ≈ 1.04/sqrt(m) → p=14 gives ~0.8%, p=10 (~0.75KB) gives ~3.2%.

Worked: 50M distinct users, p=14 → answer lands 49.6M–50.4M two-thirds of the time.
Merge across shards: reg[i] = max over shards; no coordination, exact same result.

Summing forty 5KB tables into the sketch of their union

Forty edge boxes each see traffic slices with 5KB sketches, and nobody ships raw events centrally. Count-Min merges by cell-wise summing with identical width, depth, and hash seeds agreed at deploy, since addition commutes and straggler order changes nothing. HyperLogLog merges by element-wise maximum instead. Never average sketches: sum counts and max rarities, or the math silently breaks.

shard A table: [3, 0, 7, ...]   shard B table: [1, 5, 2, ...]
merged:          [4, 5, 9, ...]  = sketch(A ∪ B) exactly
Requirement: identical width, depth, hash seeds on every shard; agree once at deploy.
HLL merge: element-wise max instead of sum. Same deploy-once-seeds rule.
Never average sketches; sum counts, max rarities, or the math silently breaks.

Surfacing top 100 URLs from 100M events with a 100-entry heap

Count-Min answers point queries but cannot list leaders. SpaceSaving, meaning a bounded most-frequent tracker, closes the loop: hold 100 watched counters, admit newcomers by evicting the minimum, and seed each newcomer with its sketch estimate rather than zero so frequent keys climb honestly. Any key above N over (K plus 1), here 100M/101 near 990k, is always found. Rejected alternative: one exact hash map counting all 100M keys so the ranking is perfect. At roughly 100 bytes per entry that is 10GB of heap plus collection pauses against a 5KB sketch plus a 100-entry heap, and the exact rank 97 still churns with noise. Redis Cell and RedisBloom commands in the in-memory store run this server-side where sketch and throttle state share one deployment.

SpaceSaving + CMS for top-100 over 100M events:
  heap holds 100 (key, count); min entry currently ("/old-promo", 410k)
  new key "/launch" arrives, CMS estimates 520k (seen across shards already)
  520k > 410k → evict "/old-promo", insert ("/launch", 520k)
  guarantee: any key with true count > N/(K+1) = 100M/101 ≈ 990k is ALWAYS found
  memory: CMS 5KB + 100 heap entries ≈ kilobytes vs 100M-entry hash map in GBs

Redis Cell / RedisBloom path: CL.THROTTLE and CMS.* commands run this server-side;
  rate-limit state and sketch state share the same Redis you already operate.

Throttling fifty million API keys from kilobytes instead of gigabytes

Tracking 50M API keys past 100 requests per minute with exact counters grows with attackers minting fresh keys. Redis Cell's CL.THROTTLE, a sketch-backed cell-rate limiter in the in-memory store, keeps kilobytes of decaying sketch: sketches window their N so error bounds apply per window rather than all-time. Over-admission admits a couple extra requests per key but never blocks legitimate users, while exact counters guard the small set of paying-plan quota ledgers where one request over plan bills.

CL.THROTTLE user123 15 30 60 1  → max 15 burst, 30 per 60s, cost 1
  returns: allowed?, limit, remaining, retry-after seconds, reset seconds
  sketch math: ε=0.001 over N=1B requests → bound ±1M; irrelevant at limit 30?
  trick: sketches DECAY (sliding window), so N = requests per window, not all time
  N=50M keys × 30 req ≈ tiny per-key counts → relative error looks scary, absolute ±few
  consequence: throttle may admit a couple extra requests per key; never blocks a saint.

Exactness where it bills: per-plan quota ledgers stay exact counters (few plans),
  per-key flood gates stay sketches (millions of keys). Two systems, two error budgets.

Deriving epsilon from the smallest gap your alert acts on

Nobody picks epsilon from aesthetics; the alert threshold picks it. A page firing past 1M errors hourly against 100M requests makes epsilon 0.01, also plus-minus 1M, a coin flip. Epsilon must sit an order of magnitude below the smallest actionable difference, or the sketch decides while you watch. Billing quotas with one-request sensitivity need exact counters, never sketches.

Estimating p99 in 2KB when averages hide a two-second tail

Average latency 40ms hides a 2s tail that users feel. Exact percentiles need full distributions, while DDSketch and t-digest, both mergeable percentile sketches, need kilobytes. DDSketch buckets latencies in exponentially growing cells with base from alpha 0.01, bumps one counter per sample, walks buckets from the top for p99, and merges shard arrays by summing. One 2KB sketch holds 1% relative error at any scale: p99 2s plus-minus 20ms and p99 2ms plus-minus 20 microseconds alike.

DDSketch: bucket i covers [base^i, base^{i+1}) with base = (1+α)/(1-α), α=0.01
  add(250ms): increment bucket(floor(log_base(250))); one counter bump
  p99: walk buckets from the top until 1% of mass remains; no sorting, ever
  1% relative error at any scale: p99=2s ± 20ms AND p99=2ms ± 20μs, same sketch
  merge: sum bucket arrays across shards; tail math that survives the fan-in.

Forgetting last month's viral spike without rebuilding the table

Raw sketches accumulate forever, so last month's viral URL haunts this week's top-K. Exponential decay, meaning halving every counter hourly with one microsecond table pass, favors recency: 10M at noon becomes 5M by 1pm and vanishes by evening. Sliding pairs, meaning current plus previous window sketches queried summed and rotated hourly, give exact windows at double memory. Choose decay for trending freshness and pairs when alert contracts name the window.

Hourly decay (factor 0.5): every hour, table[i][j] >>= 1 for all cells
  viral spike 10M at noon → 5M by 1pm → 2.5M by 2pm → gone by evening, no rebuild
  cost: full-table pass per decay tick (272×5 cells; microseconds, not a job)
Sliding pair: sketch_A (this hour) + sketch_B (last hour); query A+B; rotate hourly.
  exact 2-hour window at 2x memory; pick when the alert contract names the window.

Sizing counters so a busy sketch never wraps silently

A 32-bit counter holds 4.29B increments, which a hot cell shared by many colliding keys can approach over months of unrotated accumulation. The naive deployment sizes width and depth but leaves counters at language-default integers that wrap to zero on overflow, silently undercounting the heaviest keys the sketch exists to track. The working rule divides lifetime increments by cells: 100M events per hour times 24 hours times 90 days is 216B total, spread over 1360 cells near 159M per cell average, with hot cells an order of magnitude higher. Four-byte counters survive that window comfortably, while multi-year sketches without decay need 64-bit counters or scheduled rotation. Monitor the maximum cell value alongside the estimate error, since a wrapping cell corrupts every key hashing into it.

Lifetime math: 100M/hr × 24h × 90d = 216B increments ÷ 1360 cells ≈ 159M avg/cell
  hot cell (10x avg from collisions + heavy hitter): ~1.6B; fits 32-bit (4.29B max)
  unrotated 2-year sketch: ~1.7T ÷ 1360 ≈ 1.3B avg, hot cells past 10B → WRAP at 32-bit
  fix: 64-bit counters (8B × 1360 cells ≈ 11KB total, still trivial) or hourly decay
  alarm: track max cell value; past 3B on 32-bit counters, rotate before it wraps.

Counting without the spreadsheet

A 5KB sketch plus a 100-entry heap surfaces every key above 990k of 100M events, and 64-bit counters survive the 216B-increment lifetime. Yet every estimate assumes keys arrive distinct and comparable. What mints globally unique, sortable IDs across 50 writers with no database bottleneck?