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 参数实现一开始就是平滑固定速率。

关注我们

酷家乐质量效能团队热衷于技术的成长和分享，几乎每个月都会举办技术分享活动（海星日），每半年举办一次技术专题竞赛分享（火星日），并将优秀内容写成技术文章。

我们尽可能保障分享到社区的内容，是我们用心编写、精心挑选的优质文章。如果您想更全面地阅读我们的文章，请您关注我们的微信公众号"酷家乐技术质量"。