# TDigest Quantile Sketch
t-digest is a compact data structure for approximate quantiles such as p50, p95, p99, and p99.9.
It is designed for online accumulation and merging, which makes it useful for distributed metrics pipelines.
## Why Percentiles Are Hard
Exact percentile computation needs raw values:
```text
store values -> sort -> pick rank
```
At billions of latency measurements, that becomes expensive for interactive dashboards.
## Core Idea
t-digest groups sorted values into centroids:
```text
centroid = representative value
weight = number of points represented
```
Clusters are small near the tails and larger near the median.
That preserves accuracy where p99/p99.9 live while allowing stronger compression around common values.
The tradeoff is intentional: most observability questions care more about the slowest users than the exact median. A digest spends more detail near the extremes.
## Shape
```mermaid
flowchart LR
Values[stream of values] --> Batch[sort/compress]
Batch --> Centroids[(centroids)]
Centroids --> Merge[merge digests]
Merge --> Query[p50/p95/p99]
```
## Mergeability
Each service, host, shard, or region can build a local digest. The metrics backend merges them to answer global percentile queries.
This is the same architectural reason HLL works for unique counts: compact summaries can be moved and combined.
## System Design Use
Store digests by metric, tag set, and time bucket:
```text
tdigest:latency:checkout_api:/pay:2026-07-18-10m
tdigest:queue_wait:email:2026-07-18-1m
```
For a dashboard query:
1. Fetch all matching bucket digests.
2. Merge the digests, not their p99 values.
3. Query the merged digest for p50, p95, p99, and sample count.
Percentiles are not additive. Averaging p99 across hosts gives the wrong answer because hosts may have different traffic volumes and latency distributions.
## Design Decisions
| Decision | Why It Matters |
|---|---|
| Compression | Higher compression can improve accuracy but costs memory/CPU. |
| Bucket size | Small buckets are fresh; large buckets are cheaper. |
| Tags | Route, region, tenant, and status code can explode cardinality. |
| Sample count | Tiny samples make p99 unstable. |
| Raw fallback | Incidents may need trace examples, not only percentiles. |
For low-volume routes, report p95/p99 with caution or hide them until the sample count is meaningful.
## Caveats
- It is approximate, not exact.
- The implementation and scale function matter.
- Repeated values, ordered data, and tails need careful handling.
- Datadog's current public system uses DDSketch for distribution metrics, not necessarily t-digest.
## Failure Modes
- Computing p99 per host and then averaging those p99s.
- Dropping sample counts, making a p99 over 12 requests look authoritative.
- Merging digests produced by incompatible library versions or settings.
- Using coarse time windows that hide short tail-latency spikes.
- Letting high-cardinality tags create too many tiny digests.
Quantile sketches are dashboard tools. They should be paired with tracing, logs, or exemplars when operators need to debug the individual requests behind the tail.
## Pro Tip
Average latency hides tail pain. A service with p50 of 40 ms and p99 of 4 seconds is not "fast" for the unlucky users.
## Related Pages
- [[wiki/streaming-percentile-analytics]]
- [[wiki/mergeable-sketches-for-analytics]]
- [[wiki/observability-for-distributed-systems]]