常见限流算法

计数器固定窗口算法

原理：

• 一个时间窗口内对请求计数，超过阀值则丢弃
• 时间窗口结束，同时重置计数器为0

优点：

• 实现简单

缺点：

• 一个时间窗口内服务不可用；例如时间窗口为1s，限流100。在1ms时来了100个请求，后面999ms的请求会感觉系统不可用
• 窗口切换临界会出现2倍阀值流量；例如时间窗口为1s，限流100。在0-998ms没有请求，在999ms来了100请求。在下个时间窗口1ms时来了100请求。也就在2ms内通过了100 * 1个请求

计数器滑动时间窗口算法

原理：

• 一个时间窗口被划分成若干个小时间窗口（计数器固定窗口），每个小时间窗口内对请求单独计数，超过阀值则丢弃
• 滑动；小窗口结束时，第1个小窗口丢弃，并在最后增加1个小时间窗口

优点：

• 解决了计数器固定时间窗口算法在窗口切换时，可能出现2倍请求阀值问题
• 和漏斗算法相比，新来的请求也能被处理到，避免漏斗算法饥饿问题

漏斗（桶）算法

原理：

• 请求以不同的速度进入桶
• 桶容量可以缓存n个请求，超过桶容量则丢弃
• 请求以恒定速度出桶，被系统请求

优点：

• 漏桶流出速率是固定的

缺点：

• 不能解决突发流量问题；突发流量仅在桶中缓存，并没有被系统处理

令牌桶算法

原理：

• 匀速产生令牌放到桶中
• 请求经过时，从桶中获取1个令牌并消耗，桶中没有令牌则拒绝请求

优点：

• 允许一定程度的突发流量

总结

• 是否允许一定程度突发流量是漏斗算法和令牌桶算法的主要区别

参考

• https://juejin.cn/post/6870396751178629127