關(guān)注HHF技術(shù)博客公眾號(hào)

限流器(Rate Limiter)在微服務(wù)中的重要性不言而喻了. 下游服務(wù)的穩(wěn)定性, 防止過(guò)載, 全靠這個(gè)組件來(lái)保證. 限流器的實(shí)現(xiàn)方式, 基本有下面幾種方式

1. 計(jì)數(shù)器
2. 漏斗通 (Leaky Bucket)
3. 令牌桶 (Token Bucket)
4. 基于 BBR 算法的自適應(yīng)限流
5. 基于 Nginx 的限流
6. 分布式限流

這個(gè)系列的文章會(huì)逐一介紹各種限流器. 本篇文章會(huì)結(jié)合比較成熟組件介紹: 漏斗桶

什么是限流器

Web servers typically use a central in-memory key-value database, like Redis or Aerospike, for session management. A rate limiting algorithm is used to check if the user session (or IP address) has to be limited based on the information in the session cache.

In case a client made too many requests within a given time frame, HTTP servers can respond with status code 429: Too Many Requests

這段話是摘自維基百科. 簡(jiǎn)單來(lái)說(shuō)限流器是基于 KV 內(nèi)存數(shù)據(jù)庫(kù)的一個(gè)限速判斷, 在給定的時(shí)間內(nèi), 客戶端請(qǐng)求次數(shù)過(guò)多, 服務(wù)器就會(huì)返回狀態(tài)碼 429: Too Many Request

計(jì)數(shù)器

計(jì)數(shù)器是一種最簡(jiǎn)單的限流器.

如果把 QPS 設(shè)置為100, 從第一個(gè)請(qǐng)求進(jìn)來(lái)開(kāi)始計(jì)時(shí)故慈，在接下去的1s內(nèi)槽地，每來(lái)一個(gè)請(qǐng)求，就把計(jì)數(shù)加1怖侦，如果累加的數(shù)字達(dá)到了100，那么后續(xù)的請(qǐng)求就會(huì)被全部拒絕。等到1s結(jié)束后，把計(jì)數(shù)恢復(fù)成0楷怒，重新開(kāi)始計(jì)數(shù). 這種計(jì)數(shù)器一般稱為固定窗口計(jì)數(shù)器算法.

可以看到計(jì)數(shù)器雖說(shuō)有一定的緩沖空間, 但是需要一定的恢復(fù)空窗期, 在這個(gè)恢復(fù)時(shí)間內(nèi)請(qǐng)求全部拒絕. 計(jì)數(shù)器還存在著另外一個(gè)問(wèn)題, 特殊情況下會(huì)讓請(qǐng)求的通過(guò)量為限制的兩倍.

考慮如下情況：

限制 1 秒內(nèi)最多通過(guò) 5 個(gè)請(qǐng)求，在第一個(gè)窗口的最后半秒內(nèi)通過(guò)了 5 個(gè)請(qǐng)求瓦灶，第二個(gè)窗口的前半秒內(nèi)又通過(guò)了 5 個(gè)請(qǐng)求率寡。這樣看來(lái)就是在 1 秒內(nèi)通過(guò)了 10 個(gè)請(qǐng)求

綜合來(lái)看, 計(jì)數(shù)器方式的限流是比較簡(jiǎn)單粗暴的, 我們需要更加優(yōu)雅的限流方式

漏斗桶

相對(duì)于計(jì)數(shù)器的粗魯方式, 漏斗桶會(huì)更加優(yōu)雅一些, 如下圖

leaky_bucket

其實(shí)從字面就很好理解. 類似生活用到的漏斗, 當(dāng)客戶端請(qǐng)求進(jìn)來(lái)時(shí)，相當(dāng)于水倒入漏斗倚搬，然后從下端小口慢慢勻速的流出冶共。不管上面流量多大，下面流出的速度始終保持不變.

當(dāng)水流入速度過(guò)大時(shí), 漏斗就會(huì)溢出, 同樣會(huì)造成服務(wù)拒絕. 相對(duì)于計(jì)數(shù)器的在恢復(fù)期內(nèi)全部拒絕請(qǐng)求, 因?yàn)槁┒吠皶?huì)以一定的速率消費(fèi)請(qǐng)求, 這樣就能夠讓后續(xù)的請(qǐng)求有機(jī)會(huì)進(jìn)入到漏斗桶里面.

