Sentienl 流控效果之匀速排队与预热实现原理与实战建议

Stella981
• 阅读 594

点击上方“中间件兴趣圈”,选择“设为星标”

做积极的人,越努力越幸运!

Sentienl 流控效果之匀速排队与预热实现原理与实战建议

温馨提示:如果大家对源码不感兴趣,可以直接跳到文末,查看其实战建议。

首先先回顾一下 Sentinel 流控效果相关的类图:

Sentienl 流控效果之匀速排队与预热实现原理与实战建议

DefaultController 快速失败已经在上文详细介绍过,本文将详细介绍其他两种策略的实现原理。

首先我们应该知道,一条流控规则(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 相关的预热算法,其算法原理如图所示:

Sentienl 流控效果之匀速排队与预热实现原理与实战建议

关于该图的详细介绍,请参考笔者的另外一篇博文: 源码分析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张,有意愿的可以点击如下二维码领取优惠券。

Sentienl 流控效果之匀速排队与预热实现原理与实战建议

本文分享自微信公众号 - 中间件兴趣圈(dingwpmz_zjj)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
Canal 如何保证数据库库事务的一致性
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/65b1a5c3587b629c19b3685264434b69949.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp.wei
Stella981 Stella981
3年前
Canal binlog 日志 Dump 流程分析
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/034e6b7d680e414332a79a68829ec542244.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp.wei
Stella981 Stella981
3年前
Alibaba Sentinel 限流与熔断初探
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/44bed85e8c91c7600c2479df035e2558748.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%
Stella981 Stella981
3年前
Sentinel 调用上下文环境实现原理(含原理图)
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/33cec0d20fe42d2f34e7ea0ccb472821287.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp
Stella981 Stella981
3年前
Sentinel 集群限流设计原理
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/7366d60332fba1cdd61fffdbfe50fbb2f75.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp
Stella981 Stella981
3年前
Sentinel 动态数据源架构设计理念与改造实践
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/d4efa6c24ed1a56d0edc2e015106825c9ed.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp
Stella981 Stella981
3年前
Sentinel 系统自适应限流原理剖析与实战指导
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/71eb753c0197b1ddde74497a579296873ec.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp
Stella981 Stella981
3年前
RocketMQ核心概念扫盲篇
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/384c7d212a4a4e44966aabcd858dc011.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp.we
Stella981 Stella981
3年前
RocketMQ学习环境搭建(RocketMQ安装与IDEA Debug环境搭建)
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/dfed8e67def340ddbfc2b6470ccd886b.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp.we
Stella981 Stella981
3年前
Sentinel FlowSlot 限流实现原理(文末附流程图与总结)
点击上方“中间件兴趣圈”,选择“设为星标”做积极的人,越努力越幸运!!(https://oscimg.oschina.net/oscnet/8c5bd236633405fcff940fb8b368887110b.png)(https://www.oschina.net/action/GoToLink?urlhttp%3A%2F%2Fmp