Sentinel源码—4.FlowSlot实现流控的原理

流程图如下：

(2)RateLimiterController如何实现排队等待效果

当流控规则中指定的流控效果是排队等待时，对应的流量整形控制器是RateLimiterController。

当调用FlowSlot的entry()方法对请求进行流控规则验证时，最终会调用RateLimiterController的canPass()方法来对请求进行检查。

RateLimiterController实现排队等待的效果时使用了漏桶算法。既然使用了漏桶算法，那么就一定包含如下字段：

字段一：count，表示QPS阈值，即QPS超出多少后会进行限流。

字段二：latestPassedTime，表示最近允许请求通过的时间。有了这个参数，就能计算出当前请求最早的预期通过时间。

字段三：maxQueueingTimeMs，表示排队时的最大等待时间。

(3)RateLimiterController如何判断是否超出阈值

在RateLimiterController的canPass()方法中，为了判断是否超出QPS阈值，通过原子类变量latestPassedTime简化成单线程让请求先后通过的处理模型。为了尽量让业务不受Sentinel影响，采用预估请求的被处理时间点的方式。也就是无需等前面的请求完全被处理完，才确定后面的请求被处理的时间。因为在普通的漏桶算法中，是处理完一个请求，才从漏桶取出水滴。而RateLimiterController的漏桶算法，则是假设请求已经被通过了。

具体的判断逻辑如下：首先获取系统的当前时间currentTime。然后计算在满足流控规则中限制的QPS阈值count的情况下，先后的两个请求被允许通过时的最小时间间隔costTime。接着计算当前请求最早的预期通过时间expectedTime，也就是此次请求预计会在几时几分几秒内通过。最后比较expectedTime和currentTime就可知当前请求是否允许通过了。

一.如果expectedTime小于等于currentTime

也就是当前请求最早的预期通过时间比系统当前时间小。如果在此时(currentTime)通过当前请求，则当前请求的通过时间就比它最早的预期通过时间(expectedTime)要晚，即当前请求和最近通过的请求的时间间隔变大了，所以此时不会超QPS阈值。于是返回true允许通过，同时更新最近允许请求通过的时间戳为当前时间。

二.如果expectedTime大于currentTime

也就是当前请求最早的预期通过时间比系统当前时间大。如果在此时(currentTime)通过当前请求，则当前请求的通过时间就比它最早的预期通过时间(expectedTime)要早，即当前请求和最近通过的请求的时间间隔变小了，比最小间隔时间costTime还小，所以此时必然会超QPS阈值。因此返回进行等待或者返回false不允许通过，等待的最小时间就是：最近通过请求的时间 + 先后两个请求允许通过时的最小间隔时间 - 当前时间。

需要注意：Sentinel流量控制的漏桶算法，只能限制在costTime内的流量激增，限制不了costTime外的流量激增。比如系统启动完一瞬间就涌入大量并发请求，此时的流量激增限制不了。又比如系统处理完正常流量的最后一个请求，隔了costTime+的时间后，突然涌入超QPS阈值的并发请求，此时也限制不了这种情况的流量激增。但如果系统处理完正常流量的最后一个请求，隔了costTime-的时间后，突然涌入超QPS阈值的并发请求，此时则可以限制这种情况的流量激增。

public class RateLimiterController implements TrafficShapingController {
    //排队等待的意思是超出阈值后等待一段时间，maxQueueingTimeMs就是请求在队列中的最大等待时间
    private final int maxQueueingTimeMs;
    //流控规则中限制QPS的阈值，也就是QPS超出多少后会进行限制
    private final double count;
    //最近允许一个请求通过的时间，每次请求通过后就会更新此时间，可以根据该时间计算出当前请求最早的预期通过时间
    //注意：Sentinel是在业务前面的，尽量不要让业务受到Sentinel的影响，所以不需要等请求完全被处理完，才确定请求被通过的时间
    private final AtomicLong latestPassedTime = new AtomicLong(-1);

    public RateLimiterController(int timeOut, double count) {
        this.maxQueueingTimeMs = timeOut;
        this.count = count;
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount) {
        return canPass(node, acquireCount, false);
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        //Pass when acquire count is less or equal than 0.
        //acquireCount代表每次从桶底流出多少个请求
        //如果acquireCount小于等于0，则表示无需限流直接通过，不过acquireCount一般默认是1
        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.
        //如果限流规则的count(即限制QPS的阈值)小于等于0，则直接拒绝，相当于一个请求也不能放行
        if (count <= 0) {
            return false;
        }

        //1.首先获取系统的当前时间
        long currentTime = TimeUtil.currentTimeMillis();
        //Calculate the interval between every two requests.
        //2.然后计算，在满足流控规则中限制的QPS阈值count的情况下，先后的两个请求被允许通过时的最小间隔时间(假设请求是单线程处理的)
        long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
        //Expected pass time of this request.
        //3.接着计算当前请求最早的预期通过时间 = 满足QPS阈值下的两个请求的最小时间间隔 + 上次请求的通过时间
        long expectedTime = costTime + latestPassedTime.get();
        //4.最后判断当前请求最早的预期通过时间是否比系统当前时间小
        if (expectedTime <= currentTime) {//等价于没有超出QPS阈值
            //当前请求最早的预期通过时间比系统当前时间小
            //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要晚
            //也就是当前请求和最近通过的请求的时间间隔变大了，所以此时不会超QPS阈值，返回true允许通过

            //Contention may exist here, but it's okay.
            //latestPassedTime并不会影响costTime，也就是说，多个线程可以并发执行到这里而不受阈值的影响
            //这意味着，Sentinel流量控制的漏桶算法，只能限制在costTime时间内的流量激增，限制不了costTime时间外的流量激增
            //比如系统启动完的那一瞬间就涌入超出QPS阈值的并发请求，此时的这种流量激增是限制不了的
            //又比如系统正常运行时处理完了正常流量的最后一个请求，隔了costTime+的时间后，突然涌入超出QPS阈值的并发请求，此时也限制不了
            //只能限制住这样的一种情况：系统正常运行处理完正常流量的最后一个请求，隔了costTime-的时间，突然涌入超出QPS阈值的并发请求
            latestPassedTime.set(currentTime);
            return true;
        } else {//等价于超出了QPS阈值
            //当前请求最早的预期通过时间比系统当前时间大
            //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要早
            //也就是当前请求和最近通过的请求的时间间隔变小了，比最小间隔时间costTime还小
            //所以此时必然会超QPS阈值，因此返回进行等待或者返回false不允许通过
            //而等待的最小时间，就是最近通过请求的时间 + 先后两个请求允许通过时的最小间隔时间 - 当前时间
            ...
        }
    }
}

