引言

限流策略主要用來控制在高并發、大流量的場景中對服務接口請求的速率。

比如雙十一秒殺、搶購、搶票、搶單等場景。

舉個例子，假設某個接口能夠扛住的QPS為1k，這時有1w個請求進來，經過限流模塊，會先放1k個請求，其余的請求會阻塞一段時間。不簡單粗暴地返回404，讓客戶端重試，同時又能起到流量削峰的作用。

在業務迭代開發過程中，系統的穩定性和可靠性變得越來越重要，其中，限流算法是一種非常重要的技術手段之一。

限流算法可以有效地幫助系統控制請求的流量，防止系統因為流量過大而崩潰。在高并發的情況下，如果沒有限流機制，系統可能會因為請求過多而導致響應變慢，甚至癱瘓。此外，限流算法還可以保護系統免受惡意攻擊、惡意爬蟲等不良行為的侵害，提高系統的安全性和穩定性。

本文我們將基于限流策略，討論常見的限流算法的實現方式，以及如何從0到1設計一套可用的限流實現方案。

1. 簡介

設計一套限流算法主要包含以下三個步驟：

• 流量統計：記錄在特定時間段內通過的流量數，為后續限流判斷提供依據。
• 限流判斷：判斷當前的流量是否可以正常通過。
• 流量控制：對于已被限流的請求，需要進行的特殊處理。

2. 流量統計

流量統計主要有兩種方式：固定窗口統計和滑動窗口統計。

2.1 固定窗口統計

固定窗口統計是將時間劃分為固定長度的時間窗口，并在每個時間窗口內統計通過系統的請求數量。例如，下圖中將時間劃分為1秒的時間窗口，統計每秒通過系統的請求數量。在固定窗口統計中，每個時間窗口的計數器都會在窗口結束時清零，重新開始統計下一個窗口的請求數量。

這種統計方式簡單易懂，實現簡單，但是在流量不均勻的情況下容易出現突發流量問題，導致限流不準確。如下圖所示，假設限流設置為1秒內通過qps數為2，由于在1s的時候統計窗口清零，對于500ms-1000ms這個區間內通過的2條請求沒有記憶，1000ms-1500ms這個區間內的請求能正常通過，但實際上在500ms-1500ms這個區間的請求數已經是3了，超過設定的2的限流值，在極限情況下，固定窗口的真實流量可能達到限流值的2倍。

由于固定窗口實現簡單，在對限流準確度要求不高的情況下，也經常有使用到，以下是Apinto網關用固定窗口進行限流的實際場景應用。

//固定窗口結構體
type rateTimer struct {
        // 已請求數量
        requestCount     int64
        // 限制數量
        limitCount        int64
        timerType int
        expire    time.Duration
        startTime time.Time
}


// 檢查是否超過了限制
func (r *rateTimer) check() bool {
        if time.Now().Sub(r.startTime) > r.expire {
                r.reset()
                return true
        }
        c := atomic.LoadInt64(&r.requestCount)
        localCount := c + 1
        r.add()
        if localCount > r.limitCount {
                return false
        }
        return true
}

2.2 滑動窗口統計

滑動窗口統計是一種流量統計方式。它將時間劃分為固定長度的時間窗口，但每個時間窗口的開始和結束時間是根據當前時間動態滑動的。在每個時間窗口內，統計通過系統的請求數量，并根據窗口的滑動來更新統計數據。

在滑動窗口統計中主要涉及兩個概念：

• 統計周期：其中統計周期即為采樣周期，比如設定1s最多通過2次請求，這里的1s則是統計周期。
• 窗口大小：一個統計周期內的最小統計單元，比如下圖，1s時間劃分成4個小窗口，每個窗口負責的采樣大小即為250ms，窗口越小，一個統計周期內窗口數量越多，則統計越精準（由于最后一個小窗口總是處于未完成統計的狀態，實際的統計周期總比設定的統計周期要小）。

滑動窗口中小窗口數據結構設計上需要包含窗口統計的“開始時間”以及在需要“被統計的元素”的基本信息（這里主要是當前窗口通過的請求數），小窗口設計數據結構如下BucketWrap所示。

//小窗口的設計
type BucketWrap struct {
   // BucketStart represents start timestamp of this statistic bucket wrapper.
   BucketStart uint64
   // Value represents the actual data structure of the metrics (e.g. MetricBucket).
   Value atomic.Value
}