漏斗桶的弊端

由于漏斗桶有點(diǎn)類似隊(duì)列, 先進(jìn)去才能被消費(fèi)掉, 如果漏斗桶溢出了, 后續(xù)的請(qǐng)求都直接丟棄了, 也就是說(shuō)漏斗桶是無(wú)法短時(shí)間應(yīng)對(duì)突發(fā)流量的. 對(duì)于互聯(lián)網(wǎng)行業(yè)來(lái)說(shuō), 面對(duì)突發(fā)流量, 不能一刀切將突發(fā)流量全部干掉, 這樣會(huì)給產(chǎn)品帶來(lái)口碑上影響. 因此漏斗桶也不是完美的方案.

不過(guò)漏斗桶能夠限制數(shù)據(jù)的平均傳輸速率, 能夠滿足大部分的使用場(chǎng)景的. 如: 我們可以使用漏斗桶限制論壇發(fā)帖頻率

Uber Ratelimit

Uber Ratelimit 是漏斗桶的一個(gè)具體實(shí)現(xiàn). 下面主要結(jié)合 Uber Ratelimit 來(lái)介紹 Leaky Buckt(漏洞桶)

官方 demo

func main() {
    rl := ratelimit.New(100) // per second
    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

從這個(gè)例子的輸出結(jié)果, 可以看出來(lái)有下面這些特點(diǎn):

• 初始化時(shí)需要設(shè)置 bucket 大小
• 輸出結(jié)果是間隔 10ms, 由此可以看出來(lái) leaky bucket 一定是保證勻速率的從桶內(nèi)取值
• 通過(guò) Take() 函數(shù)與 ratelimiter 來(lái)交互, 但是 Take() 的返回值卻是上一次拿到的請(qǐng)求時(shí)間

gin 中間件

import (
    "fmt"
    "github.com/gin-gonic/gin"
    "go.uber.org/ratelimit"
    "time"
)

var rl ratelimit.Limiter

func leakyBucketRateLimiter() gin.HandlerFunc {
    prev := time.Now()
    return func(c *gin.Context) {
        now := rl.Take()
        fmt.Println(now.Sub(prev)) // 這里不需要, 只是打印下多次請(qǐng)求之間的時(shí)間間隔
        prev = now // 這里不需要, 只是打印下多次請(qǐng)求之間的時(shí)間間隔
    }
}

func main() {
    engine := gin.Default()
    engine.GET("/test", leakyBucketRateLimiter(), func(context *gin.Context) {
        context.JSON(200, true)
    })
    engine.Run(":9191")
}

func init() {
    rl = ratelimit.New(10)
}

Output:

[GIN] 2020/06/29 - 23:21:22 | 200 |     166.119μs |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:22 | 200 |  116.954372ms |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:23 | 200 |  203.502985ms |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:23 | 200 |  303.266345ms |       127.0.0.1 | GET      /test

....

[GIN] 2020/06/29 - 23:21:57 | 200 | 24.899798034s |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:57 | 200 | 24.899258055s |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:57 | 200 | 24.899960588s |       127.0.0.1 | GET      /test
100ms
[GIN] 2020/06/29 - 23:21:57 | 200 | 24.899834294s |       127.0.0.1 | GET      /test

從這個(gè)例子的輸出結(jié)果, 有下面這些特點(diǎn):

• 輸出結(jié)果是間隔仍然是 10ms
• 當(dāng)漏斗桶溢出后, 請(qǐng)求處理耗時(shí)越來(lái)越長(zhǎng)

疑問(wèn)

1. Uber Ratelimiter 溢出后為什么請(qǐng)求耗時(shí)越來(lái)越長(zhǎng)?
2. 為什么 Uber ratelimiter 不需要返回 429?

源碼分析

New 初始化函數(shù)

func New(rate int, opts ...Option) Limiter {
    l := &limiter{
        perRequest: time.Second / time.Duration(rate),
        maxSlack:   -10 * time.Second / time.Duration(rate), // 最大松弛度
    }

    // ...

    return l
}

Uber Leaky Bucket 的設(shè)計(jì)有點(diǎn)取巧. New(10) 傳入的 10 指的是 1s 內(nèi)只有能有 10 個(gè)請(qǐng)求通過(guò), 于是算出來(lái)每個(gè)請(qǐng)求之間應(yīng)該間隔 100 ms. 如果兩個(gè)請(qǐng)求之間間隔時(shí)間過(guò)短, 那么需要第二個(gè)請(qǐng)求 sleep 一段時(shí)間, 這樣保證請(qǐng)求能夠勻速?gòu)耐皟?nèi)流出. 如下圖

