的文章(zhang)， 講(jiang)述了限速的使(shi)用場景和運作方式。

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

1.

① 固定窗口限速 Fixed Window Counter

跟蹤固(gu)定(ding)時間(jian)間(jian)隔（如 1 分鐘）內的請求(qiu)數量，一旦達到上限，就(jiu)會拒絕該窗口(kou)中的后續所有請求(qiu)。

UserCase： 可(ke)預測流(liu)量、低精度(du)需求(qiu)的(de)簡(jian)單API，比如云(yun)平(ping)臺會對開發(fa)者提供 “免費調用API”的(de)限速(su)額(e)度(du)。

eg： 公共(gong)天氣 API 允許每個用(yong)戶每分鐘(zhong) 100 次請求(qiu)，任何(he)額外請求(qiu)都會返回 “429 請求(qiu)過多 ”響(xiang)應。

Drawback： 客戶端(duan)可(ke)通過在兩個時間(jian)窗口(kou)的邊界堆砌(qi)請求（例(li)如，在1min時間(jian)窗口(kou)的第59秒和(he)下一個1min窗口(kou)的第1s都堆砌(qi)100 個請求）， 輕松突(tu)破qps=100/min 語(yu)義。

固定(ding)窗口算法對(dui)應(ying)最直觀意義(yi)的qps語義(yi)，但是qps漏洞也(ye)很明(ming)顯。

② 滑動窗口限速 Sliding Window Log

維(wei)護每個請求的時間戳日志，并根據滾動(dong)時間窗口計算限制。

UserCase：要(yao)求(qiu)高精度(du)的核心系統(tong)，如金融交易 API 或欺詐檢(jian)測機制。

eg： 銀(yin)行 API 限(xian)制每小時(shi)取款次(ci)數為(wei) 10 次(ci)，每次(ci)新請求(qiu)都(dou)要根據(ju)最近1小時(shi)的(de)取款次(ci)數來評估。

Drawback： 當擴展到(dao)數(shu)百萬(wan)用戶或頻繁請(qing)求(qiu)時，內存(cun)使用量大(da)（可(ke)以想象對每一個請(qing)求(qiu)都會產生(sheng)一個kv窗口計數(shu)器），計算(suan)成本高。

滑動窗口(kou)限速器對(dui)應嚴(yan)格意(yi)義的(de)qps語義，從任(ren)意(yi)一個請求點切入的(de)統計(ji)都試(shi)圖保持(chi)恒定的(de)qps， 計(ji)算成本高。

那為什么會有漏桶和令牌桶算法？

上面的(de)固(gu)定(ding)窗(chuang)口(kou)(kou)和滑動窗(chuang)口(kou)(kou)算法，他們都聚(ju)焦在“維持qps”， 對于超出qps的(de)流量他們會(hui)直接拒絕。

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

在突發(fa)(fa)流量時，能給(gei)出等待(dai)處理(li)/有暫存令(ling)牌迅速(su)處理(li)的(de)(de)行為， 也就(jiu)是能應對(dui)突發(fa)(fa)的(de)(de)流量波(bo)動。

③ 漏桶限速 Leaky Bucket

想象一(yi)個底部有(you)小孔的(de)水(shui)桶(tong)，請求（水(shui)）被添加到(dao)桶(tong)中，并(bing)以(yi)穩定的(de) “漏水(shui) ”速度進行處理(li)，從而防止突然(ran)的(de)洪水(shui)泛濫。

UserCase： 是(shi)平滑流(liu)(liu)量的理想選擇，例如在(zai)流(liu)(liu)媒體服務或支(zhi)付(fu)處(chu)理中，可預測的輸出是(shi)至關(guan)重要的。

eg： 視頻流平臺對其內(nei)容(rong)交付網絡的 API 調用進(jin)行管理，確保一致的播放質(zhi)量。

Drawback： 不適合(he)處理突發事件，如閃電銷售或促銷活(huo)動。

漏洞算法基于“穩定的漏水機制”，也維持了嚴格意義的qps語義，但是他有桶，短時的波動流量可憑借桶容量排隊依次漏出， 超過桶容量的請(qing)求還是會被拒絕。

物理學意義（壓強/高度(du)因素、動態(tai)平衡）不能維持(chi)”穩(wen)定的漏水機(ji)制(zhi)“， 這(zhe)里的穩(wen)定漏水機(ji)制(zhi)是需要(yao)技(ji)術強制(zhi)實(shi)現。

④

令(ling)(ling)牌(pai)以固(gu)定速(su)率生成(cheng)并存儲在一個(ge)桶(tong)(tong)中。每次請求(qiu)都會消耗一個(ge)令(ling)(ling)牌(pai)；支持短(duan)時間(jian)瞬發(fa)（只要有令(ling)(ling)牌(pai)）。令(ling)(ling)牌(pai)產生快過(guo)實際請求(qiu)，桶(tong)(tong)滿會被(bei)丟棄。

