golang常見接口限流算法的實現(xiàn)
常見接口限流算法
今天面試時,面試官對我之前實習(xí)時實現(xiàn)的限流功能很感興趣,發(fā)起了奪命連問…
正好趁此機會好好整理一下,很棒。
常用的限流算法
固定窗口
實現(xiàn)思想
固定窗口的實現(xiàn)原理是:在指定周期內(nèi)累加訪問次數(shù),當(dāng)訪問次數(shù)達到限制時,觸發(fā)限流策略。
比如我們限制3s內(nèi)的請求不超過兩次,當(dāng)?shù)谌卧L問的時候檢測到當(dāng)前窗口內(nèi)以處理2次,對本次進行限制。
優(yōu)點:
- 實現(xiàn)簡單??梢灾苯油ㄟ^ redis 的 string 類型實現(xiàn)。將客戶端 ip + 訪問端口作為 key,訪問次數(shù)作為 value,并設(shè)置過期時間。
缺點:
- 限流不平滑,如第2秒到第5秒的窗口內(nèi)之間可以有3次請求。
代碼實現(xiàn)
固定窗口我們可以基于 redis 設(shè)置過期時間的 string 實現(xiàn)。當(dāng) 對 redis 的操作出現(xiàn) err 時,建議放行,因為限流的目的是降低服務(wù)器的壓力
,而不是讓服務(wù)器“宕機”。
var limit struct { count int cycle time.Duration } func init() { limit.count = 2 limit.cycle = 3 * time.Second } func ratelimit() func(c *gin.Context) { return func(c *gin.Context) { // 獲取客戶端IP clientIP := c.ClientIP() // 不包括參數(shù) path := c.Request.URL.Path key := clientIP + path valStr, err := rdb.Get(c, key).Result() if err != nil { // 根據(jù)業(yè)務(wù)處理(放行/攔截) } val, _ := strconv.Atoi(valStr) if val >= limit.count { c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{ "code": 1, "msg": "請求過于頻繁", }) return } count, err := rdb.Incr(context.Background(), key).Result() if err != nil { // 根據(jù)業(yè)務(wù)處理(放行/攔截) } if count == 1 { err = rdb.Expire(context.Background(), key, limit.cycle).Err() if err != nil { // 刪除key或者重試 } } if int(count) > limit.count { c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{ "code": 1, "msg": "請求過于頻繁", }) return } } }
滑動窗口
實現(xiàn)思想
滑動窗口是指在每一個時間窗口內(nèi)的次數(shù)都不超過限制次數(shù)。
還是以3秒內(nèi)請求不超過兩次為例子,當(dāng)我們每次請求時,統(tǒng)計一下前3秒到現(xiàn)在次數(shù)。如果大于等于2次時,則進行攔截。
優(yōu)點:
- 可以保證任意時間窗口內(nèi)的請求次數(shù)都不超過限制。
缺點:
實現(xiàn)相對復(fù)雜
還是不夠平滑。假如我們限制在60s 內(nèi)請求20次,會存在第一秒內(nèi)請求了20次,而在后面59秒內(nèi)都進行攔截的情況。
代碼實現(xiàn)
滑動窗口可以基于 reids 的 zset 實現(xiàn),以請求時的時間戳作為分?jǐn)?shù)。通過當(dāng)前查詢分?jǐn)?shù)區(qū)間[ 當(dāng)前時間戳 - 時間窗口 , 當(dāng)前時間戳 ),可以快速統(tǒng)計出時間窗口內(nèi)的次數(shù)。下面的代碼比固定窗口的代碼短的原因是因為直接將 err 忽略了(均不影響限流功能)。
var limit struct { count int64 cycle int64 // 單位s } func init() { limit.count = 2 limit.cycle = 3 } func ratelimit() func(c *gin.Context) { return func(c *gin.Context) { clientIp := c.ClientIP() path := c.Request.URL.Path key := clientIp + path t := time.Now().Unix() has, _ := rdb.Exists(context.Background(), key).Result() count, _ := rdb.ZCount(context.Background(), key, fmt.Sprintf("%d", t-limit.cycle), "+inf").Result() if has == 0 { // 如果是第一次創(chuàng)建,最長時間不超過1小時 rdb.Expire(context.Background(), key, 1*time.Hour) // 從功能上來說,此處不管是否設(shè)置成功,都不影響限流功能 } if count >= limit.count { // 超出次數(shù),限制 c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{ "code": 1, "msg": "請求過于頻繁", }) return } rdb.ZAdd(context.Background(), key, &redis.Z{Score: float64(t), Member: strconv.Itoa(int(t))}) // 刪除窗口外的數(shù)據(jù) go func() { memberToRemove, _ := rdb.ZRangeByScore(context.Background(), key, &redis.ZRangeBy{ Max: strconv.Itoa(int(t - limit.cycle)), Min: "0", }).Result() if len(memberToRemove) > 0 { rdb.ZRem(context.Background(), key, memberToRemove) } }() } }
漏桶算法
實現(xiàn)思想
漏桶算法就像小學(xué)的游泳池加水放水問題,不管如何加水,放水的速度都是固定的。
漏桶算法的原理是將請求視為水,漏桶用來存貯這些請求。漏桶有一個固定的容量,并且底部有一個小孔,以固定的速度漏水,如果漏桶已滿,超出部分的流量將被丟棄(或排隊等待)。
優(yōu)點:
- 平滑限制請求的處理速度,避免瞬間請求過多導(dǎo)致系統(tǒng)崩潰,通過桶的大小和漏出速率靈活時應(yīng)不同場景。
缺點:
- 太平滑了,無法應(yīng)對突發(fā)流量場景。
中間件
go有相關(guān)的中間件,何苦自己造輪子。"go.uber.org/ratelimit"
包正是基于漏桶算法實現(xiàn)的。
使用方式:
- 通過 ratelimit.New 創(chuàng)建限流器對象,參數(shù)為每秒允許的請求數(shù)(RPS)。
- 使用 Take() 方法來獲取限流許可,該方法會阻塞請求知道滿足限速要求。
官方示例:
import ( "fmt" "time" "go.uber.org/ratelimit" ) func main() { rl := ratelimit.New(100) // 每秒多少次 prev := time.Now() for i := 0; i < 10; i++ { now := rl.Take() // 平均時間 fmt.Println(i, now.Sub(prev)) prev = now } // Output: // 0 0 // 1 10ms // 2 10ms // 3 10ms // 4 10ms // 5 10ms // 6 10ms // 7 10ms // 8 10ms // 9 10ms }
代碼實現(xiàn)
如果是以所有的請求為粒度則定義一個全局的 ratelimit 即可。下面是以ip+接口
為粒度的限制,需要定義一個map存放 key 和 與之對應(yīng)的限流器。
import ( "github.com/gin-gonic/gin" "go.uber.org/ratelimit" "sync" "time" ) var limiters sync.Map func ratelimitMiddleware() func(c *gin.Context) { return func(c *gin.Context) { clientIp := c.ClientIP() path := c.Request.URL.Path key := clientIp + path var rl ratelimit.Limiter if limiterVal, ok := limiters.Load(key); ok { rl = limiterVal.(ratelimit.Limiter) } else { newLimiter := ratelimit.New(1) // 每秒只能請求1次 limiters.Store(key, newLimiter) rl = newLimiter go func(string) { // 簡易回收key,防止limiters 無限增大 time.Sleep(1 * time.Hour) limiters.Delete(key) }(key) } rl.Take() // 超過請求次數(shù)會進行阻塞,直到放行或放棄請求 } }
令牌桶算法
實現(xiàn)思想
令牌桶(Token Bucket)算法與漏桶十分相似,不過前者是服務(wù)端產(chǎn)生“水”,后者是服務(wù)端消費“水”。
令牌桶算法是指在固定時間間隔內(nèi)向“桶”中添加“令牌”,桶滿則暫時不放。請求在處理前需要從桶中獲取令牌。如果桶中有足夠的令牌,請求被處理;否則,請求被拒絕或等待。
中間件
基于此算法實現(xiàn)的中間件有:github.com/juju/ratelimit
、golang.org/x/time/rate
等。
下面簡單說一下 time/rate
的使用。
聲明一個限流器
limiter := rate.NewLimiter(10, 2)
第一個參數(shù)代表每秒向令牌桶中產(chǎn)生多少token。第二個參數(shù)代表令牌桶的大小,且初始狀態(tài)下令牌桶是滿的。
消費Token
Wait、WaitN
func (lim *Limiter) Wait(ctx context.Context) (err error) func (lim *Limiter) WaitN(ctx context.Context, n int) (err error)
Wait實際上就是WaitN(context.Background(),1)
。當(dāng)桶內(nèi) Token 數(shù)組不足(小于N),那么Wait方法將會阻塞一段時間,直至Token滿足條件。如果充足則直接返回。
Allow、AllowN
Allow與Wait十分相似,都是用來消費Token,區(qū)別是當(dāng)桶中Token數(shù)量不足時,前者立即返回,后者阻塞至滿足條件。
func (lim *Limiter) Allow() bool func (lim *Limiter) AllowN(now time.Time, n int) bool
Allow 實際上是 AllowN(time.Now(),1)。
AllowN方法表示,截止到當(dāng)前某一時刻,目前桶中數(shù)目是否至少為n個,滿足則返回true,同時從桶中消費 n 個 token。反之返回不消費 Token,false。
通常應(yīng)對這樣的線上場景,如果請求速率過快,就直接丟棄到某些請求。
Reserver、ReserveN
官方提供的限流器有阻塞等待式的 Wait,也有直接判斷方式的 Allow,還有提供了自己維護預(yù)留式的,但核心的實現(xiàn)都是下面的 reserveN 方法。
func (lim *Limiter) Reserve() *Reservation func (lim *Limiter) ReserveN(now time.Time, n int) *Reservation
當(dāng)調(diào)用完成后,無論 Token 是否充足,都會返回一個 *Reservation
對象。
你可以調(diào)用該對象的 Delay()
方法, 該方法返回了需要等待的時間。如果等待時間為0,則說明不用等待。必須等到等待時間結(jié)束之后,才能進行接下來的工作。
如果不想等待,可以調(diào)用 Cancel()
方法,該方法會將 Token 歸還。
代碼實現(xiàn)
下面還是以Ip + path
為粒度進行限制,和令牌桶差不多。
func ratelimitMiddleware() func(gin.Context) { return func(c gin.Context) { client := c.ClientIP() path := c.Request.URL.Path key := client + path var rl *rate.Limiter if limitersVal, ok := limiters.Load(key); ok { rl = limitersVal.(*rate.Limiter) } else { newLimiter := rate.NewLimiter(1, 10) limiters.Store(key, newLimiter) rl = newLimiter go func(string2 string) { time.Sleep(1 * time.Second) limiters.Delete(key) }(key) } if !rl.Allow() { c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{ "code": 1, "msg": "請求過于頻繁", }) } } }
小結(jié)
- 固定窗口計數(shù)器算法:
- 優(yōu)點
- 實現(xiàn)簡單,易于理解。
- 可以精確控制每個窗口期內(nèi)的請求數(shù)量。
- 缺點
- 無法應(yīng)對短時間內(nèi)的請求高峰,可能導(dǎo)致請求在窗口切換時突然增加,造成瞬時壓力。
- 無法平滑處理請求,可能導(dǎo)致用戶體驗不佳。
- 優(yōu)點
- 滑動窗口算法:
- 優(yōu)點
- 相對于固定窗口算法,可以更平滑地處理請求,減少瞬時壓力。
- 可以更靈活地應(yīng)對請求的波動。
- 缺點
- 實現(xiàn)相對復(fù)雜,需要維護多個計數(shù)器。
- 可能會因為窗口滑動導(dǎo)致計數(shù)器更新的開銷。
- 優(yōu)點
- 漏桶算法:
- 優(yōu)點
- 實現(xiàn)簡單,易于控制數(shù)據(jù)的輸出速率。
- 可以平滑處理請求,避免瞬時壓力。
- 缺點
- 無法應(yīng)對突發(fā)請求,可能導(dǎo)致請求長時間等待。
- 處理速度固定,不夠靈活。
- 優(yōu)點
- 令牌桶算法:
- 優(yōu)點
- 可以控制平均傳輸速率,同時允許一定程度的突發(fā)請求。
- 靈活性高,適用于請求速率不均勻的場景。
- 缺點
- 實現(xiàn)相對復(fù)雜,需要維護令牌的生成和消耗。
- 需要合理設(shè)置令牌的生成速率和桶的大小,否則可能無法達到預(yù)期的限流效果。
- 優(yōu)點
到此這篇關(guān)于golang常見接口限流算法的實現(xiàn)的文章就介紹到這了,更多相關(guān)golang 接口限流 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
一文帶你使用golang手?jǐn)]一個websocket中間件
這篇文章主要為大家詳細介紹了如何使用golang手?jǐn)]一個websocket中間件,文中的示例代碼講解詳細,具有一定的借鑒價值,感興趣的小伙伴可以參考一下2023-12-12Go語言實戰(zhàn)之詳細掌握正則表達式的應(yīng)用與技巧
正則表達式是一種從左到右與主題字符串匹配的模式,正則表達式用于替換字符串中的文本,驗證表單,基于模式匹配從字符串中提取子字符串等等,這篇文章主要給大家介紹了關(guān)于Go語言實戰(zhàn)之詳細掌握正則表達式的應(yīng)用與技巧,需要的朋友可以參考下2023-12-12