(4)RateLimiterController如何实现排队等待

一.实现排队等待效果的初版

首先计算当前请求预估的等待时间，用于判断是否超出最大等待时间。当前请求预估的等待时间 = 当前请求本来预期通过的时间 - 当前时间。

如果预估的等待时间超出流控规则设置的最大等待时间，则直接返回false，相当于桶内的水溢出了，处理不完，抛出异常。如果预估的等待时间没有超出流控规则设置的最大等待时间，则调用Thread.sleep()进行等待，睡眠时间就是预估的等待时间。

但是直接进行睡眠在并发场景下是无法实现排队等待效果的。因为如果多个并发请求因为在costTime内进入系统导致超QPS而等待时，canPass()方法对各个请求进行验证时，计算出来的waitTime可能都一样。这样睡眠了waitTime的时间后，等待的各个并发线程就会同时被唤醒。这样就没法实现排队等待的效果，也就是让这等待的请求按排队顺序唤醒。

public class RateLimiterController implements TrafficShapingController {
    //排队等待的意思是超出阈值后等待一段时间，maxQueueingTimeMs就是请求在队列中的最大等待时间
    private final int maxQueueingTimeMs;
    //流控规则中限制QPS的阈值，也就是QPS超出多少后会进行限制
    private final double count;
    //最近允许一个请求通过的时间，每次请求通过后就会更新此时间，可以根据该时间计算出当前请求最早的预期通过时间
    //注意：Sentinel是在业务前面的，尽量不要让业务受到Sentinel的影响，所以不需要等请求完全被处理完，才确定请求被通过的时间
    private final AtomicLong latestPassedTime = new AtomicLong(-1);
    
    public RateLimiterController(int timeOut, double count) {
        this.maxQueueingTimeMs = timeOut;
        this.count = count;
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount) {
        return canPass(node, acquireCount, false);
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        if (acquireCount <= 0) {
            return true;
        }
        if (count <= 0) {
            return false;
        }
        //1.首先获取系统的当前时间
        long currentTime = TimeUtil.currentTimeMillis();
        //2.然后计算，在满足流控规则中限制的QPS阈值count的情况下，先后的两个请求被允许通过时的最小间隔时间(假设请求是单线程处理的)
        long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
        //3.接着计算当前请求最早的预期通过时间 = 满足QPS阈值下的两个请求的最小时间间隔 + 上次请求的通过时间
        long expectedTime = costTime + latestPassedTime.get();
        //4.最后判断当前请求最早的预期通过时间是否比系统当前时间小
        if (expectedTime <= currentTime) {//等价于没有超出QPS阈值
            //当前请求最早的预期通过时间比系统当前时间小
            //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要晚
            //也就是当前请求和最近通过的请求的时间间隔变大了，所以此时不会超QPS阈值，返回true允许通过
            latestPassedTime.set(currentTime);
            return true;
        } else {//等价于超出了QPS阈值
            //当前请求最早的预期通过时间比系统当前时间大
            //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要早
            //也就是当前请求和最近通过的请求的时间间隔变小了，比最小间隔时间costTime还小
            //所以此时必然会超QPS阈值，因此返回进行等待或者返回false不允许通过
            //而等待的最小时间，就是最近通过请求的时间 + 先后两个请求允许通过时的最小间隔时间 - 当前时间
    
            //计算当前请求预估的等待时间，用于判断是否超出流控规则设置的最大等待时间
            long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
            if (waitTime > maxQueueingTimeMs) {
                //如果超出最大等待时间，则直接返回false
                return false;
            } else {
                //如果按如下3行代码让当前请求进行等待，那么执行到此处的多个并发请求，具有的waitTime都是一样的
                //这样睡眠了waitTime的时间后，等待的多个并发请求就会同时被唤醒
                //这样就没法实现排队等待的效果，不能让这等待的请求按排队顺序唤醒
                if (waitTime > 0) {
                    Thread.sleep(waitTime);
                }
                return true;
            }
        }
        return false;
    }
}

二.实现排队等待效果的优化版

为了避免等待的各个并发线程被同时唤醒，可通过原子变量latestPassedTime的addAndGet(costTime)方法 + 假设进行睡眠等待的请求已被通过，实现需要等待的并发请求进行睡眠等待的时间都不一样，从而实现并发请求排队等待的效果。

实现排队等待效果的核心逻辑：由于latestPassedTime的原子性，每个线程都会获得不一样的oldTime。接着根据oldTime - 当前时间，就可以得到每个线程需要睡眠等待的时间waitTime。此时的waitTime都将会不一样，从而避免并发线程同时被唤醒的情况。将latestPassedTime按costTime进行自增，其实相当于假设当前请求在不超过QPS阈值的情况下，被允许通过了。

