在前面一篇文章写了默认的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 流控效果之匀速排队与预热实现原理与实战建议