全部产品
云市场

限流算法介绍

更新时间:2020-04-29 10:12:25

常见的限流方式有:

  • 通过限制单位时间段内调用量来限流(QPS 限流算法)
  • 通过限制系统的并发调用程度来限流
  • 使用漏桶(Leaky Bucket)算法来进行限流
  • 使用令牌桶(Token Bucket)算法来进行限

服务限流中主要使用了其中两种:QPS 限流算法令牌桶算法

QPS 限流算法

QPS 限流算法通过限制单位时间内允许放过的请求数来限流。

优点

  • 计算简单,是否限流只跟请求数相关,放过的请求数是可预知的(令牌桶算法放过的请求数还依赖于流量是否均匀)。比较符合用户直觉和预期。
  • 可以通过拉长限流周期来应对突发流量。如 1 秒限流 10 个,想要放过瞬间 20 个请求,可以把限流配置改成 3 秒限流 30 个。拉长限流周期会有一定风险,用户可以自主决定承担多少风险。

缺点

  • 没有很好的处理单位时间的边界。比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,就看到在两毫秒内发生了两倍的 QPS。
  • 放过的请求不均匀,突发流量时,请求总在限流周期的前一部分放过。如 10 秒限 100个,高流量时放过的请求总是在限流周期的第一秒。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。

Token Bucket

优点

  • 放过的流量比较均匀,有利于保护系统。
  • 存量令牌能应对突发流量,很多时候,我们希望能放过脉冲流量。而对于持续的高流量,后面又能均匀地放过不超过限流值的请求数。

缺点

  • 存量令牌没有过期时间,突发流量时第一个周期会多放过一些请求,可解释性差。即在突发流量的第一个周期,默认最多会放过 2 倍限流值的请求数。
  • 实际限流数难以预知,跟请求数和流量分布有关。

存量桶系数

令牌桶算法中,多余的令牌会放到桶里,这个桶的容量是有上限的,决定这个容量的就是存量桶系数,默认为 1.0,即默认存量桶的容量是 1.0 倍的限流值。推荐设置 0.6~1.5 之间。

存量桶系数的影响有两方面:

  • 突发流量第一个周期放过的请求数。如存量桶系数等于 0.6,第一个周期最多放过 1.6 倍限流值的请求数。
  • 影响误杀率。存量桶系数越大,越能容忍流量不均衡问题。

误杀率:服务限流是对单机进行限流,线上场景经常会用单机限流模拟集群限流。由于机器之间的秒级流量不够均衡,所以很容易出现误限。例如两台服务器,总限流值 20,每台限流 10,某一秒两台服务器的流量分别是 5、15,这时其中一台就限流了 5 个请求。减小误杀率的两个办法:

  • 拉长限流周期。
  • 使用令牌桶算法,并且调出较好的存量桶系数。