微服务高并发：流量效果控制，经典限流算法

流量效果控制，经典限流算法

限流算法用以控制通过的流量始终在限流阈值内，不同限流算法还可以控制流量达到某种效果，如控制超阈值流量快速失败的计数器算法、允许一定数量的请求等待通过的漏桶算法（Leaky Bucket），控制流量匀速通过且允许流量在一定程度上突增的令牌桶算法（TokenBucket）。

1. 计数器算法

Sentinel 中默认实现的 QPS 限流算法和 Threads 限流算法都属于计数器算法。QPS 限流算法是根据当前时间窗口（1 秒）的 pass（被放行的请求数）指标数据判断的，当通过一个请求时，当前时间窗口的 pass 指标计数加 1，如果 pass 总数已经大于或等于限流的 QPS 阈值，则直接拒绝当前请求。

Threads 限流算法是根据当前资源并行占用的线程数是否已经达到阈值判断的，若是，则直接拒绝当前请求，并且每通过一个请求，Threads 计数加 1，每完成一个请求，Threads 计数减 1。

2. 漏桶算法

漏桶就像在一个桶的底部开一个洞，不控制水被放入桶的速率，而通过底部漏洞的大小控制水流失的速率。当水被放入桶的速率小于或等于水通过底部漏洞流出的速率时，桶中没有剩余的水；而当水被放入桶的速率大于水通过底部漏洞流出的速率时，水就会逐渐在桶中积累，当桶装满水时，若再向桶中放入水，则放入的水就会溢出。

如果把水换成请求，当处理请求的速率大于或等于请求到来的速率时放行请求，否则当请求堆积到一定程度时，溢出的请求将被拒绝，如图所示：

3. 令牌桶算法

令牌桶不存放请求，而是存放为请求生成的令牌（Token），只有拿到令牌的请求才能通过。令牌桶算法的原理是以固定速率向桶中放入令牌，每当有请求过来时，都尝试从桶中获取令牌，如果能拿到令牌，请求就能通过。当桶中放满令牌时，多余的令牌就会被丢弃，而当桶中的令牌被用完时，请求拿不到令牌就无法通过，如图所示。

流量效果控制器

Sentinel 支持采取流量效果控制器控制超过限流阈值的流量。流量效果控制器支持的功能包括直接拒绝、冷启动、匀速排队。

FlowRule 的 controlBehavior 字段用于配置采用何种流量效果控制器。在调用 FlowRuleManager#loadRules 方法时，FlowRuleManager 会将限流规则配置的 controlBehavior 转换为对应的 TrafficShapingController 实例。

TrafficShapingController 接口的源码如下：

• node：根据 limitApp 与 strategy 选出来的 Node（可为 StatisticNode、DefaultNode 或 ClusterNode）。

• acquireCount：与并发编程方法 AQS#tryAcquire 的参数作用一样，acquireCount 的值一般为 1。当限流规则配置的限流阈值类型为 Threads 时，表示需要申请一个线程；当限流规则配置的限流阈值类型为 QPS 时，表示需要申请放行一个请求。

• prioritized：表示是否对请求进行优先级排序，SphU#entry 方法传递过来的值是 false。

controlBehavior 的取值与使用的 TrafficShapingController 的对应关系如表所示：

快速失败流量效果控制器

DefaultController 是默认使用的流量效果控制器，实现的效果是直接拒绝超过阈值的请求。当 QPS 超过限流规则配置的阈值时，新的请求就会被立即拒绝，并抛出 FlowException。

DefaultController 适用于明确知道系统处理能力的情况，如通过压测确定阈值。实际上我们很难测出这个阈值，因为一个服务可能被部署在硬件配置不同的服务器上，并且随时都可能调整部署计划。

DefaultController#canPass 方法的源码如下：

1. avgUsedTokens 方法：如果规则的限流阈值类型为 QPS，则此方法返回 Node 统计的当前时间窗口已经放行的请求总数；如果规则的限流阈值类型为 Threads，则此方法返回 Node 统计的当前并行占用的线程数。

2. 如果将当前请求放行会超过限流阈值且不满足条件③，则直接拒绝当前请求。

3. 如果 prioritized 为 true 且规则的限流阈值类型为 QPS，则表示具有优先级的请求可以占用未来时间窗口的统计指标。

4. 如果可以占用未来时间窗口的统计指标，则 tryOccupyNext 会返回当前请求需要等待的时间，单位为毫秒。

5. 如果休眠时间在限制可占用的最大时间范围内，则挂起当前请求，令当前线程休眠 waitInMs 毫秒，在休眠结束后抛出 PriorityWaitException，标志当前请求是等待了 waitInMs 毫秒之后通过的。在一般情况下，prioritized 参数的值为 false。如果 prioritized 在 ProcessorSlotChain 传递的过程中，排在 FlowSlot 之前的 ProcessorSlot 都没有修改过，则条件 3 不会被满足，因此这个 canPass 方法实现的流量效果就是直接拒绝。