public class RateLimiterController implements TrafficShapingController {
    //排队等待的意思是超出阈值后等待一段时间，maxQueueingTimeMs就是请求在队列中的最大等待时间
    private final int maxQueueingTimeMs;
    //流控规则中限制QPS的阈值，也就是QPS超出多少后会进行限制
    private final double count;
    //最近允许一个请求通过的时间，每次请求通过后就会更新此时间，可以根据该时间计算出当前请求最早的预期通过时间
    //注意：Sentinel是在业务前面的，尽量不要让业务受到Sentinel的影响，所以不需要等请求完全被处理完，才确定请求被通过的时间
    private final AtomicLong latestPassedTime = new AtomicLong(-1);
    
    public RateLimiterController(int timeOut, double count) {
        this.maxQueueingTimeMs = timeOut;
        this.count = count;
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount) {
        return canPass(node, acquireCount, false);
    }
    
    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        //acquireCount代表每次从桶底流出多少个请求
        //如果acquireCount小于等于0，则表示无需限流直接通过，不过acquireCount一般默认是1
        if (acquireCount <= 0) {
            return true;
        }
        //如果限流规则的count(即限制QPS的阈值)小于等于0，则直接拒绝，相当于一个请求也不能放行
        if (count <= 0) {
            return false;
        }
        //1.首先获取系统的当前时间
        long currentTime = TimeUtil.currentTimeMillis();
        //2.然后计算，在满足流控规则中限制的QPS阈值count的情况下，先后的两个请求被允许通过时的最小间隔时间(假设请求是单线程处理的)
        long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
        //3.接着计算当前请求最早的预期通过时间 = 满足QPS阈值下的两个请求的最小时间间隔 + 上次请求的通过时间
        long expectedTime = costTime + latestPassedTime.get();
        //4.最后判断当前请求最早的预期通过时间是否比系统当前时间小
        if (expectedTime <= currentTime) {//等价于没有超出QPS阈值
            //当前请求最早的预期通过时间比系统当前时间小
            //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要晚
            //也就是当前请求和最近通过的请求的时间间隔变大了，所以此时不会超QPS阈值，返回true允许通过

            //由这里可知，latestPassedTime并不会影响costTime，也就是说，多个线程可以并发执行到这里而不受阈值的影响
            //这意味着，Sentinel流量控制的漏桶算法，只能限制在costTime时间内的流量激增，限制不了costTime时间外的流量激增
            //比如系统启动完的那一瞬间就涌入超出QPS阈值的并发请求，此时的这种流量激增是限制不了的；
            //又比如系统正常运行时处理完了正常流量的最后一个请求，隔了costTime+的时间后，突然涌入超出QPS阈值的并发请求，此时也限制不了；
            //只能限制住这样的一种情况：系统正常运行处理完正常流量的最后一个请求，隔了costTime-的时间，突然涌入超出QPS阈值的并发请求
            latestPassedTime.set(currentTime);
            return true;
        } else {
            //如果不是，即当前请求最早的预期通过时间比系统当前时间大
            //则说明latestPassedTime.get()大了，也就是上一个可能由于QPS超出阈值的原因导致请求处理慢了，所以需要进行等待

            //计算当前请求的等待时间，用于判断是否超出流控规则设置的最大等待时间
            long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
            if (waitTime > maxQueueingTimeMs) {
                //如果超出最大等待时间，则直接返回false
                return false;
            } else {//等价于超出了QPS阈值
                //当前请求最早的预期通过时间比系统当前时间大
                //如果在此时(currentTime)通过当前请求，那么当前请求的实际通过时间就比它最早的预期通过时间(expectedTime)要早
                //也就是当前请求和最近通过的请求的时间间隔变小了，比最小间隔时间costTime还小
                //所以此时必然会超QPS阈值，因此返回进行等待或者返回false不允许通过
                //而等待的最小时间，就是最近通过请求的时间 + 先后两个请求允许通过时的最小间隔时间 - 当前时间

                //首先通过latestPassedTime这个原子变量的addAndGet()方法
                //将最近通过请求的时间latestPassedTime，加上先后两次请求需要的最小间隔时间costTime，得到当前请求本来预期的通过时间
                //注意：
                //当多个并发线程执行到此处时，由于latestPassedTime的原子性，每个线程都会获得不一样的oldTime
                //接着根据oldTime - 当前时间，就可以得到每个线程需要睡眠等待的时间waitTime
                //此时的waitTime都将会不一样，从而避免并发线程同时被唤醒的情况
                //将latestPassedTime进行自增，其实相当于假设当前请求在不超过QPS阈值的情况下，被允许通过了
                long oldTime = latestPassedTime.addAndGet(costTime);
                try {
                    //然后计算当前请求需要等待多久 = 当前请求最早的预期通过时间 - 当前系统时间
                    waitTime = oldTime - TimeUtil.currentTimeMillis();
                    //如果等待时间大于流控规则设置的最大等待时间，则需要回滚刚才更新的最近通过请求的时间
                    //也就是将latestPassedTime减去costTime，然后返回false表示请求无法通过
                    if (waitTime > maxQueueingTimeMs) {
                        //如果发现新计算的等待时间 大于 最大等待时间，则需要回滚latestPassedTime
                        latestPassedTime.addAndGet(-costTime);
                        return false;
                    }
                    //in race condition waitTime may <= 0
                    if (waitTime > 0) {
                        //当前请求需要进行等待
                        Thread.sleep(waitTime);
                    }
                    return true;
                } catch (InterruptedException e) {
                }
            }
        }
        return false;
    }
}

