一、限流是什么
限流在我们的日常生活中很常见，例如我们去景区玩，然而景区每天售卖的门票数是有限的，比如 2000 张，那么每天最多只能有 2000 个人进去玩。
那我们工程上的限流是什么呢？这里要具体场景具体分析，不同场景下「流」的定义不同。一般「流」可以是每秒请求数、每秒事务处理数等。而我们通常说的限流指的是限制到达系统的并发请求数，使得系统能够正常地处理部分用户的请求，从而保证系统的稳定性。
限流不可避免的会造成用户的请求变慢甚至被拒的情况，影响用户体验。因此，限流需要在用户体验和系统稳定性之间做一个平衡（trade-off）。
二、为什么要限流
前面我们提到，限流是为了保证系统的稳定性。那么，哪些情况会影响系统的稳定性从而需要限流呢？
业务开发中，我们会遇到类似秒杀、大促或突发新闻等情况，这种场景下用户的流量会突增，然而，后端服务的处理能力是有限的，如果不能处理好突发的流量，后端服务很容易就会被打垮。
此外，如果我们的服务是对外的，那么很容易受到像爬虫、DDos 等这些非正常流量的攻击，因此，我们对外暴露的服务要以最大的恶意去防备调用者。
另一方面，对于很多第三方开放平台来说，不仅仅要防备非正常流量，还要保证资源的公平利用，防止某个调用方独占系统的资源，造成其他的调用方“饿死”。
总之，为什么要限流是因为后端服务处理能力有限，需要截掉超过处理能力之外的请求，保证系统的稳定性，亦或是为了均衡客户端对服务端资源的公平调用。
三、常见的限流算法
下面介绍几种常用的限流算法，分别是计数限流、固定窗口限流、滑动窗口限流、漏桶算法和令牌桶算法。
3.1 计数限流
最简单的限流算法就是计数限流了。
假设系统能同时处理 100 个请求，我们创建一个计数器，当处理了一个请求，计数器加一，当一个请求处理完了，计数器减一。每次请求来的时候看看计数器的值，如果超过阈值就拒绝请求。
计数限流的伪代码如下：
boolean tryAcquire() {
if (counter < threshold) {
counter++;
return true;
}
return false;
}
boolean tryRelease() {
if (counter > 0) {
counter--;
return true;
}
return false;
}
根据计数器存放的位置可以分为单机限流和分布式限流。如果计数器在内存中就是单机限流，如果计数器在一个第三方存储里，如 Redis，那就是分布式限流。
计数限流最大的优点是简单，单机限流如果是 Java 的话可以使用 Atomic 等原子类实现，分布式限流可以使用 Redis 的 incr 实现。
计数限流的缺点是：假设系统允许的阈值是 1 万，此时计数器的值为 0， 当 1 万个请求在 1 秒内一股脑儿涌进来的话，这种突发的流量系统是顶不住的。
而且一般的限流都是为了限制在指定时间间隔内的请求数量，因此还有个算法叫固定窗口限流。
3.2 固定窗口限流
固定窗口限流相比于计数限流多了个时间窗口的概念，计数器每过一个时间窗口就重置。该算法的规则如下：
- 请求次数小于阈值，允许访问并且计数器 +1；
- 请求次数大于阈值，拒绝访问；
- 这个时间窗口过了，计数器清零；
固定窗口限流的伪代码如下：
boolean tryAcquire() {
// 获取当前时间
long now = System.currentTimeMillis();
// 如果过了时间窗口，计数器清零
if (now - lastAcquireTime > timeWindow) {
counter = 0;
lastAcquireTime = now;
}
// 如果计数器的值小于阈值，允许请求
if (counter < threshold) {
counter++;
return true;
}
return false;
}
看起来好像很完美，实际上还是有缺陷的，最大的缺陷是无法处理窗口临界问题。
假设系统每秒允许 100 个请求，第一个时间窗口是 0-1s，假设在第 0.55s 处涌入了 100 个请求，过了 1 秒后时间窗口计数器清零，此时在 1.05 s 又涌入了 100 个请求。虽然窗口内的计数没有超过阈值，但是从全局来看 0.55s-1.05s 这 0.5 秒内涌入了 200 个请求，这其实对于阈值是 100/s 的系统来说是无法接受的。
为了解决这个问题引入了滑动窗口限流。
3.3 滑动窗口限流
滑动窗口限流解决了固定窗口限流临界值的问题，可以保证在任意时间窗口内请求数量都不会超过阈值。
相对于固定窗口，滑动窗口除了需要引入计数器之外，还需要记录时间窗口内每个请求到达的时间点。
假设时间窗口为 1 秒，该算法的流程如下：
- 统计每次请求的时间至往前推1秒这个时间窗口内的请求数，并且 1 秒前的数据可以删除；
- 如果统计的请求数小于阈值就允许通过，并记录这个请求的时间，反之拒绝。
采用滑动窗口可以解决上述固定窗口的窗口临界问题，如下所示：
滑动窗口限流的伪代码如下：
boolean tryAcquire() {
// 获取当前时间
long now = System.currentTimeMillis();
// 根据当前时间获取当前时间窗口的请求数
long counter = getCounterInTimeWindow(now);
// 如果小于阈值，允许通过，并记录当前时间
if (counter < threshold) {
addToTimeWindow(now);
return true;
}
return false;
}
但是滑动窗口和固定窗口都无法解决短时间之内集中流量的突击。
我们所设想的限流场景是：每秒限制 100 个请求，即希望请求每 10ms 来一个，这样我们的流量处理就很平滑。但是，真实场景很难控制请求的频率，因此可能存在 5ms 内请求就打满了阈值的情况。
下面介绍漏桶算法，它可以使得流量处理更加地平滑。
3.4 漏桶算法
如果我们把服务比作是一个漏桶，请求比作是水滴，水滴持续不断地滴入桶中，底部再定速流出。如果水滴滴入的速率大于流出的速率，当桶中的水满时就会溢出。
漏桶算法的规则如下：
- 请求来了放入桶中；
- 桶内的请求量满了拒绝请求；
- 服务定速地从桶内拿请求并处理。
漏桶算法的伪代码如下：
boolean tryAcquire() {
// 获取当前时间
long now = System.currentTimeMillis();
// 计算流出的水量
long consumeWater = (now - lastInjectTime) * rate;
// 计算桶内剩余的水量
long leftWater = Math.max(0, leftWater - consumeWater);
if (leftWater + 1 < capacity) {
lastInjectTime = now;
leftWater++;
return true;
}
return false;
}
可以看到，漏桶算法的特点就是宽进严出。无论请求量是多少，请求速率有多大，都按照固定的速率流出，对应的就是服务按照固定的速率处理请求。这其实和消息队列的思想有点像，事实上漏桶也可以用消息队列来实现，处理不过来的请求就排队，如果队列满了就拒绝请求。
虽然经过漏桶的过滤，系统可以平滑地处理请求，看起来貌似挺完美的，然而实际上，漏桶算法也是有缺点的。面对突发的请求，服务的处理速度和平时是一样的，这其实不是我们想要的。
在面对突发流量时，我们希望系统在平稳的同时，能够更快地处理请求，而不是和平常一样循规蹈矩地处理。
下面将要介绍的令牌桶算法在处理突发流量时可以更加“激进”。
3.5 令牌桶算法
令牌桶其实和漏桶的原理类似，只不过漏桶是定速地流出，而令牌桶是定速地往桶里塞入令牌，请求只有拿到了令牌才能通过，之后再被服务器处理。当然，令牌桶的大小也是有限制的，假设桶里的令牌满了之后，之后生成的令牌会被丢弃。
令牌桶算法的规则如下：
- 定速的往桶内放入令牌；
- 如果令牌的数量超过桶的容量，丢弃令牌；
- 请求来了先向桶内索要令牌，索要成功则通过，反之拒绝。
令牌桶算法的伪代码如下：
boolean tryAcquire() {
// 获取当前时间
long now = System.currentTimeMillis();
// 计算生成的令牌数
long generatedToken = (now - lastAcquireTime) * rate;
// 计算桶内的令牌数
long leftToken = Math.min(capacity, leftToken + generatedToken);
if (leftToken >= 1) {
lastAcquireTime = now;
leftToken--;
return true;
}
return false;
}
假设桶内有 100 个令牌，当面对突发流量时，这 100 个令牌可以立马被取走，而不像漏桶那样匀速的处理请求。所以令牌桶在应对突发流量时比漏桶表现更佳。
3.6 限流算法小结
从上面对几种限流算法的比较来看，貌似令牌桶算法是最优的，那是不是我们在平时开发中遇到限流问题一律采用令牌桶算法就好了呢？
其实并不是的。假设你没做预热，当系统刚上线时令牌桶里是没有令牌的，那么请求过来直接就拒绝了，造成“误杀”。
再比如，假设桶内初始没有令牌，系统每 1 秒往桶里放入一个令牌，然而，系统刚好在第 1 秒内有两个请求，第二个 1 秒没有请求，那么从 2 秒来看只有 2 个请求，应该都放行的，但是第二个请求就被拒了。
事实上，令牌桶和漏桶比较适合阻塞式限流场景，即没令牌我就等着，这样就不会误杀了。而基于时间窗口的限流比较适合对时间敏感的场景，当请求过不了时直接拒绝请求，不会出现一直等待的情况。
四、限流的难点
可以看到，每个限流都有个阈值，这个阈值如何定是个难点。
如果阈值定大了，服务器可能顶不住，如果阈值定小了，有些请求就被“误杀”了，达不到资源利用最大化，并且对用户体验也不好。
估算阈值的一个简单的方法是：
- 限流上线后先预估个大概的阈值，然后不执行真正的限流操作，而是采取打点，即记录日志的方式，然后对日志进行分析查看限流的效果，一步一步调整阈值，推算出每台机器的处理能力和集群总的处理能力；
- 将线上的流量进行重放，测试真正的限流效果，最终确定阈值并上线。
五、常见的限流组件
一般而言，我们不需要自己实现限流算法来达到限流的目的，不管是接入层限流还是细粒度的接口限流，都有现成的轮子供我们使用，其实现也是采用了上述我们所说的限流算法。
比如 Google Guava 提供的限流工具类 RateLimiter 是基于令牌桶实现的，并且扩展了算法，支持预热功能。
再比如阿里开源的限流框架 Sentinel 中的匀速排队限流策略，就采用了漏桶算法。
这里简单介绍下 Google Guava 的 RateLimiter 使用。如下所示：
boolean tryAcquire() {
RateLimiter rateLimiter = RateLimiter.create(1);
if (rateLimiter.tryAcquire()) {
return true;
}
return false;
}
RateLimiter.create(1) 创建了一个限流器，入参 1 表示每秒生成的令牌数为 1。rateLimiter.tryAcquire() 通过非阻塞的方式获取令牌，当获取令牌成功时返回 true，否则返回 false。
Google Guava 的 RateLimiter 还支持稳定模式（SmoothBursty）和渐进模式（SmoothWarmingUp）两种限流模式，其中稳定模式的令牌以恒定的速度生存，渐进模式的令牌生成速度缓慢提升直到维持在一个稳定值。这里就不做过多介绍了，感兴趣的小伙伴可以自行查阅相关资料，学习一下生产级别的限流是如何实现的。
六、总结
本文主要从概念上梳理了一下限流的背景和常见的限流算法，然后简单介绍了一下限流的难点和常见的限流组件，帮助大家对限流有一个更清晰的认识，从而更好地在项目中实践限流。