Outline
0. 背景... 1
1. 常用限流方案... 1
2. 令牌桶算法... 1
3. 写在最前的例子... 2
4. RateLimiter的设计哲学... 2
5. 快速使用... 5
0. 背景
一个业务需求对QPS有限制,因此,调研了相关限流方案,并对Guava的RateLimiter进行了深入的学习。本文着重介绍RateLimiter的设计哲学和使用,有兴趣看源码解析的同学可以关注另一篇文章《RateLimiter解析(二)》。
1. 常用限流方案
限流常见的算法有计数器法、漏桶算法与令牌桶算法。
计数器法
原理:在单位时间段内,对请求数进行计数,如果数量超过了单位时间的限制,则执行限流策略,当单位时间结束后,计数器清零,这个过程周而复始,就是计数器法。
缺点:不能均衡限流,在一个单位时间的末尾和下一个单位时间的开始,很可能会有两个访问的峰值,导致系统崩溃。
改进方式:可以通过减小单位时间来提高精度。
漏桶算法
原理:假设有一个水桶,水桶有一定的容量,所有请求不论速度都会注入到水桶中,然后水桶以一个恒定的速度向外将请求放出,当水桶满了的时候,新的请求被丢弃。
优点:可以平滑请求,削减峰值。
缺点:瓶颈会在漏出的速度,可能会拖慢整个系统,且不能有效地利用系统的资源。
令牌桶算法
原理:有一个令牌桶,单位时间内令牌会以恒定的数量(即令牌的加入速度)加入到令牌桶中,所有请求都需要获取令牌才可正常访问。当令牌桶中没有令牌可取的时候,则拒绝请求。
优点:相比漏桶算法,令牌桶算法允许一定的突发流量,但是又不会让突发流量超过我们给定的限制(单位时间窗口内的令牌数)。即限制了我们所说的QPS。
2. 令牌桶算法
令牌桶算法最初来源于计算机网络。在网络传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。
令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。因此能够应用于流量监管、通用流量整形、端口限速等点典型场景。同时,也能够扩展场景用来防止CC攻击,在Nginx等反向代理服务器上进行限流达到防御DDos攻击的目的。
Guava的RateLimiter实现了令牌桶算法,并通过SmoothBursty类和SmoothWarmingUp类进行不同的实现。下面将在源码阅读的基础上,结合例子对RateLimiter进行解析。因为SmoothBursty允许一定程度的突发,会有人担心如果允许这种突发,假设突然间来了很大的流量,那么系统很可能扛不住这种突发。因此需要一种平滑速率的限流工具,从而系统冷启动后慢慢的趋于平均固定速率(即刚开始速率小一些,然后慢慢趋于我们设置的固定速率)。Guava也提供了SmoothWarmingUp来实现这种需求,一开始的速率较慢,然后慢慢提高到期望值。
3. 写在最前的例子
一开始,让我们以一个例子来说明RateLimter实现的令牌桶算法,对它有个初步的认识,然后再来看它是如何设计实现的。
假设我们希望每秒最多发送5个请求,那么相当于每0.2秒发送一个。
-当第一个请求发送后,记为开始,即0秒。
- 0.1秒时,来了第二个请求,这时候还没到第0.2秒(可以认为当前令牌数为0),那么我们不需要考虑别的,等到0.2秒就能执行,但是,必须知道,这时候,下次允许执行的请求时间应该是第0.4秒了。
-假如第二个请求执行完后,到2.0秒还是没有新的请求到来,那么我们可以理解0.4秒到2秒的空闲时间就保存了5个令牌(最多不能超过5个,而且这个计算实际上是在新请求到来的时刻计算出来的)。
-当2.1秒时,有新请求进来了
如果它需要消耗3个请求,那么它可以立刻执行,然后存储令牌就变成了2个,而且如果此时再有新请求进来,可以立刻执行(smoothbursty),或者等待一个消耗3个存储令牌的积分时间执行(smoothwarmingup)。
如果它需要消耗9个请求,那么它也可以立刻执行,然后存储令牌清空,而且如果此时再有新请求进来,需要等待4个令牌的时间0.8秒(smoothbursty),或者等待一个消耗5个存储令牌的积分时间执行加上等待4个令牌的时间(smoothwarmingup)。
需要注意的是,桶里的令牌只有在空闲时才会增加,如果正常每0.2秒来一个请求,那么桶里的令牌一直为0。
空闲时的令牌最大可存储的数量5(smoothbursty),或者根据warmupPeriod调整(smoothwarmingup)。
4. RateLimiter的设计哲学
RateLimiter是怎么设计的,为什么这样设计?
RateLimiter的主要特性是它的“稳定速率”,表示正常情况下发起请求的速率(QPS)。例如,对于一个请求而言,根据需要计算合适的间隔时间,然后让这个请求等待相应的时间以达到限流的目的。最简单的维持QPS速率的方法是保留上次请求的时间戳,并且保证下个请求是在(1/QPS)秒之后发起。比如说,当QPS=5时,我们需要确保不会在上个请求的200ms内处理新的请求,这样就能维持想要的速率。如果一个新的请求到来,而上一个请求仅在100ms前,我们就需要再等待100ms。按照这样的速率,处理15个请求就需要3秒钟。
对于这样一个RateLimiter,我们发现它对请求的间隔处理非常粗糙:它只记得最后一个请求的时间。如果这个RateLimiter有很长一段时间没有使用了,这时突然来了一个请求,那么它马上就会被执行。这个RateLimiter就完全忽略了之前的空闲状态。这个结果会导致新请求的“不饱和”或者“溢出”。一方面,过去的“不饱和”可能意味着过剩的可用资源,然后,这个RateLimiter需要一定的时间来充分利用这些资源。另一方面,过去的不饱和可能意味着,负责处理请求的服务器可能没有做好准备来处理之后的请求。比如,它的缓存可能已经过期。
为了解决这个问题,就引入了一个额外的变量“令牌”,对“过去的空闲”状态进行建模。当没有空闲时,这个变量为0,当有了非常长的空闲情况时,它能够增长到最大允许存储令牌数。所以,一个请求需要令牌时,派发的令牌来源于两方面:存储的令牌(如果有的话),和新产生的令牌。
这个令牌到底是如何生产的呢?
对于一个RateLimiter来说,它每秒产生一个令牌,随着RateLimiter闲置,存储令牌每秒会增加1个。也就是说,Ratelimiter闲着10秒,存储令牌就达到10个了(假设最大允许令牌数≥10)。在这种情况下,一个请求acquire(3)到达。我们使用存储令牌来为这个请求服务,然后存储令牌降低到7个。紧接着,假设一个acquire(10)的请求到来,我们使用剩下的所有7个存储令牌,然后其余的3个令牌,我们要通过Ratelimiter来产生新的令牌以供消费。
我们知道,如果Ratelimiter产生令牌的速率是每秒一个的话,那就需要三秒钟。那么,已经存在的7个存储令牌要怎么消耗呢?有两种情况。如果我们要解决“不饱和”问题,那么我们就希望存储令牌被利用得比新产生令牌要快,因为不饱和程度意味着可被利用的空闲资源;如果我们解决“溢出”问题,那么存储令牌就要被利用得比新产生令牌要慢。因此,针对不同情况,我们需要一个函数来表示存储令牌与空闲时间的关系。
这个角色由storedPermitsToWaitTime(doublestoredPermits, double permitsToTake)来扮演。它的基础模型是一个连续函数,映射了存储令牌(从0到最大允许存储令牌)在 1/Rate 上的积分。怎么理解呢?
显然,存储令牌数permits基本上能够度量出空闲时间长度time。
速率
那么
所以1/rate 和令牌数量permits相乘就表示了空闲时间time。
当然,1/rate是一个特定的值,更一般的看,可以写作一个函数f(x),空闲时间就是这个函数在[0,permits]上的定积分。
那么,空闲时间
例如,在这个函数上做积分(就是 storedPermitsToWaitTime ()的计算方式),对于给定数量的请求数,等价于后续请求的最小间隔时间。当然,这个积分函数在SmoothBursty和SmoothWarmingUp是不同的实现,SmoothBursty直接返回无需等待,也就是f(x)=0。SmoothWarmingUp的积分函数f(x)就是以一定的变化来计算出相应的等待时间。
这里有个例子。如果storedPermits=10,然后我们需要3个permits,我们从存储令牌中拿走3个,还剩7个。那么对于这消耗3个令牌的时间,就需要调用storedPermitsToWaitTime(storedPermits =10.0, permitsToTake = 3.0)进行计算,就是对7到10进行积分计算。
使用积分保证了一个单独的acquire(3)等价于三个acquire(1),或者一个acquire(2)和一个acquire(1),不管使用怎样的积分函数。
需要注意的是,对于这个积分函数,如果我们选择一个水平线,高度正好等于 1/QPS,也就是f(x) = 1/rate,那么这个函数就没啥作用了,因为它表示存储令牌和新产生令牌的速率是一致的。
如果我们选择一个积分函数低于这个水平线,也就是f(x) < 1/rate,它表示在[0,permits]上的定积分变小了,减少了积分面积,也就是相同的令牌数映射的空闲时间变小了。因此,Ratelimiter在一段空闲后变得更加快速了。
反之,如果我们选择一个被积函数高于这个水平线,那就意味着面积(时间)增大了,因此存储令牌就比新产生令牌要更加耗时,也就是Ratelimiter在一段空闲后变慢了。
如下图所示
最后一点是,如果RateLimiter 采用QPS=1的限定速度,那么开销较大的acquire(100)请求到达时,它是没必要等到100s 才开始实际任务。我们可以先开始任务执行,并把未来的请求推后100s,这样我们就可以同时工作,同时生产需要的permits,而不是空等待permits生产够才开始工作。
这里有一个重要的结论:RateLimiter不需要记住上个请求的时间,它只需要记住“希望下个请求到来的时间”即可。这样使得我们能够马上识别出,一个确切的超时时间(跟tryAcquire(timeout)相关)是否满足下一个计划时间点。如果当前时间大于“期望的下个请求到来的时间”,那么这两个时间的差值就是Ratelimiter的未使用时间t,通过t*QPS计算出storedPermits。
这个方法就是 SmoothRateLimiter 中的reserveEarliestAvailable方法。
5. 快速使用
使用就比较简单了,举个几个小例子
``` java
publicstaticvoidmain(){
RateLimiterlimiter = RateLimiter.create(5);
for(inti = 0; i < 5;i++) {
System.out.println(limiter.acquire());
}
}
```
将得到类似如下的输出:
0.0
0.198239
0.196083
0.200609
0.199599
0.19961
注意,acquire的返回表示的是等待时间。
``` java
publicstaticvoidmain(){
RateLimiterlimiter = RateLimiter.create(5);
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
}
```
将得到类似如下的输出:
0.0
0.98745
0.183553
0.199909
limiter.acquire(5)表示桶的容量为5且每秒新增5个令牌,令牌桶算法允许一定程度的突发,所以可以一次性消费5个令牌,但接下来的limiter.acquire(1)将等待差不多1秒桶中才能有令牌,且接下来的请求也整形为固定速率了
``` java
publicstaticvoidmain(){
RateLimiterlimiter = RateLimiter.create(5, 1000, TimeUnit.MILLISECONDS);
for(inti = 1; i < 5;i++) {
System.out.println(limiter.acquire());
}
Thread.sleep(1000L);
for(inti = 1; i < 5;i++) {
System.out.println(limiter.acquire());
}
}
```
将得到类似如下的输出:
0.0
0.51767
0.357814
0.219992
0.199984
0.0
0.360826
0.220166
0.199723
0.199555
速率是梯形上升速率的,也就是说冷启动时会以一个比较大的速率慢慢到平均速率;然后趋于平均速率(梯形下降到平均速率)。可以通过调节warmupPeriod参数实现一开始就是平滑固定速率。