(5)RateLimiterController实现的漏桶算法与普通漏桶算法的区别

区别一：普通漏桶算法使用的是真实队列

它有个单独的字段去记录当前桶内的水量，也就是请求量。每通过一个请求，则该字段值-1。反之，每新进一个请求，此字段值+1。

区别二：RateLimiterController实现的漏桶算法使用的是虚拟队列

它没有单独的字段去记录当前桶内的请求量，而是根据最近通过请求的时间得出当前请求最早的预期通过时间来实现。其本质就是先假设当前请求可以通过，然后再按照先后请求在QPS阈值下可以允许通过时的最大时间间隔，来计算出当前请求最早的预期通过时间，再对比是否和当前发生冲突。

区别三：普通漏桶算法使用的策略是直接拒绝

如果流入速度大于流出速度，则直接拒绝。

区别四：RateLimiterController实现的漏桶算法使用的策略是排队等待

如果超出了阈值，则不会直接拒绝请求，而是会等待一段时间，只要在这段时间内能处理到这个请求就不会拒绝掉。

(6)RateLimiterController流控存在的问题

问题一：在costTime时间内出现流量激增才能限流

如果在costTime时间外，即最后一次请求通过的时间已经好久了，突然流量激增以及都并发进入系统，那么此时是无法限制住的。

问题二：Sentinel排队等待流控效果支持的QPS阈值不能超过1000

如果超过1000，且costTime计大于等于0.5，则会认为间隔时间都是1ms。如果costTime小于0.5，则认为配置失效，相当于没有配置此条流控规则。

long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
long costTime = Math.round(1.0 * (1) / 1100 * 1000)约等于0.9ms；

默认情况下，acquireCount的值是1，那么：如果QPS阈值count在1000～2000，此时costTime = 1，限流不受阈值影响。如果QPS阈值count大于2000，此时costTime = 0，限流配置失效。

4.FlowSlot实现流控规则中Warm Up效果的原理

(1)令牌桶算法介绍

(2)WarmUpController使用的预热模型

(3)WarmUpController的初始化

(4)WarmUpController的限流原理

(1)令牌桶算法介绍

一.令牌桶算法的原理

二.令牌桶算法的具体流程

三.漏桶算法和令牌桶算法的对比

四.令牌桶算法实现流控的例子

五.令牌桶算法的特点

六.令牌桶算法和漏桶算法的核心区别

七.令牌桶算法的代码实现

一.令牌桶算法的原理

通过控制令牌的生成速率和消耗速率来实现平滑地限制请求的处理速率，同时允许一定程度的突发流量。

首先，令牌桶中预先存放一定数量的令牌，每个令牌代表一个请求单位。然后，令牌会以固定的速率持续生成，并放入令牌桶中。当令牌桶满时，多余的令牌将会被丢弃。最后，每当有新请求到来时，需要从令牌桶中取出一个令牌。如果令牌桶中有足够的令牌，请求被允许通过。如果令牌桶中没有足够的令牌，请求将被限流。通过这种方式，令牌桶算法实现了平滑地限制请求的处理速率。

二.令牌桶算法的具体流程

步骤一：初始化令牌桶，设置其容量和生成速率。

步骤二：当有新请求到来时，检查令牌桶中是否有足够的令牌。如果有足够的令牌，则允许请求通过，并从令牌桶中扣除相应数量令牌。如果没有足够的令牌，则拒绝请求。

步骤三：系统会以固定的速度添加令牌，直到达到令牌桶容量，比如开启一个后台线程以固定的速度向令牌桶中添加令牌。

三.漏桶算法和令牌桶算法的对比

漏桶算法是突然往桶里注水，但是漏水的窟窿是固定大小的，因此流出水的速度是固定的，也就是"生产不限速，消费限速"。

令牌桶算法是突然从桶中抽水，也就是固定大小的窟窿变成了入水口，而没桶盖的桶口变成了出水口。相当于入水速度变得固定了，而出水速度不做限制了，也就是"生产限速，消费不限速"。

四.令牌桶算法实现流控的例子

假设有一个 API，需要限制其每秒请求数量为100，那么也可以使用令牌桶算法来实现这个限制。首先初始化一个令牌桶，其容量为100，令牌的生成速率为每秒100个。这样当有新请求到来时，就可以从令牌桶中获取令牌，以控制请求速率。

如果在某个时间点有120个请求同时到达，由于令牌桶中只有100个令牌，因此只有前100个请求能获取令牌通过，而剩下20个请求将被限流拒绝。当然也可以选择不直接拒绝，而是等待一段时间。随着时间推移，令牌桶会以固定速率(每秒100个令牌)重新填充。因此，被限流的请求在之后的时间窗口内就有机会被允许通过。

五.令牌桶算法的特点

特点一：支持突发流量

令牌桶算法允许在限流内应对突发流量，有助于提高系统的响应能力。

特点二：平滑处理速率

和漏桶算法一样，令牌桶算法也可以平滑处理流量，避免处理速率突变。

六.令牌桶算法和漏桶算法的核心区别

突发流量指的是：假设令牌桶容量为10个令牌，每秒生成2个令牌。当用户开始请求时，令牌桶可能已积累了一定数量的令牌，例如5个。如果用户突然发起大量请求，这时可以消耗令牌桶中的所有令牌。由于令牌桶此时有5个令牌，所以用户可以立即发起5个请求而不受限制。随后用户的请求速度将受到令牌生成速率的限制，每秒最多发起2个请求。可能用户1分钟内没有请求，那么令牌桶随着时间推移会放满10个令牌。当1分钟后突然来一波请求，那么此时的瞬时流量可以获取到10个令牌。

