限流：当并发访问量 / 请求速率达到一定阈值时，系统通过一些限流方案进行限制访问，以保护系统。
常见的限流方案：
1）计数器
2）令牌桶
3）漏桶
方案一：计数器
1.1 固定窗口
原理：设置每段时间内的访问数上限，并用计数器记录该段时间内的访问数。当计数值大于上限时，拒绝后面的访问
例子：规定 1s 内访问数上限是 100，用计数器来记录该 1s 内的访问数，当计数值超过 100 后，拒绝访问。当进入下 1s 时，计数器清零。
优点：实现简单
缺点：固定时间窗口算法无法限制窗口间突发流量（因为两个时间窗口之间没有任何联系，所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求）
- 比如 1s 上限是 10，第1秒后半段时间10个请求，第2秒前半段10个请求，那第1秒后半段+第2秒前半段时间组成的一秒钟里就有20个请求，没有起到限速的作用。[2]
滑动窗口
目的：解决 “固定窗口算法无法限制窗口间突发流量”
原理：将固定窗口切分成更小的窗口
效果：相对于固定窗口算法，可以抵御窗口间突发流量。【本身还是存在该问题】
方案二：令牌桶
前提介绍：
- 请求到达时，先要获得令牌，服务器才会对该请求进行处理；反之，拒绝请求
- 系统按照一定速率产生令牌，并放到令牌桶中
- 有一个桶用于存放一些令牌，称为令牌桶
- 桶存放的数量有限制，当桶满了，新产生的令牌丢弃
原理：通过控制令牌的产生速率，进而实现限流
令牌桶的原理 [1]
优点：可以抵御突发流量，因为桶存放的令牌有上限
实例：Google开源项目Guava中的RateLimiter使用的就是令牌桶算法
方案三：漏桶
原理：注水漏水过程，往桶中以一定速率流出水，以任意速率流入水，当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。这个从桶底流出去的水就是系统正常处理的请求，从旁边流出去的水就是系统拒绝掉的请求。[1]
漏桶算法的原理[1]
漏桶算法和令牌桶算法的对比
- 令牌桶通知桶的流入速率，但不控制流出速率，即只要令牌够，瞬间处理请求数是变化的，所以称为允许一定程度的流量突发。
- 漏桶控制桶的流出速率，即瞬间处理请求的速率是固定的，所以不允许流量突发。
参考文献
[1] 高并发系统的限流算法与实现_0-1的专栏-CSDN博客
[2] 高并发场景下的限流策略 - 后端 - 掘金
[3] 聊聊高并发系统之限流特技一 - 简书
网友评论