限流 通過限制併發訪問數或者限制一個時間視窗內允許處理的請求數量來保護系統，例如，通過限流，你可以過濾掉產生流量峰值的客戶和服務。 令牌桶演算法 令牌桶演算法是常見的一種限流演算法。假設有一個桶，以固定速度（rate）往桶裡加入令牌（token）。當桶滿了時停止加入。服務收到請求時嘗試從桶里取出令牌。如果 ...
限流
通過限制併發訪問數或者限制一個時間視窗內允許處理的請求數量來保護系統，例如，通過限流，你可以過濾掉產生流量峰值的客戶和服務。
令牌桶演算法
令牌桶演算法是常見的一種限流演算法。假設有一個桶，以固定速度（rate）往桶裡加入令牌（token）。當桶滿了時停止加入。服務收到請求時嘗試從桶里取出令牌。如果成功取出，則可以響應本次請求。如果沒有取到，可以進行有限時間的等待或者返回超時錯誤。
特點
遇到流量洪峰時可以應對部分突發流量，但由於桶有容量上限，當消耗完桶里堆積的令牌之後只能根據令牌的生成速率提供服務，從而起到限流的作用。
Golang 實現
Golang rate包提供了 token limiter 的實現,具體可以點擊鏈接查看rate package
漏桶演算法
一個固定容量的漏桶，按照常量固定速率流出水滴，這裡的水滴指的就是能進行響應的請求。當漏桶滿了時，請求就會被丟棄，返回一個限流標誌。
特點
流量均勻，一般作為計量工具，可以用於流量整形和流量控制。比方說對資料庫的操作。經過一層漏桶控制，可以有效控制對資料庫的請求，避免資料庫被打掛。流量穩定，但是無法應對突發流量。
Golang 實現
uber 開源了一個基於漏桶的限流器ratelimit
func main() {
rl := ratelimit.New(1) // per second
for i := 0; i < 10; i++ {
now := rl.Take()
if i > 0 {
fmt.Println(i, now)
}
}
}
1 2022-03-24 02:24:51.57952663
2 2022-03-24 02:24:52.579526624
3 2022-03-24 02:24:53.579526623
4 2022-03-24 02:24:54.579526617
5 2022-03-24 02:24:55.579526616
6 2022-03-24 02:24:56.579526617
7 2022-03-24 02:24:57.579526616
8 2022-03-24 02:24:58.579526615
9 2022-03-24 02:24:59.579526629
可以看到，通過“漏桶”這層的過濾，可以有效保護我們的服務。
// WithoutSlack configures the limiter to be strict and not to accumulate
// previously "unspent" requests for future bursts of traffic.
var WithoutSlack Option = slackOption(0)
// WithSlack configures custom slack.
// Slack allows the limiter to accumulate "unspent" requests
// for future bursts of traffic.
func WithSlack(slack int) Option {
return slackOption(slack)
}
可以簡單對比一下
rl := ratelimit.New(1, ratelimit.WithoutSlack) // per second
for i := 0; i < 10; i++ {
now := rl.Take()
if i == 2 {
time.Sleep(2 * time.Second)
}
if i > 0 {
fmt.Println(i, now)
}
}
1 2022-03-24 02:34:22.547745401
2 2022-03-24 02:34:23.54774539 //sleep 2 秒，後面 rps 還是很平穩
3 2022-03-24 02:34:25.549647721
4 2022-03-24 02:34:26.549647738
5 2022-03-24 02:34:27.549647312
6 2022-03-24 02:34:28.549647722
7 2022-03-24 02:34:29.549647716
8 2022-03-24 02:34:30.549647722
9 2022-03-24 02:34:31.549647599
rl := ratelimit.New(1, ratelimit.WithSlack(5)) // per second
for i := 0; i < 10; i++ {
now := rl.Take()
if i == 2 {
time.Sleep(5 * time.Second)
}
if i > 0 {
fmt.Println(i, now)
}
}
1 2022-03-24 02:39:58.860218897
2 2022-03-24 02:39:59.860218892 //sleep 5 秒，這裡的例子比較誇張，不過可看到我們可以一次性處理 5 個
3 2022-03-24 02:40:04.865851924
4 2022-03-24 02:40:04.865855167
5 2022-03-24 02:40:04.86585706
6 2022-03-24 02:40:04.865858894
7 2022-03-24 02:40:04.865860533
8 2022-03-24 02:40:05.860218893
9 2022-03-24 02:40:06.860218883
我們取得可以處理的請求後還應該結合 context 上下午中的上下文時間，避免拿到請求後處理請求超時。
滑動視窗演算法
滑動視窗演算法是對普通時間視窗計數的優化，我們知道普通時間視窗計數存在精度的不足，比如說我們服務1秒可以處理1000個請求，所以這裡我們限制1s處理的請求數為1000。前1秒後500ms 來了600個請求，後一秒前400ms 來了600個請求，那麼在這 900ms的間隔里就來了1200 個請求。主要的原因就在於普通時間視窗計數每間隔 1 s 會刷新，所以滑動視窗將間隔時間劃分為多個區間，從設計上優化了精度問題。
Golang 實現
type slot struct {
startTime time.Time //slot 的起始時間
count int //數量
}
type slots []*slot
type window slots //視窗
func sumReq(win window) int { //計數
count := 0
for _, slot := range win {
count += slot.count
}
return count
}
type RollingWindow struct {
slotLength time.Duration //slot 的長度
slotNum int //slot 個數
winLenght time.Duration //視窗長度
maxReqNum int //rolling window 內允許的最大請求書
win window //視窗
lock sync.Mutex //鎖
}
func NewRollingWindow(slotLength time.Duration, slotNum int, maxReqNum int) *RollingWindow {
return &RollingWindow{
slotLength: slotLength,
slotNum: slotNum,
winLenght: slotLength * time.Duration(slotNum),
maxReqNum: maxReqNum,
win: make(window, 0, slotNum),
lock: sync.Mutex{},
}
}
func (rw *RollingWindow) IsLimit() bool {
return !rw.validate()
}
func (rw *RollingWindow) validate() bool {
now := time.Now()
rw.lock.Lock()
defer rw.lock.Unlock()
//滑動視窗
rw = rw.slideRight(now)
//是否超限
can := rw.accept()
if can {
//記錄請求數
rw.update(now)
}
return can
}
//向右移動視窗 [0,1,2,3,4,5] -> [1,2,3,4,5]
func (rw *RollingWindow) slideRight(now time.Time) *RollingWindow {
offset := -1
for i, slot := range rw.win {
if slot.startTime.Add(rw.winLenght).After(now) {
break //不需要滑動
}
offset = i
}
if offset > -1 {
rw.win = rw.win[offset+1:]
}
return rw
}
//判斷請求是否超限 沒有超限返回 true
func (rw *RollingWindow) accept() bool {
return sumReq(rw.win) < rw.maxReqNum
}
func (rw *RollingWindow) update(now time.Time) *RollingWindow {
if len(rw.win) > 0 {
lastOffset := len(rw.win) - 1
lastSlot := rw.win[lastOffset]
if lastSlot.startTime.Add(rw.slotLength).Before(now) {
//填入新的 slot
newSlot := &slot{startTime: now, count: 1}
rw.win = append(rw.win, newSlot)
} else {
rw.win[lastOffset].count++
}
} else {
newSlot := &slot{startTime: now, count: 1}
rw.win = append(rw.win, newSlot)
}
return rw
}
func main() {
l := NewRollingWindow(100*time.Millisecond, 10, 10)
fakeDealReq(l, 3)
printRollingWindow(l)
time.Sleep(200 * time.Millisecond)
fakeDealReq(l, 3)
printRollingWindow(l)
time.Sleep(200 * time.Millisecond)
fakeDealReq(l, 5)
printRollingWindow(l)
time.Sleep(1 * time.Second)
fakeDealReq(l, 1)
printRollingWindow(l)
}
func fakeDealReq(l *RollingWindow, num int) {
for i := 0; i < num; i++ {
fmt.Println(l.IsLimit())
}
}
func printRollingWindow(l *RollingWindow) {
for _, v := range l.win {
fmt.Println(v.startTime, v.count)
}
}
//輸出
false
false
false
2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
false
false
false
2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
2022-03-24 05:06:04.817533239 +0000 UTC m=+0.201253793 3
false
false
false
false
true
2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
2022-03-24 05:06:04.817533239 +0000 UTC m=+0.201253793 3
2022-03-24 05:06:05.018547679 +0000 UTC m=+0.402268233 4
false
2022-03-24 05:06:06.020410484 +0000 UTC m=+1.404131050 1