令牌桶算法允许用户在短时间内发起更多请求，从而支持突发流量。漏桶算法只能支持每秒固定处理一定数量的请求，从而不支持突发流量。这就是令牌桶和漏桶的核心区别。

七.令牌桶算法的代码实现

核心代码是：用于填充令牌的refill()方法，以及获取令牌数的tryAcquire()方法。

首先，利用当前系统时间减去上一次生成令牌时间，计算出上一次生成令牌距现在已间隔了多少毫秒。

然后，根据这个间隔毫秒数和平均每秒生成的令牌数，计算出上一次令牌生成时间到现在这段时间内，应该生成多少令牌。

接着，如果计算出来的令牌数大于0，则执行更新操作。更新时会使用Math.min()方法，确保令牌桶内不会超出容量阈值。

最后，更新最后一次生成令牌的时间为当前时间，以便下一次填充令牌时可以正确计算时间间隔。

public class TokenBucket {
    //令牌桶的容量
    private final int capacity;
    //令牌生成速度，也就是每秒产生多少个令牌
    private final int tokensPerSecond;
    //当前桶内的令牌数量
    private final AtomicInteger currentTokens;
    //最后一次令牌生成时间
    private final AtomicLong lastRefillTime;
    
    //初始化
    public TokenBucket(int capacity, int tokensPerSecond) {
        this.capacity = capacity;
        this.tokensPerSecond = tokensPerSecond;
        this.currentTokens = new AtomicInteger(capacity);
        this.lastRefillTime = new AtomicLong(System.currentTimeMillis());
    }
    
    //true：放行；false：限流
    public synchronized boolean tryAcquire(int tokens) {
        //填充令牌
        refill();
        //规则判断
        return currentTokens.addAndGet(-tokens) >= 0;
    }
    
    //填充令牌
    private void refill() {
        //获取当前系统时间
        long currentTime = System.currentTimeMillis();
        //用当前系统时间 - 上一次令牌生成时间 得出两次生成令牌需要间隔多久ms
        long timeSinceLastRefill = currentTime - lastRefillTime.get();
        //得出上一次令牌生成时间到现在这段时间内，应该生成多少令牌
        int tokensToAdd = (int) (timeSinceLastRefill * tokensPerSecond / 1000);
        if (tokensToAdd > 0) {
            //更新当前令牌数
            int newTokenCount = Math.min(capacity, currentTokens.get() + tokensToAdd);
            currentTokens.set(newTokenCount);
            //更新上一次令牌生成时间为当前系统时间
            lastRefillTime.set(currentTime);
        }
    }
}

(2)WarmUpController使用的预热模型

Sentinel中的令牌桶算法，参考了Guava的RateLimiter。

//The principle idea comes from Guava. 
//However, the calculation of Guava is rate-based, which means that we need to translate rate to QPS.
//这个原理来自于Guava；
//然而，Guava的计算是基于速率的，这意味着我们需要将速率转换为QPS；

//Requests arriving at the pulse may drag down long idle systems even though it has a much larger handling capability in stable period. 
//It usually happens in scenarios that require extra time for initialization, 
//e.g. DB establishes a connection, connects to a remote service, and so on. 
//That's why we need "warm up".
//突发式的流量可能会拖累一个长期空闲的系统，即使这个系统在稳定阶段具有更大的流量处理能力；
//这通常发生在需要额外时间进行初始化的场景中，比如DB建立连接、连接到远程服务等；
//这就是为什么我们需要对系统进行"预热"；

//Sentinel's "warm-up" implementation is based on the Guava's algorithm.
//However, Guava’s implementation focuses on adjusting the request interval, which is similar to leaky bucket.
//Sentinel pays more attention to controlling the count of incoming requests per second without calculating its interval,
//which resembles token bucket algorithm.
//Sentinel的"预热"实现是基于Guava的算法的；
//然而，Guava的实现侧重于调整请求间隔，这类似于漏桶；
//而Sentinel更注重控制每秒传入请求的数量，而不计算其间隔，这类似于令牌桶算法；

//The remaining tokens in the bucket is used to measure the system utility.
//Suppose a system can handle b requests per second. 
//Every second b tokens will be added into the bucket until the bucket is full.
//And when system processes a request, it takes a token from the bucket.
//The more tokens left in the bucket, the lower the utilization of the system; 
//when the token in the token bucket is above a certain threshold, 
//we call it in a "saturation" state.
//桶中存储的令牌是用来测量系统的实用程序的；
//假设一个系统每秒可以处理b个请求；
//那么每秒就有b个令牌被添加到桶中，直到桶满为止；
//当系统处理一个请求时，就会从桶中获取一个令牌；
//桶中存储的令牌剩余得越多，那么就说明系统的利用率就越低；
//当令牌桶中的令牌数高于某个阈值时，我们称之为"饱和"状态;

//Base on Guava’s theory, there is a linear equation we can write this in the form 
//y = m * x + b where y (a.k.a y(x)), or qps(q)), 
//is our expected QPS given a saturated period (e.g. 3 minutes in), 
//m is the rate of change from our cold (minimum) rate to our stable (maximum) rate, 
//x (or q) is the occupied token.
//根据Guava的理论，有一个线性方程，我们可以把它写成y ＝ m * x + b；
//这是在给定饱和周期(例如3分钟)的情况下预期的QPS；
//m是从我们的冷(最小)速率到我们的稳定(最大)速率的变化率；
//x(或q)就是需要被占用的令牌数；
public class WarmUpController implements TrafficShapingController {
    ...
    ...
}

WarmUpController基于的预热模型如下：

x轴表示当前令牌桶已存储的令牌数，y轴表示生成令牌的时间间隔，令牌的消费是从右往左的。

