Histograms & Percentiles

Latency distributions matter (p50/p95/p99). Storing every observation is too expensive. Solution: histograms.

Bucketed histogram (Prometheus classic):

http_request_duration_seconds_bucket{le="0.005"} 12000
http_request_duration_seconds_bucket{le="0.01"}  18000
http_request_duration_seconds_bucket{le="0.025"} 22000
http_request_duration_seconds_bucket{le="0.05"}  28000
...
http_request_duration_seconds_bucket{le="+Inf"}  30000
http_request_duration_seconds_count               30000
http_request_duration_seconds_sum                 1245.6

Each bucket = count of observations ≤ that threshold (cumulative).

Compute p99:

Trade-off: precision = number of buckets. Few buckets = inaccurate quantile. Many buckets = expensive.

Native histogram (Prometheus 2.40+): exponential bucketing, better resolution.

HDR Histogram (Java, popularized by Gil Tene): logarithmic buckets, very precise.

T-Digest: approximates quantiles with bounded error and small memory. Mergeable across nodes (great for distributed quantiles).

t-digest essence:
- Stream values into "centroids": clusters with mean + count.
- Centroids near tails are smaller (more precise); near median are larger.
- Total state: ~100 centroids regardless of stream length.
- Quantile estimate: scan centroids, accumulate counts.

Use cases:

• Per-host latency p99 → t-digest in app, periodic upload.
• Cross-host p99 → merge t-digests, then quantile.
• Histograms in Prometheus → exposed via /metrics, server computes quantile on query.

Quantile pitfalls:

• avg(p99 of N hosts) != p99 globally.
• "Percentiles" of summed counts have no statistical meaning.
• Use mergeable representations (t-digest, HDR) when aggregating across sources.