如何进行限流器及Guava实现分析

这期内容当中小编将会给大家带来有关如何进行限流器及Guava实现分析，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。

限流

限流一词常用于计算机网络之中，定义如下：

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks.

通过控制数据的网络数据的发送或接收速率来防止可能出现的DOS攻击。而实际的软件服务过程中，限流也可用于API服务的保护。由于提供服务的计算机资源(包括CPU、内存、磁盘及网络带宽等)是有限的，则其提供的API服务的QPS也是有限的，限流工具就是通过限流算法对API访问进行限制，保证服务不会超过其能承受的负载压力。
本文主要涉及内容包括：

• 常用限流算法的简单介绍及比较

• Guava包中限流工具的实现分析

常用限流算法

援引wiki中关于限流的Algorithms一小节的说明，常用的限流算法主要包括：

1. Token bucket-令牌桶

2. Leaky bucket-漏桶

3. Fixed window counter-固定窗口计数

4. Sliding window log-滑动窗口日志

5. Sliding window counter-滑动窗口计数

以上几种方式其实可以简单的分为计数算法、漏桶算法和令牌桶算法。

计数限流算法

无论固定窗口还是滑动窗口核心均是对请求进行计数，区别仅仅在于对于计数时间区间的处理。

固定窗口计数

实现原理

固定窗口计数法思想比较简单，只需要确定两个参数：计数周期T及周期内最大访问（调用）数N。请求到达时使用以下流程进行操作：

固定窗口计数实现简单，并且只需要记录上一个周期起始时间与周期内访问总数，几乎不消耗额外的存储空间。

算法缺陷

固定窗口计数缺点也非常明显，在进行周期切换时，上一个周期的访问总数会立即置为0，这可能导致在进行周期切换时可能出现流量突发，如下图所示

滑动窗口计数在固定窗口计数记录数据基础上，需要增加一个长度为M的计数数组，用于记录在窗口滑动过程中各窗口访问数据。其流程示例如下：
简单说明为：人为设定漏桶流出速度及漏桶的总容量，在请求到达时判断当前漏桶容量是否已满，不满则可将请求存入桶中，否则抛弃请求。程序以设定的速率取出请求进行处理。
根据描述，需要确定参数为漏桶流出速度r及漏桶容量N，流程如下：

算法特点

令牌桶算法通过设置令牌放入速率可以控制请求通过的平均速度，且由于设置的容量为N的桶对令牌进行缓存，可以容忍一定流量的突发。

算法比较

以上提到四种算法，本小节主要对四种算法做简单比较算法进行对比。

Guava包中限流工具的实现分析

概览

上文简单介绍了常用的限流算法，在JAVA软件开发过程中可使用Guava包中的限流工具进行服务限流。Guava包中限流工具类图如下所示：
RateLimiter类即承担了builder的职责，也承担了Product的职责。

简单使用示例

在实际的代码编写过程中，对GUAVA包限流工具的使用参考以下代码：

final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is "2 permits per second"void submitTasks(List tasks, Executor executor) {  for (Runnable task : tasks) {    rateLimiter.acquire(); // may wait    executor.execute(task);  }}

以上代码摘自GUAVA包RateLimiter类的说明文档，首先使用create函数创建限流器，指定每秒生成2个令牌，在需要调用服务时使用acquire函数或取令牌。

RateLimiter实现分析

根据代码示例，抽象类RateLimiter由于承担了Product的职责，其已经确定了暴露给编程人员使用的API函数，其中主要实现的核心函数为create及acquire。因此由此为入口进行分析。

create函数分析

create函数具有两个个重载，根据不同的重载可能创建不同的RateLimiter具体实现子类。目前可返回的实现子类包括SmoothBursty及SmoothWarmingUp两种，具体不同下文详细分析。

acquire函数分析

acquire函数也具有两个重载类，但分析过程仅仅需要关系具有整形参数的函数重载即可，无参数的函数仅仅是acquire(1)的简便写法。
在acquire(int permits)函数中主要完成三件事：

1. 预分配授权数量，此函数返回需要等待的时间，可能为0；

2. 根据等待时间进行休眠；

3. 以秒为单位，返回获取授权消耗的时间。

完成以上工作的过程中，RateLimiter类确定了获取授权的过程骨架并且实现了一些通用的方法，这些通用方法中会调用为实现的抽象方法，开发人员根据不同的算法需求可实现特定子类对抽象方法进行覆盖。其调用流程如下图：
其中橙色块中reserveEarliestAvailable方法即为需要子类进行实现的，下文以该函数为核心，分析RateLimiter类的子类是如何实现该方法的。

子类实现分析

代码分析

根据上文的类图可见，RateLimiter类在GUAVA包中的直接子类仅有SmoothRateLimiter，故以reserveEarliestAvailable函数为入口研究其具体实现，而在代码实现的过程中需要使用SmoothRateLimiter类中的属性，现将类中各属性罗列出来：

reserveEarliestAvailable源码如下：

@Overridefinal long reserveEarliestAvailable(int requiredPermits, long nowMicros) {  resync(nowMicros);  long returnValue = nextFreeTicketMicros;  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);  double freshPermits = requiredPermits - storedPermitsToSpend;  long waitMicros =      storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)          + (long) (freshPermits * stableIntervalMicros);  this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);  this.storedPermits -= storedPermitsToSpend;  return returnValue;}