变量一：stableInterval

表示系统预热完成后，生成令牌的时间间隔。若QPS限制为100，则说明每10ms生成一个令牌。

变量二：coldInterval

表示系统水位最低时，生成令牌的时间间隔，与coldFactor有关。

变量三：coldFactor

冷却因子，表示倍数，即coldInterval是stableInterval的多少倍。

变量四：thresholdPermits

表示进入预热阶段的临界令牌数。当令牌桶中的令牌数量减少到临界值时，系统预热结束。当令牌桶中的令牌数量大于临界值时，系统进入冷启动模式。

变量五：maxPermits

表示令牌桶的容量。当令牌桶中的令牌数达到最大容量时，生成的令牌将被抛弃。

变量六：slope

表示斜率。用于计算当前令牌生成时的时间间隔，从而计算当前每秒能生成多少令牌。

变量七：warmUpPeriodSec

表示系统预热时间，也就是梯形的面积：

warmUpPeriodSec = 0.5 * (stableInterval + coldInterval) * (maxPermits - thresholdPermits)

在预热模型图中，梯形的面积 = (coldFactor - 1) * 长方形面积。

Guava中的预热是通过控制令牌的生成时间来实现的，Sentinel中的预热则是通过控制每秒通过的请求数来实现的。在Guava中，冷却因子coldFactor固定为3，已被写死。在Sentinel中，冷却因子coldFactor默认为3，可通过参数修改。

(3)WarmUpController的初始化

WarmUpController的初始化会调用WarmUpController的construct()方法，该方法会重点初始化三个属性的值：warningToken、maxToken、slope。

属性一：warningToken

告警值，大于告警值系统就进入预热阶段，小于告警值系统进入稳定阶段。计算公式如下：

warningToken
= warmUpPeriodSec / (coldFactor - 1) / stableInterval
= (warmUpPeriodSec * count) / (coldFactor - 1)

其中warmUpPeriodSec是构造方法中传入的预热时间，count是FlowRule中设定的QPS阈值，coldFactor默认是3。

属性二：maxToken

系统最冷时桶内存储的令牌数，即令牌桶可以存储的最大令牌数。计算公式如下：

maxToken
= warningToken + 2 * warmUpPeriodSec / (stableInterval + coldInterval)
= warningToken + 2 * warmUpPeriodSec * count / (coldFactor + 1)

属性三：slope

预热阶段令牌生成速率的增速。用于计算当前令牌生成时的时间间隔，从而计算当前每秒能生成多少令牌。计算公式如下：

slope
= (coldInterval - stableInterval) / (maxToken - warningToken)
= (coldFactor - 1) / count / (maxToken - warningToken)

注意：预热阶段生成令牌的速率会越来越慢，也就是生成令牌的间隔越来越大。当桶内已存储的令牌超过告警值后，令牌越多，那1秒可允许的QPS越小。

public class WarmUpController implements TrafficShapingController {
    //count是QPS阈值，即FlowRule中设定的阈值，表示系统在稳定阶段下允许的最大QPS
    //在预热阶段，系统允许的QPS不会直接到达count值，而是会逐渐增加(对应预热模型图从右向左)，直到达到这个count值为止
    //这样就能实现让系统接收到的流量是一个平滑上升的状态，而不是让系统瞬间被打满
    protected double count;

    //coldFactor是冷却因子，表示系统在最冷时(预热阶段刚开始时)允许的QPS阈值与稳定阶段下允许的QPS阈值之比
    //此参数直接影响预热阶段允许的QPS递增值，冷却因子越大，预热阶段允许的QPS递增值越低，默认为3
    private int coldFactor;

    //告警值，大于告警值系统就进入预热阶段，小于告警值系统进入稳定阶段
    protected int warningToken = 0;

    //令牌桶可以存储的最大令牌数
    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);
    }

    public WarmUpController(double count, int warmUpPeriodInSec) {
        //warmUpPeriodInSec是预热时长，表示系统需要多长时间从预热阶段到稳定阶段
        //比如限制QPS为100，设置预热时长为10s，那么在预热阶段，令牌生成的速率会越来越快
        //可能第1s只允许10个请求通过，第2s可能允许15个请求通过，这样逐步递增，直至递增到100为止
        construct(count, warmUpPeriodInSec, 3);
    }

    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 * warmupPeriodMicros / stableIntervalMicros;
        //1.告警值，大于告警值系统就进入预热阶段；例如预热时长为5s，QPS为100，那么warningToken就为250
        warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1);

        //maxPermits = thresholdPermits + 2 * warmupPeriodMicros / (stableIntervalMicros + coldIntervalMicros);
        //2.系统最冷时桶内存储的令牌数，例如预热时长为5s，QPS为100，那么maxToken为500
        maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor));

        //slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);
        //3.slope斜率，例如预热时长为5s，QPS为100，那么slope为0.00008
        slope = (coldFactor - 1.0) / count / (maxToken - warningToken);
    }
    ...
}

假如FlowRule设定的QPS阈值count为100(1s内QPS阈值为100)，设置的预热时间warmUpPeriodSec为5s，冷却因子coldFactor为3，那么WarmUpController初始化后的属性如下：

stableInterval = 1 / count = 10ms

coldInterval = coldFactor * stableInterval = 30ms

warningToken 
= warmUpPeriodSec / (coldFactor - 1) / stableInterval 
= (warmUpPeriodSec * count) / (coldFactor - 1) = 250

maxToken 
= warningToken + 2 * warmUpPeriodSec / (stableInterval + coldInterval) 
= warningToken + 2 * warmUpPeriodSec * count / (coldFactor + 1) = 500

