在前面一篇文章写了默认的DefaultNode的实现方法，现在讲解剩余的几种方式。
RateLimiterController 匀速排队
重要参数
public class RateLimiterController implements TrafficShapingController {
// 排队等待的最大超时时间，如果等待时间超过该时间，就会抛出FlowException
private final int maxQueueingTimeMs;
//设置的阈值，以QPS为例，即1s中可以通过的数量
private final double count;
//上一次成功通过的时间戳
private final AtomicLong latestPassedTime = new AtomicLong(-1);
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
// 当需要的令牌数小于等于0，直接通过
if (acquireCount <= 0) {
return true;
}
//当阈值小于等于0时，拒绝
if (count <= 0) {
return false;
}
long currentTime = TimeUtil.currentTimeMillis();
// 根据本次请求的令牌数计算两个请求的间隔时间
// 1.0 / count * 10000 即一个令牌消耗的时间（毫秒）， 再乘以所需的令牌数，得到本次请求要间隔的时间
long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
// 计算该请求所期望到达时间
long expectedTime = costTime + latestPassedTime.get();
//如果小于当前时间，没有超出阈值，
if (expectedTime <= currentTime) {
// 此处可能存在争用，但可以
//更新上次通过事件为当前时间
latestPassedTime.set(currentTime);
return true;
} else {
// 如果expectedTime大于当前时间，说明还没到令牌发放时间，当前请求需等待, 因为每隔一个时间产生一个令牌，超过了当前时间，说明期间产生的令牌不够
long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
//计算的需要等待的时间超过了最大排队等待时间，就拒绝通过，并抛出FlowException异常
if (waitTime > maxQueueingTimeMs) {
return false;
} else {
// 更新时间，CAS操作，可能会出现争抢，导致多次重试
long oldTime = latestPassedTime.addAndGet(costTime);
try {
// 所以还要判断等待时间
waitTime = oldTime - TimeUtil.currentTimeMillis();
if (waitTime > maxQueueingTimeMs) {
latestPassedTime.addAndGet(-costTime);
return false;
}
// 线程等待
if (waitTime > 0) {
Thread.sleep(waitTime);
}
return true;
} catch (InterruptedException e) {
}
}
}
return false;
}
WarmUpController 预热
Sentinel的"warm-up"的实现是基于Guava的算法。
但是，Guava的实施着重于调整请求间隔，类似于漏斗。Sentinel更注重控制每秒的传入请求数，而不计算其间隔，这类似于令牌桶算法。
桶中的剩余令牌用于衡量系统的可用性。假设系统每秒可以处理b个请求。每秒钟b个令牌将被添加到存储桶中，直到存储桶已满。当系统处理请求时，它会从存储桶中获取令牌。存储桶中剩余的令牌越多，系统的利用率就越低； 当令牌桶中的令牌超过某个阈值时，我们将其称为“饱和”状态。
根据Guava的理论， 有一个线性方程可以写成y = m * x + b，其中y（aka y（x））或qps（q））是我们在饱和周期（ 例如3分钟）所希望的Qps，m是从冷（最小）速率到稳定（最大）速率的变化速率，x（或q）是占用令牌。
tips: 以上是在官方注释文档翻译的。
重要变量：
public class WarmUpController implements TrafficShapingController {
//流量规则设置的阈值
protected double count;
//冷却因子，默认为3
private int coldFactor;
//警告token,与Guava中的RateLimiter的thresholdPermits对应，超过这个值后进入了预热阶段
protected int warningToken = 0;
//最大的令牌数和RateLimiter的maxPermits对应
private int maxToken;
//斜线斜率
protected double slope;
//当前存储的令牌数
protected AtomicLong storedTokens = new AtomicLong(0);
//最后更新令牌的时间
protected AtomicLong lastFilledTime = new AtomicLong(0);
构造方法：
public WarmUpController(double count, int warmUpPeriodInSec, int coldFactor) {
construct(count, warmUpPeriodInSec, coldFactor);
}
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;
// thresholdPermits = 0.5 * warmupPeriod / stableInterval.
//其中 1 / count 就是 stableInterval
warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);
// / maxPermits = thresholdPermits + 2 * warmupPeriod /
// (stableInterval + coldInterval)
// 其中 coldInterval = 3 * stableInterval ，所以 stableInterval + coldInterval = 4 * stableInterval 而 stableInterval = 1 / count， 所以 stableInterval + coldInterval = 4 * （1/count） ,就可以得到下面的公式
maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));
// slope
// slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits
// - thresholdPermits);
slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
}
在进行流量控制时会触发下面的方法：
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
//获取当前节点已通过的QPs（调用的是按秒级统计）
long passQps = (long) node.passQps();
// 当前时间窗口的前一个窗口记录的通过的QPS(调用的是按分钟统计的)
long previousQps = (long) node.previousPassQps();
//更新 storedTokens 与 lastFilledTime 的值（最后减去了上一秒通过的令牌数QPS）
syncToken(previousQps);
// 开始计算它的斜率
// 如果进入了警戒线，开始调整他的qps
long restToken = storedTokens.get();
if (restToken >= warningToken) {
long aboveToken = restToken - warningToken;
// 消耗的速度要比warning快，但是要比慢
// current interval = restToken*slope+1/count
// int temp = aboveToken * slope + 1.0 / count 计算当前生成一个令牌的时间
// 1 / temp 即按照当前速率，在1s中可以产生的令牌数
double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
// 当前通过的数加上本次需要的令牌小于warningQps可以通过
if (passQps + acquireCount <= warningQps) {
return true;
}
// 当当前处于稳定状态时
} else {
// 判断当前通过数加上本次需要的数布不超过阈值，可以通过
if (passQps + acquireCount <= count) {
return true;
}
}
return false;
}
注意：调用者是rollingCounterInMinute，它是统计分钟级别的，有60个窗口，每个窗口代表1s的数据。
@Override
public double previousPassQps() {
return this.rollingCounterInMinute.previousWindowPass();
}
public long previousWindowPass() {
//更新时间窗口，去除过期时间
data.currentWindow();
WindowWrap<MetricBucket> wrap = data.getPreviousWindow();
if (wrap == null) {
return 0;
}
return wrap.value().pass();
}
public WindowWrap<T> getPreviousWindow() {
return getPreviousWindow(TimeUtil.currentTimeMillis());
}
public WindowWrap<T> getPreviousWindow(long timeMillis) {
if (timeMillis < 0) {
return null;
}
// windowLengthInMs为一个时间窗口的长度，因为是分钟级别统计的，所以是1s
// 计算当前时间前1s，即前一个时间窗口的下标位置
int idx = calculateTimeIdx(timeMillis - windowLengthInMs);
timeMillis = timeMillis - windowLengthInMs;
WindowWrap<T> wrap = array.get(idx);
// 检查是否不建议使用存储桶，这意味着该存储桶至少在整个窗口时间段（在这里是1分钟）内都已落后
if (wrap == null || isWindowDeprecated(wrap)) {
return null;
}
if (wrap.windowStart() + windowLengthInMs < (timeMillis)) {
return null;
}
return wrap;
}
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)) {
// 更细剩余令牌数量，即减去上1秒通过的令牌
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);
}
WarmUpRateLimiterController
设计上是上面介绍的RateLimiterController和WarmUpController结合起来
public boolean canPass(Node node, int acquireCount, boolean prioritized) {
long previousQps = (long) node.previousPassQps();
syncToken(previousQps);
long currentTime = TimeUtil.currentTimeMillis();
long restToken = storedTokens.get();
long costTime = 0;
long expectedTime = 0;
主要时下面与RateLimiterController不同
if (restToken >= warningToken) {
long aboveToken = restToken - warningToken;
// current interval = restToken*slope+1/count
double warmingQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));
costTime = Math.round(1.0 * (acquireCount) / warmingQps * 1000);
} else {
costTime = Math.round(1.0 * (acquireCount) / count * 1000);
}
主要时上面与RateLimiterController不同
expectedTime = costTime + latestPassedTime.get();
if (expectedTime <= currentTime) {
latestPassedTime.set(currentTime);
return true;
} else {
long waitTime = costTime + latestPassedTime.get() - currentTime;
if (waitTime > timeoutInMs) {
return false;
} else {
long oldTime = latestPassedTime.addAndGet(costTime);
try {
waitTime = oldTime - TimeUtil.currentTimeMillis();
if (waitTime > timeoutInMs) {
latestPassedTime.addAndGet(-costTime);
return false;
}
if (waitTime > 0) {
Thread.sleep(waitTime);
}
return true;
} catch (InterruptedException e) {
}
}
}
return false;
}
实际上，就是RateLimiterController中的代码，然后加入了预热的内容。
在RateLimiterController中，单个请求的costTime是固定的，就是1/count。
但是在这里，加入了WarmUp的内容，通过令牌数量，来判断当前系统的QPS应该是多少，如果当前令牌书超过了warnTokens，那么系统的最大QPS容量已经低于我们预设的QPS了，相应的，costTime就会延长。
至此，关于Sentinel中的限流部分就讲解完了。后面将会介绍降级部分。
参考文章：
RateLimiter 源码分析(Guava 和 Sentinel 实现)
Sentienl 流控效果之匀速排队与预热实现原理与实战建议
