限流常见算法

限流总体来说需要确定3个参数:

  • 限流对象:用户、ip、api接口、设备id等等。
  • 限制数量和时间:在某个时间内最多允许多少流量

1. 合法性限流

直接拒绝掉不合法的用户,比如使用验证码、用户名密码登录的方式是用户变成合法用户。针对不合法的用户直接进行拒绝。

2. 容器限流

对运行的容器底层进行限流,比如可以设置tomcat中最大的线程数,或者在nginx转发配置中配置限流。

3. 服务端限流

3.1 固定时间窗口算法

限制在固定时间段内的请求次数。比如说:1秒中内,一个ip最多能请求10次。在1秒钟内,10次请求之后的请求会被直接拒绝。

优点:实现简单,易于理解。

缺点:可能在两个时间窗口的间隙突发接收 2 倍的流量,流量不够平滑。

固定时间窗口算法

3.2 滑动时间窗口

为了解决固定窗口存在的问题,滑动时间窗口把固定时间窗口进行进一步细分,分成多个小窗口,每个格子单独维护一个计数器。我们还是可以设置一个时间段内最多处理多少请求。但是这个时间是滚动的。比如1s划分为5个窗口,每个窗口就是200ms,每秒最多访问10次。假设1.1秒时来了一个新的请求,那么我们就通过计算“最近”1秒钟内的请求数是否超过10次(累加0.2秒-1.2秒小窗口中的请求次数)。如果超过就直接拒绝请求。这里的滑动就是值不断删除旧的时间小窗口,添加新的时间小窗口。

优点:解决固定时间窗口带来的突发流量2倍的问题,但是整体来说流量还是不够平滑。

缺点:增大了空间复杂度,算法实现也变复杂了。

滑动时间算法

3.3 漏筒限流算法

漏筒限流算法用来限制数据的流出速率。核心思路是在流量的生产端和消费端中间加上一个容量固定的桶,消费者会以恒定的速率从桶中取数据进行消费。生成端则会不断把数据放入桶中,等待消费,如果桶容量已满,则会被直接拒绝。

优点:能使流量更加平滑。

缺点:应对突发流量的能力较弱,需要等待消费。

image-20220313175228212

3.4 令牌桶算法

令牌桶算法用来限制数据的流入速率。核心思路是我们需要创建一个固定容量的桶,有一个线程会已固定的速率往桶中存放令牌(桶满则丢弃)。用户请求需要从桶中拿到令牌才能继续执行,否则直接拒绝执行。

优点:能使流量更加平滑,也可以应付一定量的突发流量。

令牌桶算法

4. 如何确定限流阈值

限流策略是微服务治理中的标配策略,只是你很难在实际中确认限流的阈值是多少,设置的小了容易误伤正常的请求,设置的大了则达不到限流的目的。所以,一般在实际项目中,我们会把阈值放置在配置中心中方便动态调整;同时,我们可以通过定期地压力测试得到整体系统以及每个微服务的实际承载能力,然后再依据这个压测出来的值设置合适的阈值。