Understanding Percentiles (2021) | Hacker News Reader

Understanding Percentiles (2021)

blog.shalvah.me

47 pointssubomi14 comments

It’s just the generalization of the median to more than two buckets (in this case 100 of them).

Your explanation made it click for me immediately. Thank you !

Wouldn't that be 99 buckets?

No. It’s 100 buckets with 101 percentiles, from p0 to p100.

With p0 and p100 being buckets whose min() values (and in the case of p100, only value) are also the min() and max() value of the whole set.

The buckets are 1,…,100, with percentiles being their boundaries. Since the 0th and 100th percentile are insufficient to form an interval, we only practically use percentiles 1,…,99.

Neither of p0…p100 are buckets. They’re x coordinate of the cumulative distribution function (https://en.wikipedia.org/wiki/Cumulative_distribution_functi...) reaches the lines y = 0.00, y = 0.01, …, y = 0.99, y = 1.00.

With the median being the same thing as p50

Or if you define median as inverseCDF(50/100) then percentiles are just inverseCDF(percentile/100)

    data series: index -> value
    integrate to cdf: value -> density
    invert monotonic: density -> value

https://webcache.googleusercontent.com/search?q=cache:k3QOar...

archive.is WIP https://archive.is/wip/vLSWG

Percentiles become painful when trying to aggregate them. Suppose you record the p99 latency of some service, but you collect these metrics at the rack or data center level. Now you ask, what is the overall p99 latency of the service? Not an easy question to answer. Especially if you automatically subsample older time series data in order to store more of it (I've seen people trying to perform a weighted average of subsampled percentile metrics—it turns into a mess).

We need an efficient way to compactly represent the entire distribution of a metric over time so arbitrary aggregations can be performed accurately. There is some research on this topic, but nothing really production-ready that I'm aware of.

> but nothing really production-ready that I'm aware of

Here are some:

http://hdrhistogram.org/

https://prometheus.io/docs/practices/histograms/ (Victoria Metrics is also worth looking at, IIRC they store quantiles differently)

https://prestodb.io/docs/current/functions/qdigest.html

Sounds like you’re looking for T-digests[1] - most production systems I’ve worked on that do this are using them under the hood.

1: https://github.com/tdunning/t-digest

You might be interested in https://www.datadoghq.com/blog/engineering/computing-accurat...

Disclaimer: I work there/built the TypeScript implementation of the library

Reply on news.ycombinator.com