type AtomicBucketWrapArray struct {
   // The base address for real data array
   base unsafe.Pointer // 窗口數組首元素地址
   // The length of slice(array), it can not be modified.
   length int // 窗口數組的長度
   data   []*BucketWrap //窗口數組
}

同時，一個統計周期是由多個小窗口順序組合而成，設計上為了避免內存空間使用上的浪費，采用原子時間輪的方式來將小窗口進行收尾相連，以循環隊列的方式進行編排，數據結構是AtomicBucketWrapArray，示意圖如下。

當前時間對應的窗口可以通過計算時間戳取模得到。如果請求在當前窗口內，則記錄請求，更新窗口內的請求次數。如果當前時間已經超過了當前窗口，就開始一個新的采樣周期，即重置窗口開始時間和請求計數。

比如此刻的時間戳是300ms，計算當前時刻的下標是(300/200)%8=1，當前窗口的開始時間是200ms；通過計算出來的窗口的開始時間與當前時間一致，則記錄請求。如果時間劃撥到了下一個采樣周期，比如此刻時間是1801ms，計算的下標是(1801/200)%8=1，開始時間是1800ms，由于窗口記錄的開始時間是200ms，則表示當前窗口的數據超采樣周期了，將下標為1的窗口開始時間重置為1800ms，并對重置窗口記錄，作為新的采樣周期進行統計計數。

// 計算開始時間
func calculateStartTime(now uint64, bucketLengthInMs uint32) uint64 {
   return now - (now % uint64(bucketLengthInMs))
}
// 窗口下標位置
func (la *LeapArray) calculateTimeIdx(now uint64) int {
    timeId := now / uint64(la.bucketLengthInMs)
    return int(timeId) % la.array.length
}

要獲取滑動窗口采樣周期內通過的請求數，主要方式是將原子時間輪進行遍歷，將符合條件的采樣窗口中請求數進行累加統計。

// 匹配符合條件的窗口
func (la *LeapArray) ValuesConditional(now uint64, predicate base.TimePredicate) []*BucketWrap {
   if now <= 0 {
      return make([]*BucketWrap, 0)
   }
   ret := make([]*BucketWrap, 0, la.array.length)
   for i := 0; i < la.array.length; i++ {
      ww := la.array.get(i)
      if ww == nil || la.isBucketDeprecated(now, ww) || !predicate(atomic.LoadUint64(&ww.BucketStart)) {
         continue
      }
      ret = append(ret, ww)
   }
   return ret
}

3. 限流判斷

通過上述采樣窗口的設計，我們可以獲取任何一個采樣周期內通過的請求數。通過流量統計，我們可以得到當前時間窗口內的請求量和相關數據，將其與限流規則進行比較，以判斷當前請求是否滿足通過條件。如果請求滿足通過條件，則可以直接通過，否則需要進行限流措施。

常用的限流判斷方式是令牌桶算法。該算法基于令牌桶的概念，即以固定的速率向令牌桶中添加令牌。每次請求需要從令牌桶中獲取一個令牌才能被處理。如果令牌桶中沒有足夠的令牌，則請求將被暫時阻塞或拒絕，直到令牌桶中有足夠的令牌可以被獲取。

限流判斷的核心在于計算當前時刻允許通過的令牌數，即token的計算策略。主要的計算策略包括固定閾值、預熱以及內存自適應三種。

3.1 固定閾值（Threshold）

這種token計算策略比較簡單，它的意思是在一個統計周期內允許通過的請求數是固定的。只需要比較統計周期內統計的通過請求數和閾值，就能判斷當前請求是否需要被限流。

func (d *DirectTrafficShapingCalculator) CalculateAllowedTokens(uint32, int32) float64 {
   return d.threshold
}

然而，固定閾值的方式存在一個問題，即在流量突增的情況下，通過的請求數會一瞬間達到閾值，容易對下游系統造成較大壓力，簡單來說，過剛易折，因此，另一種提前預熱的策略應運而生。

3.2 預熱（WarmUp）

基于固定閾值的token計算方案存在一個問題，即在流量突增的情況下，通過的請求數會一瞬間達到閾值，容易對下游系統造成較大壓力。因此，期望流量能夠經過一段時間的預熱再達到閾值，這樣能給下游系統一定的緩沖時間。

下圖展示了預熱（冷啟動）過程中允許通過請求數隨時間變化的關系圖。該方案的主要設計要求包括：

