关于 PromQL 的 histogram_quantile 的算法
关于 PromQL 的 histogram_quantile 的算法. 很长一段时间内, 我都以为是使用正态分布算的, 其实并没有那么复杂.
假如我们有11个桶, 我们的数据是从0开始的, 第一个桶是接收落在(0~10]区间的数量, 第二个桶是接收落在(10 ~ 20]区间的数量, 以此类推, 第10个桶接收落在(90~100]区间的数量, 那么第11个桶接收(100 ~ +Inf) 的区间, 通常最后一个区间应该没有值或非常少.
那么如果要求第 95分位等值, 我们就要统计这时总共有多少samples, 其中第95th/100 落在那个桶. 假如我们收到100个samples, 那么第95th/100 就是第95个sample, 看它落在哪个桶. 如果我们收到10000个samples, 那就是第9500个sample, 看它落在哪个桶.
当我们看到它落到那个桶之后, 就在数一下这个桶共有多少个数, 然后算一下这个桶占据了第多少分位(低)到第多少分位(高), 所以就知道了这个桶占据了从多少分位到多少分位.
然后按照这个桶内的数据是平均分布的, 然后算出第nth(95th)是到底处于哪个值.
这篇问答很好的解释了这个算法是如何工作的:
https://stackoverflow.com/questions/55162093/understanding-histogram-quantile-based-on-rate-in-prometheus/69938239#69938239
官方的开源代码: https://github.com/prometheus/prometheus/blob/main/promql/quantile.go
其中要注意的是:
- 分位数值在桶内假定为线性分布进行插值计算
- 如果分位数落在最高的桶内，将返回第二高桶的上界值
- 如果最低桶的上界大于0，则假定自然下界为0
设计好桶是很关键的一步:
- 尽量在较低的桶内平均分布;
- 最大值不要超过第二高桶的上界;
对于上面提到的 如果分位数落在最高的桶内，将返回第二高桶的上界值, 下面是一个演示: 其中从 10240 到正无穷也有一些samples, 但是不论我们使用多少9999, 这里最多返回10240.
http_server_requests_duration_ms_bucket{le="5",method="GET",commandName="SigninLegacyView"} 0
http_server_requests_duration_ms_bucket{le="20",method="GET",commandName="SigninLegacyView"} 0
http_server_requests_duration_ms_bucket{le="80",method="GET",commandName="SigninLegacyView"} 30
http_server_requests_duration_ms_bucket{le="320",method="GET",commandName="SigninLegacyView"} 5881
http_server_requests_duration_ms_bucket{le="640",method="GET",commandName="SigninLegacyView"} 8567
http_server_requests_duration_ms_bucket{le="1280",method="GET",commandName="SigninLegacyView"} 8831
http_server_requests_duration_ms_bucket{le="2560",method="GET",commandName="SigninLegacyView"} 8865
http_server_requests_duration_ms_bucket{le="5120",method="GET",commandName="SigninLegacyView"} 8865
http_server_requests_duration_ms_bucket{le="10240",method="GET",commandName="SigninLegacyView"} 8867
http_server_requests_duration_ms_bucket{le="+Inf",method="GET",commandName="SigninLegacyView"} 8885