Go：分布式高并發(fā)服務限流實現(xiàn)方案

服務限流場景

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

限流可能發(fā)生在多個層面：

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

2.內(nèi)部應用層：上游服務的異常調(diào)用，腳本異常請求，失敗重試策略造成流量突發(fā)。

實現(xiàn)限流方案

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

1.計算器限流

1.1 實現(xiàn)原理

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

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

1.2 代碼實現(xiàn)

//@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)        }()     }   }

測試執(zhí)行結(jié)果：

根據(jù)執(zhí)行結(jié)果可以看到，1秒中有10個請求，只有5個通過，另5個被限流返回false。

這個代碼實現(xiàn)的是固定時間窗口，有一個問題，當流量在上一個時間窗口下半段和下一個時間窗口上半段集中爆發(fā)，那么這兩段組成的時間窗口內(nèi)流量是會超過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)    }}

根據(jù)執(zhí)行結(jié)果可以看到，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 segmentsfunc 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

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

1.4 計數(shù)器的適用場景

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

局限：窗口算法對于流量限制是定速的，對細粒度時間控制突發(fā)流量控制能力就有限了。

2.漏斗桶限流

2.1 實現(xiàn)原理

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

圖片來自網(wǎng)絡

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

uber提供了基于漏斗桶的算法實現(xiàn)可以參考：

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

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

cl.throttle key capacity limitNum fillInteval

2.2 漏斗桶適用場景

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

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

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

3.令牌桶限流

3.1 實現(xiàn)原理

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

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

圖片來自網(wǎng)絡

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

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

如果可用令牌數(shù)?> 0代表有令牌，剩余令牌數(shù)-1，并更新保存本次剩余令牌數(shù)和本次請求時間用于下次計算，這種方式也是惰性加載/計算的一種體現(xiàn)。

3.2 代碼實現(xiàn)

//rate increment number per second//capacity total number in the bucketfunc 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 accessif 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

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

3.3 令牌桶適用場景

令牌桶既能夠?qū)⑺姓埱笃骄植嫉綍r間區(qū)間內(nèi)，又能接受突發(fā)請求，因此使用最廣泛的限流算法，像java中比較有名的guava就有實現(xiàn)。

?4.方案對比選擇

5.限流部署

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

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

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

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

優(yōu)點：可以有效防止單機突發(fā)流量導致的壓垮，滿足限流初衷，適合對并發(fā)做流量限制。

缺點：由于每個實例的流量不均等，可能有的實例已經(jīng)限流，有的機器實例仍很空閑，犧牲部分流量。

5.2 “集中式部署”使用統(tǒng)一限流服務中心

5.2.1 部署統(tǒng)一限流中心

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

5.2.2 限流部署在接入層

一般分布式服務都設(shè)有網(wǎng)關(guān)層/路由層/接入層，如果集中限流器可部署到其中，可以解決上述多調(diào)用問題。一般常用nginx + lua做網(wǎng)關(guān)層限流，lua腳本也可以使用上述幾種算法。

優(yōu)點：適合做細粒度限流或訪問配額

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

5.3 服務中心與單機限流結(jié)合

可以使用基于請求日志收集，分析日志，根據(jù)限流規(guī)則做限流服務，分析出限流結(jié)果后，下發(fā)限流指令（通過隊列或集中配中心）到服務節(jié)點，節(jié)點進行限流控制。架構(gòu)圖如下：

此方案關(guān)鍵在于：日志處理分析的及時性，可采用flink流式計算方式。

5.4?限流規(guī)則配置

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

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

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

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

最大限流數(shù)：一般需要性能壓測、業(yè)務預期評估、線上監(jiān)控、往期經(jīng)驗等來做參考設(shè)置。

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

5.5?限流處理方式

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

更多參考資料

文章相關(guān)實現(xiàn)代碼：

https://github.com/skyhackvip/ratelimit

dmclock算法參考：

https://github.com/ceph/dmclock

推薦閱讀

• Go：分布式鎖實現(xiàn)原理與最佳實踐