image

對(duì)比上面漏斗桶的概念, 我們發(fā)現(xiàn)當(dāng)請(qǐng)求通過(guò) Uber 限流器的時(shí)候, 如果溢出了, 就只能強(qiáng)行 sleep, 造成后續(xù)請(qǐng)求排隊(duì), 處理時(shí)長(zhǎng)越來(lái)越長(zhǎng). 另外上游服務(wù)必須得有超時(shí)機(jī)制.

Take()

func (t *limiter) Take() time.Time {
    t.Lock()
    defer t.Unlock()

    now := t.clock.Now()

    // 如果是第一次請(qǐng)求, 直接讓通過(guò)
    if t.last.IsZero() {
        t.last = now
        return t.last
    }

    // 這里有個(gè)最大松弛量的概念maxSlack
    t.sleepFor += t.perRequest - now.Sub(t.last)
    if t.sleepFor < t.maxSlack {
        t.sleepFor = t.maxSlack
    }

    // 判斷是否桶溢出. 如果桶溢出了, 需要sleep一段時(shí)間
    if t.sleepFor > 0 {
        t.clock.Sleep(t.sleepFor)
        t.last = now.Add(t.sleepFor)
        t.sleepFor = 0
    } else {
        t.last = now
    }
    return t.last
}

最大松弛量

漏斗桶有個(gè)天然缺陷就是無(wú)法應(yīng)對(duì)突發(fā)流量, 對(duì)于這種情況每界，uber-go 對(duì) Leaky Bucket 做了一些改良捅僵，引入了最大松弛量 (maxSlack) 的概念

上面計(jì)算 sleepFor 的第 14 行代碼如果按下面這樣寫:

t.sleepFor = t.perRequest - now.Sub(t.last)

請(qǐng)求 1 完成后，15ms 后眨层，請(qǐng)求 2 才到來(lái)庙楚，可以對(duì)請(qǐng)求 2 立即處理。請(qǐng)求 2 完成后趴樱，5ms 后馒闷，請(qǐng)求 3 到來(lái)酪捡，這個(gè)時(shí)候距離上次請(qǐng)求還不足 10ms，因此還需要等待 5ms, 但是纳账，對(duì)于這種情況逛薇，實(shí)際上三個(gè)請(qǐng)求一共消耗了 25ms 才完成，并不是預(yù)期的 20ms

image

Uber 實(shí)現(xiàn)的 ratelimit 中疏虫，可以把之前間隔比較長(zhǎng)的請(qǐng)求的時(shí)間永罚，勻給后面的使用，保證每秒請(qǐng)求數(shù) (RPS). 對(duì)于以上 case卧秘，因?yàn)檎?qǐng)求 2 相當(dāng)于多等了 5ms呢袱，我們可以把這 5ms 移給請(qǐng)求 3 使用。加上請(qǐng)求 3 本身就是 5ms 之后過(guò)來(lái)的翅敌，一共剛好 10ms羞福，所以請(qǐng)求 3 無(wú)需等待，直接可以處理蚯涮。此時(shí)三個(gè)請(qǐng)求也恰好一共是 20ms

image

但是也有特殊情況, 假設(shè)計(jì)算出來(lái)的間隔時(shí)間 100ms, 但是 請(qǐng)求1 和 請(qǐng)求2 之間的間隔時(shí)間 2h, 如果沒(méi)有t.sleepFor = t.maxSlack 這段 最大松弛量 的代碼, 那么 請(qǐng)求2 需要 sleep 2h 才能繼續(xù)執(zhí)行, 顯然這不符合實(shí)際情況. 故引入了最大松弛量 (maxSlack), 表示允許抵消的最長(zhǎng)時(shí)間

參考

1. 分布式服務(wù)限流實(shí)戰(zhàn)治专，已經(jīng)為你排好坑了
2. uber-go 漏桶限流器使用與原理分析