常見的限流算法

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

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

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

滑動(dòng)窗口計(jì)數(shù)器算法

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

這種算法可以更好地平滑請(qǐng)求流量，但實(shí)現(xiàn)起來相對(duì)復(fù)雜，因?yàn)樾枰櫠鄠€(gè)子窗口的計(jì)數(shù)器。

令牌桶算法

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

令牌桶算法允許短暫的請(qǐng)求突發(fā)，因?yàn)樵诘土髁繒r(shí)期，令牌可以累積到桶的容量。這種算法在實(shí)踐中表現(xiàn)良好，但實(shí)現(xiàn)起來相對(duì)復(fù)雜。

漏桶算法

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

漏桶算法可以平滑請(qǐng)求流量，但它不能處理突發(fā)流量，因?yàn)檎?qǐng)求處理速率是固定的。實(shí)現(xiàn)漏桶算法也相對(duì)復(fù)雜，因?yàn)樾枰诤笈_(tái)使用定時(shí)器或其他機(jī)制來以恒定速率處理隊(duì)列中的請(qǐng)求。

time/rate

主要方法

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

各個(gè)方法的作用

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

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

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

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

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

源碼解析

令牌桶限流器的定義

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

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

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

令牌桶更新

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

func (lim *Limiter) reserveN(now time.Time, n int) *Reservation {
    lim.mu.Lock()
    defer lim.mu.Unlock()
    // 更新令牌桶
    now, tokens := lim.advance(now)
    // 計(jì)算需要的令牌數(shù)與當(dāng)前可用令牌數(shù)之間的差值
    delta := float64(n) - tokens
    // 計(jì)算等待時(shí)間
    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ì)算上次更新以來經(jīng)過的時(shí)間
    elapsed := now.Sub(last)
    // 根據(jù)經(jīng)過的時(shí)間計(jì)算生成的令牌數(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í)間更新令牌桶，計(jì)算從上次更新以來生成的令牌數(shù)量，并將新令牌添加到桶中，但不超過桶的容量。

令牌預(yù)留和等待

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

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

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

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

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

公開 API

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

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 方法將阻塞等待，直到預(yù)留的等待時(shí)間過去：

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 包通過令牌桶算法實(shí)現(xiàn)了限流。它提供了一系列 API，允許用戶在不同場(chǎng)景下靈活地控制請(qǐng)求速率。內(nèi)部實(shí)現(xiàn)主要依賴于 reserveN 函數(shù)來更新令牌桶狀態(tài)，并根據(jù)需要等待或預(yù)留令牌。

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

最新評(píng)論