qidao123.com技术社区-IT企服评测·应用市场

标题: 常见的限流算法 [打印本页]
作者: 一给    时间: 2022-8-21 18:01
标题: 常见的限流算法
限流

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

令牌桶算法是常见的一种限流算法。假设有一个桶，以固定速度（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
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4