Question and scenario
Each edge node receives latency observations, aggregates locally, and merges summaries into regional and global layers. Queries need P50, P95, P99, and window comparisons without retaining every value. The system must handle empty windows, hot tenants, node loss, replay, upgrades, and an explanation of approximate-quantile error.
What the interviewer is testing
- Can the candidate distinguish quantiles, rank error, value error, and tail accuracy?
- Can they explain KLL's compactness and rank-error trade-off, plus t-digest's empirical tail behavior and limits?
- Do they understand mergeability, version compatibility, window boundaries, and sample weights?
- Will they use exact small samples, stratified checks, and production comparisons instead of trusting one output?
Clarifying questions to ask first
Confirm whether latency is heavy-tailed, whether P99 matters more than the median, which quantiles are queried, the minimum sample count per group, and the allowed error. Clarify fixed versus sliding windows, cross-language merging, backfill needs, storage budget, and query latency. If the business requires a strong mathematical rank guarantee, an empirical t-digest claim is insufficient.
A 30-second answer framework
First define the acceptance error: rank or latency-value error, plus the minimum sample count for P99. KLL fits a stable, mergeable design with an interpretable rank-error budget. t-digest can allocate more summary resolution to the tails, but its error depends on input distribution and implementation choices, so it is not a universal guarantee. I would generate mergeable sketches by group and window, keep exact samples as a control, and choose parameters from measured results.
Step-by-step deep dive
- Write the metric contract. Record quantile, window, grouping keys, minimum sample count, empty behavior, and error budget. Do not present P99 from a tiny sample as a stable conclusion.
- Separate two errors. Rank error describes a position in sorted data; value error describes the latency distance to the true quantile. In a heavy tail, a small rank error can mean hundreds of milliseconds.
- Evaluate KLL. KLL is a streaming, mergeable quantile sketch whose parameters trade retained space for rank accuracy. Validate implementation version, serialization format, and merge order.
- Evaluate t-digest. A t-digest controls cluster size by quantile position and commonly concentrates accuracy near the tails. Its error is empirical and depends on distribution, scale function, compression, and merging; a paper result is not a guarantee for every workload.
- Design distributed merging. Nodes upload only the sketch, count, min, max, and version. Regional layers reject incompatible parameters; late data creates a new version of its window instead of silently overwriting a published metric.
- Close the validation loop. Keep exact samples or full data for small control windows. Compare P50, P95, and P99 rank and value error by region, tenant, traffic volume, and distribution drift. Alert, increase parameters, or fall back to exact computation when the budget is exceeded.
High-quality sample answer
I would not declare one sketch universally more accurate. First put the error definition, minimum sample count, and window semantics into the metric contract. KLL suits a general distribution when an interpretable rank-error budget and stable merging matter. t-digest can spend more summary space near the tails, which is useful for P99, but Apache DataSketches notes that its results depend on input data, so I would not claim a universal error bound.
Nodes create a sketch per group and window with parameters, version, count, and bounds. Regional layers merge only compatible sketches, and late data produces a new version. Exact samples provide a control; rank and millisecond errors are measured by distribution and traffic stratum. KLL or t-digest is selected only after P99 error, memory, and query latency meet the target, with replay and dual-write checks for parameter changes. References include Apache DataSketches KLL and quantiles documentation, the t-digest paper, and BigQuery's approximate-quantile documentation.
Common mistakes
- Saying “t-digest is more accurate for P99” without defining empirical error, distribution, and merge behavior.
- Converting rank error to a fixed millisecond error while ignoring heavy tails and business units.
- Merging sketches across nodes without carrying parameters and versions, then mixing formats after an upgrade.
- Overwriting a published window with late data, making dashboards change without traceability.
- Testing only one overall sample and missing tail distortion in small tenants, low-traffic regions, or drifted distributions.
Follow-up questions and responses
Why can a small P99 rank error still be unacceptable?
If the latency distribution rises sharply in the tail, two nearby ranks can differ by hundreds of milliseconds. Report both rank and business-unit value error and enforce a minimum sample count.
Can merge order change the result?
The sketch should be mergeable, but validate merge order, compression timing, and serialization precision. Replay fixed shards with different tree shapes and compare them with a single-node aggregation; fix the implementation and version when the budget is exceeded.
When is retaining raw values the better choice?
When groups and windows are small, retention is allowed, and exact query cost is low, raw values or exact sorting is simpler. A sketch earns its complexity when scale, group count, or retention makes exact computation impractical.