🌓
搜索
 找回密码
 立即注册

RateLimiter解析(一) ———设计哲学与快速使用

酷家乐研发部 2019-2-12 16:31:27 678

Outline

0. 背景... 1

1. 常用限流方案... 1

2. 令牌桶算法... 1

3. 写在最前的例子... 2

4. RateLimiter的设计哲学... 2

5. 快速使用... 5

 

0. 背景

一个业务需求对QPS有限制,因此,调研了相关限流方案,并对GuavaRateLimiter进行了深入的学习。本文着重介绍RateLimiter的设计哲学和使用,有兴趣看源码解析的同学可以关注另一篇文章《RateLimiter解析()》。

1. 常用限流方案

限流常见的算法有计数器法、漏桶算法与令牌桶算法。

计数器法

原理:在单位时间段内,对请求数进行计数,如果数量超过了单位时间的限制,则执行限流策略,当单位时间结束后,计数器清零,这个过程周而复始,就是计数器法。 

缺点:不能均衡限流,在一个单位时间的末尾和下一个单位时间的开始,很可能会有两个访问的峰值,导致系统崩溃。 

改进方式:可以通过减小单位时间来提高精度。 

漏桶算法

原理:假设有一个水桶,水桶有一定的容量,所有请求不论速度都会注入到水桶中,然后水桶以一个恒定的速度向外将请求放出,当水桶满了的时候,新的请求被丢弃。   

优点:可以平滑请求,削减峰值。   

缺点:瓶颈会在漏出的速度,可能会拖慢整个系统,且不能有效地利用系统的资源。  

令牌桶算法

原理:有一个令牌桶,单位时间内令牌会以恒定的数量(即令牌的加入速度)加入到令牌桶中,所有请求都需要获取令牌才可正常访问。当令牌桶中没有令牌可取的时候,则拒绝请求。   

优点:相比漏桶算法,令牌桶算法允许一定的突发流量,但是又不会让突发流量超过我们给定的限制(单位时间窗口内的令牌数)。即限制了我们所说的QPS

 

2. 令牌桶算法

令牌桶算法最初来源于计算机网络。在网络传输数据时,为了防止网络拥塞,需限制流出网络的流量,使流量以比较均匀的速度向外发送。令牌桶算法就实现了这个功能,可控制发送到网络上数据的数目,并允许突发数据的发送。

 

令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。典型情况下,令牌桶算法用来控制发送到网络上的数据的数目,并允许突发数据的发送。因此能够应用于流量监管、通用流量整形、端口限速等点典型场景。同时,也能够扩展场景用来防止CC攻击,在Nginx等反向代理服务器上进行限流达到防御DDos攻击的目的。

 

GuavaRateLimiter实现了令牌桶算法,并通过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

空闲时的令牌最大可存储的数量5smoothbursty),或者根据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 ()的计算方式),对于给定数量的请求数,等价于后续请求的最小间隔时间。当然,这个积分函数在SmoothBurstySmoothWarmingUp是不同的实现,SmoothBursty直接返回无需等待,也就是f(x)=0SmoothWarmingUp的积分函数f(x)就是以一定的变化来计算出相应的等待时间。

这里有个例子。如果storedPermits=10,然后我们需要3permits,我们从存储令牌中拿走3个,还剩7个。那么对于这消耗3个令牌的时间,就需要调用storedPermitsToWaitTime(storedPermits =10.0, permitsToTake = 3.0)进行计算,就是对710进行积分计算。

使用积分保证了一个单独的acquire(3)等价于三个acquire(1),或者一个acquire(2)和一个acquire(1),不管使用怎样的积分函数。 

需要注意的是,对于这个积分函数,如果我们选择一个水平线,高度正好等于 1/QPS,也就是f(x) = 1/rate,那么这个函数就没啥作用了,因为它表示存储令牌和新产生令牌的速率是一致的。 

如果我们选择一个积分函数低于这个水平线,也就是f(x) < 1/rate,它表示在[0,permits]上的定积分变小了,减少了积分面积,也就是相同的令牌数映射的空闲时间变小了。因此,Ratelimiter在一段空闲后变得更加快速了。 

反之,如果我们选择一个被积函数高于这个水平线,那就意味着面积(时间)增大了,因此存储令牌就比新产生令牌要更加耗时,也就是Ratelimiter在一段空闲后变慢了。

如下图所示

最后一点是,如果RateLimiter 采用QPS1的限定速度,那么开销较大的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参数实现一开始就是平滑固定速率。








扫一扫

82827.jpg
随机推荐

最新主题

0 回复

高级模式
游客
返回顶部