玩转Prometheus(2)–计算Top Percentile

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1. 前言

在笔者的上一篇文章 玩转Prometheus(1)--第1个例子，我提到可以用Prometheus，来统计服务的TP90的请求耗时。

那么TP90到底是什么意思？在Prometheus中，它又是如何计算的？

2. 概念--中位数/Top Percentile

2.1 中位数

中位数（Medians）统计学名词，是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。中位数用Me表示。当变量值的项数N为奇数时，处于中间位置的变量值即为中位数；当N为偶数时，中位数则为处于中间位置的2个变量值的平均数。

我们来看一个示例，假定有1组请求，耗时(单位毫秒)如下:
[5, 8, 6, 50, 7, 10, 9, 11]
将它们按耗时，从小到大排列
[5, 6, 7, 8, 9, 10, 11, 50]
上面的示例N = 8, 中位数取(Array[3] + Array[4])/2 = (8 + 9)/2 为8.5ms

2.2 Top Percentile

Top Percentile表示百分比分布统计。TP50表示50%的请求都小于等于某个值，TP90表示90%的请求小于等于某个值。
[ 5, 6, 7, 8, 9, 10, 11, 50]
[12.5%, 25%, 37.5%, 50%, 62.5%, 75%, 87.5%, 100%]

上例中TP50=8ms，TP100=50, 50%的请求在8ms以内完成，100%的请求在50ms内完成

3. 实现

按照Top Percentile的定义，如果要实现对TP90或TP99的计算，就必须要对一段时间(比如1分钟)的所有请求耗时进行记录进行存储，然后排序，再计算对应Percentile的请求耗时，这对于一个QPS很高的系统，几乎是不可想象的。

Prometheus采用了精度有损的折中的方案
1）首先将整个值区间，分为若干bucket
下面是client_golang给出的bucket的默认划分

DefBuckets = []float64{.005, .01, .025, .05, .1, .25, .5, 1, 2.5, 5, 10}

• (0, 5ms]
• (5ms, 10ms]
• (10ms, 25ms]
• (25ms, 50ms]
• (50ms, 100ms]
• (100ms, 250ms]
• (250ms, 500ms]
• (500ms, 1s]
• (1s, 2.5s]
• (2.5s, 5s]
• (5s, 10s]
• (10s, +INF]
  每个bucket对应一个Counter
  根绝每个请求的耗时的情况对bucket分别计数
  2）为了后期计算Top Percentile方便，将bucket按上界限调整为

type bucket struct {
    upperBound float64
    count      float64
}

对于我们给出的例子
[5, 6, 7, 8, 9, 10, 11, 50]

bucket	count
(0, 5ms]	1
(0, 10ms]	6
(0, 25ms]	7
(0, 50ms]	8
(0, 100ms]	8
(0, 250ms]	8
(0, 500ms]	8
(0, 1s]	8
(0, 2.5s]	8
(0, 5s]	8
(0, 10s]	8
(0, +INF]	8

在metrics接口中看到情况形如

http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.005"} 9.295319e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.01"} 9.296761e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.025"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.05"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.1"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.25"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="0.5"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="1"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="2.5"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="5"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="10"} 9.296775e+06
http_request_duration_seconds_bucket{method="GET",path="/api/api1",le="+Inf"} 9.296775e+060.

4. histogram_quantile 的计算方法

The histogram_quantile() function interpolates quantile values by assuming a linear distribution within a bucket. The highest bucket must have an upper bound of +Inf. (Otherwise, NaN is returned.) If a quantile is located in the highest bucket, the upper bound of the second highest bucket is returned. A lower limit of the lowest bucket is assumed to be 0 if the upper bound of that bucket is greater than 0. In that case, the usual linear interpolation is applied within that bucket. Otherwise, the upper bound of the lowest bucket is returned for quantiles located in the lowest bucket.

注
如果TP90等数据落在边界上，就直接取upperBound的值，否则
histogram_quantile假定在bucket内部，值是线性分布的。histogram_quantile用线性插值的方法，确定TP90的取值。

详细代码：
./promql/functions.go

func funcHistogramQuantile(vals []Value, args Expressions, enh *EvalNodeHelper) Vector

./promql/quantile.go

func bucketQuantile(q float64, buckets buckets) float64 {
    if q < 0 {
        return math.Inf(-1)
    }
    if q > 1 {
        return math.Inf(+1)
    }
    if len(buckets) < 2 {
        return math.NaN()
    }
    sort.Sort(buckets)
    if !math.IsInf(buckets[len(buckets)-1].upperBound, +1) {
        return math.NaN()
    }

    ensureMonotonic(buckets)

    rank := q * buckets[len(buckets)-1].count
    b := sort.Search(len(buckets)-1, func(i int) bool { return buckets[i].count >= rank })

    if b == len(buckets)-1 {
        return buckets[len(buckets)-2].upperBound
    }
    if b == 0 && buckets[0].upperBound <= 0 {
        return buckets[0].upperBound
    }
    var (
        bucketStart float64
        bucketEnd   = buckets[b].upperBound
        count       = buckets[b].count
    )
    if b > 0 {
        bucketStart = buckets[b-1].upperBound
        count -= buckets[b-1].count
        rank -= buckets[b-1].count
    }
    return bucketStart + (bucketEnd-bucketStart)*(rank/count)
}

总结

Prometheus采用精度有损的折中的方案实现对Top Percentile的计算。使用这个方法，对数据值的分布的预估十分重要，在数据集中分布的区段，增加bucket的数量, 可以提高Top Percentile计算的精度。

参考资料

1. 性能测试应该怎么做?
2. histogram_quantile
3. Why Averages Suck and Percentiles are Great
4. 中位数

---