限速神器RateLimiter源码解析

作者：京东科技 李玉亮
目录指引


限流场景

软件系统中一般有两种场景会用到限流：
•场景一、高并发的用户端场景。 尤其是C端系统，经常面对海量用户请求，如不做限流，遇到瞬间高并发的场景，则可能压垮系统。
•场景二、内部交易处理场景。 如某类交易任务处理时有速率要求，再如上下游调用时下游对上游有速率要求。
•无论哪种场景，都需要对请求处理的速率进行限制，或者单个请求处理的速率相对固定，或者批量请求的处理速率相对固定，见下图：

常用的限流算法有如下几种：
•算法一、信号量算法。 维护最大的并发请求数（如连接数），当并发请求数达到阈值时报错或等待，如线程池。
•算法二、漏桶算法。 模拟一个按固定速率漏出的桶，当流入的请求量大于桶的容量时溢出。
•算法三、令牌桶算法。 以固定速率向桶内发放令牌。请求处理时,先从桶里获取令牌，只服务有令牌的请求。
本次要介绍的RateLimiter使用的是令牌桶算法。RateLimiter是google的guava包中的一个轻巧限流组件，它主要有两个java类文件，RateLimiter.java和SmoothRateLimiter.java。两个类文件共有java代码301行、注释420行，注释比java代码还要多，写的非常详细，后面的介绍也有相关内容是翻译自其注释，有些描述英文原版更加准确清晰，有兴趣的也可以结合原版注释进行更详细的了解。
使用介绍

RateLimiter使用时只需引入guava jar便可，最新的版本是31.1-jre, 本文介绍的源码也是此版本。

1.             <dependency>
2.                 <groupId>com.google.guava</groupId>
3.                 <artifactId>guava</artifactId>
4.                 <version>31.1-jre</version>
5.             </dependency>

复制代码

源码中提供了两个直观的使用示例。
示例一、有一系列任务列表要提交执行，控制提交速率不超过每秒2个。

1. final RateLimiter rateLimiter = RateLimiter.create(2.0); // 创建一个每秒2个许可的RateLimiter对象.
2. void submitTasks(List<Runnable> tasks, Executor executor) {
3.    for (Runnable task : tasks) {
4.      rateLimiter.acquire(); // 此处可能有等待
5.      executor.execute(task);
6.    }
7. }

复制代码

示例二、以不超过5kb/s的速率产生数据流。

1. final RateLimiter rateLimiter = RateLimiter.create(5000.0); // 创建一个每秒5k个许可的RateLimiter对象
2. void submitPacket(byte[] packet) {
3.    rateLimiter.acquire(packet.length);
4.    networkService.send(packet);
5. }

复制代码

可以看出RateLimiter的使用非常简单，只需要构造限速器，调用获取许可方法便可，不需要释放许可.
算法介绍

在介绍之前，先说一下RateLimiter中的几个名词：
•许可( permit )： 代表一个令牌，获取到许可的请求才能放行。
•资源利用不足( underunilization ): 许可的发放一般是匀速的，但请求未必是匀速的，有时会有无请求（资源利用不足）的场景，令牌桶会有贮存机制。
•贮存许可( storedPermit ): 令牌桶支持对空闲资源进行许可贮存，许可请求时优先使用贮存许可。
•新鲜许可( freshPermit ): 当贮存许可为空时，采用透支方式，下发新鲜许可，同时设置下次许可生效时间为本次新鲜许可的结束时间。
•如下为一个许可发放示例，矩形代表整个令牌桶，许可产生速度为1个/秒，令牌桶里有一个贮存桶，容量为2。

