Start here: the problem it solves#
TL;DRthe 30-second version
- A t-digest estimates quantiles β the median, p90, p99 β of a huge stream of numbers using a small, fixed-ish amount of memory, instead of the sort-everything memory an exact answer needs.
- It keeps a set of centroids, each a mean value and a count of the points it stands for. A new value joins the nearest centroid, or starts a new one when that centroid is already at its size cap.
- The size cap is tail-biased: tiny near the extremes, large in the middle. So tail centroids stay fine-grained and p99 is accurate, while middle centroids grow fat and the median is coarser.
- To read a quantile, walk the centroids by cumulative count and interpolate between the two that straddle the target rank. To merge two digests, concatenate their centroids and re-cluster.
- Real systems: Elasticsearch percentile aggregations, Apache Druid and PostgreSQL quantile sketches, and latency percentiles across observability and monitoring stacks.
Suppose you run a service and you care about tail latency. The average request time hides the pain; what you promise in an SLO is a percentile, like 'p99 under 200 milliseconds'. To report that honestly you need the value below which 99 percent of your requests fall, computed over every request in a window.
The exact way is to collect every latency, sort them, and read off the value at rank 0.99 times the count. That is simple and correct, and it works fine for a thousand samples. It falls apart at scale. A busy service handles millions of requests a minute across hundreds of machines. Keeping and sorting all of those samples, per window, per machine, then shipping them somewhere to combine, is far more memory and network than a monitoring pipeline can spend.
Here is the observation that saves us. You do not need the exact p99; you need it close, and you need it more accurate at the tail than in the middle. Nobody sets an SLO on the median of the median. If you can accept a small error, and if that error can be pushed toward the middle where it does not matter, you can replace megabytes of sorted samples with a few kilobytes that never really grow.
The idea that almost works: a fixed histogram#
The obvious way to summarize a stream of numbers is a histogram: pick a set of buckets in advance, and for each value add one to the bucket it falls in. This is tiny and fast, and you can read a rough quantile by walking the buckets until you have counted past the target rank. Many latency tools work exactly this way.
The trouble is that you have to choose the bucket boundaries before you see the data. Evenly spaced buckets spend most of their resolution in the crowded middle and give the sparse tail just one or two wide buckets β which is the opposite of what you want, because the tail is where p99 and p99.9 live. Buckets spaced by powers of ten help, but they still bake in a fixed grid, and if the data lands between two boundaries the estimate is only as precise as that bucket is wide. Worse, two histograms only combine if they were built with the same boundaries, so a fleet has to agree on one grid up front.
Notice what is missing. A fixed histogram cannot put more detail where the data actually is, and it cannot put more detail where the questions actually are. Both of those wants point the same direction: let the buckets adapt to the stream, and give the tails more resolution than the middle on purpose.
The mechanism: centroids with a tail-biased size cap#
A t-digest is a set of centroids kept sorted by their mean. Each centroid holds two numbers: the mean of the points it has absorbed, and how many points that is (its weight). Together the centroids are a compressed picture of the sorted data. There are three operations.
- Add a value: find the centroid whose mean is nearest to the value. If that centroid still has room under its size cap, absorb the value β update the mean and add one to the count. If it is already full, start a new centroid of weight one at the value.
- Read a quantile q: multiply q by N (the total count) to get a target rank, walk the centroids adding up their weights, and interpolate between the means of the two centroids whose cumulative weights straddle that rank.
- Merge two digests: pour both sets of centroids together, sort by mean, and sweep once left to right, combining adjacent centroids whenever the combined weight still fits under the cap at that position.
Everything rests on the size cap, and the size cap depends on position. Give each centroid an estimated quantile q equal to the fraction of all points that sit at or before its middle. A centroid near the median has q close to 0.5; a centroid out in the tail has q close to 0 or 1. The cap on a centroid's weight is largest when q is near 0.5 and shrinks to one as q approaches either extreme. A convenient form is a cap proportional to q times (1 minus q), which is a gentle hump: fat in the middle, pinched to nothing at the ends.
circle area is a centroid's weight; the tails stay as weight-one centroids so p99 reads a real observed value
This is why the whole structure works. In the middle, one fat centroid can stand for dozens of nearby values, because reading the median a little coarsely is harmless. At the tails, the cap forces centroids down to weight one, so p99 interpolates between two individual observed values rather than being lost inside a wide bucket. The digest spends its resolution where the questions are.
Go deeperThe scale function, exactly
The formal version replaces 'estimated quantile' with a scale function k(q) that stretches quantile space near the tails. The rule is that a centroid spanning quantiles from q-left to q-right is allowed only if k(q-right) minus k(q-left) is at most one. The classic choice, called k1, is k(q) = (Ξ΄ / 2Ο) Β· arcsin(2q β 1), where Ξ΄ is the compression parameter.
Because the arcsine's slope blows up as q approaches 0 or 1, a fixed step in k covers a vanishingly small step in q at the tails, forcing tiny centroids there, and a wide step in q near the middle, allowing fat ones. Working the inverse out, the maximum weight of a centroid near quantile q is roughly proportional to the square root of qΒ·(1 β q). The simpler qΒ·(1 β q) cap used in the walkthrough and the simulator has the same shape β large in the middle, one at the ends β and keeps the arithmetic legible.
The compression parameter Ξ΄ is the single accuracy dial. It bounds the number of centroids to roughly a small multiple of Ξ΄, so the footprint is set by Ξ΄ and not by N. A larger Ξ΄ keeps more, finer centroids and tightens every estimate; a smaller Ξ΄ lets centroids grow fat and coarsens them. Production digests use Ξ΄ around 100 to 200 and keep a few hundred centroids; this page uses a tiny Ξ΄ so the fat middle and the single-point tails are visible on screen.
A worked example#
Take a digest already summarizing a few dozen request latencies in milliseconds. Most requests cluster around 50 ms, and a thin tail stretches out to a few hundred. The middle has grown a couple of fat centroids; the tail is a scatter of weight-one centroids. Now feed it two more values and then ask for p99.
- A 48 ms request arrives. Its nearest centroid sits near 47 ms in the crowded middle, holding several points. That centroid's cap there is large, so it has room: it absorbs the value, its count ticks up, and its mean slides a hair. No new centroid is created.
- A 460 ms request arrives. Its nearest centroid is a lonely weight-one centroid far out in the tail, and the cap at that quantile is one, so that centroid is already full. The value starts a brand-new weight-one centroid of its own. The tail stays fine-grained.
- Ask for p99. The target rank is 0.99 Γ N. Walking the cumulative counts lands between two weight-one tail centroids. The estimate interpolates between their means, so it comes back near a genuine observed latency rather than blurred across a wide bucket.
That contrast is the entire idea in one run. The middle add disappeared into a fat centroid, because coarse is fine there. The tail add spawned its own centroid, because the cap refuses to let the tail blur. When the p99 question came, the tail had kept exactly the detail the question needed.
PredictYou add ten thousand more requests that all cluster near the median. What happens to the number of centroids, and to the accuracy of p99?
Hint: The size cap grows with N, but only in proportion to qΒ·(1 β q).
The centroid count barely moves. The new values land in the middle, where the caps are large and grow with N, so a handful of fat centroids simply absorb them all rather than spawning new ones. The footprint stays bounded by the compression, not by how many points you add. And p99 stays about as accurate as before: the tail centroids are untouched by middle traffic, so the resolution where p99 lives is unchanged. This is the payoff of the position-dependent cap β pouring data into the middle costs almost no memory and does not erode the tail.
Memory and speed#
The headline property is that the memory is set by the compression parameter, not by the number of values. A digest with compression Ξ΄ keeps on the order of Ξ΄ centroids, each a mean and a count, so a few hundred centroids β a few kilobytes β can summarize billions of numbers.
- Memory is proportional to the compression Ξ΄ and independent of N. You size it from your accuracy target: a larger Ξ΄ buys tighter estimates at the cost of more centroids. A common Ξ΄ of 100 to 200 gives quantile errors well under a percent for a few kilobytes.
- Adding a value costs a search for the nearest centroid β a binary search over the sorted centroids, so about log of the centroid count β plus a constant-time absorb or insert. There is no resize tied to N and no rescan of the data.
- Reading a quantile is one linear walk over the centroids with an interpolation at the end, so it is proportional to the centroid count, not to N.
- Two digests merge by concatenating their centroids, sorting, and re-clustering in a single pass. The merged digest is essentially what you would have built by feeding both streams into one, which makes distributed and parallel aggregation straightforward.
Variants and relatives
- Clustering vs merging digest: the online variant shown here folds each value into the nearest centroid as it arrives. The merging variant buffers a batch of raw values, sorts them, and clusters in one pass; it is faster for bulk ingestion and is what most libraries use under load. Both obey the same scale-function cap.
- Scale functions k0 to k3: k0 caps every centroid the same regardless of position (a uniform digest); k1 (arcsine) biases toward both tails; k2 and k3 use a log-odds form that biases even harder toward the extremes for use cases that live at p99.9 and beyond. The scale function is the tuning knob for where accuracy goes.
- Other quantile sketches: the GK (Greenwald-Khanna) and KLL sketches give a worst-case bound on rank error and do not assume anything about the value distribution, which t-digest's tail bias implicitly does. HdrHistogram uses fixed, value-relative buckets and is excellent for latencies with a known dynamic range. t-digest wins when you want relative, tail-focused accuracy and clean merging without agreeing on buckets in advance.
Strengths, limits, and when to reach for it
A t-digest makes one clear bargain: give up exact quantiles to gain a small, mergeable summary that is sharpest at the tails. Whether that is a good deal depends on what you are measuring.
- Small, bounded footprint β the centroid count is set by the compression, not by N, so a fleet-wide latency summary fits in kilobytes where sorted samples would need gigabytes. This is the whole reason to use it.
- Tail-focused accuracy β the position-dependent cap concentrates precision at p90, p99, and p99.9, which is exactly where SLOs and alerts live. The median is coarser, and that is a deliberate, harmless trade.
- Cleanly mergeable β digests combine by re-clustering their centroids, with no requirement that everyone agreed on bucket boundaries first, so per-machine digests roll up into a fleet-wide one.
- The limits β it gives up exact answers, cannot recover individual values, has weaker worst-case rank guarantees than GK or KLL on adversarial inputs, and its accuracy is relative to rank rather than a flat absolute error. If you need any of those, reach for exact sorting (small data), a rank-bounded sketch (adversarial data), or HdrHistogram (a known, fixed dynamic range).
t-digest vs the neighbours
| Sort the samples | Fixed histogram | GK / KLL sketch | t-digest | |
|---|---|---|---|---|
| Answers | any quantile, exact | rough quantiles | any quantile | any quantile |
| Memory | O(N) | O(buckets), fixed | O(1/Ξ΅), fixed | O(Ξ΄), fixed |
| Accuracy | exact | bucket-width bound | rank error β€ Ξ΅ | relative, best at tails |
| Bucket boundaries up front? | no | yes | no | no |
| Mergeable? | yes, expensive | only if same buckets | yes | yes (re-cluster) |
Against exact sorting, the digest wins the moment the stream is too large to hold and sort. Against a fixed histogram, it wins by adapting its buckets to the data and by merging without a shared grid. Against GK and KLL, it trades their hard worst-case rank bound for a tail-biased accuracy that is usually better in practice on real, well-behaved data β and for a design that is simple to implement and merge.
These are the same family of bargains the other sketches make: a fixed, tiny footprint in exchange for approximate answers with a known shape of error. A Bloom filter trades it for membership, a HyperLogLog for distinct counts, a Count-Min Sketch for frequencies, and a t-digest for quantiles. Systems often run several of them side by side over the same stream.
Where t-digest runs in the wild
- Elasticsearch and OpenSearch β the percentiles aggregation is backed by a t-digest, so a query can report p50, p95, and p99 of a field across a huge index without holding every value, and the per-shard digests merge into the final answer.
- Apache Druid β a t-digest sketch extension stores compact quantile summaries in segments, so percentile queries over trillions of rows read a few kilobytes per segment and combine them.
- PostgreSQL β the tdigest extension adds an aggregate that builds and merges digests inside SQL, so you can compute percentiles over large tables and roll partial digests up across partitions.
- Observability and monitoring β latency dashboards and SLO alerting across metrics pipelines lean on t-digest (and its relatives) to keep per-service percentiles cheaply and to aggregate them across machines.
Common misconceptions & gotchas
Isn't this just a histogram with clever buckets?
It is close in spirit, with two differences that matter. The buckets are centroids that form where the data lands, so nobody picks boundaries in advance, and their size cap depends on position, so the tails stay fine while the middle coarsens. A plain histogram has neither property, which is why it blurs the tail and only merges when everyone shares a grid.
Why is p99 more accurate than the median?
Because the size cap shrinks toward the tails. Near q = 0.99 the cap is one, so tail centroids each stand for a single observed value and p99 interpolates between real data points. Near q = 0.5 the cap is large, so one fat centroid stands for many values and the median is read more coarsely. The error is deliberately pushed to the middle, where it is harmless.
Can I merge digests built with different compression settings?
Yes, and this is a real advantage over fixed histograms. Merging pours both centroid sets together, sorts by mean, and re-clusters under the target compression, so the result is valid even if the inputs were tuned differently. There is no shared grid to agree on ahead of time.
Does it store the raw values, so I can get an exact answer later?
No. Once a value is absorbed into a centroid, only the running mean and count remain; the individual value is gone. That is precisely the memory it saves. If you need exact answers or the ability to recover values, keep the raw data β a t-digest is a summary, not a store.
QuizYou compute a per-minute t-digest of latency on each of 200 servers and merge them into one fleet digest every minute. Compared with shipping every raw latency to one place and sorting, what have you mainly traded away?
- Exactness β the merged p99 is a close estimate, not the true value, in exchange for tiny per-server summaries and a cheap roll-up
- Mergeability β digests from different servers cannot be combined
- Tail accuracy β merging blurs the extremes where p99 lives
- Nothing β a merged t-digest is bit-for-bit identical to sorting all the raw values
Show answer
Exactness β the merged p99 is a close estimate, not the true value, in exchange for tiny per-server summaries and a cheap roll-up β Each server keeps a few kilobytes instead of every sample, and the roll-up combines those summaries instead of moving and sorting the raw firehose. The cost is that the fleet p99 is an estimate rather than the exact value. Mergeability is preserved (that is the point), and the tail stays the most accurate region because the size cap keeps tail centroids fine even after merging.
In an interview
Lead with the problem and the shape of the answer. Reporting tail-latency percentiles over millions of requests a minute would mean storing and sorting every sample, which is far too much memory and network. A t-digest replaces the raw values with a small set of centroids and estimates any quantile from them, most accurately at the tails, in a footprint that does not grow with the data. Name where it runs: Elasticsearch percentiles, Druid and PostgreSQL sketches, and observability pipelines.
Then explain the mechanism in three moves. A centroid is a mean plus a count. Adding a value folds it into the nearest centroid, or starts a new one if that centroid is at its size cap. The cap depends on position β small at the tails, large in the middle β so the tails stay fine-grained. Reading a quantile walks the cumulative counts and interpolates between the straddling centroids, and merging re-clusters the combined centroids. Be ready to say why the median is coarser than p99: the cap deliberately spends resolution at the extremes.
If pushed, mention that the compression parameter Ξ΄ sets the size and accuracy, that the classic k1 scale function uses an arcsine to bias toward the tails, and that clean merging is what lets you compute digests per machine and roll them up. Then open the simulator: stream a value into the fat middle and watch it get absorbed, stream one into the tail and watch it spawn its own centroid, then read p99 and watch it interpolate between two single-point tail centroids.
References & further reading
- Dunning & Ertl β Computing Extremely Accurate Quantiles Using t-Digests (2019) β the definitive paper: centroids, the k1 scale function, the size bound, and the accuracy analysis
- Ted Dunning β t-digest reference implementation and design notes β the canonical Java library, with the merging and clustering variants and the scale functions k0βk3
- Elasticsearch β Percentiles aggregation β a production use: percentile queries backed by a t-digest, merged across shards
- PostgreSQL tdigest extension (TomΓ‘Ε‘ Vondra) β a SQL aggregate that builds and merges digests, with partial-aggregate roll-up across partitions
- Dunning β The Size of a t-Digest (2019) β the bound on how many centroids a digest keeps as a function of the compression
Ready to try it?
The simulator is a real, deterministic implementation β pick a scenario and step through it, scrubbing the timeline forward and backward through every change.