服务端限流
服务端限流需要配合限流的算法来执行，而算法相当于执行限流的“大脑”，用于指导限制方案的实现。
有人看到「算法」两个字可能就晕了，觉得很深奥，其实并不是。算法就相当于操作某个事务的具体实现步骤汇总，其实并不难懂，不要被它的表象给吓到哦~
限流的常见算法有以下三种：
- 时间窗口算法
- 漏桶算法
- 令牌算法
接下来我们分别看来。
1.时间窗口算法
所谓的滑动时间算法指的是以当前时间为截止时间，往前取一定的时间，比如往前取 60s 的时间，在这 60s 之内运行最大的访问数为 100，此时算法的执行逻辑为，先清除 60s 之前的所有请求记录，再计算当前集合内请求数量是否大于设定的最大请求数 100，如果大于则执行限流拒绝策略，否则插入本次请求记录并返回可以正常执行的标识给客户端。
滑动时间窗口如下图所示：
其中每一小个表示 10s，被红色虚线包围的时间段则为需要判断的时间间隔，比如 60s 秒允许 100 次请求，那么红色虚线部分则为 60s。
我们可以借助 Redis 的有序集合 ZSet 来实现时间窗口算法限流，实现的过程是先使用 ZSet 的 key 存储限流的 ID，score 用来存储请求的时间，每次有请求访问来了之后，先清空之前时间窗口的访问量，统计现在时间窗口的个数和最大允许访问量对比，如果大于等于最大访问量则返回 false 执行限流操作，负责允许执行业务逻辑，并且在 ZSet 中添加一条有效的访问记录，具体实现代码如下。
我们借助 Jedis 包来操作 Redis，实现在 pom.xml 添加 Jedis 框架的引用，配置如下：
<!-- https://mvnrepository.com/artifact/redis.clients/jedis --> <dependency> <groupId>redis.clients</groupId> <artifactId>jedis</artifactId> <version>3.3.0</version> </dependency>
具体的 Java 实现代码如下：
import redis.clients.jedis.Jedis; public class RedisLimit { // Redis 操作客户端 static Jedis jedis = new Jedis("127.0.0.1", 6379); public static void main(String[] args) throws InterruptedException { for (int i = 0; i < 15; i++) { boolean res = isPeriodLimiting("java", 3, 10); if (res) { System.out.println("正常执行请求：" + i); } else { System.out.println("被限流：" + i); } } // 休眠 4s Thread.sleep(4000); // 超过最大执行时间之后，再从发起请求 boolean res = isPeriodLimiting("java", 3, 10); if (res) { System.out.println("休眠后，正常执行请求"); } else { System.out.println("休眠后，被限流"); } } /** * 限流方法（滑动时间算法） * @param key 限流标识 * @param period 限流时间范围（单位：秒） * @param maxCount 最大运行访问次数 * @return */ private static boolean isPeriodLimiting(String key, int period, int maxCount) { long nowTs = System.currentTimeMillis(); // 当前时间戳 // 删除非时间段内的请求数据（清除老访问数据，比如 period=60 时，标识清除 60s 以前的请求记录） jedis.zremrangeByScore(key, 0, nowTs - period * 1000); long currCount = jedis.zcard(key); // 当前请求次数 if (currCount >= maxCount) { // 超过最大请求次数，执行限流 return false; } // 未达到最大请求数，正常执行业务 jedis.zadd(key, nowTs, "" + nowTs); // 请求记录 +1 return true; } }
以上程序的执行结果为：
正常执行请求：0
正常执行请求：1
正常执行请求：2
正常执行请求：3
正常执行请求：4
正常执行请求：5
正常执行请求：6
正常执行请求：7
正常执行请求：8
正常执行请求：9
被限流：10
被限流：11
被限流：12
被限流：13
被限流：14
休眠后，正常执行请求
此实现方式存在的缺点有两个：
- 使用 ZSet 存储有每次的访问记录，如果数据量比较大时会占用大量的空间，比如 60s 允许 100W 访问时；
- 此代码的执行非原子操作，先判断后增加，中间空隙可穿插其他业务逻辑的执行，最终导致结果不准确。
2.漏桶算法
漏桶算法的灵感源于漏斗，如下图所示：
滑动时间算法有一个问题就是在一定范围内，比如 60s 内只能有 10 个请求，当第一秒时就到达了 10 个请求，那么剩下的 59s 只能把所有的请求都给拒绝掉，而漏桶算法可以解决这个问题。
漏桶算法类似于生活中的漏斗，无论上面的水流倒入漏斗有多大，也就是无论请求有多少，它都是以均匀的速度慢慢流出的。当上面的水流速度大于下面的流出速度时，漏斗会慢慢变满，当漏斗满了之后就会丢弃新来的请求;当上面的水流速度小于下面流出的速度的话，漏斗永远不会被装满，并且可以一直流出。
漏桶算法的实现步骤是，先声明一个队列用来保存请求，这个队列相当于漏斗，当队列容量满了之后就放弃新来的请求，然后重新声明一个线程定期从任务队列中获取一个或多个任务进行执行，这样就实现了漏桶算法。
上面我们演示 Nginx 的控制速率其实使用的就是漏桶算法，当然我们也可以借助 Redis 很方便的实现漏桶算法。
我们可以使用 Redis 4.0 版本中提供的 Redis-Cell 模块，该模块使用的是漏斗算法，并且提供了原子的限流指令，而且依靠 Redis 这个天生的分布式程序就可以实现比较完美的限流了。
Redis-Cell 实现限流的方法也很简单，只需要使用一条指令 cl.throttle 即可，使用示例如下：
> cl.throttle mylimit 15 30 60 1）（integer）0 # 0 表示获取成功，1 表示拒绝 2）（integer）15 # 漏斗容量 3）（integer）14 # 漏斗剩余容量 4）（integer）-1 # 被拒绝之后，多长时间之后再试（单位：秒）-1 表示无需重试 5）（integer）2 # 多久之后漏斗完全空出来
其中 15 为漏斗的容量，30 / 60s 为漏斗的速率。
3.令牌算法
在令牌桶算法中有一个程序以某种恒定的速度生成令牌，并存入令牌桶中，而每个请求需要先获取令牌才能执行，如果没有获取到令牌的请求可以选择等待或者放弃执行，如下图所示：
我们可以使用 Google 开源的 guava 包，很方便的实现令牌桶算法，首先在 pom.xml 添加 guava 引用，配置如下：
<!-- https://mvnrepository.com/artifact/com.google.guava/guava --> <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.2-jre</version> </dependency>
具体实现代码如下：
import com.google.common.util.concurrent.RateLimiter; import java.time.Instant; /** * Guava 实现限流 */ public class RateLimiterExample { public static void main(String[] args) { // 每秒产生 10 个令牌（每 100 ms 产生一个） RateLimiter rt = RateLimiter.create(10); for (int i = 0; i < 11; i++) { new Thread(() -> { // 获取 1 个令牌 rt.acquire(); System.out.println("正常执行方法，ts:" + Instant.now()); }).start(); } } }
以上程序的执行结果为：
正常执行方法，ts:2020-05-15T14:46:37.175Z 正常执行方法，ts:2020-05-15T14:46:37.237Z 正常执行方法，ts:2020-05-15T14:46:37.339Z 正常执行方法，ts:2020-05-15T14:46:37.442Z 正常执行方法，ts:2020-05-15T14:46:37.542Z 正常执行方法，ts:2020-05-15T14:46:37.640Z 正常执行方法，ts:2020-05-15T14:46:37.741Z 正常执行方法，ts:2020-05-15T14:46:37.840Z 正常执行方法，ts:2020-05-15T14:46:37.942Z 正常执行方法，ts:2020-05-15T14:46:38.042Z 正常执行方法，ts:2020-05-15T14:46:38.142Z
从以上结果可以看出令牌确实是每 100ms 产生一个，而 acquire() 方法为阻塞等待获取令牌，它可以传递一个 int 类型的参数，用于指定获取令牌的个数。它的替代方法还有 tryAcquire()，此方法在没有可用令牌时就会返回 false 这样就不会阻塞等待了。当然 tryAcquire() 方法也可以设置超时时间，未超过最大等待时间会阻塞等待获取令牌，如果超过了最大等待时间，还没有可用的令牌就会返回 false。
注意：使用 guava 实现的令牌算法属于程序级别的单机限流方案，而上面使用 Redis-Cell 的是分布式的限流方案。
总结
本文提供了 6 种具体的实现限流的手段，他们分别是：Tomcat 使用 maxThreads 来实现限流；Nginx 提供了两种限流方式，一是通过 limit_req_zone 和 burst 来实现速率限流，二是通过 limit_conn_zone 和 limit_conn 两个指令控制并发连接的总数。最后我们讲了时间窗口算法借助 Redis 的有序集合可以实现，还有漏桶算法可以使用 Redis-Cell 来实现，以及令牌算法可以解决 Google 的 guava 包来实现。
需要注意的是借助 Redis 实现的限流方案可用于分布式系统，而 guava 实现的限流只能应用于单机环境。如果你嫌弃服务器端限流麻烦，甚至可以在不改代码的情况下直接使用容器限流（Nginx 或 Tomcat），但前提是能满足你的业务需求。
好了，文章到这里就结束了，期待我们下期再会~
