CloudFlare介紹限速的文章， 講述了限速的使用場(chǎng)景和運(yùn)作方式。

最難的是構(gòu)建一個(gè)既高效又匹配需求的算法。

1.流行的限速器

① 固定窗口限速 Fixed Window Counter

跟蹤固定時(shí)間間隔（如 1 分鐘）內(nèi)的請(qǐng)求數(shù)量，一旦達(dá)到上限，就會(huì)拒絕該窗口中的后續(xù)所有請(qǐng)求。

UserCase： 可預(yù)測(cè)流量、低精度需求的簡(jiǎn)單API，比如云平臺(tái)會(huì)對(duì)開發(fā)者提供 “免費(fèi)調(diào)用API”的限速額度。

eg： 公共天氣 API 允許每個(gè)用戶每分鐘 100 次請(qǐng)求，任何額外請(qǐng)求都會(huì)返回 “429 請(qǐng)求過(guò)多 ”響應(yīng)。

Drawback： 客戶端可通過(guò)在兩個(gè)時(shí)間窗口的邊界堆砌請(qǐng)求（例如，在1min時(shí)間窗口的第59秒和下一個(gè)1min窗口的第1s都堆砌100 個(gè)請(qǐng)求）， 輕松突破qps=100/min 語(yǔ)義。

固定窗口算法對(duì)應(yīng)最直觀意義的qps語(yǔ)義，但是qps漏洞也很明顯。

② 滑動(dòng)窗口限速 Sliding Window Log

維護(hù)每個(gè)請(qǐng)求的時(shí)間戳日志，并根據(jù)滾動(dòng)時(shí)間窗口計(jì)算限制。

UserCase：要求高精度的核心系統(tǒng)，如金融交易 API 或欺詐檢測(cè)機(jī)制。

eg： 銀行 API 限制每小時(shí)取款次數(shù)為 10 次，每次新請(qǐng)求都要根據(jù)最近1小時(shí)的取款次數(shù)來(lái)評(píng)估。

Drawback： 當(dāng)擴(kuò)展到數(shù)百萬(wàn)用戶或頻繁請(qǐng)求時(shí)，內(nèi)存使用量大（可以想象對(duì)每一個(gè)請(qǐng)求都會(huì)產(chǎn)生一個(gè)kv窗口計(jì)數(shù)器），計(jì)算成本高。

滑動(dòng)窗口限速器對(duì)應(yīng)嚴(yán)格意義的qps語(yǔ)義，從任意一個(gè)請(qǐng)求點(diǎn)切入的統(tǒng)計(jì)都試圖保持恒定的qps， 計(jì)算成本高。

那為什么會(huì)有漏桶和令牌桶算法？

上面的固定窗口和滑動(dòng)窗口算法，他們都聚焦在“維持qps”， 對(duì)于超出qps的流量他們會(huì)直接拒絕。

漏桶算法和令牌桶不僅聚焦“維持qps”， 同時(shí)不完全無(wú)腦拒絕：

在突發(fā)流量時(shí)，能給出等待處理/有暫存令牌迅速處理的行為， 也就是能應(yīng)對(duì)突發(fā)的流量波動(dòng)。

③ 漏桶限速 Leaky Bucket

想象一個(gè)底部有小孔的水桶，請(qǐng)求（水）被添加到桶中，并以穩(wěn)定的 “漏水 ”速度進(jìn)行處理，從而防止突然的洪水泛濫。

UserCase： 是平滑流量的理想選擇，例如在流媒體服務(wù)或支付處理中，可預(yù)測(cè)的輸出是至關(guān)重要的。

eg： 視頻流平臺(tái)對(duì)其內(nèi)容交付網(wǎng)絡(luò)的 API 調(diào)用進(jìn)行管理，確保一致的播放質(zhì)量。

Drawback： 不適合處理突發(fā)事件，如閃電銷售或促銷活動(dòng)。

漏洞算法基于“穩(wěn)定的漏水機(jī)制”，也維持了嚴(yán)格意義的qps語(yǔ)義，但是他有桶，短時(shí)的波動(dòng)流量可憑借桶容量排隊(duì)依次漏出， 超過(guò)桶容量的請(qǐng)求還是會(huì)被拒絕。

物理學(xué)意義（壓強(qiáng)/高度因素、動(dòng)態(tài)平衡）不能維持”穩(wěn)定的漏水機(jī)制“， 這里的穩(wěn)定漏水機(jī)制是需要技術(shù)強(qiáng)制實(shí)現(xiàn)。

④ 令牌桶限速

令牌以固定速率生成并存儲(chǔ)在一個(gè)桶中。每次請(qǐng)求都會(huì)消耗一個(gè)令牌；支持短時(shí)間瞬發(fā)（只要有令牌）。令牌產(chǎn)生快過(guò)實(shí)際請(qǐng)求，桶滿會(huì)被丟棄。

UserCase： 非常適合需要處理偶爾出現(xiàn)的流量高峰，同時(shí)執(zhí)行總體限制（如登錄嘗試或搜索查詢）的應(yīng)用程序接口。

eg： 某電子商務(wù)網(wǎng)站在結(jié)賬時(shí)允許每秒最多 20 個(gè)請(qǐng)求的突發(fā)流量，但將總體流量限制在每分鐘 100 個(gè)請(qǐng)求（r= 1.6, b=20）。

