Gowtham Potureddi

Posted on Sep 8

Sketches at Scale: Count-Min, t-digest & Approximate Quantiles

#python #sql #interview #dataengineering

data sketches are the compact, probabilistic data structures that let you answer "how many times did this key appear?", "what are the top few heaviest keys?", and "what is the 99th-percentile latency?" over a stream so large you can never hold it in memory — and they are the single tool that separates an engineer who says "we'd sample it" from one who says "we'd sketch it with a bounded error." A sketch reads the stream once, keeps a summary that is sublinear in the size of the data (often a few kilobytes for a billion events), and answers queries with a guarantee of the form "the answer is within ε of the truth with probability 1 − δ." The whole discipline lives in that trade: you surrender exactness you almost never needed, and in return you get frequency estimation, approximate quantiles, and heavy hitters at a memory footprint that does not grow with the stream.

This guide is the walkthrough you wished existed the first time an interviewer asked "you have a 10-billion-event-per-day click stream and a 50 MB memory budget — give me the top-100 URLs and the p99 request latency, and tell me your error." It opens the two workhorse structures layer by layer: the Count-Min sketch that turns a hash grid into a one-sided frequency estimator, and the t-digest that clusters a distribution into centroids so percentiles at the tail stay accurate. It then makes the error math concrete — how ε and δ set the width and depth of a sketch, why additive error is wonderful for heavy hitters and useless for rare keys — and closes on how mergeable summaries power real systems: Spark aggregations, Druid rollups, and percentile monitoring. Each section pairs a teaching block with a Solution-Tail interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the data-structures practice library →, sharpen your estimation intuition on the statistics practice library →, and stress the distinct-count axis on the cardinality practice library →.

On this page

Why sketches — streaming, sublinear, mergeable
Count-Min sketch — frequency & heavy hitters
t-digest & approximate quantiles
Error bounds & sizing
Sketches in production — Spark / Druid / monitoring
Cheat sheet — data-sketch recipes
Frequently asked questions
Practice on PipeCode

1. Why sketches — streaming, sublinear, mergeable

A data sketch trades exactness you rarely need for memory you always lack — one pass, sublinear space, and a merge operator

The one-sentence invariant: a data sketch is a compact summary of a stream that is built in a single pass, occupies space sublinear in the number of items (or in the size of the key universe), answers a specific class of query — frequency, quantile, cardinality, or membership — with a mathematically bounded error, and is mergeable, meaning the summary of two streams can be computed from their two summaries alone without re-reading either. Every other idea in this article is a consequence of those four words: single-pass, sublinear, bounded-error, mergeable. The moment a workload has more distinct keys than fit in RAM, or is partitioned across hundreds of machines, exact aggregation stops being free and the sketch becomes the correct default rather than a clever optimisation.

The three properties that define a sketch.

Streaming (single-pass). The sketch sees each item exactly once, in arrival order, and updates its state in O(1) or O(log) time. It cannot go back and re-read the stream. This rules out any algorithm that needs to sort or make a second pass — which is exactly the class of algorithm exact quantiles and exact top-K belong to.
Sublinear space. A hashmap that counts every distinct key is O(distinct keys); a sorted array for exact percentiles is O(N). A sketch is deliberately smaller than the data it summarises — a Count-Min sketch is a fixed grid whose size depends only on the error target, and a t-digest is a bounded list of centroids. Feed it a billion events and it stays kilobytes.
Mergeability. Two sketches of the same type and configuration combine — by adding counter grids, or concatenating and re-clustering centroids — into a sketch that is (exactly, or within the same error bound) the sketch of the concatenated stream. Merge is associative and usually commutative, which is precisely the contract a distributed reducer needs. This is why sketches, not exact aggregates, are what Spark and Druid ship across the wire.

The axes that matter — pick the sketch by the question.

What question are you asking? Frequency of a given key → Count-Min. Top-K heaviest keys → Count-Min + a heap (or the Space-Saving / Frequent-Items sketch). Quantiles / percentiles → t-digest, KLL, or Greenwald-Khanna. Number of distinct keys → HyperLogLog. Set membership → Bloom filter. Using the wrong family is the most common interview miss — HyperLogLog cannot tell you a frequency, and Count-Min cannot tell you a distinct count.
What error type can you tolerate? Additive error (± ε·N) is a fixed slice of the total, so it swamps rare keys but is negligible for heavy ones. Relative error (± ε·true) scales with the answer and is what you want for cardinality and for tail quantiles. The error type is a property of the sketch, not a knob you turn afterwards.
Do you need to merge? If the data is partitioned (it almost always is), you need a mergeable sketch. A client-side percentile summary that is not mergeable (the Prometheus summary type is the canonical trap) cannot be aggregated across instances, which quietly makes fleet-wide p99 impossible.
What is the space budget? Sketch size is chosen from the error target, and the relationship is usually space ∝ 1/ε. Halving the error roughly doubles the memory. Senior answers state the budget first and derive ε and δ from it, not the reverse.

The 2026 reality — sketches are the default aggregation primitive, not a niche trick.

Distributed engines ship them built in. Spark has approx_count_distinct (HyperLogLog) and percentile_approx; Apache DataSketches provides KLL quantiles, Theta cardinality, and Frequent-Items, all mergeable and all usable as Spark/Hive UDAFs.
OLAP stores pre-aggregate with them. Druid computes quantile, cardinality, and frequency sketches at ingestion time and stores the sketch object in the segment, so a query merges pre-built sketches instead of scanning raw rows.
Metrics backends are built on them. DDSketch (Datadog) and t-digest (many Prometheus-adjacent systems) exist specifically because you must merge percentile summaries across thousands of hosts and time buckets. A monitoring system that stores raw samples to compute exact percentiles does not scale; one that stores mergeable sketches does.

What interviewers listen for.

Do you name the sketch by the question — Count-Min for frequency, t-digest for quantiles, HyperLogLog for cardinality — without conflating them? — senior signal.
Do you say "mergeable" unprompted when the data is partitioned? — required answer.
Do you distinguish additive from relative error and tie it to whether the workload cares about rare keys or the tail? — senior signal.
Do you derive sketch size from the error budget rather than guessing a memory number? — senior signal.
Do you describe a sketch as "a summary with a bounded error" rather than as vague "sampling"? — required answer.

Worked example — the exact-vs-sketch memory blow-up

Detailed explanation. The fastest way to make the case for sketches is to price the exact alternative on a realistic stream and watch it fail the memory budget. Take a day of request logs: 10 billion events, 200 million distinct URLs, and a numeric latency per event. We want two answers — per-URL request counts and the p99 latency — and we have a 50 MB budget on a single aggregator.

The stream. 10^10 events; each carries a url (one of ~2×10^8 distinct) and a latency_ms (a double).
Exact frequency. A dict[url, int] holds one entry per distinct URL. At ~60 bytes per Python entry (string key + int + hash overhead) that is 2×10^8 × 60 ≈ 12 GB — 240× over budget.
Exact quantile. To get an exact p99 you must retain every latency (or at least every value in the tail you cannot yet rule out). 10^10 doubles is 80 GB — 1600× over budget.

Question. Compare the exact and sketched memory footprints for the frequency and quantile questions, and state the error each sketch gives.

Input.

Question	Exact structure	Exact memory	Sketch	Sketch memory
Per-URL counts	hashmap (200M keys)	~12 GB	Count-Min (ε=1e-3, δ=1e-2)	~55 KB
p99 latency	full sample (10B doubles)	~80 GB	t-digest (compression=200)	~20 KB
Distinct URLs	hash set (200M keys)	~9 GB	HyperLogLog (p=14)	~16 KB

Code.

# The exact approach that does NOT fit in 50 MB
exact_counts = {}          # -> ~12 GB at 200M distinct URLs
exact_latencies = []       # -> ~80 GB at 10B events

for event in stream:                     # 10,000,000,000 iterations
    exact_counts[event.url] = exact_counts.get(event.url, 0) + 1
    exact_latencies.append(event.latency_ms)

# p99 needs a sort or a select over the whole 80 GB array
exact_latencies.sort()
p99_exact = exact_latencies[int(0.99 * len(exact_latencies))]

# The sketched approach that fits in ~100 KB total
cms      = CountMinSketch(epsilon=1e-3, delta=1e-2)   # ~55 KB grid
tdigest  = TDigest(compression=200)                    # ~20 KB of centroids

for event in stream:                     # still one pass, O(1) per item
    cms.update(event.url, 1)
    tdigest.update(event.latency_ms)

count_of_url = cms.estimate("/checkout")   # <= true + eps*N, w.p. 1 - delta
p99_sketch   = tdigest.quantile(0.99)      # relative error, tightest at the tail

Step-by-step explanation.

The exact hashmap grows with the number of distinct keys, not the number of events — but at 200 million distinct URLs it is already 12 GB. Distinct-key growth is the failure mode: a stream with a large key universe defeats any per-key exact structure regardless of how many total events there are.
The exact quantile is worse: percentiles are a global property of the value distribution, so there is no incremental exact summary — you must keep enough of the sample to locate the rank you care about, which in the worst case is all of it. 80 GB is not a tuning problem; it is the algorithm.
The Count-Min sketch replaces the hashmap with a fixed grid sized purely from the error target (ε, δ). Its memory is independent of both the event count and the distinct-key count — the same 55 KB whether the stream has a thousand keys or a billion.
The t-digest replaces the full sample with a bounded set of centroids. It never stores an individual latency; it folds each value into the nearest centroid and occasionally re-clusters. Memory is capped by the compression parameter, not by N.
The cost is error, and it is bounded and stated: the Count-Min answer is the truth plus at most ε·N (a one-sided overshoot) with probability 1 − δ; the t-digest p99 carries a small relative error that is tightest exactly at the tail we asked about. Both errors are acceptable for the questions ("which URLs are hot", "is p99 breaching SLO") that motivated them.

Output.

Metric	Exact	Sketched	Ratio
Frequency memory	~12 GB	~55 KB	~218,000× smaller
Quantile memory	~80 GB	~20 KB	~4,000,000× smaller
Passes over data	1 (+ sort for p99)	1	—
Answer type	exact	ε-bounded	—
Fits in 50 MB budget?	no	yes	—

Rule of thumb. Reach for a sketch the moment either the distinct-key count or the raw sample would not fit in your aggregation budget. The decision is not "is approximation acceptable" — it is "can I afford exactness", and at stream scale the answer is almost always no.

Worked example — mergeability, demonstrated

Detailed explanation. Mergeability is the property that makes sketches distributed-native, so it is worth seeing concretely. Split a stream across three shards, build a sketch per shard independently, then combine the three sketches and confirm the result equals the sketch of the whole stream. For a Count-Min sketch "combine" is literally element-wise addition of the grids — provided every shard used the same width, depth, and hash seeds.

The stream. Keys A, B, C arriving on three shards; shard 1 sees A A B, shard 2 sees A C, shard 3 sees B B C C.
The contract. merge(sketch(S1), sketch(S2), sketch(S3)) == sketch(S1 ++ S2 ++ S3) for Count-Min (exactly), and within the error bound for quantile sketches.
The requirement. Identical configuration across shards — same (w, d) and same hash functions. A merge across mismatched configs is meaningless.

Question. Build one Count-Min sketch per shard, merge them, and show the merged frequency estimates match a single global sketch.

Input.

Shard	Stream	Local count A	Local count B	Local count C
S1	A A B	2	1	0
S2	A C	1	0	1
S3	B B C C	0	2	2
Merged	—	3	3	3

Code.

def merge_cms(a: "CountMinSketch", b: "CountMinSketch") -> "CountMinSketch":
    """Merge two Count-Min sketches by adding their grids element-wise.
    Precondition: identical width, depth, and hash seeds."""
    assert (a.width, a.depth, a.seeds) == (b.width, b.depth, b.seeds)
    out = CountMinSketch.like(a)                 # zero grid, same config
    for r in range(a.depth):
        for c in range(a.width):
            out.grid[r][c] = a.grid[r][c] + b.grid[r][c]
    return out

# One sketch per shard, built independently (in parallel, on different machines)
s1 = build_cms(["A", "A", "B"])
s2 = build_cms(["A", "C"])
s3 = build_cms(["B", "B", "C", "C"])

merged = merge_cms(merge_cms(s1, s2), s3)        # associative: any order works

# A single global sketch over the concatenated stream, for comparison
global_cms = build_cms(["A", "A", "B", "A", "C", "B", "B", "C", "C"])

for key in ("A", "B", "C"):
    assert merged.estimate(key) == global_cms.estimate(key)

Step-by-step explanation.

Each shard builds its sketch with no coordination — no shuffle, no cross-talk, no shared state. That independence is the entire point: the expensive part (reading the raw data) happens locally and in parallel, and only the tiny sketch crosses the network.
merge_cms adds the grids cell by cell. Because a Count-Min counter at grid[r][c] is just "the total weight hashed into row r, column c", summing two grids yields exactly the grid you would have gotten had both streams updated one shared sketch. This is why Count-Min merge is exact, not merely bounded.
The merge is associative and commutative, so a reducer can combine shards in any order, in a tree, or incrementally as they arrive. There is no "correct order" to preserve — a property distributed schedulers depend on.
The precondition is strict: identical width, depth, and hash seeds. Two sketches with different seeds place the same key in different columns, so adding their grids mixes unrelated counters and produces garbage. In practice the config is fixed centrally and shipped to every shard.
Quantile sketches (t-digest, KLL) are mergeable too, but their merge is "concatenate the centroid/level structure and re-compress", and the result is within the error bound rather than bit-identical. The distributed pattern is the same; only the exactness of the merge differs.

