限流

参考原文地址：https://blog.csdn.net/y277an/article/details/97074272

一. 固定时间窗口算法

这里先暂时不表

算法特点：

1. 实现简单。
2. 时间窗口固定，每个窗口开始时计数为零，这样后面的请求不会受到之前的影响，做到了前后请求隔离。
3. 因为两个时间窗口之间没有任何联系，所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求。所以固定时间窗口算法无法限制窗口间突发流量。

二. 滑动时间窗口算法

以窗口时间1min，窗口大小6个格子，即每个格子10s为例。

滑动窗口一直有一个疑问：窗口刚建立的时候，如果每隔10s，格子向右滑动，那么怎么初始化这个窗口呢？其实在初始化窗口的时候，格子先不移动。等1min窗口的格子，全部初始化完成后，才会每隔10s向右移动。

步骤：
初始化阶段（第一个1min内）：

1. 初始化阶段的第一个10s，初始化第一个格子。在这10s有3个请求进来，该格子的计数器统计为3。这里每进来一个请求，都会判断是否达到1min窗口最大的请求阈值。如果达到了，不在接收，直接拒绝。
2. 初始化阶段的第2个10s，初始化第二个格子。注意，这里第一个格子是不会向右移动，否则永远就只有一个格子了。在该10s内，有5个请求进来。其计数器统计为5。这里每进来一个请求，判断有没有达到阈值。同上。
3. 以此类推，第6个10s，假设前面5个格子，都还没到达阈值。这里可以继续接收请求。到这里一个窗口总算初始化完成了。
4. 在第6个10s快要结束，下个窗口开始前的时间临界点上。如果这时，有突发流量进来，那么最多计算的时候，不算步骤1中第1个10s的流量。会和2-5个格子求和。所以，这个突发流量不像“固定窗口”那样，完全没法计算。所以，滑动窗口把影响值仅仅缩小在一个格子上。固，只要格子越小，突发流量就越不容易钻空子，流量越平滑。
5. 在第7个10s的时候，窗口向右滑动一个格子，抛弃第1个格子的数据。在第7个10s内，每进来一个请求，和前面5个格子计算求和。判断是否超过阈值。
6. 以此类推，和第5步完全一样。

算法特点：

1. 可以解决“固定窗口”的窗口与窗口之间临界点的突发流量。格子越小，流量越平滑。
2. 如果一个窗口前1个格子，或者前几个格子，把阈值占满了。那么后面的格子，就无法接受请求。“固定窗口”算法，也是一样，一个窗口，一开始就满了，窗口后面的请求只能被粗暴的拒绝了。

三、漏桶算法

漏桶算法其实很简单，可以粗略的认为就是注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。这个从桶底流出去的水就是系统正常处理的请求，从旁边流出去的水就是系统拒绝掉的请求。

image.png

算法特点

1. 因为流出的速度是一定的，可以抵御突发流量，做到更加平滑的限流，而且不允许流量突发

四、令牌桶算法(Token Bucket)

令牌桶算法是比较常见的限流算法之一，Google开源项目Guava中的RateLimiter使用的就是令牌桶算法。流程如下：

1. 所有的请求在处理之前都需要拿到一个可用的令牌才会被处理。
2. 根据限流大小，设置按照一定的速率往桶里添加令牌。
3. 桶设置最大的放置令牌限制，当桶满时、新添加的令牌就被丢弃或者拒绝。

4. 请求到达后首先要获取令牌桶中的令牌，拿着令牌才可以进行其他的业务逻辑，处理完业务逻辑之后，将令牌直接删除。

   
   image.png
   

   算法特点

5. 可以抵御突发流量，因为桶内的令牌数不会超过给定的最大值
   可以做到更加平滑的限流，因为令牌是匀速放入的。
6. 令牌桶算法允许流量一定程度的突发。（相比漏桶算法）
7. 在时间点刷新的临界点上，只要剩余token足够，令牌桶算法会允许对应数量的请求通过，而后刷新时间因为token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量。因此，令牌桶算法也被广泛使用。