1、为什么要限流

单个机器或者集群能够承受的QPS是有限的。如果超过机器能够承受的QPS，那么，机器的内存、网络连接等资源就会不够用，有两方面的影响：

1）对于接口请求方而言，服务的响应很慢，超时很多，接近于服务不可用
2）对于服务提供方而言，机器cpu、内存或者网络连接等资源占用量一般会很大，与注册中心的心跳丢失，相当于节点丢失，对外不提供服务了。

因此，限流对于服务稳定性建设来说，是必不可少的。在QPS较小的时候，限流的重要性无法体现出来；但QPS增大之后，比如，有爬虫并发请求某个接口导致QPS暴增，就会体现出限流的重要性。限流，是指限制每秒请求的数量或者字节大小在某个阈值以内。

此外，限流也包括限制某个api的调用次数，即限频。比如，我们提供一个open API给用户使用，但是，得限制每个用户每天只能免费使用100次。那么，就需要使用限流（限频）。

并发中的Semaphore（信号量）限制了并发访问的数量，而不是访问的速率。

2、guava限流器使用

guava包是google提供的一个jar包，提供了各种集合操作、缓存、并发、参数校验、限流等各种方法，方便开发者书写简洁且不易出错的代码。下面，我们看看怎么使用guava的限流器。

步骤1：在pom.xml引入guava的Jar包

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>22.0</version>
</dependency>

步骤2：在代码中使用

public static void doSomeLimitedOperation() {
    RateLimiter rateLimiter = RateLimiter.create(2);
    while (true) {
        rateLimiter.acquire();
        // do something
        System.out.println("do something in " + LocalDateTime.now().getSecond());
    }
}

public static void main(String[] args) {
    doSomeLimitedOperation();
}

在doSomeLimitedOperation()中，使用RateLimiter rateLimiter = RateLimiter.create(2);来创建一个限流器对象，传入构造器的参数代表每秒发放2个许可证。

每次执行业务方法时，都使用rateLimiter.acquire();来申请一个许可证。若申请到，则会继续执行；否则，就会阻塞线程。

执行结果如下。每秒只会执行while死循环中的操作两次。

do something in 59
do something in 59
do something in 0
do something in 0
do something in 1
do something in 1
...

3、限流的几种实现算法

简单的计数器算法

对于限流，最直观的想法是，通过一个AtomicLong类型的计数值来进行累加计数。如果限定QPS为100，那么，从第一个请求的时间t1 (s)开始统计，在t1 ~ (t1+1)这一秒内，每进来一个请求，计数值加1。当计数值超过100后，则接下来拒绝t1 ~ (t1+1)这秒内的其他请求。在(t1+1) ~ (t1+2)这段时间内，计数值清空，重新进行计数。这就是最简单的计数器算法的思想。
这种算法实现简单，但存在一些缺点。

1）处理请求在时间上是不均匀的，存在”突刺现象“；

2）限流并不精确，容易被绕过限制。

比如，在t1 ~ t1 + 1这一秒内，某恶意用户在后200ms内发起了100次请求。又在t1 + 1 ~ t1 + 2这一秒内的前800ms内发起了100次请求，那么，相当于在某段时间的一秒内该恶意用户请求了200次。换句话说，如果使用该算法来限制某调用只能每秒调用服务方接口r次，那么，实际上，每秒调用次数可能为2r次。

改良的计数器算法

针对简单的计算器算法限流不精确的问题，可以使用滑动窗口来解决。实质上是
1）将每秒再划分为多个更加小的小区间，比如，每秒划分为5个区间，单独统计每个小区间处理的请求数量。
2）保证每个窗口内的请求数量都是100。窗口随着当前时间向前滑动

如下图所示。x(t)代表当前时间内窗口的位置。x(1.6)的时候，窗口内已经有了部分请求，因此，剩下可以处理请求的数量就是{100-已经处理的请求数量}。

漏桶算法

