Guava中的RateLimiter

曾经终败给现在 2022-06-14 08:15 154阅读 0赞

昨天CodeReview的时候看到同时使用RateLimiter这个类用作QPS访问限制.学习一下这个类.

RateLimiter是Guava的concurrent包下的一个用于限制访问频率的类.

# 1.限流 #

每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.

通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.

如果要准确的控制QPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零.此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的QPS.

![simple_RateLimiter.png][]

# 2.限流算法 #

常用的更平滑的限流[算法][Link 1]有两种:漏桶算法和令牌桶算法.

很多传统的服务提供商如华为中兴都有类似的专利,参考: [http://www.google.com/patents/CN1536815A?cl=zh][http_www.google.com_patents_CN1536815A_cl_zh]

### 2.1 漏桶算法 ###

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

![rate-limit1.png][]

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)，伪代码如下：

因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.

### 2.2 令牌桶算法 ###

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

![token_bucket.JPG][]

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

# 3.RateLimiter简介 #

Google开源工具包Guava提供了限流工具类RateLimiter,该类基于令牌桶算法(Token Bucket)来完成限流,非常易于使用.RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率.它支持两种获取permits接口,一种是如果拿不到立刻返回false,一种会阻塞等待一段时间看能不能拿到.

RateLimiter和[Java][]中的信号量(java.util.concurrent.Semaphore)类似,Semaphore通常用于限制并发量.

源码注释中的一个例子,比如我们有很多任务需要执行,但是我们不希望每秒超过两个任务执行,那么我们就可以使用RateLimiter:

另外一个例子,假如我们会产生一个数据流,然后我们想以每秒5kb的速度发送出去.我们可以每获取一个令牌(permit)就发送一个byte的数据,这样我们就可以通过一个每秒5000个令牌的RateLimiter来实现:

另外,我们也可以使用非阻塞的形式达到降级运行的目的,即使用非阻塞的tryAcquire()方法:

# 4.RateLimiter主要接口 #

RateLimiter其实是一个abstract类,但是它提供了几个static方法用于创建RateLimiter:

提供了两个获取令牌的方法,不带参数表示获取一个令牌.如果没有令牌则一直等待,返回等待的时间(单位为秒),没有被限流则直接返回0.0:

尝试获取令牌,分为待超时时间和不带超时时间两种:

# 5.RateLimiter设计 #

考虑一下RateLimiter是如何设计的,并且为什么要这样设计.

RateLimiter的主要功能就是提供一个稳定的速率,实现方式就是通过限制请求流入的速度,比如计算请求等待合适的时间阈值.

实现QPS速率的最简单的方式就是记住上一次请求的最后授权时间,然后保证1/QPS秒内不允许请求进入.比如QPS=5,如果我们保证最后一个被授权请求之后的200ms的时间内没有请求被授权,那么我们就达到了预期的速率.如果一个请求现在过来但是最后一个被授权请求是在100ms之前,那么我们就要求当前这个请求等待100ms.按照这个思路,请求15个新令牌(许可证)就需要3秒.

有一点很重要:上面这个设计思路的RateLimiter记忆非常的浅,它的脑容量非常的小,只记得上一次被授权的请求的时间.如果RateLimiter的一个被授权请求q之前很长一段时间没有被使用会怎么样?这个RateLimiter会立马忘记过去这一段时间的利用不足,而只记得刚刚的请求q.

过去一段时间的利用不足意味着有过剩的资源是可以利用的.这种情况下,RateLimiter应该加把劲(speed up for a while)将这些过剩的资源利用起来.比如在向网络中发生数据的场景(限流),过去一段时间的利用不足可能意味着网卡缓冲区是空的,这种场景下,我们是可以加速发送来将这些过程的资源利用起来.

另一方面,过去一段时间的利用不足可能意味着处理请求的服务器对即将到来的请求是准备不足的(less ready for future requests),比如因为很长一段时间没有请求当前服务器的cache是陈旧的,进而导致即将到来的请求会触发一个昂贵的操作(比如重新刷新全量的缓存).

为了处理这种情况,RateLimiter中增加了一个维度的信息,就是过去一段时间的利用不足(past underutilization),代码中使用storedPermits变量表示.当没有利用不足这个变量为0,最大能达到maxStoredPermits(maxStoredPermits表示完全没有利用).因此,请求的令牌可能从两个地方来:

