Go 可用性 -五- 限流 4: 自適應限流

序

在前面限流的三篇文章，我們學習了令牌桶、漏桶算法的原理、實現以及使用方式，不知道你有沒有覺得這兩種算法存在着一些問題。

• Go 可用性 (二) 限流 1: 令牌桶原理及使用

• Go 可用性 (三) 限流 2: 令牌桶的實現 rate/limt

• Go 可用性 (四) 限流 3: 漏桶算法

這兩種算法最大的一個問題就是他們都屬於需要提前設置閾值的算法，基於 QPS 進行限流的時候最麻煩的就是這個閾值應該怎麼設定。一般來說我們可以通過壓測來決定這個閾值。

• 但是如果每個系統上線前都要經過很嚴格的壓測，那麼成本相對來說會比較大

• 並且我們很多時候壓測都會在測試環境進行壓測，測試環境一般來說和生產環境會有一定的差異，即使我們在生產環境做了壓測，現在我們的應用都是以容器的形式跑在不同的宿主機上的，每臺宿主機上的差異，以及不同的負載都會導致這個壓測時的結果不一定就一定是正確的

• 當我們的機器型號、數量等發生改變時，之前壓測的指標能不能用其實是一個問題，這些數據對於系統負載的影響其實不是線性的，舉個例子之前一臺機器，後面再加一臺，負載就一定能到 2 倍麼？其實是不一定的

• 如果需要修改限流的值，雖然之前我們將令牌桶的限流是可以動態調整，但是靠人去調整，如果真出現問題然後再叫運維或者是開發同學去調整可能黃花菜都涼了

既然這種方式有這麼多的缺點，那有沒有辦法解決呢？答案就是今天講到的 自適應限流

自適應限流

自適應限流怎麼做

前面我們遇到的主要問題就是每個服務實例的限流閾值實際應該是動態變化的，我們應該根據系統能夠承載的最大吞吐量，來進行限流，噹噹前的流量大於最大吞吐的時候就限制流量進入，反之則允許通過。那現在的問題就是

• 系統的吞吐量該如何計算？

• 什麼時候系統的吞吐量就是最大的吞吐量了？

計算吞吐量：利特爾法則 L = λ * W

利特爾法則由麻省理工大學斯隆商學院（MIT Sloan School of Management）的教授 John Little﹐於 1961 年所提出與證明。它是一個有關提前期與在製品關係的簡單數學公式，這一法則爲精益生產的改善方向指明瞭道路。---- MBA 智庫百科 (mbalib.com)

如上圖所示，如果我們開一個小店，平均每分鐘進店 2 個客人 (λ)，每位客人從等待到完成交易需要 4 分鐘 (W)，那我們店裏能承載的客人數量就是 2 * 4 = 8 個人

同理，我們可以將 λ  當做 QPS， W  呢是每個請求需要花費的時間，那我們的系統的吞吐就是 L = λ * W ，所以我們可以使用利特爾法則來計算系統的吞吐量。

什麼時候系統的吞吐量就是最大的吞吐量？

首先我們可以通過統計過去一段時間的數據，獲取到平均每秒的請求量，也就是 QPS，以及請求的耗時時間，爲了避免出現前面 900ms 一個請求都沒有最後 100ms 請求特別多的情況，我們可以使用滑動窗口算法來進行統計。

最容易想到的就是我們從系統啓動開始，就把這些值給保存下來，然後計算一個吞吐的最大值，用這個來表示我們的最大吞吐量就可以了。但是這樣存在一個問題是，我們很多系統其實都不是獨佔一臺機器的，一個物理機上面往往有很多服務，並且一般還存在一些超賣，所以可能第一個小時最大處理能力是 100，但是這臺節點上其他服務實例同時都在搶佔資源的時候，這個處理能力最多就只能到 80 了

所以我們需要一個數據來做啓發閾值，只要這個指標達到了閾值那我們就進入流控當中。常見的選擇一般是 CPU、Memory、System Load，這裏我們以 CPU 爲例

只要我們的 CPU 負載超過 80% 的時候，獲取過去 5s 的最大吞吐數據，然後再統計當前系統中的請求數量，只要當前系統中的請求數大於最大吞吐那麼我們就丟棄這個請求。

kratos 自適應限流分析

限流公式

// PS: 官方文檔這裏寫的是 cpu > 800 AND (Now - PrevDrop) < 1s
// 應該是寫錯了，等下看源碼就知道了
(cpu > 800 OR (Now - PrevDrop) < 1s) AND (MaxPass * MinRt * windows / 1000) < InFlight

• cpu > 800  表示 CPU 負載大於 80% 進入限流

• (Now - PrevDrop) < 1s  這個表示只要觸發過 1 次限流，那麼 1s 內都會去做限流的判定，這是爲了避免反覆出現限流恢復導致請求時間和系統負載產生大量毛刺

• (MaxPass * MinRt * windows / 1000) < InFlight  判斷當前負載是否大於最大負載

• InFlight  表示當前系統中有多少請求

• (MaxPass * MinRt * windows / 1000)  表示過去一段時間的最大負載

• MaxPass  表示最近 5s 內，單個採樣窗口中最大的請求數

• MinRt  表示最近 5s 內，單個採樣窗口中最小的響應時間

• windows  表示一秒內採樣窗口的數量，默認配置中是 5s 50 個採樣，那麼 windows 的值爲 10。

源碼分析

BBR 結構體

