常用限流方案的设计与实现

为了保证业务在高峰期的可用性，主流系统都会配备服务降级的工具，而限流就是目前系统最常采用的方案之一。限流即流量限制，目的是在遇到流量高峰或者流量突增（流量尖刺）时，把流量速率控制在合理的范围之内，不至于被高流量击垮。

常见的限流方式

服务降级中的限流并没有我们想象的那么简单。第一，限流方案必须时可选的，没有任何方案可以适用所有场景。第二，限流策略必须时可配置的。

集中常见的限流方式：

1. 通过限制单位时间段内的调用量来限流。
2. 通过限制系统的并发调用程度来限流。
3. 通过漏桶（Leaky Bucket）算法来限流。
4. 通过令牌桶（Token Bucket）算法来限流。

限制单位时间段内的调用量

从字面上很容易理解，我们需要做的就是通过一个计数器来统计单位时间内某个服务的访问量。如果超过了阙值，则该单位时间段那不允许继续访问，或者把请求放入队列中等下一个时间段继续访问。

在 Java 系统中该如何做那？

单位时间不能太长，太长将导致限流效果不够“敏感”。比如我们的监控系统统计的事服务每分钟的调用量，所以很自然我们可以选择 1 分钟作为时间片段。

计数我们自然而然想到的事 AtomicLong，每次服务调用，我们通过 AtomicLong#incrementAndGet() 方法给计数器加 1 并返回最新值。

对于限制单位时间段内调用量的这种限流方式，实现简单，适用于大多数场景，如果阀值可以通过服务端动态配置，甚至可以当作业务开关来使用

但是也有一定的局限性，如果设定的阀值在单位时间段内的前几秒就被流量突刺消耗完了，将导致该时间段剩余的时间内该服务“拒绝服务”，这种现象被称为“突刺消耗”，并不常见。

限制系统的并发调用程度

我们通过并发限制来限流，我们通过严格的限制某服务的并发访问速度，其实也就限制了该服务单位时间段内的访问量。

相比于第一种方案，它有着更严格的限制边界，因为如果采用第一种限流方案，如果大量的服务在极短的时间产生，仍然会压垮系统，甚至雪崩。这是因为很多监控系统都是通过业务日志来做到异步调用的统计。但是如果想要统计并发量，则需要嵌入到代码调用层面中去，比如 AOP，如果这样的话，监控系统最好能和 RPC 框架和服务治理框架配合使用。

使用 Java 来控制并发程度也非常简单，我们第一个想到的可能就是信号量 Semaphore，在服务调用的入口调用非阻塞方法 Semaphore#tryAcquire() 来尝试获取一个信号量。如果失败，则直接返回或将调用放入到某个队列中。

并发限流一般用于服务资源有严格的限制的场景，比如连接数，线程数等。但是也未尝不能用于通用的服务场景。

从表面上看并发限流似乎很有作用，但也不可否认，它仍然可以造成流量尖刺，即每台服务器上该服务的并发量从 0 上升到阀值是没有任何阻力的，因为并发量考虑的只是服务能力边界的问题。

漏桶（Leaky Bucket）算法

漏桶算法事流量整形或者限流的常用算法之一。它有点像我们生活中用到的漏斗，液体倒进去以后在小口中以固定速率流出。漏桶算法就是这样，不管流量有多大，漏桶都保证了流量的常速率输出。既然是一个桶，那么肯定有容量，由于调用的消费速率已经固定，那么当桶的容量堆满了，则只能丢弃了。

漏桶算法其实是悲观的，因为它严格地限制了系统的吞吐量，漏桶算法可以用于大多数场景，但是由于它对于服务吞吐量有着严格限制，可能导致某些服务称为瓶颈。

Java 中的实现，可以准备一个队列，当作桶的容量，另外通过一个计划线程池（ScheduledExecutorService）来定期从队列中获取并执行请求调用。可以一次拿多个请求，然后并发执行。