1.过去剩余的令牌(stored permits, 可能没有)
    2.现有的令牌(fresh permits,当前这段时间还没用完的令牌)

我们将通过一个例子来解释它是如何工作的:

对一个每秒产生一个令牌的RateLimiter,每有一个没有使用令牌的一秒,我们就将storedPermits加1,如果RateLimiter在10秒都没有使用,则storedPermits变成10.0.这个时候,一个请求到来并请求三个令牌(acquire(3)),我们将从storedPermits中的令牌为其服务,storedPermits变为7.0.这个请求之后立马又有一个请求到来并请求10个令牌,我们将从storedPermits剩余的7个令牌给这个请求,剩下还需要三个令牌,我们将从RateLimiter新产生的令牌中获取.我们已经知道,RateLimiter每秒新产生1个令牌,就是说上面这个请求还需要的3个请求就要求其等待3秒.

想象一个RateLimiter每秒产生一个令牌,现在完全没有使用(处于初始状态),限制一个昂贵的请求acquire(100)过来.如果我们选择让这个请求等待100秒再允许其执行,这显然很荒谬.我们为什么什么也不做而只是傻傻的等待100秒,一个更好的做法是允许这个请求立即执行(和acquire(1)没有区别),然后将随后到来的请求推迟到正确的时间点.这种策略,我们允许这个昂贵的任务立即执行,并将随后到来的请求推迟100秒.这种策略就是让任务的执行和等待同时进行.

一个重要的结论:RateLimiter不会记最后一个请求,而是即下一个请求允许执行的时间.这也可以很直白的告诉我们到达下一个调度时间点的时间间隔.然后定一个一段时间未使用的Ratelimiter也很简单:下一个调度时间点已经过去,这个时间点和现在时间的差就是Ratelimiter多久没有被使用,我们会将这一段时间翻译成storedPermits.所有,如果每秒钟产生一个令牌(rate==1),并且正好每秒来一个请求,那么storedPermits就不会增长.

# 6.RateLimiter主要源码 #

RateLimiter定义了两个create函数用于构建不同形式的RateLimiter:

1.public static RateLimiter create(double permitsPerSecond)
    用于创建SmoothBursty类型的RateLimiter
    2.public static RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)
    用于创建

源码下面以acquire为例子,分析一下RateLimiter如何实现限流:

下面方法来自RateLimiter的具体实现类SmoothRateLimiter:

另外，对于storedPermits的使用，RateLimiter存在两种策略，二者区别主要体现在使用storedPermits时候需要等待的时间。这个逻辑由storedPermitsToWaitTime函数实现：

存在两种策略就是为了应对我们上面讲到的，存在资源使用不足大致分为两种情况： (1).资源确实使用不足，这些剩余的资源我们私海可以使用的； (2).提供资源的服务过去还没准备好，比如服务刚启动等；

为此，RateLimiter实际上由两种实现策略，其实现分别见SmoothBursty和SmoothWarmingUp。二者主要的区别就是storedPermitsToWaitTime实现以及maxPermits数量的计算。

### 6.1 SmoothBursty ###

SmoothBursty使用storedPermits不需要额外等待时间。并且默认maxBurstSeconds未1，因此maxPermits为permitsPerSecond，即最多可以存储1秒的剩余令牌，比如QPS=5，则maxPermits=5.

下面这个RateLimiter的入口就是用来创建SmoothBursty类型的RateLimiter，

一个简单的使用示意图及解释，下面私海一个QPS=4的SmoothBursty:

(1).t=0,这时候storedPermits=0，请求1个令牌，等待时间=0；
    (2).t=1,这时候storedPermits=3，请求3个令牌，等待时间=0；
    (3).t=2,这时候storedPermits=4，请求10个令牌，等待时间=0，超前使用了2个令牌；
    (4).t=3,这时候storedPermits=0，请求1个令牌，等待时间=0.5；

代码的输出：

![BurstyRateLimiter.png][]

### 6.2 SmoothWarmingUp ###