• 當流量較低時，不進行限流。（下圖1->3）
• 當流量達到冷啟動閾值時，觸發系統的冷啟動策略。(下圖3)
• 經過一段時間的預熱后，允許通過的請求數達到設定的閾值，并保持不變。（下圖2）
• 當流量下降后再次突增時，同樣需要再次觸發冷啟動策略。

為了滿足設計要求，我們需要設計一個預熱算法，其中啟動閾值的設計非常關鍵。為此，我們引入了一個冷卻因子的概念（coldFactor），它控制著觸發冷啟動的先決條件。具體來說，觸發冷啟動所需的請求量為 Threshold/coldFactor，如下圖所示。可以看出，冷卻因子越小，啟動預熱的閾值就越高。例如，當冷卻因子為2時，需要達到閾值的一半才會開始啟動預熱。

在預熱過程中間，需要設計一些變量來控制令牌桶的運作。具體來說，我們可以采用以下的變量：

• storeToken：代表令牌桶中當前的令牌數。該變量與允許通過的請求數量成負相關，即storeToken越小，允許通過的請求越多，直到達到指定的閾值。
• maxToken：代表令牌桶的最大容量，在預熱啟動時，storeToken的值為maxToken。
• warningToken：代表令牌桶的預警數量，在預熱結束時，storeToken的值為warningToken。
• aboveToken：代表距離預熱結束還剩余的令牌數量，即storeToken與warningToken的差值。這個變量用于輔助計算當前允許通過的請求數量。
• slope：代表斜率，用來計算生成每個令牌所需的時間間隔。

warningToken := uint64((float64(rule.WarmUpPeriodSec) * rule.Threshold) / float64(rule.WarmUpColdFactor-1))


maxToken := warningToken + uint64(2*float64(rule.WarmUpPeriodSec)*rule.Threshold/float64(1.0+rule.WarmUpColdFactor))


slope := float64(rule.WarmUpColdFactor-1.0) / rule.Threshold / float64(maxToken-warningToken)




//允許通過過請求數計算，當restToken=warningToken預熱過程結束
if restToken >= int64(c.warningToken) {
    aboveToken := restToken - int64(c.warningToken)
    warningQps := math.Nextafter(1.0/(float64(aboveToken)*c.slope+1.0/c.threshold), math.MaxFloat64)
    return warningQps
} else {
    return c.threshold
}

以下是生產令牌的條件：

• 達到 warningToken 閾值：即預熱階段結束并到達指定閾值。
• 通過的請求數passQps 低于Threshold/coldFactor：未滿足預熱條件，正常生產令牌。

綜上來說，在遇見突發流量的預熱過程中會停止令牌的生成，此過程會不斷消耗令牌，直到桶里的令牌數到達warningToken，結束預熱，重新生產令牌。

oldValue := atomic.LoadInt64(&c.storedTokens)
if oldValue < int64(c.warningToken) {
           newValue = int64(float64(oldValue) + (float64(currentTime)-float64(atomic.LoadUint64(&c.lastFilledTime)))*c.threshold/1000.0)
} else if oldValue > int64(c.warningToken) {
    if passQps < float64(uint32(c.threshold)/c.coldFactor) {
        newValue = int64(float64(oldValue) + float64(currentTime-atomic.LoadUint64(&c.lastFilledTime))*c.threshold/1000.0)
    }
}

預熱過程（上圖從右往左看）：

• 當流量通過較少時，令牌桶不斷填充新的令牌，因為未達到預熱閾值（threshold/coldFactor）且消耗的令牌數少于分配的令牌數，令牌桶中的 storeToken 逐漸填滿，接近于 maxToken后保持穩定。
• 當流量突然增加時，達到預熱閾值，此時令牌桶停止生成新令牌，但由于不斷有請求通過，令牌桶中的令牌不斷消耗，導致 storeToken 從右上角的 maxToken 向左下角的 warningToken 移動。
• 經過預設的預熱時間，令牌桶容量達到 warningToken 預警數量，此時 aboveToken 為 0，預熱結束，允許的通過請求數達到最大閾值，此時生產的令牌與消耗的令牌相等，令牌桶中令牌數保持穩定。

對于預熱我們做了一個仿真，以下是仿真的過程，在 Threshold 設定為 10，codeFactor 設定為 3 的情況下，參數隨時間變化的情況如下圖所示。