匀速限流效果控制器

Sentinel 基于漏桶算法并结合虚拟队列等待机制实现了匀速限流效果。可将其理解为存在一个虚拟的队列，使请求在队列中排队通过，每 count / 1000 毫秒可通过一个请求。

使用虚拟队列的好处在于队列并非真实存在，当多核 CPU 并行处理请求时，可能会出现这些请求并排占用一个位置的现象。也因为如此，实际通过的 QPS 会超过限流阈值的 QPS，但不会超过很多。

若要使用匀速限流效果控制器 RateLimiterController 配置限流规则，则必须配置限流阈值类型为 GRADE_QPS，并且阈值要小于或等于 1000。

配置使用匀速限流效果控制器的代码如下：

RateLimiterController 类的字段和构造方法的源码如下：

• maxQueueingTimeMs：请求在虚拟队列中的最大等待时间，默认为 500 毫秒。

• count：限流阈值的 QPS。

• latestPassedTime：最近一个请求通过的时间，用于计算下一个请求的预期通过时间。

RateLimiterController 类实现的 canPass 方法的源码如下：

1. 计算队列中连续两个请求通过的时间间隔，如果限流阈值为 200QPS，则 costTime 等于 5，即每 5 毫秒只允许通过一个请求，而每 5 毫秒通过一个请求就是固定速率。

2. 计算当前请求的期望通过时间，等于时间间隔加上最近一个请求通过的时间。

3. 如果期望通过时间少于或等于当前时间，则当前请求可立即通过。

4. 如果期望通过时间超过当前时间，则需要休眠等待，需要等待的时间等于预期通过时间减去当前时间。

5. 如果等待时间超过队列允许的最大等待时间，则会拒绝当前请求。

6. 如果更新 latestPassedTime 为期望通过时间后，需要等待的时间还是少于最大等待时间，则说明排队有效，否则说明在一瞬间被某个请求占位了，需要拒绝当前请求，将当前请求移出队列并回退一个时间间隔。

7. 休眠等待 waitTime 毫秒。

latestPassedTime 永远存储当前请求的期望通过时间，后续的请求将排在该请求的后面，这就是虚拟队列的核心实现，按期望通过时间排队。在虚拟队列中，将 latestPassedTime 回退一个时间间隔，相当于将虚拟队列中的一个元素移除。

在理想情况下，每个请求在队列中排队通过，则每个请求都在固定的不重叠的时间通过。但在多核 CPU 的硬件条件下，可能出现多个请求并行通过的情况，即队列中的一个位置被多个请求同时占用，这就是为什么说实际通过的 QPS 会超过限流阈值的 QPS 的原因。但是没有关系，因并行导致超出的请求数不会超过阈值太多，所以影响不大。

匀速限流效果控制器适合用于请求突发性增长后剧降的场景。例如，对于一个有定时任务调用的接口，在定时任务执行时请求量会一下“飙高”，但随后又没有了请求，这时为了避免把系统压垮，我们不希望让所有请求一下都通过，但也不想直接拒绝超过阈值的请求。在这种场景下，使用匀速限流效果控制器可以将突增的请求排队到低峰时执行，起到“削峰填谷”的效果。

在分析完源码后，我们再来看 GitHub 上 Sentinel 的一个 Issue，如图所示：

为什么将 QPS 限流阈值配置为超过 1000 后限流就不生效了呢？

计算请求通过的时间间隔的代码如下：

假设 count=1200（限流 QPS 阈值），当 acquireCount=1 时，costTime=1000/1200，这个结果是小于 1 毫秒的，使用 Math.round 方法取整后值为 1；而当 QPS 阈值增大，costTime 的计算结果小于 0.5 时，使用 Math.round 方法取整后值就变为 0。

Sentinel 支持的最小等待时间的单位是毫秒，这可能是出于性能的考虑。当限流阈值超过 1000 后，如果 costTime 的计算结果不小于 0.5，那么时间间隔都是 1 毫秒，这相当于仍然限流 1000QPS；而当 costTime 的计算结果小于 0.5 时，使用 Math.round 方法取整后值为 0，即请求通过的时间间隔为 0 毫秒，也就是不排队等待，此时限流规则就完全无效了。

冷启动限流效果控制器

Warm Up，即冷启动。在应用升级重启时，应用自身需要一个预热的过程，因为只有预热之后才能到达稳定的性能状态。在接口预热阶段可以完成 JIT 即时编译，完成一些单例对象的创建、线程池的创建，完成各种连接池的初始化并执行首次需要加锁执行的代码块。

