golang常見接口限流算法的實(shí)現(xiàn)

更新時(shí)間：2025年03月03日 09:39:38 作者：木易小熙

本文主要介紹了golang常見接口限流算法的實(shí)現(xiàn),包含固定窗口、滑動(dòng)窗口、漏桶和令牌桶,具有一定的參考價(jià)值,感興趣的可以了解一下

常見接口限流算法

今天面試時(shí)，面試官對(duì)我之前實(shí)習(xí)時(shí)實(shí)現(xiàn)的限流功能很感興趣，發(fā)起了奪命連問…

正好趁此機(jī)會(huì)好好整理一下，很棒。

常用的限流算法

固定窗口

實(shí)現(xiàn)思想

固定窗口的實(shí)現(xiàn)原理是：在指定周期內(nèi)累加訪問次數(shù)，當(dāng)訪問次數(shù)達(dá)到限制時(shí)，觸發(fā)限流策略。

比如我們限制3s內(nèi)的請(qǐng)求不超過兩次，當(dāng)?shù)谌卧L問的時(shí)候檢測(cè)到當(dāng)前窗口內(nèi)以處理2次，對(duì)本次進(jìn)行限制。

在這里插入圖片描述

優(yōu)點(diǎn)：

實(shí)現(xiàn)簡單。可以直接通過 redis 的 string 類型實(shí)現(xiàn)。將客戶端 ip + 訪問端口作為 key，訪問次數(shù)作為 value，并設(shè)置過期時(shí)間。

缺點(diǎn)：

限流不平滑，如第2秒到第5秒的窗口內(nèi)之間可以有3次請(qǐng)求。

代碼實(shí)現(xiàn)

固定窗口我們可以基于 redis 設(shè)置過期時(shí)間的 string 實(shí)現(xiàn)。當(dāng) 對(duì) redis 的操作出現(xiàn) err 時(shí)，建議放行，因?yàn)橄蘖鞯哪康氖?code>降低服務(wù)器的壓力，而不是讓服務(wù)器“宕機(jī)”。

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":  "請(qǐng)求過于頻繁",
			})
			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":  "請(qǐng)求過于頻繁",
			})
			return
		}
	}
}

滑動(dòng)窗口

實(shí)現(xiàn)思想

滑動(dòng)窗口是指在每一個(gè)時(shí)間窗口內(nèi)的次數(shù)都不超過限制次數(shù)。

還是以3秒內(nèi)請(qǐng)求不超過兩次為例子，當(dāng)我們每次請(qǐng)求時(shí)，統(tǒng)計(jì)一下前3秒到現(xiàn)在次數(shù)。如果大于等于2次時(shí)，則進(jìn)行攔截。

在這里插入圖片描述

優(yōu)點(diǎn)：

可以保證任意時(shí)間窗口內(nèi)的請(qǐng)求次數(shù)都不超過限制。

缺點(diǎn)：

實(shí)現(xiàn)相對(duì)復(fù)雜
還是不夠平滑。假如我們限制在60s 內(nèi)請(qǐng)求20次，會(huì)存在第一秒內(nèi)請(qǐng)求了20次，而在后面59秒內(nèi)都進(jìn)行攔截的情況。

代碼實(shí)現(xiàn)

滑動(dòng)窗口可以基于 reids 的 zset 實(shí)現(xiàn)，以請(qǐng)求時(shí)的時(shí)間戳作為分?jǐn)?shù)。通過當(dāng)前查詢分?jǐn)?shù)區(qū)間[ 當(dāng)前時(shí)間戳 - 時(shí)間窗口 , 當(dāng)前時(shí)間戳 )，可以快速統(tǒng)計(jì)出時(shí)間窗口內(nèi)的次數(shù)。下面的代碼比固定窗口的代碼短的原因是因?yàn)橹苯訉?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)建，最長時(shí)間不超過1小時(shí)
			rdb.Expire(context.Background(), key, 1*time.Hour) // 從功能上來說，此處不管是否設(shè)置成功，都不影響限流功能
		}
		if count >= limit.count { // 超出次數(shù)，限制
			c.AbortWithStatusJSON(http.StatusTooManyRequests, gin.H{
				"code": 1,
				"msg":  "請(qǐng)求過于頻繁",
			})
			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)
			}
		}()
	}
}

