常見的限流算法

固定窗口計數(shù)器算法

固定窗口計數(shù)器算法將時間分為固定大小的窗口，例如1秒。在每個窗口中，服務會記錄它接收到的請求數(shù)。如果在一個窗口中的請求數(shù)超過了預先設定的閾值，那么新的請求將被拒絕，直到進入下一個窗口。

這種算法簡單易實現(xiàn)，但可能會導致窗口邊界附近的請求突發(fā)。例如，如果窗口大小為1秒，閾值為100，那么在1秒的邊界處，服務可能會在短時間內(nèi)處理200個請求。

滑動窗口計數(shù)器算法

滑動窗口計數(shù)器算法試圖解決固定窗口計數(shù)器算法中的請求突發(fā)問題。它將窗口分成更小的子窗口，例如將1秒分為10個100毫秒的子窗口。每次接收到請求時，服務會更新當前子窗口的計數(shù)器。服務會檢查過去的N個子窗口的計數(shù)器之和，如果這個和超過閾值，那么新的請求將被拒絕。

這種算法可以更好地平滑請求流量，但實現(xiàn)起來相對復雜，因為需要跟蹤多個子窗口的計數(shù)器。

令牌桶算法

令牌桶算法維護一個令牌桶，其中包含一定數(shù)量的令牌。令牌以恒定速率添加到桶中，直到達到桶的容量。每次接收到請求時，服務會嘗試從桶中獲取一個令牌。如果桶中有足夠的令牌，請求被允許處理；如果沒有足夠的令牌，請求將被拒絕。

令牌桶算法允許短暫的請求突發(fā)，因為在低流量時期，令牌可以累積到桶的容量。這種算法在實踐中表現(xiàn)良好，但實現(xiàn)起來相對復雜。

漏桶算法

漏桶算法使用一個隊列模擬一個漏水的桶。請求作為水滴進入隊列，以恒定速率從隊列中移除并處理。如果隊列已滿，新的請求將被拒絕。

漏桶算法可以平滑請求流量，但它不能處理突發(fā)流量，因為請求處理速率是固定的。實現(xiàn)漏桶算法也相對復雜，因為需要在后臺使用定時器或其他機制來以恒定速率處理隊列中的請求。

time/rate

主要方法

• NewLimiter(limit Limit, burst int) *Limiter: 創(chuàng)建一個新的限流器，參數(shù)包括每秒允許的事件數(shù)量（limit）和令牌桶容量（burst）。
• (lim *Limiter) Allow() bool: 檢查令牌桶中是否有可用的令牌。如果有可用令牌，則從桶中取走一個令牌并返回 true；否則返回 false。
• (lim *Limiter) AllowN(now time.Time, n int) bool: 與 Allow() 類似，但檢查 n 個令牌是否可用。如果有足夠的令牌，從桶中取走 n 個令牌并返回 true；否則返回 false。
• (lim *Limiter) Wait(ctx context.Context) error: 阻塞等待，直到有一個可用的令牌。如果在等待過程中 context 被取消或超時，將返回一個錯誤。
• (lim *Limiter) WaitN(ctx context.Context, n int) error: 阻塞等待，直到有 n 個可用的令牌。如果在等待過程中 context 被取消或超時，將返回一個錯誤。
• (lim *Limiter) Reserve() *Reservation: 返回一個預留令牌的 Reservation 對象。你可以根據(jù)需要等待預留令牌或取消預留。
• (lim *Limiter) ReserveN(now time.Time, n int) *Reservation: 類似于 Reserve()，但預留 n 個令牌。

各個方法的作用

• NewLimiter 用于創(chuàng)建一個新的限流器實例。
• Allow 和 AllowN 用于快速檢查是否有足夠的令牌可用，這些方法非阻塞。
• Wait 和 WaitN 用于阻塞等待直到有足夠的令牌可用，這些方法會阻塞。
• Reserve 和 ReserveN 用于預留令牌，允許您根據(jù)需要等待預留令牌或取消預留。

time/rate 是如何實現(xiàn)限流的

time/rate 包基于令牌桶算法實現(xiàn)限流。限流器通過一個恒定速率（limit）向令牌桶添加令牌，直到桶的容量（burst）達到上限。每當處理一個請求時，限流器會嘗試從令牌桶中取出一個或多個令牌。

Allow 和 AllowN 方法檢查令牌桶中是否有足夠的令牌。如果沒有足夠的令牌，這些方法會立即返回 false，表示應拒絕請求。Wait 和 WaitN 方法會阻塞等待，直到有足夠的令牌可用。如果在等待過程中上下文（context）被取消或超時，這些方法會返回一個錯誤，表示請求被拒絕。Reserve 和 ReserveN 方法提供了更靈活的方式來預留令牌，您可以根據(jù)需要等待預留的令牌或取消預留。

通過這些方法，time/rate 限流器可以控制處理請求的速率，確保它不會超過設定的限制。通過調(diào)整令牌生成速率和令牌桶容量，您可以根據(jù)實際需求和系統(tǒng)負載來調(diào)整限流策略。