(图片来自https://mp.weixin.qq.com/s/zs6rkSmGeTzS5IgaqULFlA)

漏桶算法的关键是桶的设计。桶的上部进水，桶底滴水。当进水速度太大，超过桶的容量时，水就会溢出。桶的下部滴水的速度是恒定均匀的。在实际实现中，桶相当于一个队列，用于缓存请求。每个请求进来，都先缓存到队列中。如果超过队列长度，则拒绝或者返回默认兜底处理。额外一个线程，从队列中已恒定的速度取任务。

这种方式的实现比较简单，但是，由于执行任务的速度都是恒定的，因此，对于突发流量，服务方会无法及时进行响应，只能以恒定的速度慢慢处理。

令牌桶算法

令牌桶算法的示意图如下。桶中存放的是令牌（许可证），有一个令牌工厂以均匀的速度往桶里面放令牌。如果超过桶的大小，则丢弃令牌。每个请求进来的时候，都去令牌桶里面申请令牌（许可证），如果申请到令牌，则正常执行；否则，拒绝或者返回兜底信息。（图片来自https://mp.weixin.qq.com/s/zs6rkSmGeTzS5IgaqULFlA)

这种算法，可以解决计数器算法限流不精确的问题，同时可以解决漏桶算法无法及时响应的问题。google的guava限流器实现就是采用了这种算法，下面主要看看guava限流器提供的API。

4、guava RateLimiter

1）public static RateLimiter create(double permitsPerSecond)

创建一个每秒permitsPerSecond个的限流器。令牌工厂每秒往令牌桶中放入permitsPerSecond个令牌，桶的大小为permitsPerSecond。允许限流器许可证发放数暴增到permitsPerSecond。比如，假设令牌通当前拥有100个许可证，如果当前有100个请求，那么，就会立刻发放100个许可证，对于任务执行，存在暴增的情况。

2）public static RateLimiter create(double permitsPerSecond,long warmupPeriod,TimeUnit unit)

带有预热期的限流器。在预热期之内，每秒分配的许可证会逐渐增加，直到达到permitsPerSecond。带有预热期，可以避免流量突增，防止大流量压垮服务器和DB等。详情请参考 https://www.jianshu.com/p/280bf2dbd6f0

5、单机限流和集群限流

单机限流是指在单台机器上进行限流，在单个进程上进行限流。而实际的生产环境中，一般是通过集群对外提供服务，一个集群中有多台机器。因此，集群限流会比单机限流困难一些。

之前讲的那三种限流算法需要进行扩展一些，才可以适用于集群限流。

集群限流

集群限流

可以基于单机固定限流。通过指定集群的QPS，除以集群内机器数目，就是单机应该限流的数值。比如，指定集群QPS=100，有四个节点，那么，就限制每个节点的QPS=25。这样方式不太精确，因为分配个每个节点的流量不是等比例的。

另一种比较精确的方式，就是通过一个第三方的计数器来实现。比如，可以基于Redis的计数实现精确集群限流，每次限流需要和Redis进行通信。

集群限频

内部通过uuid关键字，实现各个uuid的访问频次。比如有用户a，b，c，d…. z，访问接口/index，目前的需求是限制每个用户的访问频次 2次/ 5s。可以通过集群限流并基于redis的计数实现，用户id+接口名作为key，过期时间为5s，保存在redis中。

6、超过阈值的流量处理

当请求的数量超过阈值时，超出的流量怎么处理，也是需要思考一下的。
常见的方式有：1）直接拒绝，返回错误信息；2）返回兜底信息；3）放入一个队列中继续等待，但恐怕会超时。

参考

http://ifeve.com/guava-ratelimiter/
https://segmentfault.com/a/1190000014745556
https://mp.weixin.qq.com/s/zs6rkSmGeTzS5IgaqULFlA
https://github.com/alibaba/Sentinel/wiki/%E9%9B%86%E7%BE%A4%E6%B5%81%E6%8E%A7
https://zhuanlan.zhihu.com/p/53641388
https://www.jianshu.com/p/280bf2dbd6f0

服务可用性之限流

限流