以上示例中，在T1贮存容量为0，许可请求时直接返回1个新鲜许可，贮存容量随着时间推移，增长至最大值2，在T2时收到3个许可的请求，此时会先从贮存桶中取出2个，然后再产生1个新鲜许可，0.5s后在T3时刻又来了1个许可请求，由于最近的许可0.5s后才会下发，因此先sleep0.5s再下发。
RateLimiter的核心功能是限速，我们首先想到的限速方案是记住最后一次下发令牌许可(permit)时间，下次许可请求时，如果与最后一次下发许可时间的间隔小于1/QPS，则进行sleep至1/QPS，否则直接发放，但该方法不能感知到资源利用不足的场景。一方面，隔了很长一段再来请求许可，则可能系统此时相对空闲，可下发更多的许可以充分利用资源；另一方面，隔了很长一段时间再来请求许可，也可能意味着处理请求的资源变冷（如缓存失效），处理效率会下降。因此在RateLimiter中，增加了资源利用不足（underutilization）的管理，在代码中体现为贮存许可(storedPermits)，贮存许可值最开始为0，随着时间的增加，一直增长为最大贮存许可数。许可获取时，首先从贮存许可中获取，然后再根据下次新鲜许可获取时间来进行新鲜许可获取。这里要说的是RateLimiter是记住了下次令牌发放的时间，类似于透支的功能，当前许可获取时立刻返回，同时记录下次获取许可的时间。
代码结构和主体流程

代码结构

整体类图如下：

RateLimiter类
RateLimiter类是顶级类，也是唯一暴露给使用者的类，它提供了工厂方法来创建RateLimiter方法。 create(double permitsPerSecond) 方法创建的是突发限速器，create(double permitsPerSecond, Duration warmupPeriod)方法创建的是预热限速器。同时它提供了acquire方法用于获取令牌，提供了tryAcquire方法用于尝试获取令牌。该类的内部实现上，一方面有一个SleepingStopWatch 用于sleep操作，另一方面有一个mutexDoNotUseDirectly变量和mutex（）方法进行互斥加锁。
SmoothRateLimiter类
该类继承了RateLimiter类，是一个抽象类，含义为平滑限速器，限制速率是平滑的，maxPermits和storedPermits维护了最大存储许可数量和当前存储许可数量；stableIntervalMicros指规定的稳定许可发放间隔，nextFreeTicketMicros指下一个空闲许可时间。
SmoothBursty类
平滑突发限速器，该类继承了SmoothRateLimiter，它存储许可的发放频率同设置的stableIntervalMicros，有一个成员变量maxBurstSeconds，代表最多存储多长时间的令牌许可。
SmoothWarmingUp类
平滑预热限速器，继承了SmoothRateLimiter，与SmoothBursty平级，它的预热算法需要一定的理解成本。
主体流程

获取许可的主体流程如下：

主体流程主要是对贮存许可数量和新鲜许可数量进行计算和更新，得到当前许可请求的等待时间。SmoothBursty算法和SmoothWarmingUp算法共用这一套主体流程，差异主要是贮存许可的管理策略，两种算法的不同策略在两个子类中各自实现，SmoothBursty算法相对简单一些，下面先介绍该算法，然后再介绍SmoothWarmingUp算法。
SmoothBursty算法

限速器创建

采用的是工厂模式创建，源码如下：

1.   public static RateLimiter create(double permitsPerSecond) {
2.     // permitsPerSecond指每秒允许的许可数. 该方法调用了下面的方法
3.     return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
4.   }
5.   // 创建SmoothBursty(固定贮存1s的贮存许可), 然后设置速率
6.   static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
7.     RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
8.     rateLimiter.setRate(permitsPerSecond);
9.     return rateLimiter;
10.   }

复制代码

1、SmoothBursty的构造方法相对简单：

1.     SmoothBursty(SleepingStopwatch stopwatch, double maxBurstSeconds) {
2.       super(stopwatch);
3.       this.maxBurstSeconds = maxBurstSeconds;
4.     }

复制代码

2、rateLimiter.setRate的定义在父类RateLimiter中

1.   public final void setRate(double permitsPerSecond) {
2.     checkArgument(
3.         permitsPerSecond > 0.0 && !Double.isNaN(permitsPerSecond), "rate must be positive");
4.     synchronized (mutex()) {
5.       doSetRate(permitsPerSecond, stopwatch.readMicros());
6.     }
7.   }

复制代码

该方法使用synchronized(mutex())方法对互斥锁进行同步，以保证多线程调用的安全，然后调用子类的doSetRate方法。 第二个参数nowMicros传的值是调用了stopwatch的方法，将限速器创建的时间定义为0，然后计算了当前时间和创建时间的时间差，因此采用的是相对时间。
2.1 mutex方法的实现如下：

