分佈式高併發服務限流實現方案

服務限流場景

在高併發大流量系統中，由於併發大造成服務資源不足，負載過高，進而引發致一系列問題，這裏的流量一般都是突發性的，由於系統準備不足，很難短期擴容來應對 ，進行限流是最常用的手段，所以說限流也是服務穩定性治理重要的手段。

限流可能發生在多個層面：

  1. 用戶網絡層：突發的流量場景如熱點事件流量（秒殺事件、熱門搶購，微博熱搜），惡意刷流，競對爬蟲等。

  2. 內部應用層：上游服務的異常調用，腳本異常請求，失敗重試策略造成流量突發。

實現限流方案

常用的限流方法主要有三種：計數器算法，漏斗桶算法，令牌桶算法。

1. 計算器限流

1.1 實現原理

設計限流條件，如根據用戶 id / 商戶 id/IP/UUID + 請求 url 作爲限流對象，對限流對象的每次流量訪問進行全局計數，設置限流閾值（1000 次 / 秒，10000 / 分鐘），如果統計時間窗口期內達到閾值就進行限流。

對單機限流來說，使用全局內存計數即可，但對分佈式系統需要有一個公共存儲計數，redis 是最佳存儲方案，且 redis 的 incr 能保障原子性操作。

1.2 代碼實現

//@param key string object for rate limit such as uid/ip+url
//@param fillInterval time.Duration such as 1*time.Second
//@param limitNum max int64 allowed number per fillInterval
//@return whether reach rate limit, false means reach.
func fixedWindowRateLimit(key string, fillInterval time.Duration, limitNum int64) bool {
    //current tick time window
    tick := int64(time.Now().Unix() / int64(fillInterval.Seconds()))
    currentKey := fmt.Sprintf("%s_%d_%d_%d", key, fillInterval, limitNum, tick)
    startCount := 0
    _, err := client.SetNX(currentKey, startCount, fillInterval).Result()
    if err != nil {
        panic(err)
    }
    //number in current time window
    quantum, err := client.Incr(currentKey).Result()
    if err != nil {
        panic(err)
    } 
    if quantum > limitNum {
        return false
    } 
    return true
}

完整代碼參見：

https://github.com/skyhackvip/ratelimit/blob/master/fixedwindow.go

測試代碼：

func test1() {
for i := 0; i < 10; i++ {
go func() {
            rs := fixedWindowRateLimit("test1", 1*time.Second, 5)
            fmt.Println("result is:", rs)
        }() 
    }   
}

測試執行結果：

根據執行結果可以看到，1 秒中有 10 個請求，只有 5 個通過，另 5 個被限流返回 false。

這個代碼實現的是固定時間窗口，有一個問題，當流量在上一個時間窗口下半段和下一個時間窗口上半段集中爆發，那麼這兩段組成的時間窗口內流量是會超過 limit 限制的。

測試代碼如下，拉長時間窗口爲 1 分鐘，1 分鐘限流 5 個，前 30s 沒流量，之後每 10s 一個請求：

func test2() {
    fillInteval := 1 * time.Minute
    var limitNum int64 = 5
    waitTime := 30
    fmt.Printf("time range from 0 to %d\n", waitTime)
    time.Sleep(time.Duration(waitTime) * time.Second)
    for i := 0; i < 10; i++ {
        fmt.Printf("time range from %d to %d\n", i*10+waitTime, (i+1)*10+waitTime)
        rs := fixedWindowRateLimit("test2", fillInteval, limitNum)
        fmt.Println("result is:", rs)
        time.Sleep(10 * time.Second)
    }
}

根據執行結果可以看到，0-60s 總共 4 個 true 滿足 1 分鐘窗口 5 個，60-120 總共 5 個 true，1 個 false 滿足限流，但 30-90 這 1 分鐘的時間窗總共 6 個 true，超過 5 個限制。

1.3 方案改進：使用滑動窗口

//segmentNum split inteval time into smaller segments
func slidingWindowRatelimit(key string, fillInteval time.Duration, segmentNum int64, limitNum int64) bool {
    segmentInteval := fillInteval.Seconds() / float64(segmentNum)
    tick := float64(time.Now().Unix()) / segmentInteval
    currentKey := fmt.Sprintf("%s_%d_%d_%d_%f", key, fillInteval, segmentNum, limitNum, tick)
    startCount := 0
    _, err := client.SetNX(currentKey, startCount, fillInteval).Result()
    if err != nil {
        panic(err)
    }   
    quantum, err := client.Incr(currentKey).Result()
    if err != nil {
        panic(err)
    }   
    //add in the number of the previous time
    for tickStart := segmentInteval; tickStart < fillInteval.Seconds(); tickStart += segmentInteval {
        tick = tick - 1 
        preKey := fmt.Sprintf("%s_%d_%d_%d_%f", key, fillInteval, segmentNum, limitNum, tick)
        val, err := client.Get(preKey).Result()
        if err != nil {
            val = "0" 
        }   
        num, err := strconv.ParseInt(val, 0, 64) 
        quantum = quantum + num 
        if quantum > limitNum {
            client.Decr(currentKey).Result()
            return false
        }   
    }   
    return true
}

