限流|限流算法
一、概念
限流顾名思义，就是对请求或并发数进行限制；通过对一个时间窗口内的请求量进行限制来保障系统的正常运行。如果我们的服务资源有限、处理能力有限，就需要对调用我们服务的上游请求进行限制，以防止自身服务由于资源耗尽而停止服务。
二、限流分类
限流的分类如下所示：
合法性验证限流：比如验证码、IP 黑名单等，这些手段可以有效的防止恶意攻击和爬虫采集；最常规的业务手段。
容器限流：比如 Tomcat、Nginx 等限流手段，其中 Tomcat 可以设置最大线程数（maxThreads），当并发超过最大线程数会排队等待执行；而 Nginx 提供了两种限流手段：一是控制速率，二是控制并发连接数；
服务端限流：比如我们在服务器端通过限流算法实现限流，本文介绍的重点。
三、常见的限流算法
1、固定窗口计数（Fixed window counter）
固定窗口算法又叫计数器算法，是一种简单方便的限流算法。主要通过一个支持原子操作的计数器来累计 1 秒内的请求次数，当 1 秒内计数达到限流阈值时触发拒绝策略。每过 1 秒，计数器重置为 0 开始重新计数。
滑动窗口特点：
固定窗口计数缺点也非常明显，在进行周期切换时，上一个周期的访问总数会立即置为0，这可能导致在进行周期切换时可能出现流量突发。
如图，QPS设置为2，当遇到时间窗口的临界突变时，如 1s 中的后 500 ms 和第 2s 的前 500ms 时，虽然是加起来是 1s 时间，却可以被请求 4 次。很明显超过了限流值2。
2、滑动窗口计数（Sliding window counter）
我们已经知道固定窗口算法的实现方式以及它所存在的问题，而滑动窗口算法是对固定窗口算法的改进。既然固定窗口算法在遇到时间窗口的临界突变时会有问题，那么我们在遇到下一个时间窗口前也调整时间窗口不就可以了吗？
上图的示例中，每 500ms 滑动一次窗口，可以发现窗口滑动的间隔越短，时间窗口的临界突变问题发生的概率也就越小，不过只要有时间窗口的存在，还是有可能发生时间窗口的临界突变问题。
3、漏桶算法（Leaky bucket）
漏桶算法中的漏桶是一个形象的比喻，这里可以用生产者消费者模式进行说明，请求是一个生产者，每一个请求都如一滴水，请求到来后放到一个队列（漏桶）中，而桶底有一个孔，不断的漏出水滴，就如消费者不断的在消费队列中的内容，消费的速率（漏出的速度）等于限流阈值。即假如 QPS 为 2，则每 1s / 2= 500ms 消费一次。漏桶的桶有大小，就如队列的容量，当请求堆积超过指定容量时，会触发拒绝策略。
漏桶算法主要特点在于可以保证无论收到请求的速率如何，真正抵达服务方接口的请求速率最大为r，能够对输入的请求进行平滑处理。
漏桶算法的缺点也非常明显，由于其只能以特定速率处理请求，则如何确定该速率就是核心问题，如果速率设置太小则会浪费性能资源，设置太大则会造成资源不足。并且由于速率的设置，无论输入速率如何波动，均不会体现在服务端，即使资源有空余，对于突发请求也无法及时处理，故对有突发请求处理需求时，不宜选择该方法。
4、令牌桶算法（Token bucket）
令牌桶算法同样是实现限流是一种常见的思路，最为常用的 Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一个实现。令牌桶的实现思路类似于生产者和消费之间的关系。系统服务作为生产者，按照指定频率向桶（容器）中添加令牌，如 QPS 为 2，每 500ms 向桶中添加一个令牌，如果桶中令牌数量达到阈值，则不再添加。请求执行作为消费者，每个请求都需要去桶中拿取一个令牌，取到令牌则继续执行；如果桶中无令牌可取，就触发拒绝策略，可以是超时等待，也可以是直接拒绝本次请求，由此达到限流目的。下面是令牌桶限流算法示意图。
令牌桶的实现有以下特点。
1.1s / 阈值（QPS） = 令牌添加时间间隔。
2.桶的容量等于限流的阈值，令牌数量达到阈值时，不再添加。
3.可以适应流量突发，N 个请求到来只需要从桶中获取 N 个令牌就可以继续处理。
4.有启动过程，令牌桶启动时桶中无令牌，然后按照令牌添加时间间隔添加令牌，若启动时就有阈值数量的请求过来，会因为桶中没有足够的令牌而触发拒绝策略。
四、四种算法对比
算法名称 | 需要确定参数 | 实现简介 | 空间复杂度 | 说明 |
固定窗口计数 | 计数周期T周期内最大访问数N | 使用计数器在周期内累加访问次数，达到最大次数后出发限流策略 | O(1)，仅需要记录周期内访问次数及周期开始时间 | 周期切换时可能出现访问次数超过限定值 |
滑动窗口计数 | 计数周期T周期内最大访问数N滑动窗口数M | 将时间周期分为M个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期 | O(M)，需要记录每个小周期中的访问数量 | 缓解固定窗口算法周期切换时的访问突发问题，但不能完全避免 |
漏桶算法 | 漏桶流出速度r漏桶容量N | 服务到达时直接放入漏桶，如当前容量达到N，则触发限流侧率，程序以r的速度在漏桶中获取访问请求，知道漏桶为空 | O(1)，仅需要记录当前漏桶中容量 | 平滑流量，保证服务请求到达服务方的速度恒定，突发流量不能快速响应 |
令牌桶算法 | 令牌产生速度r令牌桶容量N | 程序以r的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如有满足需求的令牌则通过请求，否则触发限流策略 | O(1)，仅需要记录当前令牌桶中令牌数 | 能够在限流的基础上，处理一定量的突发请求 |
窗口算法和桶算法，两者各有优势。
窗口算法实现简单，逻辑清晰，可以很直观的得到当前的 QPS 情况，但是会有时间窗口的临界突变问题，而且不像桶一样有队列可以缓冲。
桶算法虽然稍微复杂，不好统计 QPS 情况，但是桶算法也有优势所在。
漏桶模式消费速率恒定，可以很好的保护自身系统，可以对流量进行整形，但是面对突发流量不能快速响应。
令牌桶模式可以面对突发流量，但是启动时会有缓慢加速的过程（guava的RateLimiter基于令牌桶实现，并且对缓慢加速进行了优化）。