prometheus專題—（八）線性插值法原理和summary

前言

• prometheus官方文檔中對于兩種類型的對比說明

下面我總結了一些對比點

histogram 線性插值法

histogram_quantile為何需要先算rate

• 因為每個bucket都是`counter`型的，如果不算rate那麼分位值的結果曲線是一條直線
• 原理是因為`counter`型累加，不算rate并不知道目前bucket的增長情況，換句話說不知道這些bucket是多久積攢到現在這個值的

什麼是線性插值法

- 之前閱讀很多文章都提到`histogram`采用`線性插值法`計算分位值會導緻一定的誤差
- 對這個`線性插值法`總是了解的不到位
- 在檢視完代碼之後明白了      

代碼分析

- 代碼位置：`D:\work\go_work\pkg\mod\github.com\prometheus\[email protected]\promql\quantile.go`

###       

bucket資料結構

- 其中`bucket` 代表事先定義好的bucket
- `upperBound`代表這個bucket的上限值
- `count` 代表這個小于等于這個`upperBound`的個數/次數
- `workqueue_work_duration_seconds_bucket{name="crd_openapi_controller",le="10"} 65246 `
- 是以上述表達式含義為 `workqueue_work_duration_seconds`小于`10`秒的有`65246 `個
      

type bucket struct {
    upperBound float64
    count      float64
}

type buckets []bucket

func (b buckets) Len() int           { return len(b) }
func (b buckets) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }
func (b buckets) Less(i, j int) bool { return b[i].upperBound < b[j].upperBound }

      

核心計算函數

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

    buckets = coalesceBuckets(buckets)
    ensureMonotonic(buckets)

    if len(buckets) < 2 {
        return math.NaN()
    }
    observations := buckets[len(buckets)-1].count
    if observations == 0 {
        return math.NaN()
    }
    rank := q * observations
    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
    }
    sql:=fmt.Sprintf("%v+(%v-%v)*(%v/%v)",
        bucketStart,
        bucketEnd,
        bucketStart,
        rank,
        count,

    )
    log.Println(sql)
    return bucketStart + (bucketEnd-bucketStart)*(rank/count)
}

      

我們現在有這些資料，然後求75分位值

a := []bucket{
    {upperBound: 0.05, count: 199881},
    {upperBound: 0.1, count: 212210},
    {upperBound: 0.2, count: 215395},
    {upperBound: 0.4, count: 319435},
    {upperBound: 0.8, count: 419576},
    {upperBound: 1.6, count: 469593},
    {upperBound: math.Inf(1), count: 519593},
}

q75 := bucketQuantile(0.75, a)      

- 其計算邏輯為：根據記錄總數和分位值求目标落在第幾個bucket段`b`
- 根據`b`得到起始bucket大小`bucketStart`,終止bucket大小`bucketStart` ，本bucket寬度 ，本bucket記錄數
- 根據本段記錄數和分位值算出目标分位數在本bucket排行`rank`
- 最終的計算方式為`分位值=起始bucket大小+(本bucket寬度)*(目标分位數在本bucket排行/本bucket記錄數)`
- 換成本例中： `q75=0.4+(0.8-0.4)*(70259.75/100141) = 0.6806432929569308`

2021/02/02 19:08:55 記錄總數 = 519593
2021/02/02 19:08:55 目标落在第幾個bucket段= 4
2021/02/02 19:08:55 起始bucket大小= 0.4
2021/02/02 19:08:55 終止bucket大小= 0.8
2021/02/02 19:08:55 本bucket寬度= 0.4
2021/02/02 19:08:55 本bucket記錄數= 100141
2021/02/02 19:08:55 目标分位數在本bucket排行= 70259.75
2021/02/02 19:08:55 分位值=起始bucket大小+(本bucket寬度)*(目标分位數在本bucket排行/本bucket記錄數)
2021/02/02 19:08:55 0.4+(0.8-0.4)*(70259.75/100141) = 0.6806432929569308      

那線性插值法的含義展現在哪裡呢​

- 就是這裡 `本bucket寬度*(目标分位數在本bucket排行/本bucket記錄數)`
- 有個假定：樣本資料這個目标bucket中按照平均間隔均勻分布
- 舉例 100141個樣本在0.4-0.8 bucket中均勻分布
- 如果真實值分布靠近0.4一些，則計算出的值偏大
- 如果真實值分布靠近0.8一些，則計算出的值偏小
- 這就是線性插值法的含義      

histogram 高基數問題

具體可以看我之前寫的文章

prometheus高基數問題和其解決方案

危害在哪裡

- 一個高基數的查詢會把存儲打挂
- 一個50w基數查詢1小時資料記憶體大概的消耗為1G，再疊加cpu等消耗

### 
      

為何會出現

• label乘積太多 ，比如bucket有50種，再疊加4個10種的業務标簽，是以總基數為 50*10*10*10*10=50w

summary 流式聚合

一個qps為1萬的http服務接口的分位值如何計算

• 假設以1秒為視窗拿到1萬個請求的響應時間，排序算分位值即可
• 但是1秒視窗期内，快的請求會多，慢的請求會少
• 原理分析：說來慚愧，沒看太明白，但是可以确定就是hold一段時間的點計算的
• 使用庫"github.com/beorn7/perks/quantile"
• 感興趣的可以自己研究下D:\work\go_work\pkg\mod\github.com\prometheus\[email protected]\prometheus\summary.go