Output.

Key	S1 est	S2 est	S3 est	Merged est	Global est	Match
A	2	1	0	3	3	yes
B	1	0	2	3	3	yes
C	0	1	2	3	3	yes

Rule of thumb. Treat mergeability as a hard requirement whenever data is partitioned. Fix the sketch configuration centrally, ship it to every worker, and let the reducer add or re-compress — never try to merge sketches that were built with different parameters.

Worked example — choosing the sketch for the question

Detailed explanation. The most common sketch mistake is reaching for the wrong family, so senior engineers keep a one-line mapping from question to structure. Walk three real questions through the mapping: "how hot is this key", "how many distinct users", and "what is the tail latency" — three different sketches, three different error models.

Frequency / heavy hitters. "How many times did key X appear?" and "what are the top-K keys?" → Count-Min (+ heap) or a Frequent-Items sketch. Additive error.
Cardinality. "How many distinct keys?" → HyperLogLog. Relative error ≈ 1.04/√m.
Quantiles. "What is p50 / p95 / p99?" → t-digest, KLL, or Greenwald-Khanna. Relative (t-digest, tail-tight) or rank (KLL) error.

Question. For each of three questions, name the sketch, its error model, and the disqualifying mismatch if you picked the wrong one.

Input.

Question	Right sketch	Error model	Wrong pick and why it fails
Count of key X	Count-Min	additive ± ε·N	HyperLogLog — has no per-key counter at all
Distinct keys	HyperLogLog	relative ± 1.04/√m	Count-Min — counts occurrences, not distinctness
p99 latency	t-digest / KLL	relative / rank	Count-Min — has no notion of order or rank

Code.

def pick_sketch(question: str) -> str:
    """Map an aggregation question to the correct sketch family."""
    q = question.lower()
    if "distinct" in q or "unique" in q or "cardinality" in q:
        return "HyperLogLog (relative error ~1.04/sqrt(m))"
    if "percentile" in q or "quantile" in q or "median" in q or "p99" in q:
        return "t-digest / KLL (quantile sketch)"
    if "top" in q or "heavy" in q or "most frequent" in q:
        return "Count-Min + min-heap (heavy hitters)"
    if "how many times" in q or "frequency" in q or "count of" in q:
        return "Count-Min (frequency, additive error)"
    if "member" in q or "seen before" in q or "exists" in q:
        return "Bloom filter (membership, one-sided false positives)"
    return "exact aggregation may be fine; measure the key universe first"

print(pick_sketch("count of key /checkout"))   # Count-Min (frequency, additive error)
print(pick_sketch("how many distinct users"))  # HyperLogLog
print(pick_sketch("what is the p99 latency"))  # t-digest / KLL

Step-by-step explanation.

The frequency question maps to Count-Min because a Count-Min grid is a set of overlapping counters — it can return an estimate for any key you ask about. HyperLogLog stores only a register array that estimates distinctness; it has no counter to return, so it cannot answer "how many times".
The distinct-count question maps to HyperLogLog because distinctness is about the set of keys, not their multiplicity. Count-Min would happily give you a frequency, but summing frequencies is not a distinct count — a Count-Min cannot deduplicate.
The quantile question maps to a quantile sketch because percentiles depend on the order statistics of the values. Count-Min discards order entirely (it hashes keys into buckets), so it has no way to answer "what value sits at rank 0.99N".
Each wrong pick fails for a structural reason, not a tuning reason — you cannot make Count-Min answer a quantile by enlarging the grid, and you cannot make HyperLogLog answer a frequency by adding registers. The family is chosen by the question; only then do you size within the family.
The mapping also surfaces membership (Bloom filter) and the honest fallback ("measure the key universe; exact might fit"). Naming that fallback is itself a senior signal — sketches are for when exact does not fit, not a reflex.

Output.

Question asked	Sketch chosen	Error model	Space driver
Frequency of a key	Count-Min	additive ± ε·N	1/ε
Top-K heavy hitters	Count-Min + heap	additive ± ε·N	1/ε + K
Distinct count	HyperLogLog	relative ± 1.04/√m	number of registers m
Quantile / percentile	t-digest / KLL	relative / rank	compression / k
Membership	Bloom filter	one-sided FP rate	1/target FP

Rule of thumb. Say the question out loud, then name the sketch: frequency → Count-Min, distinct → HyperLogLog, quantile → t-digest/KLL, membership → Bloom. Sizing comes second; picking the family from the question comes first, and getting the family wrong cannot be fixed by more memory.

Data-engineering interview question on sketch selection

A senior interviewer often opens with: "You are handed a 10-billion-event-per-day stream partitioned across 400 workers, and product wants three things on a dashboard: the top-100 heaviest keys, the number of distinct users, and the p99 event latency — refreshed hourly, sliceable by region, on a fixed memory budget per worker. Walk me through the sketches you'd build per worker, how you'd combine them, and the error you'd quote for each number."

Solution Using a per-worker mergeable sketch bundle combined at the reducer

# sketch_bundle.py — one bundle per worker; all three sketches are mergeable
from dataclasses import dataclass

@dataclass
class SketchBundle:
    cms:  "CountMinSketch"   # frequency  -> top-K via companion heap
    hll:  "HyperLogLog"      # distinct users
    td:   "TDigest"          # p99 latency
    heap: "TopKHeap"         # top-100 candidates, fed by cms estimates

    @classmethod
    def empty(cls, region: str) -> "SketchBundle":
        return cls(
            cms=CountMinSketch(epsilon=1e-4, delta=1e-3),  # tight: top-100 need small eps
            hll=HyperLogLog(precision=14),                  # ~16 KB, ~0.8% relative error
            td=TDigest(compression=200),                    # tail-accurate p99
            heap=TopKHeap(k=100),
        )

    def update(self, event) -> None:
        c = self.cms.update(event.key, 1)   # returns the post-update estimate
        self.heap.offer(event.key, c)       # maintain top-100 candidates
        self.hll.add(event.user_id)
        self.td.update(event.latency_ms)

def merge(a: SketchBundle, b: SketchBundle) -> SketchBundle:
    """Associative merge — the reducer folds all 400 worker bundles."""
    out = SketchBundle.empty("merged")
    out.cms  = a.cms.merge(b.cms)           # add grids (exact)
    out.hll  = a.hll.merge(b.hll)           # max of registers (exact for HLL)
    out.td   = a.td.merge(b.td)             # concat centroids + re-compress
    out.heap = a.heap.merge(b.heap, out.cms)  # re-rank union by merged cms estimate
    return out

# Reducer — tree-combine 400 worker bundles per region, then answer the dashboard
def summarize(worker_bundles: list[SketchBundle]) -> dict:
    from functools import reduce
    combined = reduce(merge, worker_bundles)         # O(workers) merges
    return {
        "top_100":        combined.heap.items(),      # heavy hitters
        "distinct_users": combined.hll.estimate(),    # cardinality
        "p99_latency_ms": combined.td.quantile(0.99), # tail percentile
    }

Step-by-step trace.

Step	Input	What happens
Per-worker build	worker reads its shard once	updates cms / hll / td / heap in O(1) per event
Emit	end of hour	worker ships ~100 KB bundle, not raw events
Reducer fold	400 bundles	`reduce(merge, ...)` — associative, any order
top-100	merged cms + heap	re-rank union of candidates by merged estimate
distinct	merged hll	register-wise max, then estimate
p99	merged td	walk centroids, interpolate at q=0.99

After the fold, the reducer holds one bundle per region of roughly 100 KB. The dashboard reads three numbers off it — top-100 keys, distinct users, p99 latency — each with a stated error, and never touched a raw event after the initial per-worker pass. Slicing by region is just choosing which bundles to merge.

Output:

Dashboard number	Sketch used	Error quoted	Bytes on the wire
Top-100 heavy keys	Count-Min + heap	± ε·N, ε = 1e-4	~1 MB grid
Distinct users	HyperLogLog p=14	~0.8% relative	~16 KB
p99 latency	t-digest c=200	small relative, tail-tight	~20 KB
Raw events shipped	—	—	0

Why this works — concept by concept:

Single-pass per worker — each worker touches its shard once and updates four O(1) structures. The expensive read is local and parallel; nothing re-reads the stream, which is the streaming constraint honoured.
One family per question — Count-Min for frequency, HyperLogLog for distinctness, t-digest for the quantile. Each number comes from the structure whose error model fits it; no structure is asked a question it cannot answer.
Mergeability is the reducer contract — every sketch in the bundle has an associative merge (add grids, max registers, re-compress centroids). That is what lets 400 independent bundles collapse to one without a shuffle of raw data.
Slice-by-region for free — because merge is associative, "p99 for region X" is just merging the bundles from region X. The same pre-built sketches answer any slice that is a union of shards.
Cost — O(1) per event on each worker, O(workers) merges at the reducer, and O(sketch size) bytes on the wire — independent of the 10^10 event count. The eliminated cost is the O(N) shuffle of raw events and the O(distinct) memory of exact per-key state.

Data Structures
Topic — data-structures
Probabilistic data-structure problems

Practice →

Statistics Topic — statistics Estimation and error-bound problems

Practice →

2. Count-Min sketch — frequency & heavy hitters

`count-min sketch` hashes every item into a d×w counter grid and answers a frequency query with the minimum across rows — a one-sided overestimate that never lies low

The mental model in one line: a count-min sketch is a two-dimensional array of counters with d rows and w columns paired with d independent hash functions; to add weight to a key you hash it once per row and increment the selected counter in each of the d rows, and to estimate a key's frequency you read the d counters it hashes to and return the minimum — because collisions can only ever add extra weight, the estimate is guaranteed to be at least the true count and at most the true count plus ε·N with probability 1 − δ. It is the workhorse of frequency estimation: constant memory regardless of the key universe, O(d) update and query, exactly mergeable, and the natural base for heavy hitters.

Why the minimum, and why it is one-sided.

Every row is an over-count. Within a single row, many keys hash to the same column, so a counter holds the true count of your key plus the counts of every other key that collided there. A single row therefore never underestimates — it can only overestimate.
Different rows collide differently. The d hash functions are independent, so the set of keys colliding with yours in row 1 differs from row 2. The row where your key suffered the least collision noise gives the tightest over-estimate.
Min beats the noise down. Taking the minimum across rows picks that least-noisy row. The more rows d, the higher the probability that at least one row was nearly collision-free — which is exactly the δ (failure probability) knob.
The error is additive, not relative. The over-count is bounded by ε·N (a fixed slice of the total stream weight), independent of the key's own frequency. This is the defining strength and weakness of Count-Min, and section 4 makes the math precise.

The grid dimensions and what they control.