通过reserveEarliestAvailable的函数名称可以知道，该函数能够返回令牌可用的最早时间。函数需要的输入参数有需求的令牌数requiredPermits，当前时刻nowMicros。进入函数后，首先调用名为resync的函数：

void resync(long nowMicros) {  // if nextFreeTicket is in the past, resync to now  if (nowMicros > nextFreeTicketMicros) {    double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();    storedPermits = min(maxPermits, storedPermits + newPermits);    nextFreeTicketMicros = nowMicros;  }}

函数逻辑比较简单，首先获取nextFreeTicketMicros，该值在上表中已经说明，表示下一次有空闲令牌产生的时刻，如果当前时刻小于等于nextFreeTicketMicros，说明在当前时刻不可能有新的令牌产生，则直接返回。若当前时刻大于nextFreeTicketMicros，则完成以下工作：

1. 计算到当前时刻新产生的令牌数，其中涉及一个名为coolDownIntervalMicros 的函数，该函数返回创建一个新令牌需要的冷却时间（注：该函数在当前类中并未实现，具体实现下文说明）；

2. 更新storedPermits属性，取产生的令牌和最大可存储令牌之间的最小值；

3. 将nextFreeTicketMicros属性置为当前时刻。

可见，resync函数主要功能在于计算新产生的令牌数，并更新nextFreeTicketMicros属性，nextFreeTicketMicros属性取值是当前时刻和nextFreeTicketMicros属性的原始值中最大的一个。
完成resync函数的调用后，使用returnValue变量记录更新令牌后的最近可用时间（即上文更新后的nextFreeTicketMicros属性）。
使用storedPermitsToSpend变量记录需要消耗以存储的令牌数，其取值为请求令牌数和当前存储令牌数之间的最小值。
使用freshPermits变量记录需要刷新的令牌数，其实现是用需求的令牌数减去之前计算的storedPermitsToSpend变量，可见freshPermits变量取值为需求令牌数与已存储令牌数之间的差值，当需求令牌数小于已存储令牌数是则为0。
后续为该函数核心，计算需要等待的时间，计算等待时间主要分为两个部分：消耗已经存储的令牌需要的时间及生成新令牌的时间，其中storedPermitsToWaitTime函数用于计算消耗已经存储的令牌需要的时间，该函数也是抽象函数，后文具体分析子类实现。
完成等待时间的计算后，程序更新nextFreeTicketMicros属性，将最近可用时间与需要等待的时间相加。
最后在更新存储的令牌数，将需要消耗额令牌数减去。

实现逻辑特点

根据以上的代码分析可以发现，GUAVA对于令牌桶的实现跟理论有一点点小的区别。其当前一次的请求消耗的令牌数并不会影响本次请求的等待时间，而是会影响下一次请求的等待时间。
根据以上分析，当一次请求到达，最近可用时间返回当前时间和上一次请求计算的最近可用时间的最大值，而本次请求需要的令牌数会更新下一次的最近可用时间。在这样的设计下，如果每秒产生一个令牌，第一请求需求10个令牌，则当第一次请求调用acquire方法时能够立即返回，而下一次请求（无论需要多少令牌）均需要等待到第一个请求之后的10秒以后，第三次请求等待时间则取决于第二次需求了多少令牌。这也是函数名称中"reserve"的含义。

抽象函数分析

在以上文代码分析中出现了两个抽象函数coolDownIntervalMicros及storedPermitsToWaitTime，现分析这两个抽象函数。

coolDownIntervalMicros函数

coolDownIntervalMicros函数在代码中已经有说明：

Returns the number of microseconds during cool down that we have to wait to get a new permit.

主要含义为生成一个令牌需要消耗的时间，该函数主要应用于计算当前时间可产生的令牌数。根据上文的UML图SmoothRateLimiter类有两个子类SmoothBursty及SmoothWarmingUp。
SmoothBursty类中对于coolDownIntervalMicros函数的实现如下：

@Overridedouble coolDownIntervalMicros() {  return stableIntervalMicros;}

可见实现非常简单，仅仅只是返回stableIntervalMicros属性，即产生两个令牌需要的时间间隔。
SmoothWarmingUp类中对于coolDownIntervalMicros函数的实现如下：

@Overridedouble coolDownIntervalMicros() {  return warmupPeriodMicros / maxPermits;}

其中maxPermits属性上文已经出现过，表示当前令牌桶的最大容量。warmupPeriodMicros属性属于SmoothWarmingUp类的特有属性，表示令牌桶中令牌从0到maxPermits需要经过的时间，故warmupPeriodMicros / maxPermits表示在令牌数量达到maxPermits之前的令牌产生时间间隔。

storedPermitsToWaitTime函数

storedPermitsToWaitTime函数在代码中已经有说明：

Translates a specified portion of our currently stored permits which we want to spend/acquire,into a throttling time. Conceptually, this evaluates the integral of the underlying function weuse, for the range of [(storedPermits - permitsToTake), storedPermits]

主要表示消耗存储在令牌桶中的令牌需要的时间。
SmoothBursty类中对于storedPermitsToWaitTime函数的实现如下：

@Overridelong storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  return 0L;}

