限流器(Rate Limiter)在微服務中的重要性不言而喻了. 下游服務的穩(wěn)定性, 防止過載, 全靠這個組件來保證. 限流器的實現(xiàn)方式, 基本有下面幾種方式
- 計數(shù)器
- 漏斗通 (Leaky Bucket)
- 令牌桶 (Token Bucket)
- 基于 BBR 算法的自適應限流
- 基于 Nginx 的限流
- 分布式限流
這個系列的文章會逐一介紹各種限流器. 本篇文章會結(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
這段話是摘自維基百科. 簡單來說限流器是基于 KV 內(nèi)存數(shù)據(jù)庫的一個限速判斷, 在給定的時間內(nèi), 客戶端請求次數(shù)過多, 服務器就會返回狀態(tài)碼 429: Too Many Request
計數(shù)器
計數(shù)器是一種最簡單的限流器.
如果把 QPS 設置為100, 從第一個請求進來開始計時，在接下去的1s內(nèi)，每來一個請求，就把計數(shù)加1，如果累加的數(shù)字達到了100，那么后續(xù)的請求就會被全部拒絕。等到1s結(jié)束后，把計數(shù)恢復成0，重新開始計數(shù). 這種計數(shù)器一般稱為固定窗口計數(shù)器算法.
可以看到計數(shù)器雖說有一定的緩沖空間, 但是需要一定的恢復空窗期, 在這個恢復時間內(nèi)請求全部拒絕. 計數(shù)器還存在著另外一個問題, 特殊情況下會讓請求的通過量為限制的兩倍.
考慮如下情況：
限制 1 秒內(nèi)最多通過 5 個請求，在第一個窗口的最后半秒內(nèi)通過了 5 個請求，第二個窗口的前半秒內(nèi)又通過了 5 個請求。這樣看來就是在 1 秒內(nèi)通過了 10 個請求
綜合來看, 計數(shù)器方式的限流是比較簡單粗暴的, 我們需要更加優(yōu)雅的限流方式
漏斗桶
相對于計數(shù)器的粗魯方式, 漏斗桶會更加優(yōu)雅一些, 如下圖
其實從字面就很好理解. 類似生活用到的漏斗, 當客戶端請求進來時，相當于水倒入漏斗，然后從下端小口慢慢勻速的流出。不管上面流量多大，下面流出的速度始終保持不變.
當水流入速度過大時, 漏斗就會溢出, 同樣會造成服務拒絕. 相對于計數(shù)器的在恢復期內(nèi)全部拒絕請求, 因為漏斗桶會以一定的速率消費請求, 這樣就能夠讓后續(xù)的請求有機會進入到漏斗桶里面.
漏斗桶的弊端
由于漏斗桶有點類似隊列, 先進去才能被消費掉, 如果漏斗桶溢出了, 后續(xù)的請求都直接丟棄了, 也就是說漏斗桶是無法短時間應對突發(fā)流量的. 對于互聯(lián)網(wǎng)行業(yè)來說, 面對突發(fā)流量, 不能一刀切將突發(fā)流量全部干掉, 這樣會給產(chǎn)品帶來口碑上影響. 因此漏斗桶也不是完美的方案.
不過漏斗桶能夠限制數(shù)據(jù)的平均傳輸速率, 能夠滿足大部分的使用場景的. 如: 我們可以使用漏斗桶限制論壇發(fā)帖頻率
Uber Ratelimit
Uber Ratelimit 是漏斗桶的一個具體實現(xiàn). 下面主要結(jié)合 Uber Ratelimit 來介紹 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
從這個例子的輸出結(jié)果, 可以看出來有下面這些特點:
- 初始化時需要設置 bucket 大小
- 輸出結(jié)果是間隔 10ms, 由此可以看出來 leaky bucket 一定是保證勻速率的從桶內(nèi)取值
- 通過
Take()函數(shù)與 ratelimiter 來交互, 但是 Take() 的返回值卻是上一次拿到的請求時間
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)) // 這里不需要, 只是打印下多次請求之間的時間間隔
prev = now // 這里不需要, 只是打印下多次請求之間的時間間隔
}
}
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
從這個例子的輸出結(jié)果, 有下面這些特點:
- 輸出結(jié)果是間隔仍然是 10ms
- 當漏斗桶溢出后, 請求處理耗時越來越長
疑問
- Uber Ratelimiter 溢出后為什么請求耗時越來越長?
- 為什么 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 的設計有點取巧. New(10) 傳入的 10 指的是 1s 內(nèi)只有能有 10 個請求通過, 于是算出來每個請求之間應該間隔 100 ms. 如果兩個請求之間間隔時間過短, 那么需要第二個請求 sleep 一段時間, 這樣保證請求能夠勻速從桶內(nèi)流出. 如下圖
對比上面漏斗桶的概念, 我們發(fā)現(xiàn)當請求通過 Uber 限流器的時候, 如果溢出了, 就只能強行 sleep, 造成后續(xù)請求排隊, 處理時長越來越長. 另外上游服務必須得有超時機制.
Take()
func (t *limiter) Take() time.Time {
t.Lock()
defer t.Unlock()
now := t.clock.Now()
// 如果是第一次請求, 直接讓通過
if t.last.IsZero() {
t.last = now
return t.last
}
// 這里有個最大松弛量的概念maxSlack
t.sleepFor += t.perRequest - now.Sub(t.last)
if t.sleepFor < t.maxSlack {
t.sleepFor = t.maxSlack
}
// 判斷是否桶溢出. 如果桶溢出了, 需要sleep一段時間
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
}
最大松弛量
漏斗桶有個天然缺陷就是無法應對突發(fā)流量, 對于這種情況，uber-go 對 Leaky Bucket 做了一些改良，引入了最大松弛量 (maxSlack) 的概念
上面計算 sleepFor 的第 14 行代碼如果按下面這樣寫:
t.sleepFor = t.perRequest - now.Sub(t.last)
請求 1 完成后，15ms 后，請求 2 才到來，可以對請求 2 立即處理。請求 2 完成后，5ms 后，請求 3 到來，這個時候距離上次請求還不足 10ms，因此還需要等待 5ms, 但是，對于這種情況，實際上三個請求一共消耗了 25ms 才完成，并不是預期的 20ms
Uber 實現(xiàn)的 ratelimit 中，可以把之前間隔比較長的請求的時間，勻給后面的使用，保證每秒請求數(shù) (RPS). 對于以上 case，因為請求 2 相當于多等了 5ms，我們可以把這 5ms 移給請求 3 使用。加上請求 3 本身就是 5ms 之后過來的，一共剛好 10ms，所以請求 3 無需等待，直接可以處理。此時三個請求也恰好一共是 20ms
但是也有特殊情況, 假設計算出來的間隔時間 100ms, 但是 請求1 和 請求2 之間的間隔時間 2h, 如果沒有t.sleepFor = t.maxSlack 這段 最大松弛量 的代碼, 那么 請求2 需要 sleep 2h 才能繼續(xù)執(zhí)行, 顯然這不符合實際情況. 故引入了最大松弛量 (maxSlack), 表示允許抵消的最長時間