• 第一階段：流量突增，正常冷啟動過程，此時storeToken從最大值往warningToken移動，允許通過的流量逐步上升到指定的閾值10
• 第二階段：限流階段，超過閾值10的請求都被限流
• 第三階段：請求量下降到2，在Threshold/coldFactor（3.33）以下，正常為storeToken分配令牌，storeToken主鍵補充到maxToken后停止增加，此時請求都正常通過
• 第四階段：流量再次突增，重復冷啟動的過程直到達到請求閾值
• 第五階段：限流階段
• 第六階段：請求量下降到4，小于閾值且大于Threshold/coldFactor（3.33），此時storeToken在小于warningToken時候正常分配令牌，在大于warningToken的時候停止分配令牌，但會按實際的請求量消耗令牌，從而使得storeToen在warningToken附近左右橫跳。

通過仿真可以發現，在面對突發流量時，真實允許通過的請求量需要經過一段時間的預熱才能到達指定閾值。并且隨著真實請求量的變化，預熱過程可以來回進行，符合預熱設計的預期。

3.3 內存自適應

這是一種根據機器使用內存的多少來動態調節token數量的計算方式。其核心思想是在內存使用較少的情況下，允許通過的請求數量越高；而在內存使用較多的情況下，允許通過的請求數量將會降低。該方式會根據設定的閾值范圍，隨著內存使用量的增加而線性調整。

{
   Resource:               resName,
   TokenCalculateStrategy: flow.MemoryAdaptive,
   ControlBehavior:        flow.Reject,
   StatIntervalInMs:       1000,
   LowMemUsageThreshold:   1000, // 低水位限流閾值
   HighMemUsageThreshold:  100,  // 高水位限流閾值
   MemLowWaterMarkBytes:  1024,  // 低水位內存字節
   MemHighWaterMarkBytes: 2048,  // 高水位內存字節
}

在上述配置中，下圖顯示了內存實際使用量與允許通過請求量的變化關系。然而，在實際線上情況下，大部分情況下是由于請求量增長導致CPU增加，而不是因為內存使用量突然增加而需要進行限流，因此這種限流方式使用較少，或者可以采用類似的思路來實現基于cpu的自適應方式的限流方式的開發。

4. 流量控制

根據限流判斷的結果，對于需要進行流量控制的請求通常有兩種方式：一種是直接拒絕請求，返回 HTTP 狀態碼 429；另一種是阻塞請求，控制請求速率，并在一段時間后再進行后續請求操作。常用的算法是漏桶算法。

漏桶算法是一種流量整形算法，可用于平滑網絡流量、限制數據傳輸速率。其基本原理是，將數據以恒定的速率流入一個固定大小的漏桶中。當漏桶已滿時，多余的數據將溢出并被丟棄。每次請求時，先從漏桶中獲取令牌。若令牌不足，則請求被拒絕。

具體來說，漏桶算法會維護一個固定大小的漏桶，并以固定的速率流出數據。每當一個請求到達時，漏桶中的容量會相應減少請求數據量。如果此時容量不足，則請求被拒絕；否則，容量不變，請求被允許通過。

具體實現上來看，桶的大小由緩沖時間間隔與每個排隊請求的時間片大小決定，假設時間間隔是1s，每個請求的排隊時長是200ms，整個桶大小為5，可以緩沖5個請求作為排隊的請求序列，通過sleep后執行的方式進行后續請求，超出的請求會直接被拒絕。

漏桶單元測試：設定桶的允許的時間間隔是2s，每個請求的排隊時間200ms，15個請求進入之后的每個請求的狀態值與等待觸發執行的時間如下所示：

至此，我們完成了一整套的限流系統的設計過程，過程中針對計數器、令牌桶、漏桶原理等主要應用場景和結合各自特點進行了闡述。

5. 應用

在實際業務場景中，限流被廣泛應用于秒殺、活動抽獎、網關等場景。網關服務，通常用于進行流量的轉發和預處理。限流也是這套網關系統中必不可少的環節，通過配置滑動窗口形式的閾值和預熱等較為常用的限流算法，能夠有效地為接入的系統提供限流能力的支持。

6. 總結

上述過程中，本文從實際業務場景出發，從流量統計，限流判斷，流量控制三方面討論了如何設計一整套功能完備的限流系統，并結合源碼分析，模擬仿真等手段闡述了限流系統各個環節在限流中所起到的作用。

在實際業務場景中，需要根據實際情況合理設置閾值和限流策略，避免對真實用戶請求的過度限制。限流系統只是保障系統穩定的手段，而不是目的，因此需要根據實際情況來制定相應的限流策略，既要保障系統穩定，又要保證用戶體驗和業務效益。限流系統需要不斷優化和完善，才能更好地適應不同的業務場景和流量變化。