舒适提示,若是你们对源码不感兴趣,能够直接跳到本文的总结部分,了解一下预热实现原理的一些实战建议。java
首先先回顾一下 Sentinel 流控效果相关的类图:
DefaultController 快速失败已经在上文详细介绍过,本文将详细介绍其余两种策略的实现原理。node
首先咱们应该知道,一条流控规则(FlowRule)对应一个 TrafficShapingController 对象。web
匀速排队策略实现类,首先咱们先来介绍一下该类的几个成员变量的含义:算法
接下来咱们详细来看一下其算法的实现:
RateLimiterController#canPassapi
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 表示。svg
代码@5:若是计算的须要等待的时间大于容许排队的时间,则返回 false,即本次请求将被限流,返回 FlowException。函数
代码@6:进入排队,默认是本次请求经过,故先将上一次经过流量的时间戳增长 costTime,而后直接调用 Thread 的 sleep 方法,将当前请求先阻塞一会,而后返回 true 表示请求经过。
匀速排队模式的实现的关键:主要是记录上一次请求经过的时间戳,而后根据流控规则,判断两次请求之间最小的间隔,并加入一个排队时间。
预热策略的实现,首先咱们先来介绍一下该类的几个成员变量的含义:
内部的构造函数,最终将调用 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:首先介绍该方法的参数列表:
代码@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 也能理解。
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,启动预热机制,进行速率限制。
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。
若是文章对你有所帮助的话,还请点个赞,谢谢。
欢迎加笔者微信号(dingwpmz),加群探讨,笔者优质专栏目录:
一、源码分析RocketMQ专栏(40篇+)
二、源码分析Sentinel专栏(12篇+)
三、源码分析Dubbo专栏(28篇+)
四、源码分析Mybatis专栏
五、源码分析Netty专栏(18篇+)
六、源码分析JUC专栏
七、源码分析Elasticjob专栏
八、Elasticsearch专栏(20篇+)
九、源码分析MyCat专栏