1.   // Can't be initialized in the constructor because mocks don't call the constructor.
2.   // 从上行注释可看出，这是因为mock才用了懒加载, 实际上即时加载代码更简洁
3.   @CheckForNull private volatile Object mutexDoNotUseDirectly;
4.   // 双重检查锁的懒加载模式
5.   private Object mutex() {
6.     Object mutex = mutexDoNotUseDirectly;
7.     if (mutex == null) {
8.       synchronized (this) {
9.         mutex = mutexDoNotUseDirectly;
10.         if (mutex == null) {
11.           mutexDoNotUseDirectly = mutex = new Object();
12.         }
13.       }
14.     }
15.     return mutex;
16.   }

复制代码

该方法使用了双重检查锁来对锁对象mutexDoNotUseDirectly进行懒加载，另外该方法通过mutex临时变量来解决了双重检查锁失效的问题。
2.2 doSetRate方法的主体实现在SmoothRateLimiter类中：

1.   final void doSetRate(double permitsPerSecond, long nowMicros) {
2.     // 同步贮存许可和时间
3.     resync(nowMicros);
4.     double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
5.     this.stableIntervalMicros = stableIntervalMicros;
6.     doSetRate(permitsPerSecond, stableIntervalMicros);
7.   }

复制代码

该方法在限速器创建时会调用，创建后调用限速器的setRate重置速率时也会调用。
2.2.1 resync方法用于基于当前时间刷新计算最新的storedPermis和nextFreeTicketMicros.

1.   /** Updates {@code storedPermits} and {@code nextFreeTicketMicros} based on the current time. */
2.   void resync(long nowMicros) {
3.     // if nextFreeTicket is in the past, resync to now
4.     if (nowMicros > nextFreeTicketMicros) {
5.       double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
6.       storedPermits = min(maxPermits, storedPermits + newPermits);
7.       nextFreeTicketMicros = nowMicros;
8.     }
9.   }

复制代码

该方法从现实场景上讲，代表的是随着时间的流逝，贮存许可不断增加，但从技术实现的角度，并不是真正的持续刷新，而是仅在需要时调用刷新。该方法如果当前时间小于等于下次许可时间，则贮存许可数量和下次许可时间不需要刷新；否则通过 (当前时间-下次许可时间)/贮存许可的发放间隔计算出的值域最大贮存数量取小，则为已贮存的许可数量，需要注意的是贮存许可数量是double类型的。
限速器使用

限速器常用的方法主要有accquire和tryAccquire。
先说一下accquire方法， 共有两个共有方法，一个是无参的，每次获取1个许可，再一个是整数参数的，每次调用获取多个许可。

1.   // 获取1个许可
2.   public double acquire() {
3.     return acquire(1);
4.   }
6.   // 获取多个许可
7.   public double acquire(int permits) {
8.     // 留出permits个许可，得到需要sleep的微秒数.
9.     long microsToWait = reserve(permits);
10.     // 该方法如果小于等于零则直接返回，否则sleep
11.     stopwatch.sleepMicrosUninterruptibly(microsToWait);
12.     // 返回休眠的秒数.
13.     return 1.0 * microsToWait / SECONDS.toMicros(1L);
14.   }

复制代码

从以上源码可看出，获取许可的逻辑很简单：留出permits个许可，根据返回值决定是否sleep等待。留出许可的方法实现如下：

1. // 预留出permits个许可
2.   final long reserve(int permits) {
3.     checkPermits(permits);
4.     synchronized (mutex()) {
5.       return reserveAndGetWaitLength(permits, stopwatch.readMicros());
6.     }
7.   }
8.    
9.   // 预留出permits个需求，得到需要等待的时间
10.   final long reserveAndGetWaitLength(int permits, long nowMicros) {
11.     long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
12.     return max(momentAvailable - nowMicros, 0);
13.   }
14.   abstract long reserveEarliestAvailable(int permits, long nowMicros);

复制代码

reserveEarliestAvailable为抽象方法，实现在SmoothRateLimiter类中，该方法是核心主链路方法，该方法先从贮存许可中获取，如果数量足够则直接返回，否则先将全部贮存许可取出，再计算还需要的等待时间，逻辑如下：

