Sentinel 深度剖析 之 流量控制中算法
原创
Sentinel的流量控制是监控应用流量的 QPS 或 并发线程数等指标，当达到指定的阈值时对流量进行控制，以避免被瞬时的流量⾼峰冲垮，从而保证高可用。
本文从数学公式角度、代码角度去分析流控算法，所以需要先了解一些Sentinel的名词。
- QPS：每秒请求数, 即在不断向服务器发送请求的情况下, 服务器每秒能够处理的请求数。
- 并发线程数: 指的是同时访问该资源的线程数量。
Sentinel 流控界面涉及参数如下：
- resource：资源名, 即限流规则的作用对象。
- count：限流阈值。
- grade：限流阈值类型：1-QPS、0-并发线程数，默认值QPS。
- limitApp：流控针对的调用来源：默认值default。
- 若为default则不区分调用来源。
- strategy：判断的根据资源：0-自身、1-根据其他关联资源、2-根据链路入口，默认值是根据资源本身。
- controlBehavior：流控效果：0-直接拒绝、2-排队等待、1-预热冷启动, 默认值直接拒绝。
- 直接拒绝又叫快速失败：公式为限流算法-总计数法；当QPS超过任意规则的阈值, 新的请求就会被立即拒绝。
一. 预热及令牌桶算法
当系统长度处于低水位，当流量突然增加时，直接把系统拉升到高水位可能瞬间把系统压垮。通过“冷启动”，当通过的流量缓慢增加，在一定时间内逐渐增加到阈值上限，给冷系统一个预热时间，避免冷系统被压垮。
注：这效果只针对QPS流控，不支持并发线程数流控
1. 原理
使用sentinel设置QPS的预热流控，需要设置阈值count和预热时长warmUpPeriodInSec。
如上图所示：X轴表示令牌桶中的令牌数量，y轴表示生产一个令牌需要的时间(秒)；相关参数如下：
- stableInterval(稳定区间)：稳定生产一个令牌需要时间
- coldInterval：生产一个令牌需要的最长时长，与冷启动因子coldFactor有关；可以通过-Dcsp.sentinel.flow.cold.factor设置，默认为3。
- warmUpPeriodSec(预热时间秒)：预热时长，默认10秒，对应坐标图中为(2)梯形面积。
- thresholdPermits阈值允许(warningToken)：令牌桶中一个阈值，超过该值时开启预热。
- maxPermits(maxtoken)：令牌桶中最⼤令牌数。
2. 换算关系
count：已知由用户设置，eg：每秒允许通过100请求。 warmUpPeriodInSec：已知由用户设置,默认10秒，时间区域上(2)梯形区域coldFactor，已经默认3。
公式1：
stableInterval=1/count(稳定生产一个令牌需要时间)公式2：
coldInterval=stableInterval*coldFactor冷启动因子(生产一个令牌需要的最长时长)公式3：
前提：由于coldFactor默认为3，y轴stableInterval~coldInterval的距离是0~stableInterval的距离两倍，时间区域上红色(2)梯形区域是红色1的长方形区域的两倍
坐标时间(1)长方形区域面积=长(thresholdPermits(warningToken))*宽(stableInterval)公式4：
坐标时间(1)长方形区域面积=0.5*warmUpPeriodSec公式5：
(thresholdPermits(warningToken))=0.5*warmUpPeriodSec/stableInterval代码：
warningToken=(int)(warmUpPeriodInSec*count)/(coldFactor-1);公式6：
前提：梯形的面积=(上低+下低)*高/2推导出maxPermits(maxToken)值
maxPermits=2*warmUpPeriodSec/(stableInterval+coldInterval)+thresholdPermits(warningToken)代码：
maxToken=warningToken+(int)(2*warmUpPeriodInSec*count/(1.0+coldFactor));公式7：
前提：斜率公式=(y1-y2)/(x1-x2)
slope=(coldInterval-stableInterval)/(maxToken-warningToken)代码：
slope=(coldFactor-1.0)/count/(maxToken-warningToken);3. 原理
当令牌桶中的令牌 < thresholdPermits(warningToken)时，令牌按照固定速率生产，请求流量稳定。
当令牌 > thresholdPermits(warningToken)时，开启预热，生产的令牌的速率 < 令牌滑落的速度，一段时间后，令牌 <= thresholdPermits(warningToken)，请求回归到稳定状态,预热结束。
4.WarmUpControlle
private void construct(double count, int warmUpPeriodInSec,int coldFactor) {
if (coldFactor <= 1) {
throw new IllegalArgumentException("Cold factor should be larger than 1");
}
this.count = count;
this.coldFactor = coldFactor;
// (1) thresholdPermits = 0.5 * warmupPeriod / stableInterval.
// warningToken = 100;
warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);
// (2) maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval)
// maxToken = 200
maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));
// slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);
slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
}
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
long passQps = (long) node.passQps();
long previousQps = (long) node.previousPassQps();
// (1) 令牌的生产过程和滑落过程
syncToken(previousQps);
// 开始计算它的斜率
// 如果进入了警戒线，开始调整他的qps
long restToken = storedTokens.get();
// (2) 令牌桶中剩余的令牌数
if (restToken >= warningToken) { // (3-1) 当剩余令牌大于令牌桶阈值,开启预热
long aboveToken = restToken - warningToken;
// 消耗的速度要比warning快，但是要比慢
// current interval = restToken*slope+1/count
// (4)根据斜率计算出预热时的QPS
double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
if (passQps + acquireCount <= warningQps) { //(5) 判断是否放行
return true;
}
} else { // (3-2) 剩余令牌小于令牌桶阈值, 不开启预热,流量稳定通行
if (passQps + acquireCount <= count) {
return true;
}
}
return false;
}
protected void syncToken(long passQps) {
long currentTime = TimeUtil.currentTimeMillis();
// 去除尾数即秒数
currentTime = currentTime - currentTime % 1000;
// 上次记录的时间戳
long oldLastFillTime = lastFilledTime.get();
if (currentTime <= oldLastFillTime) {
return;
}
// 获取桶中令牌数
long oldValue = storedTokens.get();
// 令牌生产
long newValue = coolDownTokens(currentTime, passQps);
if (storedTokens.compareAndSet(oldValue, newValue)) { // 2 将生产的令牌放入令牌桶
long currentValue = storedTokens.addAndGet(0 -passQps); // 从令牌桶中滑落已使用的令牌
if (currentValue < 0) {
storedTokens.set(0L);
}
lastFilledTime.set(currentTime);
}
}
private long coolDownTokens(long currentTime, long passQps) {
long oldValue = storedTokens.get();
long newValue = oldValue;
// 添加令牌的判断前提条件:
// 当令牌的消耗程度远远低于警戒线的时候
if (oldValue < warningToken) {
newValue = (long)(oldValue + (currentTime -
lastFilledTime.get()) * count / 1000);
} else if (oldValue > warningToken) {
if (passQps < (int)count / coldFactor) {
newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
}
}
return Math.min(newValue, maxToken);
}- 排队等待 -
匀速排队方式会严格控制请求通过的间隔时间，也即是让请求以均匀的速度通过；对应的是漏桶算法。
这效果只针对QPS流控，并发线程流控不支持。
1. 匀速排队
有超时等待时间，一旦超过这个预定设置的时间将会被限流。
2. 漏桶算法(leakyBucket)
随机突发流量通过漏桶以后稳定的速率流出，起到流量控制和平滑作用。
3. 实现类
RateLimiterController：通过控制请求通过的时间间隔来实现达到匀速目的。
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
// Pass when acquire count is less or equal than 0.
if (acquireCount <= 0) {
return true;
}
// Reject when count is less or equal than 0.
// Otherwise,the costTime will be max of long and waitTime will overflow in some cases.
if (count <= 0) {
return false;
}
long currentTime = TimeUtil.currentTimeMillis();
// Calculate the interval between every two requests.
// 1) 两次请求的时间间隔
long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
// Expected pass time of this request.
// 2)计算这次请求的通过预留时间 = 上次请求通过时间+时间间隔
long expectedTime = costTime + latestPassedTime.get();
// 3)当预期时间 <= 当前时间, 则允许通过并更新上次请求时间戳
if (expectedTime <= currentTime) {
// Contention may exist here, but it's okay.
latestPassedTime.set(currentTime);
return true;
} else {
// Calculate the time to wait.
// 4)当预期时间 > 当前时间, 则需要等待; 计算需要等待时间
long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
// 5)需要等待的时间> 最⼤队列时间, 则拒绝 默认超时时间500毫秒
if (waitTime > maxQueueingTimeMs) {
return false;
} else {
long oldTime =
latestPassedTime.addAndGet(costTime);
try {
waitTime = oldTime -
TimeUtil.currentTimeMillis();
// 6)
if (waitTime > maxQueueingTimeMs) {
latestPassedTime.addAndGet(-costTime);
return false;
}
// in race condition waitTime may <= 0
// 7)
if (waitTime > 0) {
Thread.sleep(waitTime);
}
return true;
} catch (InterruptedException e) {
}
}
}
return false;
}说明：假设设置的阈值count=100即每秒允许100个请求，每次通过一个请求acquireCount=1，套入公式costTime=10，即两次请求的时间间隔为10秒。
若水 架构师一枚，现就职于小米小爱开放平台，一个才貌双全的美女码农，平常喜欢总结知识和刷算法题，经常参加LeetCode算法周赛。
林淮川
毕业于西安交通大学；奈学教育首席架构师，教学教研负责人；前大树金融高级架构师、技术委员会开创者、技术总监；前天阳宏业交易事业部技术主管；多年互联网金融行业（ToB）经验。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。