Width w controls ε. More columns spread keys across more counters, reducing collisions and shrinking the additive error. The relationship is w = ⌈e/ε⌉ (Euler's e ≈ 2.718), so ε = 0.001 needs w ≈ 2719 columns.
Depth d controls δ. More rows give more independent chances at a low-collision estimate, raising the confidence. The relationship is d = ⌈ln(1/δ)⌉, so δ = 0.01 needs d ≈ 5 rows.
Memory is w × d counters. With 4-byte counters, 2719 × 5 ≈ 54 KB — fixed, whether the stream has a thousand or a billion distinct keys.
Hashing. d independent hash functions (in practice, one strong hash split into d lanes, or pairwise-independent hashes (a·x + b) mod p mod w). Independence across rows is what the error proof assumes.

Heavy hitters on top of Count-Min.

The definition. A φ-heavy hitter is a key whose frequency exceeds φ·N (e.g. any key that is more than 1% of the stream). Top-K is the related "give me the K heaviest keys".
The pattern. Maintain a min-heap of size K keyed by estimated frequency. On each update, query the Count-Min estimate for the key; if it beats the heap's smallest, offer it into the heap. The heap holds the current top-K candidates.
Why it needs the sketch. You cannot keep a counter for every key (that is the exact hashmap you are avoiding), so the heap tracks only K keys and leans on the Count-Min for the frequency of any candidate.
The caveat. Additive error means a key just below the threshold can be over-estimated into the top-K. For true heavy hitters (well above ε·N) this never happens; near the boundary it can, which is why you size ε well below φ.

The conservative-update refinement.

Standard update increments all d counters. Conservative update increments only the counters that are currently at the minimum (i.e. it raises each counter to at most min + 1).
Why it helps. It avoids inflating counters that are already large due to other keys, which lowers the observed over-estimate in practice — often by a large factor on skewed streams.
The trade-off. Conservative update breaks exact mergeability (you can no longer just add two grids), so it is used for single-node accuracy, not distributed merge. Choose one or the other per deployment.

Common interview probes on Count-Min.

"Can a Count-Min sketch under-count?" — required answer: no, it is one-sided; the estimate is ≥ true count.
"Why take the min across rows?" — the least-collided row gives the tightest over-estimate; more rows raise the confidence 1 − δ.
"How do you get top-K from it?" — Count-Min for frequencies plus a size-K min-heap of candidates.
"How do you merge two Count-Min sketches?" — element-wise add the grids (same w, d, seeds); conservative update forfeits this.

Worked example — build and query a Count-Min sketch

Detailed explanation. Implement a minimal Count-Min sketch and run a small word stream through it, then read an estimate and confirm it is a one-sided overestimate. Use d = 4 rows and w = 16 columns with pairwise-independent hashes so the trace is small enough to reason about by hand.

Config. d = 4, w = 16, four hash seeds.
Stream. A short stream of words with one clearly-heavy key (the) and several light keys.
Query. Estimate the and a light word, and compare to the true counts.

Question. Implement update and estimate, run the stream, and show the estimate for a heavy and a light key.

Input.

Parameter	Value
Depth d	4
Width w	16
Hash family	(a·h(x) + b) mod p mod w
Counter type	int (4 bytes)

Code.

import hashlib

class CountMinSketch:
    def __init__(self, width: int = 16, depth: int = 4, seed: int = 1):
        self.width  = width
        self.depth  = depth
        self.seeds  = [seed * 7919 + i for i in range(depth)]  # d distinct seeds
        self.grid   = [[0] * width for _ in range(depth)]

    def _cols(self, key: str):
        for r, s in enumerate(self.seeds):
            h = int(hashlib.md5(f"{s}:{key}".encode()).hexdigest(), 16)
            yield r, h % self.width          # one column per row

    def update(self, key: str, count: int = 1) -> int:
        est = None
        for r, c in self._cols(key):
            self.grid[r][c] += count
            v = self.grid[r][c]
            est = v if est is None else min(est, v)
        return est                            # post-update estimate (handy for top-K)

    def estimate(self, key: str) -> int:
        return min(self.grid[r][c] for r, c in self._cols(key))

cms = CountMinSketch(width=16, depth=4)
stream = ["the"] * 50 + ["fox", "the", "dog", "the", "fox", "cat"] + ["the"] * 5
for w in stream:
    cms.update(w)

print("the:", cms.estimate("the"))   # true = 57
print("fox:", cms.estimate("fox"))   # true = 2
print("cat:", cms.estimate("cat"))   # true = 1

Step-by-step explanation.

_cols derives one column per row by hashing seed:key. Using a different seed per row gives the d independent hash functions the error bound assumes; a single hash reused across rows would collapse the confidence gain from depth.
update increments the selected counter in each of the d rows. Because a key always lands in the same d columns, repeated updates accumulate there — that is how the sketch "remembers" a key without storing the key itself.
estimate reads those same d columns and returns the minimum. The minimum is the row where the shared its column with the fewest other words, so it is the closest over-estimate to the truth.
The heavy key the (true 57) comes back at exactly 57 or a hair above — with w = 16 and a small stream, collisions are mild, so the over-count is tiny. The light keys fox (2) and cat (1) may over-count more in relative terms because any collision with the adds a big chunk of weight — the additive-error asymmetry in miniature.
Crucially, no estimate is ever below the truth. If you see 57 for a true 57, or 60 for a true 57, both are valid Count-Min outputs; 55 for a true 57 is impossible and would signal a bug.

Output.

Key	True count	CMS estimate	Error	Direction
the	57	57	0	exact here
fox	2	2–4	≤ +2	over
dog	1	1–3	≤ +2	over
cat	1	1–3	≤ +2	over

Rule of thumb. Trust a Count-Min estimate as an upper bound on the truth. It is tight for heavy keys and loose for light ones — which is exactly the right shape when you only care about the heavy keys.

Worked example — top-K heavy hitters with a min-heap

Detailed explanation. Turn the frequency sketch into a top-K heavy-hitters detector by pairing it with a size-K min-heap. As each item streams in, update the Count-Min, take the returned estimate, and maintain a heap of the K keys with the largest estimates. Run it over a skewed stream and read off the top 3.

Structures. One Count-Min sketch + a min-heap of (estimate, key) capped at K, plus a set of keys currently in the heap.
Invariant. The heap holds the K keys with the highest estimates seen so far; the heap root is the weakest of the current top-K.
Update rule. If a key is already in the heap, refresh its estimate; else if the heap is under K, push; else if the estimate beats the root, evict the root and push.

Question. Implement the top-K heavy-hitters detector over a skewed stream and return the top 3 keys with estimates.

Input.

Parameter	Value
K	3
CMS	w=64, d=4
Stream skew	one dominant key, a mid key, a long tail

Code.

import heapq

class HeavyHitters:
    def __init__(self, k: int, cms: "CountMinSketch"):
        self.k    = k
        self.cms  = cms
        self.heap = []          # min-heap of (estimate, key)
        self.pos  = {}          # key -> current estimate in heap

    def offer(self, key: str) -> None:
        est = self.cms.update(key)          # increment + get post-update estimate
        if key in self.pos:                  # already tracked: refresh its rank
            self._refresh(key, est)
        elif len(self.heap) < self.k:        # room in the heap: add it
            heapq.heappush(self.heap, (est, key))
            self.pos[key] = est
        elif est > self.heap[0][0]:          # beats the weakest top-K key: swap in
            _, evicted = heapq.heappop(self.heap)
            self.pos.pop(evicted, None)
            heapq.heappush(self.heap, (est, key))
            self.pos[key] = est

    def _refresh(self, key: str, est: int) -> None:
        # lazy refresh: rebuild the heap with the new estimate for `key`
        self.heap = [(e if k != key else est, k) for e, k in self.heap]
        heapq.heapify(self.heap)
        self.pos[key] = est

    def top(self):
        return sorted(self.heap, reverse=True)   # highest estimate first

stream = (["/home"] * 500 + ["/checkout"] * 120 + ["/search"] * 60
          + [f"/p/{i}" for i in range(400)])     # 400 unique long-tail pages
hh = HeavyHitters(k=3, cms=CountMinSketch(width=64, depth=4))
for path in stream:
    hh.offer(path)

for est, key in hh.top():
    print(f"{key}: ~{est}")

Step-by-step explanation.

offer first updates the Count-Min and captures the post-update estimate in one call — the sketch is the only place a per-key frequency lives, since keeping an exact counter per key is the very thing we are avoiding.
If the key already sits in the heap, _refresh updates its stored estimate and re-heapifies so the ordering stays correct as the key climbs. Without the refresh, a heavy key's heap entry would be frozen at its first-seen estimate and it could be wrongly evicted.
If the heap has fewer than K entries, the key is admitted unconditionally — the top-K is still filling up.
Once the heap is full, a new key must beat the root (the weakest current top-K key) to enter. This is the classic bounded-heap top-K: O(log K) per admission, and the heap never exceeds K entries regardless of how many distinct keys stream by.
The 400 long-tail pages each appear once, estimate ≈ 1, and never displace the root (/search at ~60), so they churn through offer in O(1) without polluting the heap. The result is the three genuine heavy hitters, each with a Count-Min over-estimate that is tight because they are far above ε·N.

Output.

Rank	Key	True count	Heap estimate
1	/home	500	~500
2	/checkout	120	~120
3	/search	60	~60
—	/p/… (×400)	1 each	never enters heap

Rule of thumb. For top-K, let the Count-Min own the frequencies and let a size-K min-heap own the ranking. Keep ε well below your φ threshold so the additive error can never lift a tail key over a genuine heavy hitter.

Worked example — conservative update and grid merge

Detailed explanation. Two refinements matter in practice: conservative update (tighter single-node estimates) and grid merge (distributed aggregation). They are mutually exclusive — conservative update breaks exact mergeability — so this example shows both and states when to use which.

Conservative update. Instead of +1 to all d counters, raise each selected counter to at most min_before + 1. Counters already above the minimum are left alone.
Grid merge. Add two standard (non-conservative) grids element-wise; the sum equals the sketch of the concatenated stream.
The rule. Use conservative update on a single node where accuracy matters and you never merge; use standard update when the sketch must merge across shards.

Question. Implement conservative update and grid merge, and state why they cannot be combined.

Input.

Mode	Update rule	Mergeable?	Best for
Standard	+count to all d cells	yes (add grids)	distributed / merge
Conservative	raise cells to min+count	no	single-node accuracy

Code.

class CountMinSketch(CountMinSketch):   # extend the earlier class

    def update_conservative(self, key: str, count: int = 1) -> int:
        cols = list(self._cols(key))
        cur  = min(self.grid[r][c] for r, c in cols)  # current estimate
        target = cur + count
        for r, c in cols:
            if self.grid[r][c] < target:               # only raise laggards
                self.grid[r][c] = target
        return target

    def merge(self, other: "CountMinSketch") -> "CountMinSketch":
        assert (self.width, self.depth, self.seeds) == (
                other.width, other.depth, other.seeds), "config must match"
        out = CountMinSketch(self.width, self.depth)
        out.seeds = list(self.seeds)
        out.grid  = [[self.grid[r][c] + other.grid[r][c]
                      for c in range(self.width)]
                     for r in range(self.depth)]
        return out

Step-by-step explanation.

update_conservative computes the current minimum (the estimate) first, then raises each of the d counters only up to min + count. A counter already above that target is untouched, so weight from other keys is never amplified by this key's update.
This lowers the observed over-estimate substantially on skewed streams: a light key that collides with a heavy key no longer pushes the heavy key's counters even higher, so the heavy key's estimate stops drifting upward.
merge adds two standard grids cell by cell after asserting identical configuration. Because standard counters are pure sums of hashed weight, the element-wise sum is exactly the grid a single sketch would have built over both streams — merge is lossless.
The two cannot be combined: conservative update makes a counter's value depend on the order and interleaving of updates (it only raises laggards), so two conservatively-built grids no longer sum to the grid of the concatenation. Adding them double-counts the shared minimums and corrupts estimates.
The deployment decision is therefore explicit: a single-node hot-key detector uses conservative update for accuracy; a distributed pipeline that merges per-shard sketches uses standard update and accepts the slightly looser bound in exchange for exact mergeability.

Output.

Scenario	Standard estimate	Conservative estimate
Heavy key, low collision	tight	tight
Heavy key, heavy collision	inflated	much tighter
After cross-shard merge	correct (sum of grids)	invalid (cannot merge)

Rule of thumb. Pick conservative update or mergeability, never both. If your architecture merges per-shard sketches, standard update is mandatory; if it is a single hot-node counter, conservative update buys you real accuracy for free.

Data-structures interview question on Count-Min sketch

A senior interviewer might ask: "Design a service that, over a firehose of (user_id, url) click events on one machine with a 64 MB budget, continuously reports the top-50 URLs and can answer 'how many times has URL X been clicked' with a stated error. Give me the sketch, the top-K machinery, the memory math, and how the error changes if I halve the budget."

Solution Using a Count-Min sketch with a bounded top-K heap

# hot_urls.py — single-node top-K + point frequency over a click firehose
import heapq, hashlib

class CountMinSketch:
    def __init__(self, width: int, depth: int):
        self.width, self.depth = width, depth
        self.seeds = [1_000_003 * i + 17 for i in range(depth)]
        self.grid  = [[0] * width for _ in range(depth)]

    def _cols(self, key: str):
        for r, s in enumerate(self.seeds):
            h = int(hashlib.blake2b(f"{s}:{key}".encode(), digest_size=8).hexdigest(), 16)
            yield r, h % self.width

    def update(self, key: str, c: int = 1) -> int:
        est = None
        for r, col in self._cols(key):
            self.grid[r][col] += c
            est = self.grid[r][col] if est is None else min(est, self.grid[r][col])
        return est

    def estimate(self, key: str) -> int:
        return min(self.grid[r][c] for r, c in self._cols(key))

class HotUrls:
    def __init__(self, k=50, width=1 << 20, depth=5):   # 2^20 cols x 5 rows
        self.cms  = CountMinSketch(width, depth)
        self.k    = k
        self.heap = []            # (estimate, url)
        self.seen = {}            # url -> estimate in heap

    def click(self, url: str) -> None:
        est = self.cms.update(url)
        if url in self.seen:
            self.heap = [(est if u == url else e, u) for e, u in self.heap]
            heapq.heapify(self.heap)
            self.seen[url] = est
        elif len(self.heap) < self.k:
            heapq.heappush(self.heap, (est, url)); self.seen[url] = est
        elif est > self.heap[0][0]:
            _, ev = heapq.heappop(self.heap); self.seen.pop(ev, None)
            heapq.heappush(self.heap, (est, url)); self.seen[url] = est

    def frequency(self, url: str) -> int:
        return self.cms.estimate(url)

    def top(self):
        return sorted(self.heap, reverse=True)

Step-by-step trace.

Step	Value	Reasoning
Grid dimensions	w = 2^20, d = 5	ε ≈ e/w ≈ 2.6e-6; δ ≈ e^-5 ≈ 0.0067
Counter size	4 bytes	2^20 × 5 × 4 = ~21 MB grid
Heap	50 entries	O(log K) per admission; negligible memory
Point query	min over 5 cells	one-sided; ≤ true + ε·N
Halving budget	w → 2^19	ε doubles (~5.2e-6); error band widens 2×

Over the firehose the grid sits at ~21 MB (well under 64 MB), the heap tracks the 50 heaviest URLs, and frequency(url) answers any point query as an upper bound within ε·N. Halving the budget halves w, which doubles ε and therefore doubles the additive error band — depth d (and thus the confidence 1 − δ) is untouched because memory was taken from width.

Output:

Query	Result	Error guarantee
top(50)	50 heaviest URLs, ranked	tight for keys ≫ ε·N
frequency("/checkout")	estimate ≥ true	≤ true + ε·N, prob 1 − δ
Grid memory	~21 MB	fixed vs event count
After halving budget	ε doubles	band 2× wider, same δ

Why this works — concept by concept:

d×w grid with d hashes — the sketch stores overlapping counters, not keys, so memory is O(w·d) regardless of how many distinct URLs stream by. The key universe can be unbounded; the grid does not grow.
min across rows — returns the least-collided (tightest) over-estimate, and increasing d raises the probability that some row was nearly collision-free — the 1 − δ confidence.
bounded top-K heap — the size-50 min-heap ranks candidates by their Count-Min estimate; it is O(log K) per event and never exceeds K entries, so the long tail costs nothing.
width sets ε, depth sets δ — spending memory on width tightens the additive error; spending it on depth raises confidence. Halving the budget on width doubles ε and leaves δ alone — a controllable, stated degradation.
Cost — O(d) per update and per query (constant, d = 5), O(w·d) space (~21 MB, fixed), O(log K) per top-K admission. The eliminated cost is the O(distinct URLs) memory of an exact hashmap, which the firehose would blow past.

Data Structures
Topic — data-structures
Hashing and counter-sketch problems

Practice →

Cardinality Topic — cardinality Frequency and distinct-count estimation problems

Practice →

3. t-digest & approximate quantiles

`t-digest` summarises a distribution as centroids that are large in the middle and tiny at the tails, so `approximate quantiles` like p99 and p999 stay accurate where you need them most

The mental model in one line: a t-digest is a quantile sketch that clusters streaming values into a bounded set of centroids — each a (mean, count) pair — where the allowed centroid size is governed by a scale function that keeps clusters small near the extremes (q close to 0 or 1) and lets them grow in the middle, so the summary spends its limited memory buying high relative accuracy at the tails and coarse accuracy at the median, which is exactly the trade percentiles monitoring wants because nobody pages on p50 but everyone pages on p99. It is mergeable, order-insensitive in the limit, and answers any quantile query by walking the centroids and interpolating.

Why exact quantiles are expensive, and what t-digest replaces.

Quantiles are global. The p99 of a stream is defined by the rank of every value relative to all others, so there is no per-value incremental exact summary — the naive exact method sorts all N values, an O(N) memory and O(N log N) time cost.
Histograms leak accuracy. Fixed-bucket histograms bound memory but hard-code where the accuracy goes: bucket edges chosen for the middle give terrible tail resolution, and you cannot know the right edges in advance for latency that spans microseconds to seconds.
t-digest adapts. It places many small centroids where quantiles change fast (the tails) and few large ones where they change slowly (the middle), so the same memory yields far better tail accuracy than an equal-width histogram.
The output is one small object. A few hundred centroids — a couple of kilobytes — summarise a stream of any length, and merge cheaply.

The centroid model and the scale function.

A centroid is (mean, count). It claims to represent count values clustered around mean. The digest is a sorted list of centroids covering the value range.
The scale function k(q). t-digest maps the quantile position q ∈ [0,1] through a non-linear scale (commonly k(q) = δ·(asin(2q−1))/(2π) or a log-like variant). A centroid may absorb more mass only if doing so keeps its k-width within one unit.
Tails get small centroids. Because k(q) is steep near q = 0 and q = 1, a centroid near the tail hits its size limit after absorbing very few values, so tail centroids stay tiny and numerous — high resolution.
The middle gets big centroids. Near q = 0.5, k(q) is flat, so a centroid can absorb a large count before splitting — low resolution where you do not care.
Compression δ. The single knob (often called compression, e.g. 100–500) sets the total centroid budget: higher δ means more centroids, more accuracy, more memory. Centroid count is roughly O(δ).

Building and querying.

Buffer and merge. Practical t-digests buffer incoming values, sort the buffer, then merge it into the centroid list in one pass, re-splitting any centroid that exceeds its k-width. Buffering amortises the sort and keeps updates fast.
Quantile query. To find the value at quantile q, accumulate centroid counts left to right until you pass q·N, then interpolate between adjacent centroid means. The tiny tail centroids make that interpolation precise at p99/p999.
Rank query. The inverse — given a value, sum the counts of centroids below it to estimate its percentile (useful for "what percentile is this 800 ms request").

Merging t-digests across shards.

Concatenate then re-compress. Merge is: take the union of both centroid lists, sort by mean, and re-cluster under the scale function into a fresh bounded digest. The result approximates the digest of the combined stream within the same error.
Order-insensitive in the limit. Because merging re-clusters from means, the combined digest is (nearly) independent of shard order — the property a reducer needs.
This is the production superpower. Each shard ships a few kilobytes of centroids; the reducer merges them; fleet-wide p99 falls out without shipping a single raw latency.

t-digest vs KLL vs Greenwald-Khanna.

t-digest. Excellent relative accuracy at the tails, tiny, mergeable, hugely popular — but no strict worst-case rank-error bound; accuracy is empirical and can degrade on adversarial inputs.
KLL. A newer quantile sketch with a provable (ε, rank) guarantee (the answer's rank is within ε·N of the query), mergeable, and the basis of Apache DataSketches quantiles — pick it when you must prove the error.
Greenwald-Khanna (GK). The classic deterministic ε-approximate quantile summary with a worst-case rank bound; mergeable but historically fiddlier to merge than KLL.

Common interview probes on t-digest.

"Why is t-digest more accurate at p99 than a histogram?" — required answer: centroids are small at the tails (scale function), so tail resolution is high.
"What is a centroid?" — a (mean, count) cluster; the digest is a sorted, bounded list of them.
"How do you merge two t-digests?" — union the centroids, sort by mean, re-cluster under the scale function.
"When would you use KLL instead?" — when you need a provable worst-case rank-error bound, not just empirical tail accuracy.

Worked example — build a t-digest and query p99

Detailed explanation. Implement a compact t-digest (buffer-and-merge style) and push a right-skewed latency stream through it, then query p50, p99, and p999 and compare to the exact values. The skew mimics real latency: most requests fast, a heavy right tail.

Config. compression δ = 100.
Stream. 100,000 latencies: a lognormal-like bulk plus a small fraction of slow outliers.
Query. p50, p99, p999.

Question. Implement the digest, ingest the stream, and report the three quantiles against exact.

Input.

Parameter	Value
Compression δ	100
Stream size N	100,000
Distribution	right-skewed latency (ms)
Queries	p50, p99, p999

Code.

import bisect, math

class TDigest:
    def __init__(self, compression: float = 100.0):
        self.delta = compression
        self.centroids = []   # sorted list of [mean, count]
        self.n = 0

    def _k_to_q_limit(self, q: float) -> float:
        # centroid size limit at quantile q: small near 0/1, large near 0.5
        return 4 * self.n * (1.0 / self.delta) * q * (1 - q) + 1

    def update(self, x: float, w: int = 1) -> None:
        self.n += w
        self.centroids.append([x, w])
        if len(self.centroids) > 10 * self.delta:  # buffer full -> compress
            self._compress()

    def _compress(self) -> None:
        self.centroids.sort(key=lambda c: c[0])
        merged, cum = [], 0.0
        for mean, count in self.centroids:
            if not merged:
                merged.append([mean, count]); cum = count; continue
            q = (cum + count / 2) / self.n
            limit = self._k_to_q_limit(q)
            m0, c0 = merged[-1]
            if c0 + count <= limit:                 # absorb into current centroid
                merged[-1][0] = (m0 * c0 + mean * count) / (c0 + count)
                merged[-1][1] = c0 + count
            else:                                   # start a new centroid
                merged.append([mean, count])
            cum += count
        self.centroids = merged

    def quantile(self, q: float) -> float:
        self._compress()
        target, cum = q * self.n, 0.0
        for i, (mean, count) in enumerate(self.centroids):
            if cum + count >= target:
                if i == 0:
                    return mean
                pm, pc = self.centroids[i - 1]
                frac = (target - cum) / count       # interpolate between means
                return pm + (mean - pm) * frac
            cum += count
        return self.centroids[-1][0]

    def merge(self, other: "TDigest") -> "TDigest":
        out = TDigest(self.delta)
        out.centroids = [c[:] for c in self.centroids] + [c[:] for c in other.centroids]
        out.n = self.n + other.n
        out._compress()
        return out

Step-by-step explanation.

update appends each value as a singleton centroid into a buffer and only triggers _compress when the buffer grows past 10·δ. Buffering means the expensive sort happens once per batch, not per value — the standard amortisation that keeps ingestion fast.
_compress sorts the centroids by mean and sweeps left to right, folding each into the previous centroid only if the combined count stays under the scale-function limit _k_to_q_limit(q). That limit is small when q is near 0 or 1 and large near 0.5, which is what forces tiny tail centroids and fat middle centroids.
The limit formula 4·N·(1/δ)·q·(1−q) + 1 is the q(1−q) shape in action: at q = 0.5 it is largest (centroids can be big), and it shrinks toward the tails (centroids must stay small). This is the whole trick that makes p99 accurate.
quantile accumulates centroid counts until it passes q·N, then linearly interpolates between the two straddling centroid means. Because tail centroids are tiny, the interpolation interval at p99 is narrow, so the answer is close to exact.
merge simply unions the two centroid lists and re-compresses — the same code path, which is why merge and update share accuracy behaviour. The digest stays a few hundred centroids no matter how many values or merges it has seen.

Output.

Quantile	Exact (ms)	t-digest (ms)	Relative error
p50	100.0	~100.4	~0.4%
p99	512.0	~510	~0.4%
p999	1180.0	~1173	~0.6%
Centroids stored	100,000 (exact)	~180	—

Rule of thumb. Read a t-digest as "accurate where it is steep" — tails are tight, the middle is coarse. That is the correct default for latency SLOs, where p99 and p999 are the numbers that matter and p50 rarely does.

Worked example — merging t-digests across shards

Detailed explanation. The reason t-digest dominates fleet monitoring is that per-shard digests merge into a global digest that answers p99 for the whole fleet — without shipping raw latencies. Build one digest per shard on disjoint slices of the same latency population, merge them, and compare the merged p99 to a digest built over all values at once.

Setup. 4 shards, each ingesting 25,000 latencies from the same distribution.
Merge. Fold the four digests pairwise into one.
Check. Merged p99 ≈ single-digest p99.

Question. Build four shard digests, merge them, and confirm the merged p99 matches an all-at-once digest.

Input.

Shard	Values	Local p99 (ms)
1	25,000	~509
2	25,000	~514
3	25,000	~511
4	25,000	~513

Code.

from functools import reduce

# Each shard builds its digest independently, in parallel, no coordination
shard_digests = []
for shard_values in (shard1, shard2, shard3, shard4):
    td = TDigest(compression=200)
    for v in shard_values:
        td.update(v)
    shard_digests.append(td)          # only ~2 KB of centroids leaves each shard

# Reducer folds them — merge is associative, so order does not matter
global_td = reduce(lambda a, b: a.merge(b), shard_digests)

# Compare against a digest built over every value at once
reference = TDigest(compression=200)
for v in shard1 + shard2 + shard3 + shard4:
    reference.update(v)

print("merged  p99:", round(global_td.quantile(0.99), 1))
print("single  p99:", round(reference.quantile(0.99), 1))

Step-by-step explanation.

Each shard ingests its 25,000 values into a local digest with no cross-shard communication. The heavy work — touching every latency — happens locally and in parallel, exactly as with Count-Min.
Only the centroid lists (a couple of kilobytes each) leave the shards. This is the bandwidth win: merging p99 across a 400-node fleet moves kilobytes, not the terabytes of raw latency the exact method would require.
reduce(merge, ...) folds the digests in a chain (a tree in a real reducer). Merge is associative because it re-clusters from centroid means, so any fold order yields the same result within the error bound.
The merged p99 lands within a fraction of a percent of the reference digest built over all values at once. Small discrepancies come from re-compression at merge time, bounded by the compression parameter — raise δ to shrink it.
This is precisely the pattern Druid and Spark use: sketch per partition, merge at query. The digest's order-insensitive merge is what makes "p99 by region, then p99 across all regions" a matter of choosing which digests to fold.

Output.

Metric	Value
Merged p99 (ms)	~512
Single-digest p99 (ms)	~512
Difference	< 0.3%
Bytes shipped per shard	~2 KB
Raw latencies shipped	0

Rule of thumb. Build one digest per partition and merge at the reducer. Because merge re-clusters from means, the fold order is irrelevant and any dimensional slice (region, service, time bucket) is just a different set of digests to combine.

Worked example — why the tails are accurate (scale-function intuition)

Detailed explanation. The tail accuracy is not magic; it is the scale function spending centroids where quantiles change fast. Contrast t-digest with an equal-width histogram on the same skewed latency stream and show that the histogram's fixed buckets blur the tail while t-digest resolves it.

Histogram. 200 equal-width buckets from min to max. With a heavy tail, almost all buckets sit in the sparse tail region or the dense head, wasting resolution.
t-digest. ~200 centroids placed by k(q); density follows the data, concentrating at both tails.
The measurement. Estimate p999 with each and compare error.

Question. Compare p999 error between an equal-width histogram and a t-digest of the same size.

Input.

Structure	Size	Placement	p999 error
Equal-width histogram	200 buckets	fixed edges	large (blurred tail)
t-digest	~200 centroids	scale-function adaptive	small

Code.

def equal_width_p999(values, buckets=200):
    lo, hi = min(values), max(values)
    width  = (hi - lo) / buckets
    counts = [0] * buckets
    for v in values:
        idx = min(int((v - lo) / width), buckets - 1)
        counts[idx] += 1
    target, cum = 0.999 * len(values), 0
    for i, c in enumerate(counts):
        cum += c
        if cum >= target:
            return lo + (i + 0.5) * width         # bucket midpoint = coarse guess
    return hi

def tdigest_p999(values, compression=200):
    td = TDigest(compression)
    for v in values:
        td.update(v)
    return td.quantile(0.999)

exact_p999 = sorted(latencies)[int(0.999 * len(latencies))]
print("exact   p999:", round(exact_p999, 1))
print("hist    p999:", round(equal_width_p999(latencies), 1))   # coarse at tail
print("tdigest p999:", round(tdigest_p999(latencies), 1))       # tight at tail

Step-by-step explanation.

The equal-width histogram divides the entire [min, max] range into 200 fixed buckets. With a heavy tail, the max is far out, so each bucket is wide — and the p999 lands inside one wide tail bucket whose midpoint can be off by tens of milliseconds.
The histogram cannot fix this by adding buckets in the middle; its accuracy at the tail is set by the range, not the data density, so a few extreme outliers stretch every bucket and blur the very quantile you asked for.
The t-digest places centroids by quantile position, not value position. Near q = 0.999 the scale function forces tiny centroids, so the digest keeps fine-grained structure exactly where the histogram is coarsest.
The result: the t-digest's p999 sits within a fraction of a percent of exact, while the equal-width histogram's p999 can be off by a large margin — same memory, very different tail resolution.
The lesson generalises: any fixed-bucket scheme hard-codes where accuracy lives, and for latency the tail is unknowable in advance. t-digest (and KLL) adapt to the data, which is why they, not histograms, back serious percentile systems.

Output.

Method	p999 estimate (ms)	Error vs exact
Exact	1180	0
Equal-width histogram	~1240	~5%
t-digest	~1173	~0.6%

Rule of thumb. If the tail matters, do not use equal-width histograms — their accuracy is dictated by the range, so a single outlier blurs every bucket. Use a t-digest (or KLL) whose resolution follows the data to the tail.

Statistics interview question on approximate quantiles

A senior interviewer might ask: "You run 500 service replicas and need a fleet-wide p50/p95/p99/p999 latency dashboard refreshed every 10 seconds, sliceable by service and region, and you cannot ship raw latencies off the hosts. Design the quantile pipeline — the per-replica structure, the merge, the accuracy you'd promise at p999, and how you'd choose the compression."

Solution Using per-replica t-digests merged at the collector

# quantile_pipeline.py — per-replica t-digest, merged per (service, region) slice
from collections import defaultdict
from functools import reduce

# 1. On each replica: fold latencies into a local digest, flush every 10s
class ReplicaAgg:
    def __init__(self, compression=200):
        self.td = TDigest(compression)

    def observe(self, latency_ms: float) -> None:
        self.td.update(latency_ms)

    def flush(self) -> "TDigest":
        out, self.td = self.td, TDigest(self.td.delta)   # swap out, reset
        return out                                        # ~2-4 KB of centroids

# 2. At the collector: group incoming digests by slice key, merge each group
def collect(digests_by_slice: dict[tuple, list["TDigest"]]) -> dict:
    dashboard = {}
    for slice_key, digests in digests_by_slice.items():
        merged = reduce(lambda a, b: a.merge(b), digests)
        dashboard[slice_key] = {
            "p50":  merged.quantile(0.50),
            "p95":  merged.quantile(0.95),
            "p99":  merged.quantile(0.99),
            "p999": merged.quantile(0.999),
        }
    return dashboard

# 3. "All regions for service X" = merge every region's slice digest
def rollup(service: str, dashboard_digests: dict[tuple, "TDigest"]) -> dict:
    parts = [d for (svc, _region), d in dashboard_digests.items() if svc == service]
    merged = reduce(lambda a, b: a.merge(b), parts)
    return {q: merged.quantile(v) for q, v in
            {"p50": .5, "p95": .95, "p99": .99, "p999": .999}.items()}

Step-by-step trace.

Layer	Component	Purpose
Replica	ReplicaAgg t-digest (c=200)	fold latencies locally; flush ~3 KB every 10s
Wire	centroid lists	kilobytes per replica, not raw samples
Collector	merge per (service, region)	associative fold -> one digest per slice
Rollup	merge slices sharing a service	cross-region p99 = union of region digests
Dashboard	quantile(q) per slice	p50/p95/p99/p999 with tail-tight accuracy

After deployment, each of the 500 replicas ships a ~3 KB digest every 10 seconds. The collector merges per slice and can roll up any union of slices, so "p99 for checkout across all regions" is a fold of the checkout digests. p999 stays within roughly half a percent because compression 200 keeps ample tail centroids; raising compression tightens it at a linear memory cost.

Output:

Slice	p50 (ms)	p95 (ms)	p99 (ms)	p999 (ms)
checkout / us-east	42	180	512	1170
checkout / eu-west	45	190	528	1205
checkout / all (rollup)	43	185	519	1188
Bytes/replica/flush	~3 KB	—	—	—

Why this works — concept by concept:

Per-replica t-digest — each replica summarises its own latencies into a few hundred centroids, so the raw samples never leave the host and the ingestion cost is a cheap buffered merge.
Scale-function tail accuracy — compression 200 forces small centroids near q = 0.999, so p999 — the number the SLO cares about — is resolved tightly while the middle stays deliberately coarse.
Associative merge = arbitrary slices — because merging re-clusters from means, any dimensional rollup (service, region, or their union) is just a different set of digests to fold, computed at query time.
Compression is the accuracy knob — higher compression buys more centroids and tighter tails at linear memory cost; you choose it from the p999 error you must promise, not from a guess.
Cost — O(1) amortised per observation on the replica, O(centroids) bytes per flush (~3 KB, independent of request volume), and O(slices × digests) merges at the collector. The eliminated cost is shipping and storing every raw latency to compute exact percentiles.

Statistics
Topic — statistics
Quantile and percentile estimation problems

Practice →

Data Structures Topic — data-structures Streaming summary structure problems

Practice →

4. Error bounds & sizing

Sketch memory is a function of the error you demand — `ε` sets the width, `δ` sets the confidence, and additive vs relative error decides whether the sketch can even answer your question

The one-sentence invariant: every sketch exposes an error budget you must set from the question — for a Count-Min sketch the width is w = ⌈e/ε⌉ and the depth is d = ⌈ln(1/δ)⌉, giving an additive error of at most ε·N with probability 1 − δ at a cost of w·d counters; for a t-digest the compression δ_t sets the centroid budget and the relative tail accuracy — and the single most important judgement is whether the sketch's error is additive (a fixed slice of the total, fatal for rare keys) or relative (scales with the answer, right for cardinality and tails). Sizing is not guesswork: you state the budget or the tolerance, and the formulas give the other.

The Count-Min error theorem, in plain terms.

The guarantee. For a Count-Min sketch with width w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉, the estimate f̂(x) satisfies f(x) ≤ f̂(x) ≤ f(x) + ε·N with probability at least 1 − δ, where N is the total weight (sum of all counts).
ε is the additive error fraction. The overshoot is bounded by ε times the whole stream's weight — not the key's own count. Halve ε, double the width, halve the overshoot.
δ is the failure probability. With probability up to δ the bound can be exceeded (all d rows happened to collide badly). Add rows to shrink δ; each row multiplies the failure probability by roughly 1/e.
Memory falls out. space = w·d counters = ⌈e/ε⌉·⌈ln(1/δ)⌉. Width dominates the memory because 1/ε grows fast while ln(1/δ) grows slowly — you buy accuracy mostly by widening.

Additive vs relative error — the judgement that decides the sketch.

Additive (± ε·N). Count-Min. The error is a fixed number of "stream units". For a heavy key (count ≫ ε·N) it is negligible; for a rare key (count ≲ ε·N) it swamps the true value. Count-Min is therefore a heavy-hitters tool, not a rare-key tool.
Relative (± ε·true). HyperLogLog (cardinality), t-digest/KLL at the tails. The error scales with the answer, so small answers get small absolute error — the right model when the small values matter.
The trap. Using Count-Min to ask "how many keys appeared exactly once" is hopeless: ε·N is enormous relative to a count of 1, so every rare key's estimate is dominated by collision noise. Know which error type your question needs before sizing.
The tell in an interview. Saying "Count-Min gives additive error, so it's for heavy hitters, not rare keys" is the senior signal that you understand the bound, not just the formula.

t-digest sizing.

Compression δ_t sets the budget. Centroid count is roughly O(δ_t) (a few times δ_t in practice). Compression 100 → ~hundreds of centroids → a couple of kilobytes; compression 500 → more centroids, tighter tails, ~10 KB.
Accuracy is relative and tail-tight. t-digest promises small relative error that is smallest at the extremes; there is no simple closed-form worst-case bound (that is KLL's territory), so you validate empirically against exact on representative data.
Choose from the p-you-care-about. If you page on p999, pick compression high enough that p999 error is within tolerance on your data; p50 will be more than accurate enough regardless.

Working backward from the requirement.

From a memory budget. Given B bytes and 4-byte counters, w·d ≤ B/4. Fix δ (hence d), then w = B/(4d) gives the achievable ε = e/w. State the resulting error.
From an accuracy target. Given a required ε and δ, compute w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉, and report the memory. If it exceeds budget, either relax ε or accept that the question needs a different structure.
From a heavy-hitter threshold. To reliably find φ-heavy hitters, set ε a factor (say 5–10×) below φ so the additive band cannot lift a sub-threshold key over the line.

Common interview probes on sizing.

"How do you size a Count-Min sketch?" — required answer: w = ⌈e/ε⌉, d = ⌈ln(1/δ)⌉, memory w·d.
"What error does it guarantee?" — additive ε·N, one-sided, with confidence 1 − δ.
"Why is Count-Min bad for rare keys?" — additive error ε·N swamps small counts.
"How do you pick t-digest compression?" — from the p999 error you must hit on representative data; centroid count ≈ O(compression).

Worked example — size a Count-Min from a memory budget

Detailed explanation. Given a 1 MB budget and a required confidence, derive the achievable error and check it against a heavy-hitter threshold. This is the calculation you do on a whiteboard before writing any code.

Budget. 1 MB = 1,048,576 bytes, 4-byte counters → 262,144 counters total.
Confidence. Want δ = 0.001 → d = ⌈ln(1000)⌉ = ⌈6.9⌉ = 7 rows.
Derive ε. w = floor(262144 / 7) = 37,449 columns → ε = e/w ≈ 2.718 / 37449 ≈ 7.3e-5.

Question. For a 1 MB budget and δ = 0.001, compute w, d, ε, and the additive error on a stream of N = 2×10^9. Can it find 0.1%-heavy hitters?

Input.

Given	Value
Budget	1 MB (262,144 counters)
δ	0.001
Stream weight N	2,000,000,000
Heavy-hitter threshold φ	0.001 (0.1%)

Code.

import math

BYTES        = 1_048_576
COUNTER_SIZE = 4
delta        = 0.001
N            = 2_000_000_000
phi          = 0.001

d = math.ceil(math.log(1 / delta))          # depth from delta
w = (BYTES // COUNTER_SIZE) // d             # width from remaining budget
eps = math.e / w                             # achievable additive fraction

additive_error = eps * N                     # worst-case overshoot in counts
threshold      = phi * N                     # a 0.1%-heavy hitter has this many

print(f"d = {d} rows")                       # 7
print(f"w = {w} cols")                       # ~37449
print(f"eps = {eps:.2e}")                    # ~7.3e-5
print(f"additive error = {additive_error:,.0f}")   # ~145,000
print(f"heavy-hitter threshold = {threshold:,.0f}") # 2,000,000
print(f"error / threshold = {additive_error/threshold:.3f}")  # ~0.07

Step-by-step explanation.

Start from confidence: δ = 0.001 needs d = ⌈ln(1/0.001)⌉ = ⌈ln 1000⌉ = ⌈6.9⌉ = 7 rows. Depth is cheap — it grows only logarithmically in 1/δ — so buying high confidence costs little memory.
Spend the rest of the budget on width: 262144 / 7 ≈ 37,449 columns. Width is where the memory goes, and width is what tightens the additive error.
The achievable error fraction is ε = e/w ≈ 7.3×10⁻⁵. On a stream of N = 2×10⁹, the worst-case additive overshoot is ε·N ≈ 145,000 counts.
A 0.1%-heavy hitter has φ·N = 2,000,000 occurrences. The additive error (145,000) is about 7% of that threshold — comfortably below it, so genuine 0.1%-heavy hitters stand well clear of the noise band and cannot be confused with sub-threshold keys.
The check error/threshold ≈ 0.07 ≪ 1 is the sign-off: the sketch fits the budget and resolves the heavy hitters you care about. Had the ratio approached 1, you would need more width (more memory) or a looser threshold.

Output.

Quantity	Value
Depth d	7
Width w	37,449
ε	7.3e-5
Additive error (ε·N)	~145,000
0.1% threshold (φ·N)	2,000,000
Error / threshold	~0.07 (safe)

Rule of thumb. Size depth from δ first (it is cheap), then spend all remaining memory on width to minimise ε. Confirm ε·N is well under your heavy-hitter threshold φ·N — a ratio under ~0.1 means genuine heavy hitters are safe from collision noise.

Worked example — additive vs relative error, side by side

Detailed explanation. Make the additive-vs-relative distinction concrete by asking two questions of the same stream: "how big is the heaviest key" (heavy — additive error fine) and "how many singletons" (rare — additive error fatal). Show numerically why Count-Min answers the first and cannot answer the second.

Stream. N = 10^9 with one key at 5% (5×10^7) and millions of singletons.
Additive band. With ε = 10^-4, the band is ε·N = 10^5.
Verdict. For the 5% key, 10^5 overshoot on 5×10^7 is 0.2% relative — fine. For a singleton, 10^5 overshoot on 1 is a 100,000× error — useless.

Question. Compute the relative impact of the same additive band on a heavy key and a rare key, and state which questions Count-Min can answer.

Input.

Key type	True count	Additive band ε·N	Relative impact
Heavy (5%)	50,000,000	100,000	0.2%
Mid (0.01%)	100,000	100,000	100%
Rare (singleton)	1	100,000	100,000×

Code.

N   = 1_000_000_000
eps = 1e-4
band = eps * N                       # 100,000 additive overshoot

for label, true in [("heavy 5%", 50_000_000),
                    ("mid 0.01%", 100_000),
                    ("rare x1", 1)]:
    relative = band / true
    verdict  = "usable" if relative < 0.1 else "useless"
    print(f"{label:10s} true={true:>12,}  band/true={relative:>10.2%}  -> {verdict}")

# heavy 5%   true=  50,000,000  band/true=     0.20%  -> usable
# mid 0.01%  true=     100,000  band/true=   100.00%  -> useless
# rare x1    true=           1  band/true= 10,000,000.00%  -> useless

Step-by-step explanation.

The additive band is a constant ε·N = 100,000, identical for every key regardless of its own frequency. That constancy is the entire character of additive error.
For the 5% heavy key (true 5×10⁷), a 100,000 overshoot is 0.2% — the estimate is essentially exact in relative terms. Count-Min nails heavy hitters.
For a mid key at the 0.01% mark (true 100,000), the band equals the true value — a potential 100% error. The estimate is worthless; the key is right at the edge of the noise floor.
For a singleton, the band is 100,000× the true value. Count-Min literally cannot distinguish a singleton from any other sub-band key — asking it "how many keys appeared once" is a category error.
The takeaway: Count-Min's noise floor is ε·N. Any question about keys near or below that floor (rare keys, exact tail frequencies, distinct-of-rare) needs a relative-error structure — HyperLogLog for distinctness, or simply exact if the rare-key set fits.

Output.

Key	True	Estimate band	Relative error	Count-Min usable?
Heavy 5%	50,000,000	+0–100,000	~0.2%	yes
Mid 0.01%	100,000	+0–100,000	up to 100%	no
Rare ×1	1	+0–100,000	up to 10⁷%	no

Rule of thumb. Count-Min's error floor is ε·N. If the answers you care about are smaller than that floor, the sketch is the wrong tool — switch to a relative-error structure or exact counting for the rare-key regime.

Worked example — t-digest compression vs accuracy sweep

Detailed explanation. Show the compression knob's effect by sweeping it and measuring p999 error and memory. This is how you choose compression from a promised accuracy rather than guessing.

Sweep. Compression ∈ {50, 100, 200, 500}.
Measure. p999 relative error and approximate centroid count (memory proxy).
Choose. The smallest compression that meets the p999 tolerance.

Question. Sweep compression and pick the smallest value meeting a 1% p999 tolerance.

Input.

Compression	~Centroids	~Memory	p999 error
50	~120	~2 KB	~1.8%
100	~220	~4 KB	~0.9%
200	~420	~7 KB	~0.5%
500	~1000	~16 KB	~0.2%

Code.

import bisect

def p999_error(values, compression) -> float:
    td = TDigest(compression)
    for v in values:
        td.update(v)
    est   = td.quantile(0.999)
    exact = sorted(values)[int(0.999 * len(values))]
    return abs(est - exact) / exact, len(td.centroids)

TOLERANCE = 0.01
choice = None
for c in (50, 100, 200, 500):
    err, ncent = p999_error(latencies, c)
    print(f"compression={c:4d}  centroids~{ncent:4d}  p999_err={err:.2%}")
    if choice is None and err <= TOLERANCE:
        choice = c

print("smallest compression meeting 1% p999:", choice)   # 100

Step-by-step explanation.

Each compression value builds a digest, queries p999, and compares to the exact p999 on the same data. This is the empirical validation t-digest requires — there is no closed-form bound to trust in place of measurement.
Error falls as compression rises: more centroids means smaller tail clusters and tighter interpolation at p999. The relationship is smooth and monotone, so the sweep is quick.
Memory rises roughly linearly with compression (centroid count ≈ O(compression)), so doubling compression roughly doubles the digest size — the standard accuracy-for-memory trade.
The chooser picks the smallest compression that meets the 1% tolerance — here compression 100 at ~0.9% error and ~4 KB. Going higher would only spend memory for accuracy the SLO does not require.
The method generalises: sweep on representative data, pick the cheapest setting that clears your promised tail error, and re-validate if the distribution shifts materially. Never pick compression by folklore ("100 is fine") without checking against your own p999.

Output.

Compression	Centroids	Memory	p999 error	Meets 1%?
50	~120	~2 KB	~1.8%	no
100	~220	~4 KB	~0.9%	yes ← pick
200	~420	~7 KB	~0.5%	yes (overkill)
500	~1000	~16 KB	~0.2%	yes (overkill)

Rule of thumb. Choose t-digest compression by sweeping on representative data and taking the smallest value that clears your p999 tolerance. Memory scales linearly with compression, so higher settings only make sense when the tail error must be tighter.

Data-engineering interview question on sketch sizing

A senior interviewer might ask: "You have 8 MB per worker for a frequency sketch and must reliably surface any key above 0.05% of the stream, plus answer point frequencies with a stated error, on a 5×10^9-weight stream. Size the Count-Min sketch, justify the depth and width split, quote the error, and say what breaks if the stream grows 10×."

Solution Using the ε/δ sizing formulas with a heavy-hitter margin

# size_cms.py — derive (w, d, eps) from budget, confidence, and HH threshold
import math

def size_cms(budget_bytes: int, counter_size: int, delta: float,
             N: int, phi: float, margin: float = 8.0) -> dict:
    counters = budget_bytes // counter_size
    d        = math.ceil(math.log(1 / delta))         # depth from confidence
    w        = counters // d                            # width from remaining budget
    eps      = math.e / w                               # achievable additive fraction

    additive = eps * N
    threshold = phi * N
    # require eps*N to sit at least `margin`x below the HH threshold
    safe = additive * margin <= threshold
    return {
        "d": d, "w": w, "eps": eps,
        "additive_error": additive,
        "hh_threshold": threshold,
        "ratio": additive / threshold,
        "safe_for_heavy_hitters": safe,
        "memory_mb": counters * counter_size / 1e6,
    }

cfg = size_cms(budget_bytes=8 * 1024 * 1024, counter_size=4,
               delta=1e-3, N=5_000_000_000, phi=5e-4)
for k, v in cfg.items():
    print(f"{k:24s} {v}")

Step-by-step trace.

Step	Value	Reasoning
Counters	2,097,152	8 MB / 4 bytes
Depth d	7	⌈ln(1/0.001)⌉
Width w	299,593	counters / d
ε	~9.1e-6	e / w
Additive error ε·N	~45,400	on N = 5e9
HH threshold φ·N	2,500,000	0.05% of 5e9
Ratio	~0.018	ε·N well under threshold

The 8 MB budget yields d = 7, w ≈ 299,593, and ε ≈ 9.1×10⁻⁶. On the 5×10⁹ stream the additive band is ~45,400 — about 1.8% of the 2,500,000 heavy-hitter threshold, so any key above 0.05% is safely separable from noise. Depth is fixed by confidence (cheap, logarithmic); everything else went to width to minimise ε.

Output:

Requirement	Result	Status
Fits 8 MB	2.1M counters	yes
Confidence 1 − δ	0.999 (d=7)	met
ε·N vs 0.05% threshold	~1.8% of it	safe (8× margin)
Point-frequency error	≤ ~45,400, one-sided	stated
Stream grows 10× (N=5e10)	ε·N → ~454,000	still 18% of threshold — degraded but safe

Why this works — concept by concept:

Depth from δ, width from budget — d = ⌈ln(1/δ)⌉ buys confidence logarithmically, so it is set first and cheaply; the remaining ~2.1M counters go entirely to width to drive ε down.
ε·N is the noise floor — the additive error scales with the total stream weight N, not the key's count, so the sizing check is always "is ε·N well below φ·N", i.e. is the margin big enough.
Heavy-hitter margin — requiring ε·N to sit ~8× under the threshold guarantees a sub-threshold key cannot be over-estimated across the line, which is what "reliably surface any key above 0.05%" demands.
Graceful growth — if N grows 10×, ε·N grows 10× too (to ~454,000), still only ~18% of the threshold; the sketch degrades predictably rather than failing, and you would rewiden only if the margin got tight.
Cost — O(w·d) space (fixed at ~8 MB), O(d) per update/query (constant). The error is O(ε·N) additive; the only thing that erodes it is a growing N, which is a known, quantifiable dial — not a surprise.

Statistics
Topic — statistics
Error-bound and confidence-interval problems

Practice →

Cardinality Topic — cardinality Sketch sizing and accuracy problems

Practice →

5. Sketches in production — Spark / Druid / monitoring

The production pattern is always the same — sketch at ingest, store the sketch, merge at query — and Spark, Druid, and metrics backends each expose `mergeable summaries` as first-class objects

The one-sentence invariant: in every production system that scales approximate aggregation — Spark batch jobs, Druid OLAP rollups, and percentile-based monitoring — the sketch is computed once per partition or per ingest interval, the sketch object itself (not the raw data) is stored and shipped, and queries merge the relevant sketches on demand, so the expensive pass over raw data happens once and any slice or rollup is answered by an O(sketch size) merge. Spark exposes approx_count_distinct and percentile_approx plus the Apache DataSketches UDAFs; Druid stores quantile/cardinality/frequency sketches in segments; monitoring systems store t-digest/DDSketch objects so p99 merges across hosts.

Spark — approximate aggregation built in and via DataSketches.

Built-in functions. approx_count_distinct(col, rsd) uses HyperLogLog++ with a target relative standard deviation; percentile_approx(col, p, accuracy) computes quantiles with an accuracy knob (higher = more memory, tighter).
Apache DataSketches UDAFs. The datasketches-spark package adds mergeable KLL quantiles, Theta (set-operation cardinality), and Frequent-Items sketches usable in groupBy(...).agg(...). Because they are mergeable, Spark computes partial sketches per partition and combines them in the shuffle — no raw-row aggregation.
Why it matters. A groupBy(region).agg(sketch(...)) builds one sketch per region by merging partial per-partition sketches; the sketch column can be persisted and later merged across regions without re-reading the source.
The persistence trick. Store the serialized sketch as a column. Tomorrow's "distinct users over the last 7 days" merges 7 daily sketch rows — an O(7) merge instead of a re-scan of a week of events.

Druid — sketches as aggregators at ingestion.

Ingest-time rollup. Druid can apply sketch aggregators during ingestion so each segment stores, per dimension combination, a quantilesDoublesSketch (KLL), thetaSketch or HLLSketch (cardinality), and frequency sketches — instead of raw rows.
Query-time merge. A query over a time range and dimension filter merges the pre-built segment sketches. The cost is proportional to the number of segments touched, not the number of raw events they summarise.
The extension. The druid-datasketches extension provides these aggregators; a quantilesDoublesSketch field answers p50/p95/p99 for any slice by merging segment sketches at query time.
Why it wins. Retention of raw events is expensive and often unnecessary; retaining sketches gives bounded storage and mergeable quantiles/cardinalities across arbitrary time-and-dimension slices.

Monitoring — histograms, summaries, and why mergeability decides.

Prometheus histogram. A fixed set of cumulative buckets per series. Buckets are mergeable across instances (sum the bucket counts), so fleet-wide quantiles are computable via histogram_quantile(...) — but accuracy is bounded by bucket layout, which is hard to pick for wide-range latency.
Prometheus summary. Computes quantiles client-side on each instance and exposes them directly. Summaries are not mergeable — you cannot average per-instance p99s into a fleet p99 — which quietly makes cross-instance percentiles impossible. This is the canonical monitoring trap.
DDSketch. A relative-error quantile sketch (Datadog's) with a guaranteed relative-error bound and full mergeability, so fleet-wide p99 with a promised error is a merge of per-host DDSketches. It is the answer to the summary's non-mergeability.
t-digest backends. Many metrics stores use t-digest for the same reason: mergeable, tail-accurate percentiles across hosts and time.

The universal contract.

Sketch at ingest. Build the sketch where the raw data first lands — per Spark partition, per Druid segment, per monitored host.
Store the sketch. Persist the serialized sketch object; discard or cold-store the raw data.
Merge at query. Any slice, rollup, or time range is a merge of the relevant sketches — associative, cheap, and independent of the raw event count.

Common interview probes on production sketches.

"How does Spark compute an approximate distinct count?" — approx_count_distinct (HyperLogLog++), merged per partition in the shuffle.
"Why store sketches in Druid segments?" — mergeable pre-aggregation; query merges segment sketches instead of scanning raw rows.
"Why can't you average Prometheus summary quantiles?" — summaries are computed client-side and are not mergeable.
"What does DDSketch guarantee that t-digest doesn't?" — a provable relative-error bound with full mergeability.

Worked example — Spark percentile_approx and DataSketches KLL

Detailed explanation. Compute approximate quantiles and distinct counts in Spark two ways — the built-in percentile_approx / approx_count_distinct, and a mergeable DataSketches KLL column you can persist and re-merge later. Group by region so the per-partition-then-merge behaviour is visible.

Built-in. percentile_approx(latency, array(0.5, 0.95, 0.99), 10000) and approx_count_distinct(user_id, 0.01).
DataSketches. Build a KLL sketch per region, store it, and merge across days later.
Grouping. groupBy("region") so Spark merges partial sketches in the shuffle.

Question. Write the Spark job for both approaches and show the mergeable KLL persistence.

Input.

Column	Type	Question
region	string	group key
latency_ms	double	p50/p95/p99
user_id	long	distinct count

Code.

from pyspark.sql import functions as F

# 1. Built-in approximate aggregations, grouped by region
agg = (events
    .groupBy("region")
    .agg(
        F.expr("percentile_approx(latency_ms, array(0.5, 0.95, 0.99), 10000)").alias("pcts"),
        F.approx_count_distinct("user_id", 0.01).alias("distinct_users"),
    )
    .select(
        "region",
        F.col("pcts")[0].alias("p50"),
        F.col("pcts")[1].alias("p95"),
        F.col("pcts")[2].alias("p99"),
        "distinct_users",
    ))
agg.show()

-- 2. Apache DataSketches (SQL / UDAF form): mergeable KLL quantile sketch per region
--    Persist the sketch column so it can be merged across days without re-scanning.
CREATE TABLE region_latency_sketch AS
SELECT
    region,
    kll_sketch_agg(latency_ms) AS latency_kll   -- mergeable sketch object
FROM events
GROUP BY region;

-- 3. Later: fleet p99 for the last 7 days = merge 7 daily sketch rows (no re-scan)
SELECT
    region,
    kll_sketch_get_quantile(kll_sketch_merge(latency_kll), 0.99) AS p99_7d
FROM   region_latency_sketch_daily
WHERE  day >= current_date - INTERVAL 7 DAYS
GROUP  BY region;

Step-by-step explanation.

percentile_approx(col, ps, accuracy) computes the requested quantiles in one pass; the accuracy argument (10,000 here) is the memory/accuracy knob — higher trades RAM for tighter quantiles. Spark builds partial summaries per partition and merges them in the shuffle triggered by groupBy.
approx_count_distinct(user_id, 0.01) is HyperLogLog++ with a 1% target relative standard deviation. Like the quantile function, it is mergeable, so the per-region distinct count is a merge of per-partition HLLs — never an exact countDistinct shuffle of all user IDs.
The DataSketches kll_sketch_agg builds a serializable, mergeable KLL quantile sketch per region and stores it as a column. This is the crucial difference from the built-in: the sketch object is persisted, not just a scalar quantile.
Because the stored KLL is mergeable, "p99 over the last 7 days" is kll_sketch_get_quantile(kll_sketch_merge(daily_sketches), 0.99) — an O(7) merge of daily sketch rows, not a re-scan of a week of raw events. This is the persistence trick that makes rolling windows cheap.
KLL (unlike t-digest) carries a provable (ε, rank) guarantee, so when an SLA requires a stated quantile error, the DataSketches path is preferable to percentile_approx, whose accuracy is empirical.

Output.

region	p50	p95	p99	distinct_users
us-east	42	180	512	1,204,880
eu-west	45	190	528	843,207
ap-south	51	205	560	512,006

Rule of thumb. Use percentile_approx / approx_count_distinct for one-shot approximate answers, but persist a mergeable DataSketches column when you need rolling windows or cross-slice rollups — storing the sketch object turns a re-scan into an O(days) merge.

Worked example — Druid quantiles sketch at ingestion

Detailed explanation. Configure a Druid ingestion spec to build a quantilesDoublesSketch (KLL) on latency at rollup time, then query p99 for a dimension slice by merging segment sketches. The raw latencies are never stored — only the sketch per segment.

Ingest. A quantilesDoublesSketch metric on latency_ms with a chosen k (accuracy/size).
Store. Each segment holds the sketch per dimension combination.
Query. A quantilesDoublesSketch post-aggregator merges segment sketches and reads p99.

Question. Write the Druid ingestion metricsSpec and the query that returns p99 latency by region.

Input.

Field	Role
region	dimension
latency_ms	sketched metric
k	sketch accuracy (e.g. 256)

Code.

// Ingestion metricsSpec — build a KLL quantiles sketch on latency at rollup
{
  "metricsSpec": [
    { "type": "count", "name": "events" },
    {
      "type": "quantilesDoublesSketch",
      "name": "latency_sketch",
      "fieldName": "latency_ms",
      "k": 256
    }
  ],
  "granularitySpec": { "queryGranularity": "minute", "rollup": true }
}

// Query — merge segment sketches and read p99 by region
{
  "queryType": "groupBy",
  "dataSource": "requests",
  "granularity": "all",
  "dimensions": ["region"],
  "intervals": ["2026-09-05/2026-09-06"],
  "aggregations": [
    { "type": "quantilesDoublesSketch", "name": "merged_latency", "fieldName": "latency_sketch" }
  ],
  "postAggregations": [
    {
      "type": "quantilesDoublesSketchToQuantile",
      "name": "p99_latency",
      "field": { "type": "fieldAccess", "fieldName": "merged_latency" },
      "fraction": 0.99
    }
  ]
}

Step-by-step explanation.

The quantilesDoublesSketch metric in the ingestion spec tells Druid to fold latency_ms into a KLL sketch during rollup, with k = 256 setting the accuracy/size. Each segment ends up storing the sketch per dimension combination rather than the raw latencies.
Because rollup is on, many raw rows collapse into one sketch per (minute, region, …) bucket — bounded storage that grows with dimension cardinality and time, not with raw event volume.
At query time, the quantilesDoublesSketch aggregator merges the sketches from every segment matching the interval and dimension filter. This merge is the KLL merge — associative and error-bounded — so the result is a single sketch for the whole slice.
The quantilesDoublesSketchToQuantile post-aggregator reads p99 off the merged sketch. Changing fraction to 0.95 or 0.5 answers other percentiles from the same merged sketch — no re-query of raw data.
The net effect mirrors Spark's persistence trick: sketch at ingest, merge at query. Adding a region filter or widening the interval simply changes which segment sketches are merged, and the cost scales with segment count, not raw event count.

Output.

region	merged sketch (retained values)	p99_latency (ms)
us-east	KLL, k=256	512
eu-west	KLL, k=256	528
ap-south	KLL, k=256	560

Rule of thumb. In Druid, sketch the metric at ingestion and let queries merge segment sketches. It bounds storage (no raw rows), keeps all percentiles queryable from one merged sketch, and makes any dimension/time slice an O(segments) merge.

Worked example — Prometheus histogram vs summary, and DDSketch

Detailed explanation. The most common monitoring mistake is picking a Prometheus summary and then discovering you cannot compute a fleet-wide p99. Contrast histogram (mergeable) with summary (not), and show why DDSketch/t-digest backends exist. This is a design decision, not a coding one, so the "code" is the metric definitions and the query.

Histogram. Cumulative buckets per series; mergeable across instances; histogram_quantile estimates percentiles from merged buckets.
Summary. Client-side quantiles per instance; not mergeable; averaging p99s is statistically wrong.
DDSketch. Relative-error, mergeable quantile sketch — fleet p99 with a guaranteed bound.

Question. Show a histogram vs summary metric and explain why only the histogram (or DDSketch) yields a correct fleet-wide p99.

Input.

Metric type	Mergeable?	Fleet p99 correct?
Histogram	yes (sum buckets)	yes (bucket-bounded)
Summary	no	no (cannot merge quantiles)
DDSketch	yes	yes (relative-error bound)

Code.

# Prometheus HISTOGRAM — buckets are mergeable across instances
request_latency_seconds_bucket{le="0.05"}  ...
request_latency_seconds_bucket{le="0.1"}   ...
request_latency_seconds_bucket{le="0.5"}   ...
request_latency_seconds_bucket{le="1.0"}   ...
request_latency_seconds_bucket{le="+Inf"}  ...

# Fleet-wide p99 = histogram_quantile over the SUM of buckets across instances
histogram_quantile(0.99, sum by (le) (rate(request_latency_seconds_bucket[5m])))

# Prometheus SUMMARY — quantiles computed CLIENT-SIDE, per instance
request_latency_seconds{quantile="0.5"}   ...
request_latency_seconds{quantile="0.9"}   ...
request_latency_seconds{quantile="0.99"}  ...

# There is NO correct way to combine these across instances:
#   avg(request_latency_seconds{quantile="0.99"})   <-- STATISTICALLY WRONG
# The average of per-host p99s is not the fleet p99.

Step-by-step explanation.

A histogram exposes cumulative bucket counts (le="0.1" = "requests ≤ 100 ms"). Bucket counts are additive, so summing them across instances gives the fleet's bucket counts — a valid merge. histogram_quantile then interpolates p99 from the merged buckets.
The histogram's accuracy is bounded by bucket layout: too-coarse buckets around the tail give a fuzzy p99. You must choose bucket edges up front, which is hard for latency spanning several orders of magnitude — the same weakness equal-width histograms had in section 3.
A summary computes quantiles on each instance and exports the numbers. There is no bucket structure to merge — only pre-computed p50/p90/p99 per host. Averaging per-host p99s does not yield the fleet p99 (the p99 of a union is not the mean of the parts' p99s), so cross-instance percentiles are simply unavailable.
This is the trap: a summary looks convenient (exact-looking quantiles per host) but silently forecloses fleet aggregation. Teams discover it only when they try to build a global dashboard and find no correct query.
DDSketch (and t-digest backends) resolve this by exporting a mergeable, relative-error sketch instead of pre-computed quantiles. Fleet p99 is a merge of per-host DDSketches with a guaranteed relative-error bound — the histogram's mergeability plus tail accuracy the fixed buckets lack.

Output.

Approach	Fleet p99 query	Correct?	Tail accuracy
Histogram	`histogram_quantile` over summed buckets	yes	bucket-bounded
Summary	none exists	no	n/a (not mergeable)
DDSketch / t-digest	merge sketches, read p99	yes	relative-error, tail-tight

Rule of thumb. For any metric you will aggregate across instances, never use a Prometheus summary — its quantiles are not mergeable. Use a histogram (mergeable, bucket-bounded) or a DDSketch/t-digest backend (mergeable, relative-error) so fleet-wide p99 is a correct merge.

Systems interview question on production sketches

A senior interviewer might ask: "Design fleet-wide latency monitoring for 2,000 hosts where on-call must see p50/p95/p99/p999 sliceable by service, region, and endpoint, refreshed every 15 seconds, with a stated accuracy bound at p99 — and explain why a Prometheus summary would sink the design. Give me the per-host structure, the merge, the storage, and the accuracy guarantee."

Solution Using per-host mergeable DDSketch merged per slice at the collector

# ddsketch_monitoring.py — per-host relative-error sketch, merged per slice
# DDSketch: buckets on a logarithmic value scale -> guaranteed relative error.
import math

class DDSketch:
    def __init__(self, relative_accuracy: float = 0.01):
        self.alpha = relative_accuracy
        self.gamma = (1 + self.alpha) / (1 - self.alpha)   # log base
        self.buckets: dict[int, int] = {}                   # index -> count
        self.count = 0

    def _index(self, value: float) -> int:
        return math.ceil(math.log(value, self.gamma))       # log-scale bucket

    def add(self, value: float) -> None:
        if value <= 0:
            return
        self.buckets[self._index(value)] = self.buckets.get(self._index(value), 0) + 1
        self.count += 1

    def merge(self, other: "DDSketch") -> "DDSketch":
        assert abs(self.alpha - other.alpha) < 1e-12, "accuracy must match"
        out = DDSketch(self.alpha)
        out.buckets = dict(self.buckets)
        for idx, c in other.buckets.items():
            out.buckets[idx] = out.buckets.get(idx, 0) + c   # add bucket counts
        out.count = self.count + other.count
        return out

    def quantile(self, q: float) -> float:
        target, cum = q * self.count, 0
        for idx in sorted(self.buckets):
            cum += self.buckets[idx]
            if cum >= target:
                return 2 * self.gamma ** idx / (self.gamma + 1)  # bucket representative
        return 0.0

# Collector — group per-host DDSketches by (service, region, endpoint) and merge
from functools import reduce
from collections import defaultdict

def fleet_quantiles(host_sketches: list[tuple]) -> dict:
    groups: dict[tuple, list[DDSketch]] = defaultdict(list)
    for slice_key, sk in host_sketches:          # slice_key = (service, region, endpoint)
        groups[slice_key].append(sk)
    out = {}
    for slice_key, sketches in groups.items():
        merged = reduce(lambda a, b: a.merge(b), sketches)
        out[slice_key] = {p: merged.quantile(v) for p, v in
                          {"p50": .5, "p95": .95, "p99": .99, "p999": .999}.items()}
    return out

Step-by-step trace.

Layer	Component	Purpose
Host	DDSketch(alpha=0.01)	log-scale buckets; guaranteed 1% relative error
Wire	bucket map	small, mergeable; no raw latencies
Collector	merge per (service, region, endpoint)	add bucket counts -> one sketch per slice
Rollup	merge slices sharing a service	any union of slices = another merge
Dashboard	quantile(q) per slice	p50/p95/p99/p999 within 1% relative

Each of the 2,000 hosts keeps a DDSketch with alpha = 0.01, so every reported quantile is within 1% relative error by construction — the log-scale buckets guarantee it. The collector merges by adding bucket counts, so any slice (service × region × endpoint) or rollup is a fold of the relevant sketches, refreshed every 15 seconds. A Prometheus summary would have exported per-host quantiles that cannot be merged, making the sliceable fleet p99 impossible — which is exactly why the design uses a mergeable sketch.

Output:

Slice	p50 (ms)	p95 (ms)	p99 (ms)	p999 (ms)	Guarantee
checkout / us-east / POST	42	180	512	1170	±1% relative
checkout / eu-west / POST	45	190	528	1205	±1% relative
checkout / all (rollup)	43	185	519	1188	±1% relative
Raw latencies shipped	0	—	—	—	—

Why this works — concept by concept:

DDSketch log-scale buckets — buckets sized geometrically (gamma = (1+α)/(1−α)) give a guaranteed relative-error bound at every quantile, so p999 carries the same 1% promise as p50 — unlike a fixed-bucket histogram.
Additive bucket merge — merging two DDSketches adds their bucket counts, an associative and exact operation, so fleet aggregation across 2,000 hosts is a clean fold with no accuracy loss from merging.
Slice by any dimension — because merge is associative, "p99 for checkout across all regions" is a fold of the matching per-host sketches, computed at query time from stored bucket maps.
Summary would sink it — a Prometheus summary exports pre-computed per-host quantiles with no mergeable structure; averaging them is statistically wrong, so the sliceable fleet p99 the design requires would be uncomputable.
Cost — O(1) per observation (a log and a dict bump), O(distinct buckets) bytes per host (tiny, grows logarithmically with value range), O(hosts per slice) merges at query. The eliminated cost is storing and shipping raw latencies to compute exact percentiles across the fleet.

Data Structures
Topic — data-structures
Mergeable-summary and streaming problems

Practice →

Statistics
Topic — statistics
Percentile-monitoring and accuracy problems

Practice →

Cheat sheet — data-sketch recipes

Sketch by the question. Frequency of a key or top-K → Count-Min (+ heap) or Frequent-Items; distinct count → HyperLogLog; quantile/percentile → t-digest or KLL; membership → Bloom filter. The family is fixed by the question; the wrong family cannot be fixed with more memory. Say the question, then name the sketch.
Count-Min sizing. w = ⌈e/ε⌉ (width sets the additive error), d = ⌈ln(1/δ)⌉ (depth sets the confidence), memory = w·d counters. Guarantee: f(x) ≤ f̂(x) ≤ f(x) + ε·N with probability 1 − δ, one-sided (never under-counts). Size depth from δ first (cheap, logarithmic), then spend the rest on width.
Heavy hitters recipe. Count-Min + a size-K min-heap keyed by estimate; on each event update the sketch, take the post-update estimate, and offer it to the heap (O(log K)). Keep ε 5–10× below your φ threshold so the additive band can never lift a tail key over a genuine heavy hitter.
Conservative update vs merge. Conservative update (raise only the minimum counters) tightens single-node estimates on skewed streams but breaks exact mergeability. Standard update (increment all d) is exactly mergeable (add grids). Pick one: accuracy on a single node, or mergeability across shards — never both.
t-digest recipe. Buffer values, sort, merge into centroids under the scale function k(q) so centroids stay tiny at the tails and grow in the middle; compression sets the centroid budget (≈ O(compression)) and thus tail accuracy. Query by accumulating counts to q·N and interpolating between centroid means. Merge = union centroids + re-compress (order-insensitive).
Quantile sketch choice. t-digest for excellent empirical tail accuracy, tiny and mergeable, but no closed-form worst-case bound. KLL for a provable (ε, rank) guarantee (Apache DataSketches). Greenwald-Khanna for a classic deterministic ε-rank summary. Use KLL when an SLA needs a stated quantile error.
Additive vs relative error. Additive (± ε·N, Count-Min): negligible for heavy keys, fatal for rare keys — a heavy-hitters tool. Relative (± ε·true, HyperLogLog, t-digest tails): error scales with the answer — right for cardinality and tail quantiles. The error floor of Count-Min is ε·N; any answer below it is noise.
Mergeability contract. Fix the sketch config centrally (same w/d/seeds for Count-Min, same compression for t-digest, same alpha for DDSketch) and ship it to every worker. Merge is associative — add grids, max HLL registers, union+re-compress centroids, add DDSketch buckets — so any fold order and any dimensional slice work.
Spark. approx_count_distinct(col, rsd) (HLL++), percentile_approx(col, p, accuracy) for one-shot answers; persist a mergeable Apache DataSketches KLL/Theta/Frequent-Items column when you need rolling windows or cross-slice rollups — a stored sketch turns a re-scan into an O(days) merge.
Druid. Sketch metrics at ingestion (quantilesDoublesSketch = KLL, thetaSketch/HLLSketch = cardinality) so segments store sketches, not raw rows; queries merge segment sketches. All percentiles come from one merged sketch; any slice is O(segments).
Monitoring anti-pattern. Never use a Prometheus summary for anything you aggregate across instances — its client-side quantiles are not mergeable and averaging per-host p99s is wrong. Use a histogram (mergeable, bucket-bounded) or a DDSketch/t-digest backend (mergeable, guaranteed relative error) for fleet-wide p99.
The universal pattern. Sketch at ingest (per partition / segment / host), store the sketch object (discard or cold-store raw data), merge at query for any slice or rollup. One O(N) pass over raw data; every subsequent question is an O(sketch size) merge.

Frequently asked questions

What is a data sketch in one sentence?

A data sketch is a compact, probabilistic summary of a data stream that is built in a single pass, occupies space sublinear in the number of items (often kilobytes for billions of events), answers a specific class of query — frequency, quantile, cardinality, or membership — with a mathematically bounded error, and is mergeable so the summary of two streams can be combined from their summaries alone. The whole point is to trade an exactness you almost never need for a memory footprint that does not grow with the data. That combination — one pass, sublinear, bounded error, mergeable — is exactly what distributed aggregation at scale requires, which is why sketches, not exact aggregates, back Spark, Druid, and modern metrics systems.

Count-Min sketch vs HyperLogLog — what does each answer?

They answer different questions and are not interchangeable. A count-min sketch estimates the frequency of a given key (how many times did X appear) and, with a companion heap, the top-K heavy hitters; its error is additive (± ε·N), which makes it excellent for heavy keys and useless for rare ones. HyperLogLog estimates the number of distinct keys (cardinality) with a relative error of about 1.04/√m for m registers; it has no per-key counter at all, so it cannot tell you a frequency. Picking between them is a category decision driven by the question — "how many times" is Count-Min, "how many distinct" is HyperLogLog — and no amount of extra memory lets one answer the other's question.

How does t-digest get accurate p99s?

t-digest clusters streaming values into centroids — (mean, count) pairs — whose allowed size is governed by a scale function k(q) that keeps clusters small near the tails (q close to 0 or 1) and lets them grow in the middle. Because the tail centroids are tiny and numerous, the digest keeps fine-grained structure exactly where percentiles like p99 and p999 live, and a quantile query interpolates between those small centroids to land close to the true value. An equal-width histogram, by contrast, hard-codes its resolution by value range, so a single outlier stretches every bucket and blurs the tail. t-digest gives excellent relative accuracy at the tails for a couple of kilobytes; if you need a provable worst-case bound instead, use a KLL sketch.

Are sketches mergeable across shards?

Yes — mergeability is a defining property, and it is what makes sketches distributed-native. A count-min sketch merges by adding its counter grids element-wise (exact, provided identical width, depth, and hash seeds); HyperLogLog merges by taking the register-wise maximum; a t-digest merges by unioning centroids and re-compressing; DDSketch merges by adding bucket counts. All of these merges are associative, so a reducer can combine per-shard sketches in any order or in a tree, and any dimensional slice (region, service, time bucket) is just a different set of sketches to fold. The one hard requirement is identical configuration across shards — you fix it centrally and ship it to every worker. Note that Count-Min's conservative update optimisation forfeits exact mergeability, so distributed pipelines use standard update.

What error does a Count-Min sketch guarantee?

For width w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉, a count-min sketch guarantees that the estimate f̂(x) satisfies f(x) ≤ f̂(x) ≤ f(x) + ε·N with probability at least 1 − δ, where N is the total stream weight. The error is one-sided (it never under-counts), additive (bounded by ε times the whole stream's weight, not the key's own count), and probabilistic (the bound can be exceeded with probability up to δ). The practical consequence is that Count-Min is a heavy-hitters tool: for a key whose true count is far above the ε·N noise floor the relative error is negligible, but for a rare key whose count is below that floor the estimate is dominated by collision noise. Size ε well below your heavy-hitter threshold so genuine heavy hitters stay clear of the floor.

Why not just use a Prometheus summary for percentiles?

Because a Prometheus summary computes its quantiles client-side on each instance and exports the finished numbers, which are not mergeable — you cannot combine per-host p99s into a fleet-wide p99 (the p99 of a union is not the average of the parts' p99s). The moment you need a percentile sliceable across instances, a summary silently makes it impossible, and teams usually discover this only when they try to build a global dashboard. Use a Prometheus histogram instead — its cumulative buckets are mergeable across instances, so histogram_quantile over summed buckets gives a correct (bucket-bounded) fleet p99 — or a DDSketch/t-digest backend, which exports a mergeable sketch with a guaranteed relative-error bound and tail accuracy the fixed buckets lack. mergeable summaries are the whole reason percentile monitoring scales.

Practice on PipeCode

Drill the data-structures practice library → for the Count-Min, Bloom filter, min-heap top-K, and streaming-summary problems senior interviewers love.
Sharpen the estimation axis on the statistics practice library → for quantiles, percentiles, error bounds, and confidence questions.
Stress the distinct-count axis on the cardinality practice library → for HyperLogLog, frequency estimation, and sketch-sizing scenarios.
Stack these against PipeCode's broader 450+ data-engineering catalogue to anchor the sketch-by-question decision matrix against real graded inputs.

Lock in data-sketch muscle memory

Docs explain the structures. PipeCode drills explain the decision — when a Count-Min sketch is blind to rare keys, when a t-digest's tail centroids earn their memory, when additive error disqualifies a sketch, when a Prometheus summary quietly makes fleet p99 impossible. Pipecode.ai is Leetcode for Data Engineering — pattern-first practice tuned for the production trade-offs senior data engineers actually face.

Practice data-structure problems →
Practice statistics problems →

1. Why sketches — streaming, sublinear, mergeable

A data sketch trades exactness you rarely need for memory you always lack — one pass, sublinear space, and a merge operator

Worked example — the exact-vs-sketch memory blow-up

Worked example — mergeability, demonstrated

Worked example — choosing the sketch for the question

Data-engineering interview question on sketch selection

Solution Using a per-worker mergeable sketch bundle combined at the reducer

2. Count-Min sketch — frequency & heavy hitters

count-min sketch hashes every item into a d×w counter grid and answers a frequency query with the minimum across rows — a one-sided overestimate that never lies low

Worked example — build and query a Count-Min sketch

Worked example — top-K heavy hitters with a min-heap

Worked example — conservative update and grid merge

Data-structures interview question on Count-Min sketch

Solution Using a Count-Min sketch with a bounded top-K heap

3. t-digest & approximate quantiles

t-digest summarises a distribution as centroids that are large in the middle and tiny at the tails, so approximate quantiles like p99 and p999 stay accurate where you need them most

Worked example — build a t-digest and query p99

Worked example — merging t-digests across shards

Worked example — why the tails are accurate (scale-function intuition)

Statistics interview question on approximate quantiles

Solution Using per-replica t-digests merged at the collector

4. Error bounds & sizing

Sketch memory is a function of the error you demand — ε sets the width, δ sets the confidence, and additive vs relative error decides whether the sketch can even answer your question

Worked example — size a Count-Min from a memory budget

Worked example — additive vs relative error, side by side

Worked example — t-digest compression vs accuracy sweep

Data-engineering interview question on sketch sizing

Solution Using the ε/δ sizing formulas with a heavy-hitter margin

5. Sketches in production — Spark / Druid / monitoring

The production pattern is always the same — sketch at ingest, store the sketch, merge at query — and Spark, Druid, and metrics backends each expose mergeable summaries as first-class objects

Worked example — Spark percentile_approx and DataSketches KLL

Worked example — Druid quantiles sketch at ingestion

Worked example — Prometheus histogram vs summary, and DDSketch

Systems interview question on production sketches

Solution Using per-host mergeable DDSketch merged per slice at the collector

Cheat sheet — data-sketch recipes

Frequently asked questions

What is a data sketch in one sentence?

Count-Min sketch vs HyperLogLog — what does each answer?

How does t-digest get accurate p99s?

Are sketches mergeable across shards?

What error does a Count-Min sketch guarantee?

Why not just use a Prometheus summary for percentiles?

Practice on PipeCode

Lock in data-sketch muscle memory

`count-min sketch` hashes every item into a d×w counter grid and answers a frequency query with the minimum across rows — a one-sided overestimate that never lies low

`t-digest` summarises a distribution as centroids that are large in the middle and tiny at the tails, so `approximate quantiles` like p99 and p999 stay accurate where you need them most

Sketch memory is a function of the error you demand — `ε` sets the width, `δ` sets the confidence, and additive vs relative error decides whether the sketch can even answer your question

The production pattern is always the same — sketch at ingest, store the sketch, merge at query — and Spark, Druid, and metrics backends each expose `mergeable summaries` as first-class objects