常见的限流算法

限流

通过限制并发访问数或者限制一个时间窗口内允许处理的请求数量来保护系统，例如，通过限流，你可以过滤掉产生流量峰值的客户和服务。
令牌桶算法

令牌桶算法是常见的一种限流算法。假设有一个桶，以固定速度（rate）往桶里加入令牌（token）。当桶满了时停止加入。服务收到请求时尝试从桶里取出令牌。如果成功取出，则可以响应本次请求。如果没有取到，可以进行有限时间的等待或者返回超时错误。
特点

遇到流量洪峰时可以应对部分突发流量，但由于桶有容量上限，当消耗完桶里堆积的令牌之后只能根据令牌的生成速率提供服务，从而起到限流的作用。
Golang 实现

Golang rate包提供了 token limiter 的实现,具体可以点击链接查看rate package
漏桶算法

一个固定容量的漏桶，按照常量固定速率流出水滴，这里的水滴指的就是能进行响应的请求。当漏桶满了时，请求就会被丢弃，返回一个限流标志。
特点

流量均匀，一般作为计量工具，可以用于流量整形和流量控制。比方说对数据库的操作。经过一层漏桶控制，可以有效控制对数据库的请求，避免数据库被打挂。流量稳定，但是无法应对突发流量。
Golang 实现

uber 开源了一个基于漏桶的限流器ratelimit

1. func main() {
2.         rl := ratelimit.New(1) // per second
3.         for i := 0; i < 10; i++ {
4.                 now := rl.Take()
5.                 if i > 0 {
6.                         fmt.Println(i, now)
7.                 }
8.         }
9. }
11. 1 2022-03-24 02:24:51.57952663
12. 2 2022-03-24 02:24:52.579526624
13. 3 2022-03-24 02:24:53.579526623
14. 4 2022-03-24 02:24:54.579526617
15. 5 2022-03-24 02:24:55.579526616
16. 6 2022-03-24 02:24:56.579526617
17. 7 2022-03-24 02:24:57.579526616
18. 8 2022-03-24 02:24:58.579526615
19. 9 2022-03-24 02:24:59.579526629

复制代码

可以看到，通过“漏桶”这层的过滤，可以有效保护我们的服务。

1. // WithoutSlack configures the limiter to be strict and not to accumulate
2. // previously "unspent" requests for future bursts of traffic.
3. var WithoutSlack Option = slackOption(0)
5. // WithSlack configures custom slack.
6. // Slack allows the limiter to accumulate "unspent" requests
7. // for future bursts of traffic.
8. func WithSlack(slack int) Option {
9.         return slackOption(slack)
10. }

复制代码

可以简单对比一下

1. rl := ratelimit.New(1, ratelimit.WithoutSlack) // per second
2. for i := 0; i < 10; i++ {
3.         now := rl.Take()
4.         if i == 2 {
5.                 time.Sleep(2 * time.Second)
6.         }
7.         if i > 0 {
8.                 fmt.Println(i, now)
9.         }
10. }
11. 1 2022-03-24 02:34:22.547745401
12. 2 2022-03-24 02:34:23.54774539   //sleep 2 秒，后面 rps 还是很平稳
13. 3 2022-03-24 02:34:25.549647721
14. 4 2022-03-24 02:34:26.549647738
15. 5 2022-03-24 02:34:27.549647312
16. 6 2022-03-24 02:34:28.549647722
17. 7 2022-03-24 02:34:29.549647716
18. 8 2022-03-24 02:34:30.549647722
19. 9 2022-03-24 02:34:31.549647599
21. rl := ratelimit.New(1, ratelimit.WithSlack(5)) // per second
22. for i := 0; i < 10; i++ {
23.         now := rl.Take()
24.         if i == 2 {
25.                 time.Sleep(5 * time.Second)
26.         }
27.         if i > 0 {
28.                 fmt.Println(i, now)
29.         }
30. }
31. 1 2022-03-24 02:39:58.860218897
32. 2 2022-03-24 02:39:59.860218892  //sleep 5 秒，这里的例子比较夸张，不过可看到我们可以一次性处理 5 个
33. 3 2022-03-24 02:40:04.865851924
34. 4 2022-03-24 02:40:04.865855167
35. 5 2022-03-24 02:40:04.86585706
36. 6 2022-03-24 02:40:04.865858894
37. 7 2022-03-24 02:40:04.865860533
38. 8 2022-03-24 02:40:05.860218893
39. 9 2022-03-24 02:40:06.860218883

复制代码

我们取得可以处理的请求后还应该结合 context 上下午中的上下文时间，避免拿到请求后处理请求超时。
滑动窗口算法