slope 
= (coldInterval - stableInterval) / (maxToken - warningToken)
= (coldFactor - 1) / count / (maxToken - warningToken) = 0.00008

(4)WarmUpController的限流原理

一.WarmUpController.canPass()方法

二.WarmUpController.syncToken()方法

三.WarmUpController.coolDownTokens()方法

一.WarmUpController.canPass()方法

步骤一：调用WarmUpController的syncToken()方法生成令牌并同步到令牌桶内

步骤二：判断令牌桶内剩余令牌数是否大于告警值

情况一：如果剩余令牌数大于警戒值，说明系统处于预热阶段，此时需要进一步比较令牌的生产速率与令牌的消耗速率。若消耗速率大，则限流，否则请求正常通行。

情况二：如果剩余令牌数小于警戒值，说明系统处于稳定阶段。此时就直接判断当前请求的QPS与阈值大小，超过阈值则限流。

二.WarmUpController.syncToken()方法

该方法会生成令牌并同步到令牌桶内。其中入参passQps是前一个时间窗口的QPS，即上一秒通过的QPS数。首先验证当前时间与最后更新时间，避免在同一时间窗口重复添加令牌。其次通过WarmUpController的coolDownTokens()方法获取最新的令牌数，接着利用CAS来保证更新令牌桶的线程安全性，最后通过减去上一秒通过的QPS数得到目前令牌桶剩余的令牌数来进行更新。

三.WarmUpController.coolDownTokens()方法

该方法会根据当前时间和上一个时间窗口通过的QPS计算更新后的令牌数。具体来说就是，首先获取当前令牌桶已存储的令牌数，然后判断桶内令牌数和告警值的大小。

情况一：如果令牌桶中已存储的令牌数小于告警值

说明系统已结束冷启动，即退出预热阶段进入了稳定阶段。也就是桶内已存储的令牌数没达到进入预热阶段的阈值，此时需要较快地向令牌桶中添加令牌。

情况二：如果令牌桶中已存储的令牌数大于告警值

说明系统处于预热阶段，还在进行冷启动。此时如果上一个时间窗口通过的QPS，小于系统最冷时允许通过的QPS。那么就说明当前系统的负载比较低，可以向令牌桶中添加令牌。系统最冷时允许通过的QPS = (1 / (1 / count * coldFactor))。

其中，向令牌桶中添加令牌的处理，就是在当前令牌数量的基础上，加上从上次添加令牌到现在经过的时间乘以QPS阈值。

注意：Guava中的预热是通过控制令牌的生成时间来实现的，Sentinel中的预热是通过控制每秒通过的请求数来实现的。

Guava的实现侧重于调整请求间隔，这类似于漏桶算法。而Sentinel更注重控制每秒传入请求的数量，而不计算其间隔，这类似于令牌桶算法。

//The principle idea comes from Guava. 
//However, the calculation of Guava is rate-based, which means that we need to translate rate to QPS.
//这个原理来自于Guava；
//然而，Guava的计算是基于速率的，这意味着我们需要将速率转换为QPS；

//Requests arriving at the pulse may drag down long idle systems even though it has a much larger handling capability in stable period. 
//It usually happens in scenarios that require extra time for initialization, 
//e.g. DB establishes a connection, connects to a remote service, and so on. 
//That's why we need "warm up".
//突发式的流量可能会拖累一个长期空闲的系统，即使这个系统在稳定阶段具有更大的流量处理能力；
//这通常发生在需要额外时间进行初始化的场景中，比如DB建立连接、连接到远程服务等；
//这就是为什么我们需要对系统进行"预热"；

//Sentinel's "warm-up" implementation is based on the Guava's algorithm.
//However, Guava’s implementation focuses on adjusting the request interval, which is similar to leaky bucket.
//Sentinel pays more attention to controlling the count of incoming requests per second without calculating its interval,
//which resembles token bucket algorithm.
//Sentinel的"预热"实现是基于Guava的算法的；
//然而，Guava的实现侧重于调整请求间隔，这类似于漏桶；
//而Sentinel更注重控制每秒传入请求的数量，而不计算其间隔，这类似于令牌桶算法；

//The remaining tokens in the bucket is used to measure the system utility.
//Suppose a system can handle b requests per second. 
//Every second b tokens will be added into the bucket until the bucket is full.
//And when system processes a request, it takes a token from the bucket.
//The more tokens left in the bucket, the lower the utilization of the system; 
//when the token in the token bucket is above a certain threshold, 
//we call it in a "saturation" state.
//桶中存储的令牌是用来测量系统的实用程序的；
//假设一个系统每秒可以处理b个请求；
//那么每秒就有b个令牌被添加到桶中，直到桶满为止；
//当系统处理一个请求时，就会从桶中获取一个令牌；
//桶中存储的令牌剩余得越多，那么就说明系统的利用率就越低；
//当令牌桶中的令牌数高于某个阈值时，我们称之为"饱和"状态;

//Base on Guava’s theory, there is a linear equation we can write this in the form 
//y = m * x + b where y (a.k.a y(x)), or qps(q)), 
//is our expected QPS given a saturated period (e.g. 3 minutes in), 
//m is the rate of change from our cold (minimum) rate to our stable (maximum) rate, 
//x (or q) is the occupied token.
//根据Guava的理论，有一个线性方程，我们可以把它写成y ＝ m * x + b；
//这是在给定饱和周期(例如3分钟)的情况下预期的QPS；
//m是从我们的冷(最小)速率到我们的稳定(最大)速率的变化率；
//x(或q)就是需要被占用的令牌数；
public class WarmUpController implements TrafficShapingController {
    ...
    @Override
    public boolean canPass(Node node, int acquireCount) {
        return canPass(node, acquireCount, false);
    }

    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        //获取当前1s的QPS
        long passQps = (long) node.passQps();