完整代碼參見：

https://github.com/skyhackvip/ratelimit/blob/master/slidingwindow.go

滑動窗口增加一個參數 segmentNum，表示把固定窗口再分成幾段，如上圖的 0-10 ... 50-60，把 1 分鐘分成 6 段，代碼執行結果如下，30-90,40-100, 任意 1 分鐘滑動窗口都滿足 5 個最大限制。

1.4 計數器的適用場景

適用於做 API 限流，比如對外提供 ip 定位查詢服務 api，天氣查詢 api 等，可以根據 ip 做粒度控制，防止惡意刷接口造成異常，也適用於提供 API 查詢服務做配額限制，一般限流後會對請求做丟棄處理。

侷限：窗口算法對於流量限制是定速的，對細粒度時間控制突發流量控制能力就有限了。

2. 漏斗桶限流

2.1 實現原理

漏斗桶形象比喻爲一個濾水漏斗，水滴（請求）可能很快把漏斗填滿（流量流入），漏斗出來的水滴（流量處理）是勻速固定的，桶滿則新進入水滴（請求）會被限流。

圖片來自網絡

常用隊列方式來實現，請求到達後放入隊列中，有一個處理器從隊列勻速取出進行處理。當桶滿了，新流量過來會被限流。

uber 提供了基於漏斗桶的算法實現可以參考：

https://github.com/uber-go/ratelimit

另外：redis4.0 提供了限流模塊，redis-cell，該模塊使用漏斗算法，並提供原子限流指令。

cl.throttle key capacity limitNum fillInteval

2.2 漏斗桶適用場景

漏斗桶更像是對流量進行整形 Traffic Shaping，所有流量過來都要進行排隊，依次出去，可用於做一些論壇博客發帖頻率限制。

相對於計數器限流，達到限流後該時間窗口會丟棄一切請求，漏斗在桶滿後，由於還會有持續流出，新到達請求還有機會流入。

侷限：由於出口處理速率是勻速的，短時有大量突發請求，即使負載壓力不大，請求仍需要在隊列等待處理。

3. 令牌桶限流

3.1 實現原理

令牌桶算法是一個桶，勻速向桶裏放令牌，控制桶最大容量（令牌最大數）和放入令牌速率（生成令牌 / 秒）。請求從桶中拿令牌，拿到令牌可以通過，拿不到就被限流了。

當訪問量小時，令牌桶可以積累令牌到桶滿，而當短時突發流量，積累的令牌能保障大量請求可以立刻拿到令牌，令牌用完了，請求會依賴於新令牌申請速度，這時會退化成類似漏斗桶算法。

圖片來自網絡

具體實現上，可以使用 redis 的 list，啓動任務向 list 勻速放置數據，當有請求時從 list 取數據，取到代表通過，否則被限流。這麼實現是可行的，但有個弊端，就是需要不斷操作 list，浪費內存空間，而實際上可以使用實時算法計算的方式來計算可用令牌數。

公式：可用令牌數 =（當前請求時間 - 上次請求時間）* 令牌生成速率 + 上次使用後剩餘令牌數，當然這個數需要再和桶容量比較求小。

如果可用令牌數 > 0 代表有令牌，剩餘令牌數 - 1，並更新保存本次剩餘令牌數和本次請求時間用於下次計算，這種方式也是惰性加載 / 計算的一種體現。

3.2 代碼實現

//rate increment number per second
//capacity total number in the bucket
func bucketTokenRateLimit(key string, fillInterval time.Duration, limitNum int64, capacity int64) bool {
    currentKey := fmt.Sprintf("%s_%d_%d_%d", key, fillInterval, limitNum, capacity)
    numKey := "num"
    lastTimeKey := "lasttime"
    currentTime := time.Now().Unix()
//only init once
    client.HSetNX(currentKey, numKey, capacity).Result()
    client.HSetNX(currentKey, lastTimeKey, currentTime).Result()
//compute current available number
    result, _ := client.HMGet(currentKey, numKey, lastTimeKey).Result()
    lastNum, _ := strconv.ParseInt(result[0].(string), 0, 64) 
    lastTime, _ := strconv.ParseInt(result[1].(string), 0, 64) 
    rate := float64(limitNum) / float64(fillInterval.Seconds())
    fmt.Println(rate)
    incrNum := int64(math.Ceil(float64(currentTime-lastTime) * rate)) //increment number from lasttime to currenttime
    fmt.Println(incrNum)
    currentNum := min(lastNum+incrNum, capacity)
//can access
if currentNum > 0 { 
var fields = map[string]interface{}{lastTimeKey: currentTime, numKey: currentNum - 1}
        a := client.HMSet(currentKey, fields)
        fmt.Println(a)
return true
    }
return false
}