漏桶算法

實(shí)現(xiàn)思想

漏桶算法就像小學(xué)的游泳池加水放水問題，不管如何加水，放水的速度都是固定的。

漏桶算法的原理是將請(qǐng)求視為水，漏桶用來存貯這些請(qǐng)求。漏桶有一個(gè)固定的容量，并且底部有一個(gè)小孔，以固定的速度漏水，如果漏桶已滿，超出部分的流量將被丟棄（或排隊(duì)等待）。

在這里插入圖片描述

優(yōu)點(diǎn)：

平滑限制請(qǐng)求的處理速度，避免瞬間請(qǐng)求過多導(dǎo)致系統(tǒng)崩潰，通過桶的大小和漏出速率靈活時(shí)應(yīng)不同場(chǎng)景。

缺點(diǎn)：

太平滑了，無法應(yīng)對(duì)突發(fā)流量場(chǎng)景。

中間件

go有相關(guān)的中間件，何苦自己造輪子。"go.uber.org/ratelimit" 包正是基于漏桶算法實(shí)現(xiàn)的。

使用方式：

通過 ratelimit.New 創(chuàng)建限流器對(duì)象，參數(shù)為每秒允許的請(qǐng)求數(shù)（RPS）。
使用 Take() 方法來獲取限流許可，該方法會(huì)阻塞請(qǐng)求知道滿足限速要求。

官方示例：

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()	// 平均時(shí)間
        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
}

代碼實(shí)現(xiàn)

如果是以所有的請(qǐng)求為粒度則定義一個(gè)全局的 ratelimit 即可。下面是以ip+接口為粒度的限制，需要定義一個(gè)map存放 key 和與之對(duì)應(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)	// 每秒只能請(qǐng)求1次
			limiters.Store(key, newLimiter)
			rl = newLimiter
			go func(string) { // 簡易回收key，防止limiters 無限增大
				time.Sleep(1 * time.Hour)
				limiters.Delete(key)
			}(key)
		}

		rl.Take() // 超過請(qǐng)求次數(shù)會(huì)進(jìn)行阻塞，直到放行或放棄請(qǐng)求

	}
}

令牌桶算法

實(shí)現(xiàn)思想

令牌桶（Token Bucket）算法與漏桶十分相似，不過前者是服務(wù)端產(chǎn)生“水”，后者是服務(wù)端消費(fèi)“水”。

令牌桶算法是指在固定時(shí)間間隔內(nèi)向“桶”中添加“令牌”，桶滿則暫時(shí)不放。請(qǐng)求在處理前需要從桶中獲取令牌。如果桶中有足夠的令牌，請(qǐng)求被處理；否則，請(qǐng)求被拒絕或等待。

在這里插入圖片描述

中間件

基于此算法實(shí)現(xiàn)的中間件有：github.com/juju/ratelimit、golang.org/x/time/rate等。

下面簡單說一下 time/rate 的使用。

聲明一個(gè)限流器

limiter := rate.NewLimiter(10, 2)

第一個(gè)參數(shù)代表每秒向令牌桶中產(chǎn)生多少token。第二個(gè)參數(shù)代表令牌桶的大小，且初始狀態(tài)下令牌桶是滿的。

