常见的限流算法
计算机系统中，常常会有各种业务场景需要限制调用方的调用频次，当下游调用频次过高时，往往会造成服务端过多资源占用从而请求报错，超时甚至服务崩溃等超出预期的情况。在此时限流算法就显得非常有必要。
在介绍之前，有一点需要弄清楚：当我们分别说限流 1 次/s 和 60 次/min 时，我们是在谈论一件事吗？
我们姑且认为限流次数在 n 时间内 m 次的调用的定义为：在程序启动的任意时间区间内划分一个 n 时间段，调用次数不会大于 m 次（后文的令牌桶实现其实打破了这个定义）。那么 1次/s 的限制是比 60次/min 是要严格得多的，后者允许 30s 的时刻出现 59 次调用，然后其余的时间没有任何调用，而前者是不允许的。
常见的限流算法包括：
- 固定窗口计数器(Fixed window counter)
- 滑动窗口日志(Sliding window log)
- 滑动窗口计数器(Sliding window counter)
- 漏桶(Leaky bucket)
- 令牌桶(Token bucket)
其中，前三种限流算法中，一旦窗口流量到达阈值，就会被马上丢弃，在一些实际应用的过程中往往需要并不是马上掐断，而是使得流量平稳地过渡，在这个场景下，漏桶和令牌桶就更加有用武之地了。
固定窗口计数器(Fixed window counter)
固定窗口技术法是最简单粗暴的限流算法。
- 将时间划分为固定的窗口大小，相邻的窗口不重叠；
- 在当前时间窗口之内，每来一个请求就对计数器加 1；
- 当计数器达到设定的时间限制之后，则抛弃超出的请求；
- 窗口时间结束之后，计数器清零，重新开始计数。
固定窗口计数法的优点十分明显，就是简单，但是缺点也非常突出，本质上也无法实现文章开头的严格的限流定义，而且在很多情况下，如果有很多请求被限流，那么计数都在每个窗口开始的一小段时间被迅速消耗，而剩下的时间则处理不了任何请求。
滑动窗口计数器(Sliding window counter)
滑动窗口计数法和固定窗口计数法比较类似。只不过将时间窗口分成了一个个 slot ，比如下图中本来是一个每秒 2 次的限流。按照 250 ms 的区间，将每个 1s 都划分成了 4 个 slot，然后时间窗口按照 slot 的长度去移动，可以做到比单纯的固定时间区间更加平滑的限流。
slot 足够小的话，滑动窗口计数法可以实现文章开头的严格的限流定义。不过滑动窗口的 slot 不可能无限小，所以以上这种基于滑动窗口的限流想要做到完全精确的话，实践起来也是不可能的，只能做到近似。
滑动窗口日志(Sliding window log)
滑动窗口日志的实现说起来比较简单，当用户限制 n 秒内 m 次调用时候，那么就维持住最近 n 秒最多 m 次调用的时间戳（时间戳相同就维持时间戳和对应调用次数的映射）在集合 C 中（C 的容量即为 m），每当有新的请求过来时，就从 C 中删除掉 n 秒前的请求数据，如果集合是满的，那么就拒绝请求，反之则通过请求，并将请求的时间戳加入集合。
滑动窗口日志算法可以实现严格的限流定义，但是在高并发情况下，对删除操作的性能要求比较高，占用的内存存储空间也比较高。因为成本比较高，所以相对应的会有一些优化算法。
因为算法的复杂度本身在于计算过去时间的请求数有多少个来执行集合数据清理逻辑，一种思路就是因此结合一下固定窗口的思路，只维持每个固定窗口内请求的个数，比如 0s-1s 的请求为 10 个，此时如果要计算 0.2s-1s 的请求个数，那么就执行一个估算为 8 个，这样就可以不维护对应的时间戳了，可以较大程度上降低原生滑动窗口日志算法的计算成本。
漏桶(Leaky bucket)
漏桶算法中：
- 每个请求是“水滴”，放在桶中进行暂存。
- 桶底有个洞，所以是漏桶。漏桶以固定的速率，从桶中滴出请求来进行执行。
- 如果桶中没有水了，则停止执行请求。
- 如果桶满了，则新的请求会被丢弃。
总结下来：
漏桶是将用户的请求放在了一个队列中进行了缓存。比如用户限流的参数是 1 次/秒，那么最终的结果就是每秒钟的调用次数一定是小于等于 1 次/秒的，多余的请求会被缓存在桶中。
令牌桶(Token bucket)
令牌桶和漏桶有一些类似，一定程度上可以认为是漏桶的一种改进。不过现在桶里装的不再是水了，而是令牌。
请求是否被限流与桶中的令牌数是相关的，具体来说：
- 令牌按照用户设置好的速率放入令牌桶中；
- 桶的容量也是有限的，当桶满时，多余的令牌将会被丢弃；
- 请求到达时候先获取令牌桶中的令牌：
- 如果有令牌，那么执行请求，然后将对应的令牌丢弃。
- 如果没有令牌，那么请求将被限流直到令牌到达。
漏桶不允许任何的突发流量，但是在令牌桶中，是允许一定的突发流量的，比如用户限流的参数是 1 次/秒，桶的容量为 20，那么是可以允许用户在前 19 秒的时间里没有任何调用，在最后的 1 秒里完成 20 次的调用的。