Sentinel中的冷启动限流算法

 

冷启动算法基于令牌桶算法实现。

令牌桶算法的原理是：按一定的速率往令牌桶中放入令牌，当接收到请求时，从令牌桶申请令牌，只有拿到令牌的请求才能通过。当令牌桶放满时，多余的令牌就会被丢弃;当令牌桶为空时，请求拿不到令牌就拒绝请求。

例如，想要使用令牌桶算法限制接口的最大QPS为200，那么就要每5毫秒就要生产一个令牌放入令牌桶，且生产令牌放入的速度不变。

冷启动算法用于控制令牌桶的令牌生产速率，即控制每个令牌生产的时间间隔。

假设冷启动时长为10秒，初始状态为冷启动状态，限流阈值为200QPS，正常情况下生产令牌的速率应该为5毫秒/个，而在冷启动阶段，速率会从最小值上升至5毫秒/个，最小速率与冷启动系数有关，与冷启动周期时长有关。

Sentinel与Guava的实现不同，Sentinel可能是出于对性能的考虑，并不控制每个请求的通过时间间隔，只控制每秒钟能通过的请求数。

通过下面这张图来理解冷启动算法。

坐标轴：

• 横坐标storedPermits代表存储桶中的令牌数量;
• 纵坐标代表获取一个令牌需要的时间，即请求通过的时间间隔;

stableInterval：稳定产生令牌的时间间隔，假设限流阈值QPS为200，stableInterval的值为5毫秒。

coldInterval：冷启动产生令牌的最大时间隔间，等于稳定产生令牌的时间间隔乘以冷启动系数(stableInterval * coldFactor)，Sentinel中coldFactor默认为3。

warmupPeriod：预热时间，即冷启动周期，对应上图中的梯形面积，Sentinel中默认为10秒。

thresholdPermits：从冷启动到正常的令牌桶中令牌数量的阈值，当令牌桶中的令牌数量超过该值时，则进入冷启动阶段。

由于coldFactor默认为3，所以(coldInterval - stableInterval)是stableInterval的两倍，所以从thresholdPermits到0的时间是从maxPermits到thresholdPermits时间的一半，也就是冷启动周期的一半。因为梯形的面积等于warmupPeriod，所以长方形面积是梯形面积的一半，长方形的面积是warmupPeriod / 2。

根据长方形面积公式：长 * 宽 = 面积

可得：

thresholdPermits = 0.5 * warmupPeriod / stableInterval 

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

根据梯形的面积公式：(上低 + 下低)* 高 / 2

可得：

warmupPeriod = （stableInterval + coldInterval）* （maxPermits - thresholdPermits）/ 2 

推出：

maxPermits = thresholdPermits + 2 * warmupPeriod / （stableInterval + coldInterval） 

slope：直线的斜率，即生产令牌的速率。

根据斜率计算公式：(y2-y1) / (x2-x1)，可得：

slope = (coldInterval - stableInterval) / （maxPermits - thresholdPermits） 

Sentinel每秒生产一次令牌，将新生产的令牌放入令牌桶，并记录本次生产令牌的时间，当下次生产时，根据当前时间与上一次生产令牌的时间间隔计算、以及每个令牌的生产间隔时间计算出本次需要生产的令牌数。

服务第一次启动时，或者接口很久没有被访问，都会导致当前时间与上次生产令牌的时间相差甚远，所以第一次生产令牌将会生产maxPermits个令牌，直接将令牌桶装满。由于令牌桶已满，接下来10s就是冷启动阶段。

由于冷启动阶段生产令牌的间隔时间比较正常消费速度慢，因此随着时间的推移，桶中的剩余令牌数就会趋近于thresholdPermits，生产令牌的时间间隔也会从coldInterval降低到stableInterval。当桶中剩余令牌数小于thresholdPermits时，冷启动结束，系统进入稳定状态，生产令牌的时间间隔为stableInterval，每秒生产的令牌数就等于QPS。

Sentinel并不会在请求通过时减少令牌桶中的令牌数量，而是在下一秒生产新的令牌时，再减去桶中与上一秒通过的请求数相等数量的令牌，这就是Sentinel官方介绍的令牌自动掉落。

Sentinel没有在每个请求通过时从令牌桶取走令牌，那么Sentinel是如何控制QPS的呢，我们再来看一张图：

x1：当前令牌桶中超过thresholdPermits的令牌数量;

y1：y1加上stableInterval等于当前令牌生产的时间间隔;

根据斜率和x1可算出y1：

y1 = slope * x1 

y1加上stableInterval即为当前的令牌生产速率。

当前秒生产令牌的时间间隔为：

slope * (storedTokens - thresholdPermits) + stableInterval 

由于：stableInterval = 1.0(1秒) / 限流阈值(count)

所以上述等式 = slope * (storedTokens - thresholdPermits) + 1.0 / count

最后算得当前时间戳的QPS阈值为：

1.0 / slope * (storedTokens - thresholdPermits) + 1.0 / count 

参考文献：

[1] Guava RateLimiter分析：

https://blog.wangqi.love/articles/Java/Guava%20RateLimiter%E5%88%86%E6%9E%90.html

本文转载自微信公众号「Java艺术」，可以通过以下二维码关注。转载本文请联系Java艺术公众号。

本文转载自网络，原文链接：https://mp.weixin.qq.com/s/z5KClg-FNpimpn47GAqcaA
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！