限流之漏桶算法实现

漏桶算法把发请求的动作比作成注水到桶中,处理请求的过程可以比喻为漏桶漏水。

往桶中以任意速率流入水,以一定速率流出水,当水超过桶流量则丢弃,因为桶容量是不变的,保证了整体的速率。

漏桶算法

本质就是:通过一个缓冲区将不平滑的流量”整形”成平滑的(高于均值的流量暂存下来补足到低于均值的时期),以此最大化计算处理资源的利用率。

漏桶限流解决了计数器限流模式下流量突刺的问题,当服务器处理完请求后,只要能从漏桶中流出请求则能继续处理,不会造成长时间等待拒绝请求。

缺点

程序本身的处理能力是会被干扰的,是会变化的。所以,你可以预估某一个阶段内的平均值、中位数,但无法预估具体某一个时刻的程序处理能力。

因此,必然会使用相对悲观的标准去作为阈值,防止程序超负荷。

始终恒定的处理速率有时候并不一定是好事情,对于突发的请求洪峰,在保证服务安全的前提下,应该尽最大努力去响应,这个时候漏桶算法显得有些呆滞。

漏桶满后此时大量请求到来,由于服务器已扩容可以满足请求处理,但是漏桶会拒绝大量请求,导致无法应对突发流量问题。

实现思路

  • 队列实现:准备一个队列用来保存请求,然后我们定期从队列中拿请求来执行。
  • 延迟计算:
    • 请求时计算上次到本次时间间隔漏掉的流量 water
    • 使用一个变量 Balance 记录漏桶的空余量(包含漏掉的 water)
    • Balance 如果有空余就可以放行此次请求并减少 1

Golang 实现

基于时间延迟计算的思路实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package main

import (
"fmt"
"sync"
"time"
)

// BucketLimiter 定义漏桶算法struct
type BucketLimiter struct {
Lck *sync.Mutex // 锁
Rate float64 //最大速率限制,每秒请求个数
Balance float64 //漏桶的余量
Cap float64 //漏桶的最大容量限制
LastTime time.Time //上次检查的时间
}

// NewBucketLimiter 初始化BucketLimiter
func NewBucketLimiter(rate int, cap int) *BucketLimiter {
return &BucketLimiter{
Lck: new(sync.Mutex),
Rate: float64(rate),
Balance: float64(cap),
Cap: float64(cap),
LastTime: time.Now(),
}
}

// leakyBucket 漏桶算法实现
func (r *BucketLimiter) leakyBucket() bool {
ok := false
r.Lck.Lock()
defer r.Lck.Unlock()
now := time.Now()
dur := now.Sub(r.LastTime).Seconds() //当前时间与上一次检查时间差
r.LastTime = now

// 计算该时间间隔新流出的水
water := dur * r.Rate // 计算这段时间内漏桶流出水的流量water
r.Balance += water // 漏桶流出 water 容量的水,自然漏桶的余量多出 water
if r.Balance > r.Cap {
r.Balance = r.Cap
}

if r.Balance >= 1 { // 漏桶余量足够容下当前的请求
r.Balance -= 1
ok = true
}
return ok
}

func main() {
// 初始化 限制每秒2个请求 漏洞容量为5
r := NewBucketLimiter(2, 5)
for i := 0; i < 20; i++ {
ok := r.leakyBucket()
if ok {
fmt.Println("pass ", i)
} else {
fmt.Println("limit ", i)
}
time.Sleep(100 * time.Millisecond)
}
}

引用

  1. 分布式限流:基于 Redis 实现
  2. 分布式系统关注点——限流该怎么做?
  3. 分布式系统限流算法分析与实现
作者

Jakes Lee

发布于

2021-11-02

更新于

2023-01-03

许可协议

评论