type BBR struct {
 cpu             cpuGetter
    // 請求數，和響應時間的採樣數據，使用滑動窗口進行統計
 passStat        metric.RollingCounter
 rtStat          metric.RollingCounter

    // 當前系統中的請求數
 inFlight        int64
 // 每秒鐘內的採樣數量，默認是10
    winBucketPerSec int64
    // 單個 bucket 的時間
 bucketDuration  time.Duration
 // 窗口數量
    winSize         int
 // 配置
    conf            *Config
 prevDrop        atomic.Value
    // 表示最近 5s 內，單個採樣窗口中最大的請求數的緩存數據
 maxPASSCache    atomic.Value
    // 表示最近 5s 內，單個採樣窗口中最小的響應時間的緩存數據
 minRtCache      atomic.Value
}

Allow: 判斷請求是否允許通過

func (l *BBR) Allow(ctx context.Context, opts ...limit.AllowOption) (func(info limit.DoneInfo), error) {
 // ... 省略配置修改代碼

    if l.shouldDrop() {
  return nil, ecode.LimitExceed
 }

 atomic.AddInt64(&l.inFlight, 1)
 stime := time.Since(initTime)

 return func(do limit.DoneInfo) {
  rt := int64((time.Since(initTime) - stime) / time.Millisecond)
  l.rtStat.Add(rt)
  atomic.AddInt64(&l.inFlight, -1)
  switch do.Op {
  case limit.Success:
   l.passStat.Add(1)
   return
  default:
   return
  }
 }, nil
}

這個方法主要是給中間件使用的

• 首先使用 shouldDrop  方法判斷這個請求是否應該丟棄

• 如果成功放行，那麼當前系統中的請求數就 +1

• 然後返回一個 function  用於請求結束之後

• 統計請求的響應時間

• 如果請求成功了，給成功的請求數 +1

• 並且當前系統中的請求數量 Inflight  -1

shouldDrop: 判斷請求是否應該被丟棄

func (l *BBR) shouldDrop() bool {
 if l.cpu() < l.conf.CPUThreshold {
  prevDrop, _ := l.prevDrop.Load().(time.Duration)
  if prevDrop == 0 {
   return false
  }
  if time.Since(initTime)-prevDrop <= time.Second {
   inFlight := atomic.LoadInt64(&l.inFlight)
   return inFlight > 1 && inFlight > l.maxFlight()
  }
  l.prevDrop.Store(time.Duration(0))
  return false
 }
 inFlight := atomic.LoadInt64(&l.inFlight)
 drop := inFlight > 1 && inFlight > l.maxFlight()
 if drop {
  prevDrop, _ := l.prevDrop.Load().(time.Duration)
  if prevDrop != 0 {
   return drop
  }
  l.prevDrop.Store(time.Since(initTime))
 }
 return drop
}

這個方法其實就是開頭講到的限流公式了，邏輯如下圖所示

• 首先看 CPU 的使用率是否達到了閾值

• 如果沒到，則回去判斷一下上次觸發限流到現在是否在一秒以內

• 如果在一秒內，就判斷當前負載是否超過限制，如果超過了就需要丟棄

• 如果不在 1s 內或者是請求數量已經降下來了，那麼就吧 prevDrop  清零然後返回 false

• 如果到了，則判斷一下當前負載是否超過限制

• 如果超過了，則設置丟棄時間 prevDrop，返回 true 需要丟棄請求

• 如果沒超過直接返回 false

maxFlight: 系統的最大負載

func (l *BBR) maxFlight() int64 {
 return int64(math.Floor(float64(l.maxPASS()*l.minRT()*l.winBucketPerSec)/1000.0 + 0.5))
}

這個就是計算過去一段時間系統的最大負載是多少

總結

這篇文章我們講了一下爲什麼需要自適應限流，令牌桶和漏桶這類需要手動設置 rps 算法的問題所在，瞭解了自適應限流的實現原理，最後看了一下 kratos 當中是如何實現自適應限流的。但是由於篇幅關係，CPU 的數據如何進行統計，文章中提到了很多次的滑動窗口是個什麼原理這些知識點大家可以自行查看 kratos 中的源碼，或者去看極客時間的 Go 進階訓練營都有講到。

kratos 中的限流算法其實是借鑑了 sentinel 的實現，只是 sentinel 默認使用 load 作爲啓發閾值，而 kratos 使用了 cpu，kratos 爲什麼要使用 cpu 呢？這個大家可以自己想想。而 sentinel 的實現其實是參考了 TCP 中的 BBR 算法，在 BBR 的基礎上加上了 load 作爲啓發閾值的判斷，所以多瞭解一下基礎知識總是沒錯的，指不定當下遇到的場景就能解決。

參考文獻

1. Go 進階訓練營 - 極客時間

2. B 站高可用架構實踐 | 趙坤的個人網站 (kunzhao.org)

3. 利特爾法則 - MBA 智庫百科 (mbalib.com)

4. 從流量控制算法談網絡優化 – 從 CUBIC 到 BBRv2 算法 | 亞馬遜 AWS 官方博客 (amazon.com)

5. kratos/ratelimit.md at v1.0.x · go-kratos/kratos (github.com)

6. 限流器系列 (3)-- 自適應限流 - 郝洪範的個人空間 - OSCHINA - 中文開源技術交流社區

7. TCP congestion control - Wikipedia

8. 系統自適應限流 · alibaba/Sentinel Wiki · GitHub

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/-4OpxtuLUWr1MKSGVodehg