直接返回0，表示消耗令牌不需要时间。
SmoothBursty类中对于storedPermitsToWaitTime函数的实现如下：

@Overridelong storedPermitsToWaitTime(double storedPermits, double permitsToTake) {  double availablePermitsAboveThreshold = storedPermits - thresholdPermits;  long micros = 0;  // measuring the integral on the right part of the function (the climbing line)  if (availablePermitsAboveThreshold > 0.0) {    double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake);    // TODO(cpovirk): Figure out a good name for this variable.    double length =        permitsToTime(availablePermitsAboveThreshold)            + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake);    micros = (long) (permitsAboveThresholdToTake * length / 2.0);    permitsToTake -= permitsAboveThresholdToTake;  }  // measuring the integral on the left part of the function (the horizontal line)  micros += (long) (stableIntervalMicros * permitsToTake);  return micros;}

实现较为复杂，其核心思想在于计算消耗当前存储令牌时需要根据预热设置区别对待。其中涉及到新变量thresholdPermits，该变量为令牌阈值，当当前存储的令牌数大于该值时，消耗(storedPermits-thresholdPermits)范围的令牌需要有预热的过程（即消耗每个令牌的间隔时间慢慢减小），而消耗0~thresholdPermits个数的以存储令牌，每个令牌消耗时间为固定值，即stableIntervalMicros。
而thresholdPermits取值需要考虑预热时间及令牌产生速度两个属性，即thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros;。可见阈值为预热时间中能够产生的令牌数的一半，并且根据注释计算消耗阈值以上的令牌的时间可以转换为计算预热图的梯形面积（实际为积分），本处不详细展开。
使用此种设计可以保证在上次请求间隔时间较长时，令牌桶中存储了较多的令牌，当消耗这些令牌时，最开始的令牌消耗时间较长，后续时间慢慢缩短直到达到stableIntervalMicros的状态，产生预热的效果。

GUAVA限流器实现总结

以上分析GUAVA限流器实现，其使用了两个抽象类及两个具体子类完成了限流器实现，其中使用顶层抽象类承担了创建者角色，将所有子类进行了透明化，减少了程序员在使用工具过程中需要了解的类的数量。
在实现限流器的过程中，基于令牌桶的思想，并且增加了带有预热器的令牌桶限流器实现。被限流的线程使用其自带的SleepingStopwatch工具类，最终使用的是Thread.sleep(ms, ns);方法，而线程使用sleep休眠时其持有的锁并不会释放，在多线程编程时此处需要注意。
最后，GUAVA的限流器触发算法采用的是预定令牌的方式，即当前请求需要的令牌数不会对当前请求的等待时间造成影响，而是会影响下一次请求的等待时间。

上述就是小编为大家分享的如何进行限流器及Guava实现分析了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注行业资讯频道。