消費(fè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實(shí)際上就是WaitN(context.Background(),1)。當(dāng)桶內(nèi) Token 數(shù)組不足（小于N），那么Wait方法將會(huì)阻塞一段時(shí)間，直至Token滿足條件。如果充足則直接返回。

Allow、AllowN

Allow與Wait十分相似，都是用來消費(fèi)Token，區(qū)別是當(dāng)桶中Token數(shù)量不足時(shí)，前者立即返回，后者阻塞至滿足條件。

func (lim *Limiter) Allow() bool
func (lim *Limiter) AllowN(now time.Time, n int) bool

Allow 實(shí)際上是 AllowN(time.Now(),1)。

AllowN方法表示，截止到當(dāng)前某一時(shí)刻，目前桶中數(shù)目是否至少為n個(gè)，滿足則返回true，同時(shí)從桶中消費(fèi) n 個(gè) token。反之返回不消費(fèi) Token，false。

通常應(yīng)對(duì)這樣的線上場(chǎng)景，如果請(qǐng)求速率過快，就直接丟棄到某些請(qǐng)求。

Reserver、ReserveN

官方提供的限流器有阻塞等待式的 Wait，也有直接判斷方式的 Allow，還有提供了自己維護(hù)預(yù)留式的，但核心的實(shí)現(xiàn)都是下面的 reserveN 方法。

func (lim *Limiter) Reserve() *Reservation
func (lim *Limiter) ReserveN(now time.Time, n int) *Reservation

當(dāng)調(diào)用完成后，無論 Token 是否充足，都會(huì)返回一個(gè) *Reservation 對(duì)象。

你可以調(diào)用該對(duì)象的 Delay() 方法，該方法返回了需要等待的時(shí)間。如果等待時(shí)間為0，則說明不用等待。必須等到等待時(shí)間結(jié)束之后，才能進(jìn)行接下來的工作。

如果不想等待，可以調(diào)用 Cancel() 方法，該方法會(huì)將 Token 歸還。

代碼實(shí)現(xiàn)

下面還是以Ip + path 為粒度進(jìn)行限制，和令牌桶差不多。

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":  "請(qǐng)求過于頻繁",
			})
		}
	}
}

小結(jié)

固定窗口計(jì)數(shù)器算法:
- 優(yōu)點(diǎn)
  - 實(shí)現(xiàn)簡單，易于理解。
  - 可以精確控制每個(gè)窗口期內(nèi)的請(qǐng)求數(shù)量。
- 缺點(diǎn)
  - 無法應(yīng)對(duì)短時(shí)間內(nèi)的請(qǐng)求高峰，可能導(dǎo)致請(qǐng)求在窗口切換時(shí)突然增加，造成瞬時(shí)壓力。
  - 無法平滑處理請(qǐng)求，可能導(dǎo)致用戶體驗(yàn)不佳。
滑動(dòng)窗口算法:
- 優(yōu)點(diǎn)
  - 相對(duì)于固定窗口算法，可以更平滑地處理請(qǐng)求，減少瞬時(shí)壓力。
  - 可以更靈活地應(yīng)對(duì)請(qǐng)求的波動(dòng)。
- 缺點(diǎn)
  - 實(shí)現(xiàn)相對(duì)復(fù)雜，需要維護(hù)多個(gè)計(jì)數(shù)器。
  - 可能會(huì)因?yàn)榇翱诨瑒?dòng)導(dǎo)致計(jì)數(shù)器更新的開銷。
漏桶算法:
- 優(yōu)點(diǎn)
  - 實(shí)現(xiàn)簡單，易于控制數(shù)據(jù)的輸出速率。
  - 可以平滑處理請(qǐng)求，避免瞬時(shí)壓力。
- 缺點(diǎn)
  - 無法應(yīng)對(duì)突發(fā)請(qǐng)求，可能導(dǎo)致請(qǐng)求長時(shí)間等待。
  - 處理速度固定，不夠靈活。
令牌桶算法:
- 優(yōu)點(diǎn)
  - 可以控制平均傳輸速率，同時(shí)允許一定程度的突發(fā)請(qǐng)求。
  - 靈活性高，適用于請(qǐng)求速率不均勻的場(chǎng)景。
- 缺點(diǎn)
  - 實(shí)現(xiàn)相對(duì)復(fù)雜，需要維護(hù)令牌的生成和消耗。
  - 需要合理設(shè)置令牌的生成速率和桶的大小，否則可能無法達(dá)到預(yù)期的限流效果。