        //获取上一窗口通过的QPS
        long previousQps = (long) node.previousPassQps();

        //1.生成令牌并同步到令牌桶内
        syncToken(previousQps);

        //获取令牌桶内剩余的令牌数
        long restToken = storedTokens.get();

        //2.如果令牌桶中的令牌数量大于告警值，说明还处于预热阶段，此时需要判断令牌的生成速度和消费速度
        if (restToken >= warningToken) {
            //获取桶内剩余令牌数超过告警值的令牌个数
            long aboveToken = restToken - warningToken;

            //当前令牌的生成间隔 = 稳定阶段的生成间隔 + 桶内超出告警值部分的已存储令牌数 * slope
            //其中，稳定阶段的生成间隔是1/count，桶内超出告警值部分的已存储令牌数是aboveToken
            //注意：预热阶段生成令牌的速率会越来越慢，也就是生成令牌的间隔越来越大；
            //当桶内已存储的令牌超过告警值后，令牌越多，那1秒可允许的QPS越小；

            //下面代码计算的是：
            //当前1s内的时间窗口能够生成的令牌数量，即当前时间窗口生成的令牌可满足的QPS = 1 / 当前令牌的生成间隔
            double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count));

            //如果当前消费令牌的速度(passQps + acquireCount) <= 当前生成令牌的速度(warningQps)，则允许通过
            //如果当前时间窗口通过的QPS + 客户端申请的令牌数 小于等于 当前预热阶段的告警QPS，则代表允许通过
            if (passQps + acquireCount <= warningQps) {
                return true;
            }
        }
        //3.如果令牌桶中的令牌数量小于告警值，说明预热结束，进入稳定阶段
        else {
            //如果当前消费令牌的速度(passQps + acquireCount) <= 当前生成令牌的速度(count)，则允许通过
            if (passQps + acquireCount <= count) {
                return true;
            }
        }

        return false;
    }

    //生成令牌并同步到令牌桶内
    //入参passQps是前一个时间窗口的QPS，也就是上一秒通过的QPS数
    //syncToken()方法的逻辑是：
    //1.首先验证当前时间与最后更新令牌桶的时间，避免在同一个时间窗口重复添加令牌；
    //2.其次通过WarmUpController.coolDownTokens()方法获取最新的令牌数；
    //3.接着利用CAS来保证更新令牌桶的线程安全性；
    //4.最后将桶内已存储的令牌数，减去上一秒通过的QPS数，得到目前令牌桶剩余的令牌数；
    protected void syncToken(long passQps) {
        //获取当前时间ms
        long currentTime = TimeUtil.currentTimeMillis();

        //将当前时间ms转换为s
        currentTime = currentTime - currentTime 00;

        //获取上一次更新令牌桶已存储的令牌数量的时间
        long oldLastFillTime = lastFilledTime.get();

        //如果上一次更新令牌桶已存储的令牌数量的时间和当前时间一样，或发生了时钟回拨等情况导致比当前时间还小
        //那么就无需更新，直接return即可
        if (currentTime <= oldLastFillTime) {
            return;
        }

        //先获取目前令牌桶已存储的令牌数
        long oldValue = storedTokens.get();

        //调用WarmUpController.coolDownTokens()方法得到最新的令牌数
        long newValue = coolDownTokens(currentTime, passQps);

        //通过CAS更新令牌桶已存储的令牌数
        //注意：系统初始化完毕，第一个请求进来调用WarmUpController.canPass()方法时，storedTokens = maxToken
        if (storedTokens.compareAndSet(oldValue, newValue)) {
            //设置令牌桶内已存储的最新令牌数 = 当前令牌数 - 上一个时间窗口通过的请求数
            long currentValue = storedTokens.addAndGet(0 - passQps);

            if (currentValue < 0 xss=removed xss=removed xss=removed> warningToken) {
            //如果上一个时间窗口通过的QPS，小于系统最冷时允许通过的QPS(1 / (1 / count * coldFactor))
            //那么就说明当前系统的负载比较低，可以向令牌桶中添加令牌
            if (passQps < (int)count / coldFactor) {
                //在当前令牌数量的基础上，加上从上次添加令牌到现在经过的时间(以秒为单位)乘以令牌生成速率(QPS阈值count)
                newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
            }
        }
        //确保令牌桶更新后的令牌数不超过最大令牌数(maxToken)
        //系统初始化完毕，第一个请求进来调用WarmUpController.canPass()方法时，
        //oldValue = 0，lastFilledTime = 0，此时返回maxToken
        return Math.min(newValue, maxToken);
    }
}

(5)总结

WarmUpController的核心原理是：首先根据当前时间和上一个时间窗口通过的QPS同步令牌桶内的令牌数，然后比较桶内令牌数和告警值来计算当前时间窗口允许通过的告警QPS，最后比较当前请求下的QPS是否大于允许通过的告警QPS来决定限流。

注意：系统在预热阶段会逐渐提高令牌的生成速度，从而平滑过渡到稳定阶段。当系统启动时，桶内令牌数最大，令牌生成速率最低，允许的QPS最低。随着桶内令牌数减少，令牌生成速度逐渐提高，允许的QPS也逐渐提高。最后到达稳定阶段，此时允许的QPS便是FlowRule中设置的QPS阈值。

所以根据稳定阶段令牌的生成速率是1/count，默认冷却因子为3，得出系统最冷时令牌的生成速率是3/count。因此预热阶段一开始允许的QPS为count/3，预热完毕的QPS就是count。