UserCase： 非常適合需(xu)要處理偶爾(er)出現的流(liu)量(liang)高峰，同時執行(xing)總體限制(zhi)（如登錄(lu)嘗試或(huo)搜索查(cha)詢(xun)）的應(ying)用程序接(jie)口。

eg： 某電子商務網站在(zai)(zai)結賬時(shi)允許(xu)每秒最多 20 個(ge)請求(qiu)的突發流量(liang)，但將總體流量(liang)限制在(zai)(zai)每分鐘 100 個(ge)請求(qiu)（r= 1.6, b=20）。

Drawback： 需要(yao)固定速率補充(chong)令牌(pai)，技術上有點復雜。

令(ling)(ling)(ling)牌(pai)桶通過穩定(ding)的投放令(ling)(ling)(ling)牌(pai)，也(ye)嘗試維持了恒(heng)定(ding)的qps語義，嚴格(ge)上講他維持恒(heng)定(ding)的qps不(bu)是依靠穩定(ding)的投放令(ling)(ling)(ling)牌(pai)， 而(er)是消耗(hao)令(ling)(ling)(ling)牌(pai)。

消耗令牌的(de)速(su)率某些時(shi)刻可能就不是恒定的(de)：在(zai)突發(fa)大流量時(shi)，桶中暫存的(de)令牌可以迅速(su)給到(dao)請求用(這一瞬間突破qps語義)，而(er)不用像漏桶一樣排隊等待被(bei)處理（因(yin)流量漏水塑(su)形）。

漏桶算法和令牌桶的區別

漏桶算法聚焦(jiao)于”流(liu)量(liang)塑形(xing)“，有一定(ding)量(liang)的突發(fa)流(liu)量(liang)對應(ying)能力，但(dan)不多；

令牌(pai)桶算法 大(da)部分情況下會產生(sheng)”流量(liang)塑(su)形“的效果(guo)，能(neng)應(ying)對(dui)突(tu)發大(da)流量(liang)。

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

日(ri)常流量恰(qia)好穩定是(shi)10/s，某瞬間突發流量： 來了100個(ge)請求。

請求迅速堆滿漏(lou)桶：后80個(ge)(ge)請求被拒絕，前20個(ge)(ge)請求被處理(li)(li)（第(di)一個(ge)(ge)請求迅速被處理(li)(li)，第(di)20個(ge)(ge)在第(di)2s末(mo)被處理(li)(li)完，beacuse漏(lou)水塑(su)形）。

而令牌桶在這一瞬間，因為桶中有暫存令牌， 可迅速給到請求使用，在這一瞬間能突破10/s
的(de)qps（第1s放(fang)行30個請求(qiu)，第2s依靠令牌放(fang)行10個請求(qiu)，只要請求(qiu)不自己取消，這突發(fa)的(de)流(liu)量最后都會被消化掉）， 因此令牌桶(tong)才成為互(hu)聯網突發(fa)流(liu)量的(de)優質限速算法。

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

golang內置了一款限速器, 基于令牌桶限速算法。

維基百科
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.

將該(gai)限速(su)器應用到gin框(kuang)架上：

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 限速器控制事件發生的頻率。
它實現了一個大小為 b 的 “令牌桶”，最初是滿的，并以每秒 r 個令牌的速度重新裝滿。Limiter對多(duo)個goroutine同時使用是安全的。

Limiter主要有三個方法，Allow、Reserve、Wait,大多數時候開發者應該使用Wait。

這(zhe)三種方法都消耗一個令(ling)牌(pai),當(dang)沒有(you)可用令(ling)牌(pai)時，它們的行為有(you)所不(bu)同。

• 如果沒有可用的令牌，Allow 將返回 false。
• 如果沒有可用的令牌，Reserve 將返回未來令牌的預留以及調用者在使用它之前必須等待的時間。
• 如果沒有可用的令牌，則 Wait 會阻塞，直到可以獲得令牌或其關聯的 context.Context 被取消。

方法AllowN、ReserveN 和WaitN 消耗n 個令牌。

2.1 使用壓測

wrk -t12 -c400 -d30s //localhost:8080/themes/2
運行(xing)基(ji)準測(ce)試 30 秒(miao)，使用 12 個(ge)線程，并(bing)保持 400 個(ge) HTTP 連接打(da)開。

① 不(bu)加限速中間件(jian)：

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

② 將RateLimiter應用(yong)到可(ke)能被刷單的API

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

在r=10， b=30的令牌桶(tong)設定下，大部分(fen)請(qing)求都被(bei)迅速拒絕了(le)，顯得qps很大。

最后介紹一(yi)個(ge)企業級的

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

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