1.   final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
2.     // 刷新贮存许可和下个令牌时间
3.     resync(nowMicros);
4.     // 返回值为当前的下次空闲时间
5.     long returnValue = nextFreeTicketMicros;
6.     // 要消耗的贮存数量为需要的贮存数量
7.     double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
8.     // 新鲜许可数=需要的许可数-使用的贮存许可
9.     double freshPermits = requiredPermits - storedPermitsToSpend;
10.     // 等待时间=贮存许可等待时间(实现方决定)+新鲜许可等待时间(数量*固定速率)
11.     long waitMicros =
12.         storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
13.             + (long) (freshPermits * stableIntervalMicros);
14.     // 透支后的下次许可可用时间=当前时间(nextFreeTicketMicros)+等待时间(waitMicros)
15.     this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
16.     // 贮存许可数量减少
17.     this.storedPermits -= storedPermitsToSpend;
18.     return returnValue;
19.   }

复制代码

该方法有两点说明：1、returnValue为之前计算的下次空闲时间（前面有说RateLimiter采用预支的模式，本次直接返回，同时计算下次的最早空闲时间） 2、贮存许可的等待时间不同的实现方逻辑不同，SmoothBursty算法认为贮存许可直接可用，所以返回0, 后面的SmoothWarmingUp算法认为贮存许可需要消耗比正常速率更多的预热时间，有一定算法逻辑.
至此整个accquire方法的调用链路分析结束，下面再看tryAccquire方法就比较简单了，tryAccquire比accquire差异的逻辑在于tryAccquire方法会判断下次许可时间-当前时间是否大于超时时间，如果是则直接返回false，否则进行sleep并返回true. 方法源码如下：

1.   public boolean tryAcquire(Duration timeout) {
2.     return tryAcquire(1, toNanosSaturated(timeout), TimeUnit.NANOSECONDS);
3.   }
5.   public boolean tryAcquire(long timeout, TimeUnit unit) {
6.     return tryAcquire(1, timeout, unit);
7.   }
9.   public boolean tryAcquire(int permits) {
10.     return tryAcquire(permits, 0, MICROSECONDS);
11.   }
13.   public boolean tryAcquire() {
14.     return tryAcquire(1, 0, MICROSECONDS);
15.   }
17.   public boolean tryAcquire(int permits, Duration timeout) {
18.     return tryAcquire(permits, toNanosSaturated(timeout), TimeUnit.NANOSECONDS);
19.   }
21.   public boolean tryAcquire(int permits, long timeout, TimeUnit unit) {
22.     long timeoutMicros = max(unit.toMicros(timeout), 0);
23.     checkPermits(permits);
24.     long microsToWait;
25.     synchronized (mutex()) {
26.       long nowMicros = stopwatch.readMicros();
27.       // 判断超时微秒数是否可等到下个许可时间
28.       if (!canAcquire(nowMicros, timeoutMicros)) {
29.         return false;
30.       } else {
31.         microsToWait = reserveAndGetWaitLength(permits, nowMicros);
32.       }
33.     }
34.     // 休眠等待
35.     stopwatch.sleepMicrosUninterruptibly(microsToWait);
36.     return true;
37.   }
38.   
39.   // 下次许可时间-超时时间<=当前时间
40.   private boolean canAcquire(long nowMicros, long timeoutMicros) {
41.     return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;
42.   }

复制代码

思考总结

sleep说明和相对时间

RateLimiter内部使用类StopWatch进行了一个相对时间的度量，RateLimiter创建时，时间为0，然后向后累计，sleep时不受interrupt异常影响。
double浮点数

RateLimiter暴露的API的许可数量入参为整数类型，但内部计算时实际是浮点double类型，支持小数许可数量，一方面浮点存在丢失精度，另一方面也不便于理解；是否可以使用整数值得考虑。
只支持单机

RateLimiter的这几种算法只支持单机限流，如要支持集群限流，一种方式是先根据负载均衡的权重计算出单机的限速值，再进行单节点限速；另一种方式是参考该组件使用redis等中心化数量管理的中间件，但性能和稳定性会降低一些。
扩展性

RateLimiter提供了有限的扩展能力，自带的SmoothBursty和SmoothWarmingUp类不是公开类，不能直接创建或调整参数，如关闭贮存功能或调整预热系数等。这种场景需要继承SmoothRateLimiter进行重写，贮存许可的生产和消费算法是容易变化和重写的点，将整个源码拷贝出来进行二次修改也是一种方案。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！