常见限流算法
背景
在网络应用程序中，用于控制请求的流量，防止系统过载，会使用限流算法对请求做限流。最近我参与的一个项目中需要限制最大 QPS，以及最大的读写带宽。这都需要使用到限流算法。 本文中我会系统地梳理了常见的限流算法，并分析其优缺点和适用场景。
固定窗口计数算法 (Fixed window counter algorithm)
固定窗口计数算法的基本思想是将时间轴分成多个固定大小的窗口，每个窗口内统计请求的次数。如果请求次数超过了阈值，就拒绝请求。比如窗口时间为 1 秒，限流 QPS 为 1000，每次请求到达时，将计数器加 1，如果计数器的值超过了 1000，则拒绝请求。
固定窗口计数算法的实现比较简单，存在较多问题。当流量较大时，在单位时间的刚开始的阶段，请求的次数可能就超过了阈值，在后续的时间里所有请求都会被拒绝，而在单位时间的前半段允许请求。这可能会导致系统的负载不均衡。
如果突发的流量横跨两个时间窗口，比如下图中，在前前后两个时间窗口内均处理了 5 个请求，但在同样的时间范围实际处理了 10 个请求。
滑动窗口计数算法 (Sliding window counter algorithm)
滑动窗口算法是对固定窗口计数算法的改进，解决固定窗口计数算法中突发流量可能超过阈值的问题。在滑动窗口算法中，时间窗口是不断滑动的，窗口的起点是当前时间点减去窗口的大小。在判断是否拒绝请求时，需要判断当前时间窗口内的请求数量是否超过了阈值。
在计算滑动窗口内已经处理的请求数量时，会使用滑动窗口和前一个窗口重叠的比例。设重叠比例为 ，前一个窗口的请求数量为 ，当前窗口的请求数量为 ，那么滑动窗口内已经处理的请求数量为 。
滑动窗口算法利用前一个固定窗口的请求数量，并使用重叠比例，来预估当前滑动窗口内可以处理的请求数量。这可以避免固定窗口计数算法中突发流量可能超过阈值的问题，可以让流量更加平滑地被处理。
滑动窗口日志算法 (Sliding window log algorithm)
滑动窗口日志算法记录了每个请求的时间戳，当请求到达时，使用当前时间减去窗口的大小，得到窗口的起点。先将所有小于窗口起点的时间戳从日志中移除。如果当前时间窗口的日志数量超过了阈值，就拒绝请求。否则，就将当前请求的时间戳放入日志中。
上图中，队列的容量为 5，时间窗口为 1 分钟。前两幅子图中，队列未满，请求被接受。而在第三幅子图中，队列已满，请求被拒绝。第四幅子图中，删除了队列头部已经过期的元素，队列中有了空间，请求被接受。
可以看到滑动窗口日志算法的实现很直观，就是将窗口内的请求的时间戳保存下来，这样可以始终精确地获知到当前滑动窗口内已经处理了多少个请求，这样就可以准确地实现限流，避免了固定窗口计数算法中突发流量可能超过阈值的问题。
因为需要维护一个日志数据结构，所以会占用额外的内存空间。尤其是限流阈值比较大时，这种算法就不适用了。但此算法可以严格保证，在单位时间内，请求的数量不会超过阈值。
令牌桶算法 (Token bucket algorithm)
令牌桶算法的基本思想是维护一个令牌桶，并以恒定的速率生成令牌放入令牌桶中。当令牌桶已满时，新生成的令牌会被丢弃。当请求到达时，需要从令牌桶中获取令牌。如果成功获取到令牌，则对请求进行处理；否则，对请求进行限流。
令牌桶算法的一个优势是可以平滑地处理流量，因为令牌桶以恒定的速率生成令牌，当令牌消耗完后，令牌生成的速率就可以控制请求处理的速率。而如果流量不均匀，有时会有突发的流量，令牌桶中堆积的令牌可以用于应对这些突发流量。
令牌桶算法有两个参数：
- 令牌桶的容量：令牌桶的容量表示令牌的最大数量，储存的令牌可以用于应对突发流量。
- 令牌生成速率：令牌生成速率可以根据系统的处理能力和流量情况进行调整。当流量比较平稳时，生成速率就决定了请求处理的速率。
我认为令牌桶算法的精髓在于引入了令牌桶作为缓冲，以应对突发流量。如果没有令牌桶，而只是以恒定速率生成令牌，这就和固定窗口计数算法一样了。
漏桶算法 (Leaking bucket algorithm)
漏桶算法的基本思想是维护一个容量固定的桶，这个桶里装的是请求。当一个请求达到时，将请求放入桶中。如果桶满了，就拒绝请求。另外一边，系统会以恒定的速率从桶中取出请求进行处理。
漏桶算法中，请求处理的速度决定了限流的速度。如果请求处理的速度大于等于令牌生成的速度，那么就不会有请求被拒绝。如果请求处理的速度小于令牌生成的速度，那么待处理的请求就会堆积，这个时候部分请求会被拒绝。
总结
本文中我系统地梳理了常见的限流算法，并分析了各自的特点：
- 固定窗口计数算法：实现简单，存在突发流量可能超过阈值的问题。
- 滑动窗口计数算法：使用滑动窗口，结合与前一个窗口的重叠比例，来预估当前滑动窗口内可以处理的请求数量。
- 滑动窗口日志算法：记录了每个请求的时间戳，占用额外的内存空间，但是可以严格保证单位时间内请求的数量不会超过阈值。
- 令牌桶算法：以固定速率往令牌桶中放入令牌，可以平滑地处理流量，引入了令牌桶作为缓冲，可以应对突发流量。
- 漏桶算法：使用固定的桶来存储请求，以固定的速率从桶中取出请求进行处理，请求处理的速度决定了限流的速度。
限流算法种类不少，但我认为令牌桶算法和固定窗口计数算法是最常用的两种限流算法。在我参与的项目中，对限流准确性要求不高的场景下，通常使用固定窗口计数算法，比如用来限制每秒最多打印的日志数量。而对限流准确性和流量处理的平滑度要求高的场景下，可以使用令牌桶算法，比如限制带宽、QPS 等等。