冷启动并非只在应用重启时需要，以下这些场景也需要冷启动：在一段时间内没有访问的情况下，连接池中存在大量过期连接需要待下次使用才移除并创建新的连接、一些热点数据缓存过期需要重新查找数据库并写入缓存，等等。

WarmUpController 支持设置冷启动周期，即冷启动的时长，默认为 10 秒。

WarmUpController 控制流量在冷启动周期内平缓地增长到限流阈值。

例如，某个接口限流为 200QPS，预热时间为 10 秒，那么在这 10 秒内，相当于每秒的限流阈值分别为 5QPS、15QPS、35QPS、70QPS、90QPS、115QPS、145QPS、170QPS、190QPS、200QPS。当然，这组数据只是假设的。

如果要使用 WarmUpController，则必须将限流规则阈值类型配置为 GRADE_QPS，代码如下：

Sentinel 的冷启动限流算法参考了 Guava 的 SmoothRateLimiter 的冷启动限流算法，但两者在实现上有很大的区别。Sentinel 主要用于控制 QPS，不会控制每个请求的时间间隔。正因为与 Guava 有所不同，官方文档目前没有很详细地介绍算法的具体实现，单看源码很难揣摩作者的思路，因此我们也不过深地去分析 WarmUpController 的实现源码，只是结合 Guava 的实现算法进行简单介绍。

Guava 的 SmoothRateLimiter 基于令牌桶（TokenBucket）算法实现冷启动。

我们先看图 5.6，从而了解 SmoothRateLimiter 中的一些基础知识。

如图 5.6 所示，横坐标（storedPermits）代表存令牌桶中的令牌数，纵坐标（throttling）代表获取一个令牌需要的时间，即请求通过的时间间隔。

• stableInterval：稳定产生令牌的时间间隔。

• coldInterval：冷启动产生令牌的最大时间间隔，等于稳定产生令牌的时间间隔乘以冷启动系数（即 stableInterval×coldFactor）。

• thresholdPermits：令牌桶中剩余令牌数的阈值，介于以正常速率生产令牌还是以冷启动速率生产令牌的阈值，是判断是否需要进入冷启动阶段的依据。

• maxPermits：允许令牌桶中存放的最大令牌数。

• slope：直线的斜率。

• warmupPeriod：预热时长，即冷启动周期，对应图 5.6 中梯形的面积。

假设设置冷启动周期（warmupPeriod）为 10s，限流为每秒钟生产 200 个令牌。

那么，用 1 秒（转换为微秒）除以每秒需要生产的令牌数，计算出生产令牌的时间间隔（stableInterval）为 5000μs，对应 SmoothRateLimiter 的源码如下：

在 SmoothRateLimiter 中，冷启动系数（coldFactor）的值固定为 3，所以冷启动阶段生产令牌的最长时间间隔（coldInterval）等于稳定速率下生产令牌的时间间隔（stableInterval）乘以 3，即 15000μs。

由于 coldFactor 等于 3，且 coldInterval 等于 stableInterval 乘以 coldFactor，故（coldIntervalstableInterval）是 stableInterval 的两倍，因此从 thresholdPermits 到 0 的时间是从 maxPermits 到 thresholdPermits 时间的一半，也就是 warmupPeriod 的一半。

因为梯形的面积等于 warmupPeriod，所以点 stableInterval 与点 thresholdPermits 所在的长方形面积是梯形面积的一半，即长方形面积为 warmupPeriod/2。

根据长方形的面积计算公式：面积=长×宽。

可得：stableInterval×thresholdPermits=0.5×warmupPeriod。

所以：thresholdPermits=0.5×warmupPeriod/stableInterval。

对应 SmoothRateLimiter 的源码如下：

因此，在本例中，thresholdPermits=0.5×10s/5000μs，计算结果为 1000（个）。

根据梯形面积公式：(上底+下底)×高/2。

可得：warmupPeriod=((stableInterval+coldInterval)×(maxPermits-thresholdPermits))/2。

所以：maxPermits=thresholdPermits+2×warmupPeriod/(stableInterval+coldInterval)。

对应 SmoothRateLimiter 的源码如下：

因此，在本例中，maxPermits=1000+2.0×10s/(20000μs)，计算结果为 2000（个）。

根据直线的斜率计算公式：斜率=(y2-y1)/(x2-x1)。

可得：slope=(coldInterval - stableInterval)/(maxPermits - thresholdPermits)。

因此，在本例中，slope=10000μs/1000 个，计算结果为 101s/个。

在正常情况下，令牌以稳定时间间隔 stableInterval 生产令牌，1 秒内能生产的令牌就刚好是限流的阈值。

假设当初始化令牌数为 maxPermits 时，系统直接进入冷启动阶段，此时生产令牌的时间间隔最长，等于 coldInterval。