Drawback： 需要固定速率補(bǔ)充令牌，技術(shù)上有點(diǎn)復(fù)雜。

令牌桶通過(guò)穩(wěn)定的投放令牌，也嘗試維持了恒定的qps語(yǔ)義，嚴(yán)格上講他維持恒定的qps不是依靠穩(wěn)定的投放令牌， 而是消耗令牌。

消耗令牌的速率某些時(shí)刻可能就不是恒定的：在突發(fā)大流量時(shí)，桶中暫存的令牌可以迅速給到請(qǐng)求用(這一瞬間突破qps語(yǔ)義)，而不用像漏桶一樣排隊(duì)等待被處理（因流量漏水塑形）。

漏桶算法和令牌桶的區(qū)別

漏桶算法聚焦于”流量塑形“，有一定量的突發(fā)流量對(duì)應(yīng)能力，但不多；

令牌桶算法 大部分情況下會(huì)產(chǎn)生”流量塑形“的效果，能應(yīng)對(duì)突發(fā)大流量。

舉個(gè)例子：
容量均為20的漏桶和令牌桶， 分別以10/s的速率漏水、投放令牌。

日常流量恰好穩(wěn)定是10/s，某瞬間突發(fā)流量： 來(lái)了100個(gè)請(qǐng)求。

請(qǐng)求迅速堆滿漏桶：后80個(gè)請(qǐng)求被拒絕，前20個(gè)請(qǐng)求被處理（第一個(gè)請(qǐng)求迅速被處理，第20個(gè)在第2s末被處理完，beacuse漏水塑形）。

而令牌桶在這一瞬間，因?yàn)橥爸杏袝捍媪钆疲?可迅速給到請(qǐng)求使用，在這一瞬間能突破10/s
的qps（第1s放行30個(gè)請(qǐng)求，第2s依靠令牌放行10個(gè)請(qǐng)求，只要請(qǐng)求不自己取消，這突發(fā)的流量最后都會(huì)被消化掉）， 因此令牌桶才成為互聯(lián)網(wǎng)突發(fā)流量的優(yōu)質(zhì)限速算法。

2. 今日快閃：基于gin框架的原生api限速器

golang內(nèi)置了一款限速器golang/x/time/rate, 基于令牌桶限速算法。

維基百科令牌桶限速器
Think in this way, someone put 1 candy per second(r) in your bucket, then you can eat only 1 candy per sec. If your bucket can hold 10(b) candies and if you haven't eaten any of them for a while, your bucket will be full then you can eat 10 candies as fast as you can eat at a time.

將該限速器應(yīng)用到gin框架上：

package main

import (

    "github.com/gin-gonic/gin"

    "golang.org/x/time/rate"
)

func RateLimiter() gin.HandlerFunc {
    limiter := rate.NewLimiter(10, 30)
    return func(c *gin.Context) {

        if limiter.Allow() {
            c.Next()
        } else {
            c.JSON(http.StatusTooManyRequests, gin.H{
                "message": "Limite exceed",
            })
        }

    }

func NewLimiter(r Limit, b int) *Limiter 限速器控制事件發(fā)生的頻率。
它實(shí)現(xiàn)了一個(gè)大小為 b 的 “令牌桶”，最初是滿的，并以每秒 r 個(gè)令牌的速度重新裝滿。Limiter對(duì)多個(gè)goroutine同時(shí)使用是安全的。

Limiter主要有三個(gè)方法，Allow、Reserve、Wait,大多數(shù)時(shí)候開發(fā)者應(yīng)該使用Wait。

這三種方法都消耗一個(gè)令牌,當(dāng)沒(méi)有可用令牌時(shí)，它們的行為有所不同。

• 如果沒(méi)有可用的令牌，Allow 將返回 false。
• 如果沒(méi)有可用的令牌，Reserve 將返回未來(lái)令牌的預(yù)留以及調(diào)用者在使用它之前必須等待的時(shí)間。
• 如果沒(méi)有可用的令牌，則 Wait 會(huì)阻塞，直到可以獲得令牌或其關(guān)聯(lián)的 context.Context 被取消。

方法AllowN、ReserveN 和WaitN 消耗n 個(gè)令牌。

2.1 使用http基準(zhǔn)測(cè)試工具wrk壓測(cè)

wrk -t12 -c400 -d30s http://localhost:8080/themes/2
運(yùn)行基準(zhǔn)測(cè)試 30 秒，使用 12 個(gè)線程，并保持 400 個(gè) HTTP 連接打開。

① 不加限速中間件：

在此壓力下，宏觀的qps：250

② 將RateLimiter應(yīng)用到可能被刷單的API

r.GET("/themes/:id", RateLimiter(), func(c *gin.Context) {
......
})

在r=10， b=30的令牌桶設(shè)定下，大部分請(qǐng)求都被迅速拒絕了，顯得qps很大。

最后介紹一個(gè)企業(yè)級(jí)的ulule/limiter限速器

• Simple API
• "Store" approach for backend
• Redis support (but not tied too)
• Middlewares: HTTP, FastHTTP and Gin

小小外包仔， 拜托一鍵三連哦。??????