Prompt and context
This data-engineering question uses a streaming observability scenario. Events arrive continuously, node memory is bounded, and results must be emitted by window and merged across nodes. The goal is to explain approximate-quantile requirements, error budgets, and validation rather than memorize a library API.
What the interviewer evaluates
- Separating exact quantiles, fixed-bucket histograms, and mergeable sketches.
- Explaining why a t-digest allocates more summary resolution near distribution tails.
- Handling duplicates, outliers, window boundaries, merge order, and empty input.
- Validating an approximation against offline truth instead of presenting a precise-looking number without evidence.
Clarifying questions to ask
Confirm whether queried quantiles focus on tails, whether values have weights, whether windows roll, whether summaries cross machines, what absolute or relative error is allowed, and whether results drive alerts, billing, or compliance. If audit-grade exactness is required, an approximate sketch cannot replace raw sorting or an exact structure.
30-second answer framework
I would use a mergeable t-digest instead of retaining every sample. It compresses sorted values into weighted clusters and keeps tail clusters smaller, giving more resolution for P95 and P99 than for the middle. Each node updates its own digest, then a closed window merges digests before querying. Compression controls size and error; I would retain a sampled truth set, compute exact quantiles offline, and test error across distributions, outliers, duplicates, and merge orders.
Step-by-step deep answer
1. Define the exact target and alternatives
An exact quantile retains and sorts every sample, so memory grows with event count. A fixed-bucket histogram is easy to aggregate, but bucket boundaries determine its error and can make tails coarse. A t-digest stores ordered weighted clusters for streaming updates and merges; it remains approximate and must not be formatted as an exact percentile.
2. Understand clusters and the scale function
A cluster has a center and a weight representing covered samples. During compression, the allowed cluster weight varies with quantile position: clusters near zero and one are smaller, while middle clusters may be larger. The scale function and compression parameter jointly determine digest size and tail accuracy; “more compression is more accurate” is incomplete without the memory trade-off.
3. Design the distributed merge path
Each shard maintains a digest for a time window and emits it on close or a size threshold. Merge by ordering cluster centers and compressing again; never average shard P99 values because quantiles are not linearly averageable. Carry the window id, sample weights, and digest version to prevent cross-window mixing or duplicate consumption.
4. Handle boundaries and numeric data
Return an explicit missing state for an empty window. When values are identical or highly duplicated, weight concentrates in a few clusters; tests must confirm stable queries. Reject or normalize NaN, negative latency, extreme values, and mixed units before insertion. For rolling windows, define where late events land and how expired digests are released.
5. Build error validation and alert rules
Keep a controlled sample of production values as a truth set, sort it offline, and compare P50, P95, and P99 using absolute error, relative error, and breach rate. Test distributions, sample counts, shard counts, merge trees, and merge order. If size or error exceeds budget, change window granularity, compression, or sketch; alerts should show sample count and error context so tiny samples do not create tail false positives.
6. Know when not to use t-digest
Exact audit requirements, small samples, or stable bucket boundaries can make sorting or a histogram simpler. A sketch such as KLL is worth evaluating when rank-error guarantees matter and quantiles are not especially tail-focused. For long replay windows, retain rebuildable raw or stratified samples; a compressed digest is not a permanent source of truth.
Model high-quality answer
I would first set the P95/P99 error budget, window, and cross-node merge requirement. A t-digest represents the distribution with ordered weighted clusters and uses smaller clusters at both tails, which fits latency metrics. Shards update independently; closed windows merge and recompress clusters, never average shard P99 values. I normalize units and reject NaN or invalid latency, carrying window and weight metadata. Validation keeps sampled raw values, computes exact quantiles, and compares error across distributions, shard counts, and merge orders. If the budget is missed, I adjust compression or windows, or choose a histogram, KLL, or exact sorting.
Common mistakes
- Averaging each machine’s P99 → quantiles are not linearly averageable → merge sketches or raw samples first.
- Treating t-digest output as exact → compression loses ordering detail → state an error budget and sample count.
- Increasing compression blindly → the digest grows and tail gains may not be linear → measure size and error against truth.
- Ignoring late events → window metrics cannot be reproduced → define watermarks, lateness, and digest versions.
- Alerting on a tiny-sample P99 → tail variance is high → require a minimum sample count and an error guardrail.
Follow-up questions and responses
Why not merge shard P99 values directly?
P99 is nonlinear, and shard sizes and distributions differ. Merging only P99 loses the ordering information between shards; merge weighted summaries or raw samples instead.
Can merge order affect the result?
Approximate compression can cause small differences. Sort centers before a final compression, pin the implementation and parameters, and regression-test multiple merge trees and orders.
P99 error suddenly rises; which parameter changes first?
Check sample count, invalid values, late events, and duplicate merges before changing parameters. Only after confirming representational capacity is insufficient should you increase tail resolution or reduce window size, then verify against truth.
When is KLL a better fit?
Evaluate KLL when explicit rank-error guarantees matter, queried quantiles are broadly distributed, and the workload is not tail-focused. Choose from the error definition, merge behavior, memory budget, and implementation maturity rather than one benchmark.