如果此时以稳定的速率消费令牌桶中的令牌，由于消费速率大于生产速率，那么令牌桶中的令牌将会慢慢减少；当令牌桶中的令牌数慢慢下降到 thresholdPermits 时，冷启动周期结束，接下来将会以稳定的时间间隔 stableInterval 生产令牌。

当消费速率等于生产速率时，令牌数稳定在限流阈值；而当消费速率远远小于生产速率时，令牌桶中的令牌就会堆积，如果堆积的令牌数超过 thresholdPermits，又会是一轮新的冷启动。

在 SmoothRateLimiter 中，当每个请求获取令牌时，根据当前时间与上一次生产令牌时间（nextFreeTicketMicros）的时间间隔计算需要的新令牌数并将令牌加入令牌桶中。

在应用重启时或接口很久没有被访问时，nextFreeTicketMicros 的值要么为 0，要么远远小于当前时间，所以当前时间与 nextFreeTicketMicros 的时间间隔非常大，导致第一次生产的令牌数就达到了 maxPermits，直接进入冷启动阶段。

SmoothRateLimiter#resync 方法的源码如下：

在了解了 Guava 的 SmoothRateLimiter 实现后，我们再来看一下 Sentinel 的 WarmUpController，其源码如下。

• warningToken：等同于 thresholdPermits，在稳定的令牌生产速率下，令牌桶中存储的令牌数。

• maxToken：等同于 maxPermits，令牌桶的最大容量。

• storedTokens：令牌桶当前存储的令牌数。

• lastFilledTime：上一次生产令牌的时间。

• coldFactor：冷启动系数，默认为 3。

• slope：斜率，每秒放行请求数的增长速率。

• count：限流阈值的 QPS。

提示：warningToken、maxToken 和 slope 的计算可参考 Guava 的 SmoothRateLimiter。

WarmUpController#canPass 方法的源码如下：

如源码所示，在 canPass 方法中，首先获取当前令牌桶中的令牌数，若大于 warningToken，则控制 QPS。

根据当前令牌桶中存储的令牌数超出 warningToken 的令牌数，计算当前秒需要控制的 QPS 的阈值，下面这两行代码是关键。

我们可以通过图来理解这个公式。

结合上图可以看出以下两点：

• 图中的 x1 虚线的长度等于 aboveToken。

• 生产令牌的间隔时间等于 y1 的长度加上 stableInterval，其在 Sentinel 中的单位为秒。

根据斜率和 x1 可以计算出 y1 的值。

y1=slope×aboveToken。

而 1.0/count 计算出来的值是正常情况下每隔多少毫秒生产一个令牌，即 stableInterval。

所以，计算 warningQps 的公式等同于下面这行代码。

当前生产令牌的时间间隔：aboveToken×slope+stableInterval=stableInterval+y1。

当前秒所能生产的令牌数：1.0/(stableInterval+y1)。

所以，warningQps 等于当前秒所能生产的令牌数。

Sentinel 中的 resync 方法与 SmoothRateLimiter 的 resync 方法不同，在 Sentinel 中每秒只生产一个令牌。WarmUpController 的 syncToken 方法的源码如下：

Sentinel 并不是每通过一个请求就从令牌桶中移除一个令牌，而是在每秒更新令牌桶的令牌数时再扣除上一秒消耗的令牌数，上一秒消耗的令牌数等于上一秒通过的请求数，这就是官方文档所写的每秒会自动掉落令牌。这种做法避免了每次放行请求都需要使用 CAS 更新令牌桶中的令牌数，可以降低 Sentinel 对应用性能的影响，是一种非常巧妙的做法。

更新令牌桶中的令牌数=当前令牌桶中剩余的令牌数+当前秒需要生产的令牌数。

coolDownTokens 方法的源码如下：

其中，currentTime-lastFilledTime.get()为当前时间与上一次生产令牌时间的时间间隔，虽然单位为毫秒，但是已经去掉了毫秒的部分（毫秒部分全为 0）。

如果 currentTime-lastFilledTime.get()等于 1 秒，则根据 1 秒等于 1000 毫秒，新生产的令牌数等于限流阈值（count），新的令牌桶中的剩余令牌数（newValue）等于当前剩余令牌数（oldValue）加新生产的令牌数。

newValue=oldValue+1000×count/1000=oldValue+count。

如果是在很久没有访问的情况下，lastFilledTime 远远小于 currentTime，则第一次生产的令牌数将等于 maxToken。

小结

本篇主要分析了 Sentinel 限流功能的实现原理、can pass check 全过程，以及流量效果控制的实现原理，同时详细地介绍了 Sentinel 实现匀速限流与冷启动效果所采用的算法。