<table style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; line-height:inherit; font-family:inherit; font-size:18.4px; vertical-align:baseline; border-collapse:collapse; border-spacing:0px"> 
 <tbody style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; line-height:inherit; font-family:inherit; font-size:18.4px; vertical-align:baseline"> 
 <tr style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; line-height:inherit; font-family:inherit; font-size:18.4px; vertical-align:baseline"> 
 <td style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; line-height:inherit; font-family:inherit; font-size:18.4px; vertical-align:middle"> <pre style="white-space: pre-wrap; word-wrap: break-word; margin-top: 0px; margin-bottom: 0px; border-top-style: none; border-bottom-style: none; border-left-style: none; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: 1.45em; font-family: Menlo, Monaco, &quot;Andale Mono&quot;, &quot;lucida console&quot;, &quot;Courier New&quot;, monospace; font-size: 13px; vertical-align: baseline; color: rgb(147, 161, 161); overflow: auto; text-align: right; padding: 0.8em !important; border-right: 1px solid rgb(0, 35, 44) !important; background-color: rgb(7, 54, 66) !important;"><span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">1
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">2
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">3
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">4
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">5
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">6
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">7
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">8
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">9
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">10
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">11
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">12
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">13
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">14
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">15
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">16
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">17
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">18
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">19
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">20
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">21
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">22
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">23
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">24
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">25
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">26
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">27
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">28
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">29
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">30
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">31
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">32
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">33
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">34
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">35
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">36
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">37
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">38
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">39
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">40
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">41
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">42
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">43
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">44
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">45
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">46
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">47
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">48
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">49
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">50
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">51
<span style="margin: 0px; padding: 0px; border: 0px; font-style: inherit; font-variant: inherit; font-weight: inherit; line-height: inherit; font-family: inherit; vertical-align: baseline; color: rgb(88, 110, 117) !important;">52
</pre></td> 
 <td style="margin:0px; padding:0px; border:0px; font-style:inherit; font-variant:inherit; line-height:inherit; font-family:inherit; font-size:18.4px; vertical-align:middle; width:843px"> <pre style="white-space:pre-wrap; word-wrap:break-word; margin-top:0px; margin-bottom:0px; padding:0px; border:none; font-style:inherit; font-variant:inherit; font-weight:inherit; line-height:1.45em; font-family:Menlo,Monaco,&quot;Andale Mono&quot;,&quot;lucida console&quot;,&quot;Courier New&quot;,monospace; font-size:13px; vertical-align:baseline; color:rgb(147,161,161); overflow:auto; background:none"><code style="margin:0px; padding:0.8em; border:0px; font-style:inherit; font-variant:inherit; font-weight:inherit; line-height:1.45em; vertical-align:baseline; overflow-y:hidden; display:block; overflow-x:auto; background:rgb(0,0,0); font-family:Menlo,Monaco,&quot;Andale Mono&quot;,&quot;lucida console&quot;,&quot;Courier New&quot;,monospace!important">static final class SmoothWarmingUp extends SmoothRateLimiter { private final long warmupPeriodMicros; /** * The slope of the line from the stable interval (when permits == 0), to the cold interval * (when permits == maxPermits) */ private double slope; private double halfPermits; SmoothWarmingUp(SleepingStopwatch stopwatch, long warmupPeriod, TimeUnit timeUnit) { super(stopwatch); this.warmupPeriodMicros = timeUnit.toMicros(warmupPeriod); } @Override void doSetRate(double permitsPerSecond, double stableIntervalMicros) { double oldMaxPermits = maxPermits; maxPermits = warmupPeriodMicros / stableIntervalMicros; halfPermits = maxPermits / 2.0; // Stable interval is x, cold is 3x, so on average it's 2x. Double the time -&gt; halve the rate double coldIntervalMicros = stableIntervalMicros * 3.0; slope = (coldIntervalMicros - stableIntervalMicros) / halfPermits; if (oldMaxPermits == Double.POSITIVE_INFINITY) { // if we don't special-case this, we would get storedPermits == NaN, below storedPermits = 0.0; } else { storedPermits = (oldMaxPermits == 0.0) ? maxPermits // initial state is cold : storedPermits * maxPermits / oldMaxPermits; } } @Override long storedPermitsToWaitTime(double storedPermits, double permitsToTake) { double availablePermitsAboveHalf = storedPermits - halfPermits; long micros = 0; // measuring the integral on the right part of the function (the climbing line) if (availablePermitsAboveHalf &gt; 0.0) { double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake); micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf) + permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0); permitsToTake -= permitsAboveHalfToTake; } // measuring the integral on the left part of the function (the horizontal line) micros += (stableIntervalMicros * permitsToTake); return micros; } private double permitsToTime(double permits) { return stableIntervalMicros + permits * slope; } }</code></pre> </td> 
 </tr> 
 </tbody> 
</table>

maxPermits等于热身(warmup)期间能产生的令牌数，比如QPS=4，warmup为2秒，则maxPermits=8.halfPermits为maxPermits的一半.

参考注释中的神图：

下面是我们QPS=4，warmup为2秒时候对应的图。 ![SmoothWarmingUp.png][]

maxPermits=8，halfPermits=4，和SmoothBursty相同的请求序列：

(1).t=0,这时候storedPermits=8，请求1个令牌，使用1个storedPermits消耗时间=1×(0.75+0.625)/2=0.6875秒；
    (2).t=1,这时候storedPermits=8，请求3个令牌，使用3个storedPermits消耗时间=3×(0.75+0.375)/2=1.6875秒(注意已经超过1秒了，意味着下次产生新Permit时间为2.6875)；
    (3).t=2,这时候storedPermits=5，请求10个令牌，使用5个storedPermits消耗时间=1×(0.375+0.25)/2+4*0.25=1.3125秒，再加上额外请求的5个新产生的Permit需要消耗=5*0.25=1.25秒，即总共需要耗时2.5625秒，则下一次产生新的Permit时间为2.6875+2.5625=5.25，注意当前请求私海2.6875才返回的，之前一直阻塞；
    (4).t=3,因为前一个请求阻塞到2.6875，实际这个请求3.6875才到达RateLimiter，请求1个令牌，storedPermits=0，下一次产生新Permit时间为5.25，因此总共需要等待5.25-3.6875=1.5625秒；

实际执行结果：

# 7.其他限流器 #

ASP[.NET][]版本的一个比较成熟限流器:WebApiThrottle 参考：[http://www.cnblogs.com/mushroom/archive/2015/07/21/4659200.html][http_www.cnblogs.com_mushroom_archive_2015_07_21_4659200.html]

参考: [https://github.com/springside/springside4/wiki/Rate-Limiter][https_github.com_springside_springside4_wiki_Rate-Limiter]

[https://en.wikipedia.org/wiki/Token\_bucket][https_en.wikipedia.org_wiki_Token_bucket]

[https://en.wikipedia.org/wiki/Leaky\_bucket][https_en.wikipedia.org_wiki_Leaky_bucket]

[simple_RateLimiter.png]: /images/20220614/5bca82425b464f9a9fd87e0ff0c6bd7c.png
[Link 1]: http://lib.csdn.net/base/datastructure
[http_www.google.com_patents_CN1536815A_cl_zh]: http://www.google.com/patents/CN1536815A?cl=zh
[rate-limit1.png]: /images/20220614/b72a68fade3c437c9c5d6ba760a012fc.png
[token_bucket.JPG]: /images/20220614/4daf721ecfb34d28baabab195b356f5f.png
[Java]: http://lib.csdn.net/base/java
[BurstyRateLimiter.png]: /images/20220614/227bf51c85cf48169ebcceccb07a6b3b.png
[SmoothWarmingUp.png]: /images/20220614/3abd7b07a142466ba8ab2daf244fef43.png
[.NET]: http://lib.csdn.net/base/dotnet
[http_www.cnblogs.com_mushroom_archive_2015_07_21_4659200.html]: http://www.cnblogs.com/mushroom/archive/2015/07/21/4659200.html
[https_github.com_springside_springside4_wiki_Rate-Limiter]: https://github.com/springside/springside4/wiki/Rate-Limiter
[https_en.wikipedia.org_wiki_Token_bucket]: https://en.wikipedia.org/wiki/Token_bucket
[https_en.wikipedia.org_wiki_Leaky_bucket]: https://en.wikipedia.org/wiki/Leaky_bucket