令牌桶（Token Bucket）算法

令牌桶算法可以说是漏桶算法的一种改进，漏桶算法能够强行限制请求调用的速率，而令牌桶算法能够在限制调用的平均速率的同时还允许某种程度的突发调用。

令牌桶算法中，桶中会有一定数量的令牌，每次请求调用需要去桶中拿取一个令牌，拿到令牌后才有资格执行，否则必须等待。

有的同学或许有些疑问，如果把令牌比喻成信号量，那么好像和并发限流没什么区别嘛。

其实不是，令牌桶算法的精髓在于拿令牌和放令牌的方式，这和单纯的并发限流有明显的区别，因为每次请求时需要获取的令牌数不是固定的，比如当桶中的令牌比较多时，每次调用只需要获取一个令牌，随着令牌数的逐渐减少，当令牌使用率（使用中的令牌数/令牌总数）达到某个比率时，可能一次需要获取两个令牌，获取令牌的个数可能还会升高。归还令牌有两种方法，第一种是直接放回，第二种是什么也不做，有另一个额外的令牌生成步骤将令牌允许放回桶中。

下面给出不同限流方式下服务并发能力图：

上图也并不能说明实际并发度越高就吞吐量越高，因为还必须把稳定性等因素考虑进去。

相比于其他三种降级方式来说，令牌桶算法限流无疑是最为灵活的，因为它有着众多可配置的参数来直接影响限流的效果。Google 的 Guava 保重 RateLimiter 提供了令牌桶算法的实现。

我们先来看看如何创建一个 RateLimiter 实例：

RateLimiter create(double permitsPerSecond);  // 创建一个每秒包含permitsPerSecond个令牌的令牌桶，可以理解为QPS最多为permitsPerSecond

RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)// 创建一个每秒包含permitsPerSecond个令牌的令牌桶，可以理解为QPS最多为permitsPerSecond，并包含某个时间段的预热期

获取令牌桶的相关方法：

double acquire(); // 阻塞直到获取一个许可，返回被限制的睡眠等待时间，单位秒

double acquire(int permits); // 阻塞直到获取permits个许可，返回被限制的睡眠等待时间，单位秒

boolean tryAcquire();  // 尝试获取一个许可

boolean tryAcquire(int permits);  // 尝试获取permits个许可

boolean tryAcquire(long timeout, TimeUnit unit);  // 尝试获取一个许可，最多等待timeout时间

boolean tryAcquire(int permits, long timeout, TimeUnit unit);  // 尝试获取permits个许可，最多等待timeout时间

来看看一个简单的使用的例子：

SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyyMMdd HH:mm:ss.SSS");

RateLimiter rateLimiter = RateLimiter.create(2);

while(true) {

    rateLimiter.acquire();

    System.out.println(simpleDateFormat.format(new Date()));

}

运行结果（每秒能获取两个）：

20160716 17:04:03.352

20160716 17:04:03.851

20160716 17:04:04.350

20160716 17:04:04.849

20160716 17:04:05.350

20160716 17:04:05.850

20160716 17:04:06.350

20160716 17:04:06.850

其实，单从 RateLimiter 实例的创建方式来说，它更像是漏桶算法的实现（第三种方式），或者像一个单位时间段为 1 秒的调用量限流方式（第一种方式）。唯一看起来像令牌桶的算法是其获取信号量的时候，可以一次性尝试获取多个令牌。

从RateLimiter提供的操作来看，要实现一个实用的漏桶算法限流工具还有些路要走，比如

1. 它似乎不允许并发，虽然当我们每秒设置的令牌数足够多时或者服务处理时间超过1秒时，效果和并发类似。
2. 它没有提供一些通用的函数，来表式令牌使用率和获取令牌数之间的关系，需要外部实现。
3. 除了默认的自动添加令牌的方式，如果能提供手动释放令牌的方式，适用的的场景可能会更多。