When would you not keep an exact two-heap median for per-endpoint latency across a large fleet?

## Where the exact structure runs out The two-heap median is a good structure with two hard limits, and both are about the system rather than the algorithm. **Memory grows with the stream, forever.** Every sample occupies a slot for the life of the process. A collector tracking one endpoint at a thousand requests per second accumulates 3.6 million samples an hour. Multiply by the endpoints an instance serves and the instances in the fleet, and the aggregate is decided by a number nobody chose deliberately: how long the process has been up. Restarts silently "fix" it, which is worse than failing, because the metric's memory cost becomes a function of deploy cadence. **Medians do not merge.** This is the limit people meet second and regret first. Given the exact median of instance A's samples and of instance B's, there is no way to compute the median of the union — the value depends on the distributions, not just the two answers. Anything that must produce a fleet-wide percentile therefore cannot use per-instance exact medians as its input; it needs either the raw samples shipped somewhere central, or a summary that composes. ## The three alternatives, and what each costs **Exact over a bounded trailing window.** Memory becomes O(window), which is a number you chose. The answer is still exact, just about a different question: the median of the last N samples rather than of all time. The costs are the eviction machinery — arbitrary removal is not a heap operation, so lazy deletion and separate logical size counters appear — and the fact that the window silently defines the metric's smoothing. It still does not merge. **Bounded random sample.** Keep a fixed-size uniform sample of the stream, for instance by reservoir sampling, and compute the median of the sample. Memory is a constant you pick, the estimate is unbiased, and the error is statistical: small samples give noisy percentiles, and the tails are worst served. Samples do merge, with care about weights. **Quantile sketch with an error bound.** Structures in this family — Greenwald-Khanna and t-digest are the usual references — keep a compressed summary in sub-linear space and answer any quantile with a bounded rank error. Two properties make them the default at fleet scale: memory is bounded by a parameter, and sketches **merge**, so per-instance summaries roll up to a fleet answer without shipping raw samples. The price is a real dependency, an error budget you must be able to explain, and answers that are not reproducible to the digit. ## Making the call The question I ask is what the number is *for*. - **Local, small, consumed locally** — a per-request adaptive timeout, a load-shedding threshold inside one process. Exact two heaps over a bounded window: small code, no dependency, exact enough that nobody argues. - **Aggregated across instances, or shown on a fleet dashboard** — mergeability decides it before memory does. A sketch, because the alternative is shipping raw samples and paying for that pipeline. - **Contractual: SLO reporting, penalty clauses, billing** — here "approximately the median" is a conversation with a customer, not an implementation detail. Either compute exactly from durable raw data offline, or get the error bound written into the definition so that everyone reading the number knows what it means. ## The organisational half of the answer Two arguments matter more than the asymptotics. First, **an error bound is only useful if it is understood**. A sketch guaranteeing rank error within a fraction of a percent is invisible on a latency dashboard and catastrophic in a discussion about whether an SLO was breached — not because the number is bad, but because nobody wrote down what it promises. Whatever is chosen, the promise belongs in the metric's documentation next to its name. Second, **someone maintains this at 3 a.m.** The two-heap structure is a few dozen lines that any engineer can read and reason about during an incident. A sketch is a dependency with its own failure modes, version skew across a fleet, and merge semantics that are easy to misuse. That is not a reason to avoid it — at fleet scale it is usually correct — but it is a reason to standardise on one implementation, wrap it behind the team's own metric interface, and not let three services each pick differently. The defensible position is rarely "always exact" or "always approximate". It is: bound the memory deliberately rather than by accident, choose exactness where the number is consumed locally, choose mergeability where it is aggregated, and state the error wherever it is not zero.