完整代碼參見：

https://github.com/skyhackvip/ratelimit/blob/master/buckettoken.go

還有更多需要可實現細節如預熱桶、一次性放入多個令牌、一次性取多個令牌。同時由於原子性問題，通過 redis+lua 腳本操作（lua 實現令牌桶）會更好。

3.3 令牌桶適用場景

令牌桶既能夠將所有請求平均分佈到時間區間內，又能接受突發請求，因此使用最廣泛的限流算法，像 java 中比較有名的 guava 就有實現。

** 4. 方案對比選擇**

vpao1z

5. 限流部署

5.1 “分佈式部署” 限流單個服務實例

限流代碼在應用服務內，使用 aop 方式（如 gin 的 middleware），當應用請求時（request）進行攔截檢查，通過則繼續執行請求，否則將被限流進行處理。

func rateLimitMiddleware() gin.HandlerFunc {
    return func(c *gin.Context) {
        bucketTokenRateLimit(c.Param("uid"))
    }
}

由於應用服務是分佈式集羣，每個服務實例中的限流攔截器只能攔截本實例中的請求數，那麼對於總體限流就需要有一定策略分攤到每個單體實例中。比如 10000 次 / 秒，服務部署 10 個實例，每個實例限流可以平均分配（1000 次 / 秒），也可根據不同實例不同權重分配。

**優點：**可以有效防止單機突發流量導致的壓垮，滿足限流初衷，適合對併發做流量限制。

**缺點：**由於每個實例的流量不均等，可能有的實例已經限流，有的機器實例仍很空閒，犧牲部分流量。

5.2 “集中式部署” 使用統一限流服務中心

5.2.1 部署統一限流中心

所有服務實例去請求統一限流中心，中心根據流量情況告知服務是否通過，這種方案最大的問題就是多了一次服務調用，同時集中限流器也會成爲最大性能瓶頸。

5.2.2 限流部署在接入層

一般分佈式服務都設有網關層 / 路由層 / 接入層，如果集中限流器可部署到其中，可以解決上述多調用問題。一般常用 nginx + lua 做網關層限流，lua 腳本也可以使用上述幾種算法。

**優點：**適合做細粒度限流或訪問配額

**缺點：**對下游單個服務實例或依賴的服務不夠平滑，仍有流量突發過載的可能，所以可以結合上面的方式一起部署，多重防護。

5.3 服務中心與單機限流結合

可以使用基於請求日誌收集，分析日誌，根據限流規則做限流服務，分析出限流結果後，下發限流指令（通過隊列或集中配中心）到服務節點，節點進行限流控制。架構圖如下：

此方案關鍵在於：日誌處理分析的及時性，可採用 flink 流式計算方式。

5.4 限流規則配置

限流關鍵在於限流規則配置，是針對某個 url 還是針對一個服務，閾值應該如何設置，時間窗口如何設計，都是需要考慮的因素。

一般分幾部分：接口粒度，時間粒度，最大限流數

**接口粒度：**限流對象可以配置多種限流策略針對服務單個實例，針對整個服務集羣，針對某個接口，針對某類接口等。

**時間粒度：**如上述計數器算法中舉例，使用 1 分鐘做限流粒度更容易出某個小粒度時間窗口期出現異常流量。60000 次 / 分鐘，1000 次 / 秒，10 次 / 毫秒看似一樣，但限流效果不同，時間粒度越細流量整形越好，越平滑，但也不越小越好。對秒殺類場景，瞬時流量非常大，QPS 大，適合時間粒度小的。對 QPS 不大的場景，可以使用大的時間粒度。

**最大限流數：**一般需要性能壓測、業務預期評估、線上監控、往期經驗等來做參考設置。

更多考慮，如 API 接口服務針對 vip 用戶針對普通用戶，限流不同，可以用預留、權重、上限等維度進行不同調度，參考 dmclock,mclock 算法。

5.5 限流處理方式

限流後處理方式可以做服務降級（返回默認值、默認頁面）、請求丟棄（拒絕請求）、請求排隊（阻塞請求）、發送報警人工介入處理等。有直接結合服務降級熔斷的如 Sentinel、Hystrix。

更多參考資料

文章相關實現代碼：

https://github.com/skyhackvip/ratelimit

dmclock 算法參考：

https://github.com/ceph/dmclock

作者：賀鵬 Kavin

架構師

我們都是架構師！

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

猜你喜歡