Sentienl 流控效果之匀速排队与预热实现原理与实战建议
点击上方“中间件兴趣圈”，选择“设为星标”
做积极的人，越努力越幸运！
温馨提示：如果大家对源码不感兴趣，可以直接跳到文末，查看其实战建议。
首先先回顾一下 Sentinel 流控效果相关的类图：
首先我们应该知道，一条流控规则(FlowRule)对应一个 TrafficShapingController 对象。
1、RateLimiterController
匀速排队策略实现类，首先我们先来介绍一下该类的几个成员变量的含义：
int maxQueueingTimeMs
排队等待的最大超时时间，如果等待超过该时间，将会抛出 FlowException。double count
流控规则中的阔值，即令牌的总个数，以QPS为例，如果该值设置为1000，则表示1s可并发的请求数量。AtomicLong latestPassedTime
上一次成功通过的时间戳。
接下来我们详细来看一下其算法的实现：
RateLimiterController#canPass
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
if (acquireCount <= 0) {
return true;
}
if (count <= 0) {
return false;
}
long currentTime = TimeUtil.currentTimeMillis();
long costTime = Math.round(1.0 * (acquireCount) / count * 1000); // @1
long expectedTime = costTime + latestPassedTime.get(); // @2
if (expectedTime <= currentTime) { // @3
latestPassedTime.set(currentTime);
return true;
} else {
long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis(); // @4
if (waitTime > maxQueueingTimeMs) { // @5
return false;
} else {
long oldTime = latestPassedTime.addAndGet(costTime); // @6
try {
waitTime = oldTime - TimeUtil.currentTimeMillis();
if (waitTime > maxQueueingTimeMs) {
latestPassedTime.addAndGet(-costTime);
return false;
}
if (waitTime > 0) { // @7
Thread.sleep(waitTime);
}
return true;
} catch (InterruptedException e) {
}
}
}
return false;
}
代码@1：首先算出每一个请求之间最小的间隔，时间单位为毫秒。例如 cout 设置为 1000,表示一秒可以通过 1000个请求，匀速排队，那每个请求的间隔为 1 / 1000(s)，乘以1000将时间单位转换为毫秒，如果一次需要2个令牌，则其间隔时间为2ms，用 costTime 表示。
代码@2：计算下一个请求的期望达到时间，等于上一次通过的时间戳 + costTime ，用 expectedTime 表示。
代码@3：如果 expectedTime 小于等于当前时间，说明在期望的时间没有请求到达，说明没有按照期望消耗令牌，故本次请求直接通过，并更新上次通过的时间为当前时间。
代码@4：如果 expectedTime 大于当前时间，说明还没到令牌发放时间，当前请求需要等待。首先先计算需要等待是时间，用 waitTime 表示。
代码@5：如果计算的需要等待的时间大于允许排队的时间，则返回 false，即本次请求将被限流，返回 FlowException。
代码@6：进入排队，默认是本次请求通过，故先将上一次通过流量的时间戳增加 costTime，然后直接调用 Thread 的 sleep 方法，将当前请求先阻塞一会，然后返回 true 表示请求通过。
匀速排队模式的实现的关键：主要是记录上一次请求通过的时间戳，然后根据流控规则，判断两次请求之间最小的间隔，并加入一个排队时间。
2、WarmUpController
预热策略的实现，首先我们先来介绍一下该类的几个成员变量的含义：
double count
流控规则设定的阔值。int coldFactor
冷却因子。int warningToken
告警token，对应 Guava 中的 RateLimiter 中的int maxToken
double slope
AtomicLong storedTokens
AtomicLong lastFilledTime
2.1 WarmUpController 构造函数
内部的构造函数，最终将调用 construct 方法。
WarmUpController#construct
private void construct(double count, int warmUpPeriodInSec, int coldFactor) { // @1
if (coldFactor <= 1) {
throw new IllegalArgumentException("Cold factor should be larger than 1");
}
this.count = count;
this.coldFactor = coldFactor;
warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1); // @2
maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor)); // @3
slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
}
要理解该方法，就需要理解 Guava 框架的 SmoothWarmingUp 相关的预热算法，其算法原理如图所示：
关于该图的详细介绍，请参考笔者的另外一篇博文：源码分析RateLimiter SmoothWarmingUp 实现原理(文末附流程图)，对该图进行了详细解读。
代码@1：首先介绍该方法的参数列表：
double count
限流规则配置的阔值，例如是按 TPS 类型来限流，如果限制为100tps，则该值为100。int warmUpPeriodInSec
预热时间，单位为秒，通用在限流规则页面可配置。int coldFactor
冷却因子，这里默认为3，与 RateLimiter 中的冷却因子保持一致，表示的含义为 coldIntervalMicros 与 stableIntervalMicros 的比值。
代码@2：计算 warningToken 的值，与 Guava 中的 RateLimiter 中的 thresholdPermits 的计算算法公式相同，thresholdPermits = 0.5 * warmupPeriod / stableInterval，在Sentienl 中，而 stableInteral = 1 / count，thresholdPermits 表达式中的 0.5 就是因为 codeFactor 为3，因为 warm up period与 stable 面积之比等于 (coldIntervalMicros - stableIntervalMicros ) 与 stableIntervalMicros 的比值，这个比值又等于 coldIntervalMicros / stableIntervalMicros - stableIntervalMicros / stableIntervalMicros 等于 coldFactor - 1。
代码@3：同样根据 Guava 中的 RateLimiter 关于 maxToken 也能理解。
2.2 canPass 方法详解
WarmUpController#canPass
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
long passQps = (long) node.passQps(); // @1
long previousQps = (long) node.previousPassQps(); // @2
syncToken(previousQps); // @3
// 开始计算它的斜率
// 如果进入了警戒线，开始调整他的qps
long restToken = storedTokens.get();
if (restToken >= warningToken) { // @4
long aboveToken = restToken - warningToken;
// 消耗的速度要比warning快，但是要比慢
// current interval = restToken*slope+1/count
double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
if (passQps + acquireCount <= warningQps) {
return true;
}
} else { // @5
if (passQps + acquireCount <= count) {
return true;
}
}
return false;
}
代码@1：先获取当前节点已通过的QPS。
代码@2：获取当前滑动窗口的前一个窗口收集的已通过QPS。
代码@3：调用 syncToken 更新 storedTokens 与 lastFilledTime 的值，即按照令牌发放速率发送指定令牌，将在下文详细介绍 syncToken 方法内部的实现细节。
代码@4：如果当前存储的许可大于warningToken的处理逻辑，主要是在预热阶段允许通过的速率会比限流规则设定的速率要低，判断是否通过的依据就是当前通过的TPS与申请的许可数是否小于当前的速率（这个值加入斜率，即在预热期间，速率是慢慢达到设定速率的。
代码@5：当前存储的许可小于warningToken，则按照规则设定的速率进行判定。
不知大家有没有一个疑问，为什么 storedTokens 剩余许可数越大，限制其通过的速率竟然会越慢，这又怎么理解呢？大家可以思考一下这个问题，将在本文的总结部分进行解答。
我们先来看一下 syncToken 的实现细节，即更新 storedTokens 的逻辑。
WarmUpController#syncToken
protected void syncToken(long passQps) {
long currentTime = TimeUtil.currentTimeMillis();
currentTime = currentTime - currentTime % 1000; // @1
long oldLastFillTime = lastFilledTime.get();
if (currentTime <= oldLastFillTime) { // @2
return;
}
long oldValue = storedTokens.get();
long newValue = coolDownTokens(currentTime, passQps); // @3
if (storedTokens.compareAndSet(oldValue, newValue)) {
long currentValue = storedTokens.addAndGet(0 - passQps); // @4
if (currentValue < 0) {
storedTokens.set(0L);
}
lastFilledTime.set(currentTime);
}
}
代码@1：这个是计算出当前时间秒的最开始时间。例如当前是 2020-04-06 08:29:01:056，该方法返回的时间为 2020-04-06 08:29:01:000。
代码@2：如果当前时间小于等于上次发放许可的时间，则跳过，无法发放令牌，即每秒发放一次令牌。
代码@3：具体方法令牌的逻辑，稍后详细介绍。
代码@4：更新剩余令牌，即生成的许可后要减去上一秒通过的令牌。
我们详细来看一下 coolDownTokens 方法。
WarmUpController#coolDownTokens
private long coolDownTokens(long currentTime, long passQps) {
long oldValue = storedTokens.get();
long newValue = oldValue;
// 添加令牌的判断前提条件:
// 当令牌的消耗程度远远低于警戒线的时候
if (oldValue < warningToken) { // @1
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
} else if (oldValue > warningToken) { // @2
if (passQps < (int)count / coldFactor) {
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
}
}
return Math.min(newValue, maxToken);// @3
}
代码@1：如果当前剩余的 token 小于警戒线，可以按照正常速率发放许可。
代码@2：如果当前剩余的 token 大于警戒线但前一秒的QPS小于 (count 与 冷却因子的比)，也发放许可（这里我不是太明白其用意）。
代码@3：这里是关键点，第一次运行，由于 lastFilledTime 等于0，这里将返回的是 maxToken，故这里一开始的许可就会超过 warningToken，启动预热机制，进行速率限制。
3、总结
WarmUpController 这个预热算法还是挺复杂的，接下来我们来总结一下它的特征。
不知大家有没有一个疑问，为什么 storedTokens 剩余许可数越大，限制其通过的速率竟然会越慢，这又怎么理解呢？
这里感觉有点逆向思维的味道，因为一开始就会将 storedTokens 的值设置为 maxToken，即开始就会超过 warningToken，从而一开始进入到预热阶段，此时的速率有一个爬坡的过程，类似于数学中的斜率，达到其他启动预热的效果。
实战指南：注意 warmUpPeriodInSec 与 coldFactor 的设置，将会影响最终的限流效果。
为了更加直观的理解，我们举例如下，warningToken 与 maxToken 的生成公式如下：
warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);
maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));
coldFactor 设定为 3，例如限流规则中配置每秒允许通过的许可数量为 10，即 count 值等于 10，我们改变 warmUpPeriodInSec 的值来看一下 warningToken 与 maxToken 的值，以此来探究 Sentinel WarmUpController 的工作机制或工作效果。
| warmUpPeriodInSec | warningToken | maxToken |
|---|---|---|
| 1 | 5 | 10 |
| 2 | 10 | 20 |
| 3 | 15 | 30 |
| 4 | 20 | 40 |
根据上面的算法，如果 warningToken 的值小于 count，则限流会变的更严厉，即最终的限流TPS会小于设置的TPS。即 warmUpPeriodInSec 设置过大过小都不合适，其标准是要使得 warningToken 的值大于 count。
如果本文对您有所帮助，希望帮忙点一下【在看】，谢谢。
思考题：匀速排队方式存在什么弊端？该问题正在我的知识星球如火如荼的展开讨论中。
欢迎加入我的知识星球，一起交流源码，探讨架构，揭秘亿级订单的架构设计与实践经验，打造高质量的技术交流圈，为广大星友提供高质量问答服务，为庆祝笔者正式晋升为一名“10年IT老兵”，特发放了一批知识星球优惠券，目前还剩下不足10张，有意愿的可以点击如下二维码领取优惠券。