源碼解析

令牌桶限流器的定義

在 rate.go 文件中，定義了 Limiter 結(jié)構(gòu)體：

type Limiter struct {
    mu     sync.Mutex
    limit  Limit
    tokens float64
    // last 是上次令牌桶更新的時間
    last time.Time
    // 用于調(diào)整令牌桶更新時間的時鐘
    clock Clock
    // 用于在 Wait 系列方法中進行休眠的定時器
    sleepFn func(time.Duration)
}

Limiter 結(jié)構(gòu)體包含了一些關鍵屬性，例如令牌生成速率（limit）、當前令牌數(shù)（tokens）和上次更新時間（last）。

令牌桶更新

time/rate 包中的核心函數(shù)之一是 reserveN，它負責預留 N 個令牌。在此過程中，令牌桶會根據(jù)時間更新。

func (lim *Limiter) reserveN(now time.Time, n int) *Reservation {
    lim.mu.Lock()
    defer lim.mu.Unlock()
    // 更新令牌桶
    now, tokens := lim.advance(now)
    // 計算需要的令牌數(shù)與當前可用令牌數(shù)之間的差值
    delta := float64(n) - tokens
    // 計算等待時間
    waitDuration := lim.limit.durationFromTokens(delta)
    // 更新令牌桶狀態(tài)
    tokens -= float64(n)
    lim.last = now.Add(waitDuration)
    lim.tokens = tokens
    return &Reservation{
        ok:        true,
        lim:       lim,
        tokens:    n,
        timeToAct: now.Add(waitDuration),
    }
}

在 reserveN 函數(shù)中，首先調(diào)用 advance 函數(shù)來更新令牌桶：

func (lim *Limiter) advance(now time.Time) (time.Time, float64) {
    last := lim.last
    // 計算上次更新以來經(jīng)過的時間
    elapsed := now.Sub(last)
    // 根據(jù)經(jīng)過的時間計算生成的令牌數(shù)
    delta := elapsed.Seconds() * float64(lim.limit)
    // 更新令牌桶中的令牌數(shù)，但不超過令牌桶容量
    tokens := math.Min(lim.tokens+delta, float64(lim.limit.Burst()))
    return now, tokens
}

advance 函數(shù)根據(jù)時間更新令牌桶，計算從上次更新以來生成的令牌數(shù)量，并將新令牌添加到桶中，但不超過桶的容量。

令牌預留和等待

在 reserveN 函數(shù)中，首先計算需要的令牌數(shù)與當前可用令牌數(shù)之間的差值。然后根據(jù)差值計算等待時間。如果等待時間為正值，則表示需要等待一段時間

才能獲得足夠的令牌。最后，更新令牌桶狀態(tài)，將所需令牌數(shù)從當前令牌數(shù)中減去。

reserveN 函數(shù)返回一個 Reservation 對象，其中包含預留的令牌數(shù)、等待時間等信息。Reservation 結(jié)構(gòu)體定義如下：

type Reservation struct {
    ok        bool
    lim       *Limiter
    tokens    int
    timeToAct time.Time
}

Reservation 對象提供了一些方法，例如 Delay（返回需要等待的時間）和 Cancel（取消預留）。這些方法允許用戶在需要時等待預留的令牌，或在不再需要令牌時取消預留。

公開 API

time/rate 包提供了一系列公開 API，例如 Allow, AllowN, Wait, WaitN, Reserve 和 ReserveN。這些方法都是基于 reserveN 函數(shù)的封裝。例如，Allow 方法只需檢查預留的等待時間是否為零：

func (lim *Limiter) Allow() bool {
    return lim.AllowN(time.Now(), 1)
}
func (lim *Limiter) AllowN(now time.Time, n int) bool {
    return lim.reserveN(now, n).Delay() == 0
}

類似地，Wait 和 WaitN 方法將阻塞等待，直到預留的等待時間過去：

func (lim *Limiter) Wait(ctx context.Context) error {
    return lim.WaitN(ctx, 1)
}
func (lim *Limiter) WaitN(ctx context.Context, n int) error {
    if n > lim.limit.Burst() {
        return fmt.Errorf("rate: Wait(n=%d) exceeds limiter's burst %d", n, lim.limit.Burst())
    }
    r := lim.ReserveN(time.Now(), n)
    delay := r.DelayFrom(time.Now())
    if delay == 0 {
        return nil
    }
    t := lim.clock.AfterFunc(delay, r.Cancel)
    defer t.Stop()
    select {
    case <-ctx.Done():
        r.Cancel()
        return ctx.Err()
    case <-t.C:
        return nil
    }
}

總之，time/rate 包通過令牌桶算法實現(xiàn)了限流。它提供了一系列 API，允許用戶在不同場景下靈活地控制請求速率。內(nèi)部實現(xiàn)主要依賴于 reserveN 函數(shù)來更新令牌桶狀態(tài)，并根據(jù)需要等待或預留令牌。

到此這篇關于Golang官方限流器time/rate的使用與實現(xiàn)詳解的文章就介紹到這了,更多相關Golang限流器time/rate內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論