Swoole 的限流算法的实现
这篇文章来源于我在团队内部分享的内容，PPT 和代码已经上传到了 github。
better-maksim/swoole-rate-limiting: 基于 swoole 实现限流算法 (github.com)
- 什么是限流
- 限流的实现原理
- 优缺点分析
什么是限流？
- 通过并发限速（拒绝[降级]、排队、等待）形式达到保护服务的目的。
- 一部分人能访问，好过所有人都无法访问。
- 如何做：统计当前并发情况，当并发量达到预设峰值时拒绝访问。
生活中的限流场景
- 布达拉宫需要提前几个月进行预订
- 海底捞在满座后需要进行等待
- 魔兽世界需要排队登录
- 12306 如果使用刷票软件的话会被暂时禁止访问，还有就是限制时段购票
常见的限流算法
- 计数器
- 滑动窗口
- 漏铜
- 令牌
计数器算法
计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。
特点分析
优点：实现简单，容易理解。
缺点：流量曲线可能不够平滑，有“突刺现象”，如下图所示。这样会有两个问题：
一段时间内（不超过时间窗口）系统服务不可用。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
窗口切换时可能会产生两倍于阈值流量的请求。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第999ms来了100个请求，窗口前期没有请求，所以这100个请求都会通过。再恰好，下一个窗口的第1ms有来了100个请求，也全部通过了，那也就是在2ms之内通过了200个请求，而我们设定的阈值是100，通过的请求达到了阈值的两倍。
计数器滑动窗口算法
计数器滑动窗口算法是计数器固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点。
滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器。当请求的时间大于当前窗口的最大时间时，则将计时窗口向前平移一个小窗口。平移时，将第一个小窗口的数据丢弃，然后将第二个小窗口设置为第一个小窗口，同时在最后面新增一个小窗口，将新的请求放在新增的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之后不能超过设定的阈值。
从图中不难看出，滑动窗口算法就是固定窗口的升级版。将计时窗口划分成一个小窗口，滑动窗口算法就退化成了固定窗口算法。而滑动窗口算法其实就是对请求数进行了更细粒度的限流，窗口划分的越多，则限流越精准。
特点分析
- 避免了计数器固定窗口算法固定窗口切换时可能会产生两倍于阈值流量请求的问题；
- 和漏斗算法相比，新来的请求也能够被处理到，避免了漏斗算法的饥饿问题。
漏斗算法
漏斗算法的原理也很容易理解。请求来了之后会首先进到漏斗里，然后漏斗以恒定的速率将请求流出进行处理，从而起到平滑流量的作用。当请求的流量过大时，漏斗达到最大容量时会溢出，此时请求被丢弃。从系统的角度来看，我们不知道什么时候会有请求来，也不知道请求会以多大的速率来，这就给系统的安全性埋下了隐患。但是如果加了一层漏斗算法限流之后，就能够保证请求以恒定的速率流出。在系统看来，请求永远是以平滑的传输速率过来，从而起到了保护系统的作用。
令牌桶算法是对漏斗算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发。在令牌桶算法中，存在一个令牌桶，算法中存在一种机制以恒定的速率向令牌桶中放入令牌。令牌桶也有一定的容量，如果满了令牌就无法放进去了。当请求来时，会首先到令牌桶中去拿令牌，如果拿到了令牌，则该请求会被处理，并消耗掉拿到的令牌；如果令牌桶为空，则该请求会被丢弃。
特点分析
- 漏桶的漏出速率是固定的，可以起到整流的作用。即虽然请求的流量可能具有随机性,忽大忽小，但是经过漏斗算法之后，变成了有固定速率的稳定流量，从而对下游的系统起到保护作用。
- 不能解决流量突发的问题。还是拿刚刚测试的例子，我们设定的漏斗速率是2个/秒，然后突然来了10个请求，受限于漏斗的容量，只有5个请求被接受，另外5个被拒绝。你可能会说，漏斗速率是2个/秒，然后瞬间接受了5个请求，这不就解决了流量突发的问题吗？不，这5个请求只是被接受了，但是没有马上被处理，处理的速度仍然是我们设定的2个/秒，所以没有解决流量突发的问题。而接下来我们要谈的令牌桶算法能够在一定程度上解决流量突发的问题，读者可以对比一下。
令牌桶算法
令牌桶算法是对漏斗算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发。在令牌桶算法中，存在一个令牌桶，算法中存在一种机制以恒定的速率向令牌桶中放入令牌。令牌桶也有一定的容量，如果满了令牌就无法放进去了。当请求来时，会首先到令牌桶中去拿令牌，如果拿到了令牌，则该请求会被处理，并消耗掉拿到的令牌；如果令牌桶为空，则该请求会被丢弃。
特点分析
令牌桶算法是对漏桶算法的一种改进，除了能够在限制调用的平均速率的同时还允许一定程度的流量突发。
总结
计数器固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有“突刺现象”，在窗口切换时可能会产生两倍于阈值流量的请求。而计数器滑动窗口算法作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题。
漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决流量突发的问题。令牌桶算法作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。
以上四种限流算法都有自身的特点，具体使用时还是要结合自身的场景进行选取，没有最好的算法，只有最合适的算法。
比如令牌桶算法一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。如果自身的系统实际的处理能力强于配置的流量限制时，可以允许一定程度的流量突发，使得实际的处理速率高于配置的速率，充分利用系统资源。而漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的打到第三方的接口上。
算法是死的，而算法中的思想精髓才是值得我们学习的。实际的场景中完全可以灵活运用，还是那句话，没有最好的算法，只有最合适的算法。