滑动窗口算法是对普通时间窗口计数的优化，我们知道普通时间窗口计数存在精度的不足，比如说我们服务1秒可以处理1000个请求，所以这里我们限制1s处理的请求数为1000。前1秒后500ms 来了600个请求，后一秒前400ms 来了600个请求，那么在这 900ms的间隔里就来了1200 个请求。主要的原因就在于普通时间窗口计数每间隔 1 s 会刷新，所以滑动窗口将间隔时间划分为多个区间，从设计上优化了精度问题。
Golang 实现

1. type slot struct {
2.         startTime time.Time //slot 的起始时间
3.         count     int       //数量
4. }
6. type slots []*slot
8. type window slots //窗口
10. func sumReq(win window) int { //计数
11.         count := 0
12.         for _, slot := range win {
13.                 count += slot.count
14.         }
15.         return count
16. }
18. type RollingWindow struct {
19.         slotLength time.Duration //slot 的长度
20.         slotNum    int           //slot 个数
21.         winLenght  time.Duration //窗口长度
22.         maxReqNum  int           //rolling window 内允许的最大请求书
23.         win        window        //窗口
24.         lock       sync.Mutex    //锁
25. }
27. func NewRollingWindow(slotLength time.Duration, slotNum int, maxReqNum int) *RollingWindow {
28.         return &RollingWindow{
29.                 slotLength: slotLength,
30.                 slotNum:    slotNum,
31.                 winLenght:  slotLength * time.Duration(slotNum),
32.                 maxReqNum:  maxReqNum,
33.                 win:        make(window, 0, slotNum),
34.                 lock:       sync.Mutex{},
35.         }
36. }
38. func (rw *RollingWindow) IsLimit() bool {
39.         return !rw.validate()
40. }
43. func (rw *RollingWindow) validate() bool {
44.         now := time.Now()
45.         rw.lock.Lock()
46.         defer rw.lock.Unlock()
47.         //滑动窗口
48.         rw = rw.slideRight(now)
49.         //是否超限
50.         can := rw.accept()
51.         if can {
52.                 //记录请求数
53.                 rw.update(now)
54.         }
56.         return can
57. }
59. //向右移动窗口 [0,1,2,3,4,5] -> [1,2,3,4,5]
60. func (rw *RollingWindow) slideRight(now time.Time) *RollingWindow {
61.         offset := -1
62.         for i, slot := range rw.win {
63.                 if slot.startTime.Add(rw.winLenght).After(now) {
64.                         break //不需要滑动
65.                 }
66.                 offset = i
67.         }
68.         if offset > -1 {
69.                 rw.win = rw.win[offset+1:]
70.         }
71.         return rw
72. }
74. //判断请求是否超限 没有超限返回 true
75. func (rw *RollingWindow) accept() bool {
76.         return sumReq(rw.win) < rw.maxReqNum
77. }
79. func (rw *RollingWindow) update(now time.Time) *RollingWindow {
81.         if len(rw.win) > 0 {
82.                 lastOffset := len(rw.win) - 1
83.                 lastSlot := rw.win[lastOffset]
84.                 if lastSlot.startTime.Add(rw.slotLength).Before(now) {
85.                         //填入新的 slot
86.                         newSlot := &slot{startTime: now, count: 1}
87.                         rw.win = append(rw.win, newSlot)
88.                 } else {
89.                         rw.win[lastOffset].count++
90.                 }
91.         } else {
92.                 newSlot := &slot{startTime: now, count: 1}
93.                 rw.win = append(rw.win, newSlot)
94.         }
96.         return rw
97. }
99. func main() {
100.         l := NewRollingWindow(100*time.Millisecond, 10, 10)
101.         fakeDealReq(l, 3)
102.         printRollingWindow(l)
103.         time.Sleep(200 * time.Millisecond)
105.         fakeDealReq(l, 3)
106.         printRollingWindow(l)
108.         time.Sleep(200 * time.Millisecond)
109.         fakeDealReq(l, 5)
110.         printRollingWindow(l)
112.         time.Sleep(1 * time.Second)
113.         fakeDealReq(l, 1)
114.         printRollingWindow(l)
115. }
117. func fakeDealReq(l *RollingWindow, num int) {
118.         for i := 0; i < num; i++ {
119.                 fmt.Println(l.IsLimit())
120.         }
121. }
123. func printRollingWindow(l *RollingWindow) {
124.         for _, v := range l.win {
125.                 fmt.Println(v.startTime, v.count)
126.         }
127. }
129. //输出
130. false
131. false
132. false
133. 2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
134. false
135. false
136. false
137. 2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
138. 2022-03-24 05:06:04.817533239 +0000 UTC m=+0.201253793 3
139. false
140. false
141. false
142. false
143. true
144. 2022-03-24 05:06:04.616315628 +0000 UTC m=+0.000036182 3
145. 2022-03-24 05:06:04.817533239 +0000 UTC m=+0.201253793 3
146. 2022-03-24 05:06:05.018547679 +0000 UTC m=+0.402268233 4
147. false
148. 2022-03-24 05:06:06.020410484 +0000 UTC m=+1.404131050 1

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！