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

阅读量:

Outline

0. 背景

1. 常用限流方案

2. 令牌桶算法

3. 写在最前的例子

4. RateLimiter 的设计哲学

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. 快速使用

使用就比较简单了,举个几个小例子

public static void main(){
    RateLimiterlimiter = RateLimiter.create(5);
    for(int i = 0; i < 5;i++) {
        System.out.println(limiter.acquire());
    }
}

将得到类似如下的输出:

0.0

0.198239

0.196083

0.200609

0.199599

0.19961

注意,acquire 的返回表示的是等待时间。

public static void main(){
    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 秒桶中才能有令牌,且接下来的请求也整形为固定速率了

public static void main() {
    RateLimiterlimiter = RateLimiter.create(5, 1000, TimeUnit.MILLISECONDS);
    for (int i = 1; i < 5;i++) {
        System.out.println(limiter.acquire());
    }
    Thread.sleep(1000L);
    for(int i = 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 参数实现一开始就是平滑固定速率。


comments powered by Disqus