11-限流降级与流量效果控制器（中）

经典限流算法

计数器算法

Sentinel中默认实现的QPS限流算法和THREADS限流算法都属于计数器算法。QPS限流的默认算法是通过判断当前时间窗口（1秒）的pass（被放行的请求数量）指标数据判断，如果pass总数已经大于等于限流的QPS阈值，则直接拒绝当前请求，每通过一个请求当前时间窗口的pass指标计数加1。THREADS限流的实现是通过判断当前资源并行占用的线程数是否已经达到阈值，是则直接拒绝当前请求，每通过一个请求THREADS计数加1，每完成一个请求THREADS计数减1。

漏桶算法（Leaky Bucket）

漏桶就像在一个桶的底部开一个洞，不控制水放入桶的速度，而通过底部漏洞的大小控制水流失的速度，当水放入桶的速率小于或等于水通过底部漏洞流出的速率时，桶中没有剩余的水，而当水放入桶的速率大于漏洞流出的速率时，水就会逐渐在桶中积累，当桶装满水时，若再向桶中放入水，则放入的水就会溢出。我们把水换成请求，往桶里放入请求的速率就是接收请求的速率，而水流失就是请求通过，水溢出就是请求被拒绝。

令牌桶算法（Token Bucket）

令牌桶不存放请求，而是存放为请求生成的令牌（Token），只有拿到令牌的请求才能通过。原理就是以固定速率往桶里放入令牌，每当有请求过来时，都尝试从桶中获取令牌，如果能拿到令牌请求就能通过。当桶放满令牌时，多余的令牌就会被丢弃，而当桶中的令牌被用完时，请求拿不到令牌就无法通过。

流量效果控制器：TrafficShapingController

Sentinel支持对超出限流阈值的流量采取效果控制器控制这些流量，流量效果控制支持：直接拒绝、Warm Up（冷启动）、匀速排队。对应 FlowRule中的controlBehavior字段。在调用FlowRuleManager#loadRules方法时，FlowRuleManager会将限流规则配置的controlBehavior转为对应的TrafficShapingController。

public interface TrafficShapingController {
    // 判断当前请求是否能通过
    boolean canPass(Node node, int acquireCount, boolean prioritized);
    boolean canPass(Node node, int acquireCount);
}

node：根据limitApp与strategy选出来的Node（StatisticNode、DefaultNode、ClusterNode）；
acquireCount：与并发编程AQS#tryAcquire方法的参数作用一样，Sentinel将需要被保护的资源包装起来，这与锁的实现是一样的，需要先获取锁才能继续执行，acquireCount表示申请占用共享资源的数量，只有申请到足够的共享资源才能执行。例如，线程池有200个线程，当前方法执行需要申请3个线程才能执行，那么acquireCount就是3。acquireCount的值一般为1，当限流规则配置的限流阈值类型为threads时，表示需要申请一个线程，当限流规则配置的限流阈值类型为qps时，表示需要申请放行一个请求；
prioritized：表示是否对请求进行优先级排序，SphU#entry传递过来的值是false；

controlBehavior的取值与使用的TrafficShapingController对应关系如下表格所示：

control_Behavior	TRAFFIC_SHAPING_controller
CONTROL_BEHAVIOR_WARM_UP	WarmUpController
CONTROL_BEHAVIOR_RATE_LIMITER	RateLimiterController
CONTROL_BEHAVIOR_WARM_UP_RATE_LIMITER	WarmUpRateLimiterController
CONTROL_BEHAVIOR_DEFAULT	DefaultController

DefaultController

DefaultController是默认使用的流量效果控制器，直接拒绝超出阈值的请求。当QPS超过限流规则配置的阈值，新的请求就会被立即拒绝，抛出FlowException。适用于对系统处理能力明确知道的情况下，比如通过压测确定阈值。实际上我们很难测出这个阈值，因为一个服务可能部署在硬件配置不同的服务器上，并且随时都可能调整部署计划。

DefaultController#canPass方法源码如下。

    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        // (1) 
        int curCount = avgUsedTokens(node);
        // (2)
        if (curCount + acquireCount > count) {
            // （3）
            if (prioritized && grade == RuleConstant.FLOW_GRADE_QPS) {
                long currentTime;
                long waitInMs;
                currentTime = TimeUtil.currentTimeMillis();
                // （4）
                waitInMs = node.tryOccupyNext(currentTime, acquireCount, count);
                // （5）
                if (waitInMs < OccupyTimeoutProperty.getOccupyTimeout()) {
                    // 将休眠之后对应的时间窗口的pass(通过)这项指标数据的值加上acquireCount
                    node.addWaitingRequest(currentTime + waitInMs, acquireCount);
                    // 添加占用未来的pass指标的数量
                    node.addOccupiedPass(acquireCount);
                    // 休眠等待，当前线程阻塞
                    sleep(waitInMs);
                    // 抛出PriorityWait异常，表示当前请求是等待了waitInMs之后通过的
                    throw new PriorityWaitException(waitInMs);
                }
            }
            return false;
        }
        return true;
    }

（1）、avgUsedTokens方法：如果当前规则的限流阈值类型为QPS，则avgUsedTokens返回node当前时间窗口统计的每秒被放行的请求数；如果当前规则的限流阈值类型为THREADS，则avgUsedTokens返回node统计的当前并行占用的线程数。
（2）、如果将当前请求放行会超过限流阈值，且不满足（3），则直接拒绝当前请求。
（3）、如果限流阈值类型为QPS，表示具有优先级的请求可以占用未来时间窗口的统计指标。
（4）、如果可以占用未来时间窗口的统计指标，则tryOccupyNext返回当前请求需要等待的时间，单位毫秒。
（5）、如果休眠时间在限制可占用的最大时间范围内，则挂起当前请求，当前线程休眠waitInMs毫秒。休眠结束后抛出PriorityWait异常，表示当前请求是等待了waitInMs之后通过的。

一般情况下，prioritized参数的值为false，如果prioritized在ProcessorSlotChain传递的过程中，排在FlowSlot之前的ProcessorSlot都没有修改过，那么条件（3）就不会满足，所以这个canPass方法实现的流量效果就是直接拒绝。

RateLimiterController

Sentinel匀速流控效果是漏桶算法结合虚拟队列等待机制实现的，可理解为存在一个虚拟的队列，请求在队列中排队通过，每(count / 1000)毫秒可通过一个请求。虚拟队列的好处在于队列非真实存在，多核CPU多个请求并行通过时也可以通过，也就是说，实际通过的QPS会超过限流阈值的QPS，但不会超很多。

要配置限流规则使用匀速通过效果控制器RateLimiterController，则必须配置限流阈值类型为GRADE_QPS，并且阈值要少于等于1000。例如：

FlowRule flowRule = new FlowRule();
flowRule.setCount(30);
// 流量控制效果配置为使用匀速限流控制器
flowRule.setControlBehavior(RuleConstant.CONTROL_BEHAVIOR_RATE_LIMITER);
// 虚拟队列的最大等待时长，排队等待时间超过这个值的请求会被拒绝
flowRule.setMaxQueueingTimeMs(1000);
flowRule.setResource("GET:/hello");    
FlowRuleManager.loadRules(Collections.singletonList(flowRule));

RateLimiterController的字段和构造方法源码如下。

public class RateLimiterController implements TrafficShapingController {
    private final int maxQueueingTimeMs;
    private final double count;
    private final AtomicLong latestPassedTime = new AtomicLong(-1);

    public RateLimiterController(int timeOut, double count) {
        this.maxQueueingTimeMs = timeOut;
        this.count = count;
    }
}

maxQueueingTimeMs：请求在虚拟队列中的最大等待时间，默认500毫秒；
count：限流QPS阈值；
latestPassedTime：最近一个请求通过的时间，用于计算下一个请求的预期通过时间；

RateLimiterController实现的canPass方法源码如下。

    @Override
    public boolean canPass(Node node, int acquireCount, boolean prioritized) {
        //....
        // (1) 
        long currentTime = TimeUtil.currentTimeMillis();
        long costTime = Math.round(1.0 * (acquireCount) / count * 1000);
        // (2) 
        long expectedTime = costTime + latestPassedTime.get();
        // （3）
        if (expectedTime <= currentTime) {
            latestPassedTime.set(currentTime);
            return true;
        } else {
            // （4） 
            long waitTime = costTime + latestPassedTime.get() - TimeUtil.currentTimeMillis();
            if (waitTime > maxQueueingTimeMs) {
                return false;
            } else {
                try {
                    // （5）
                    long oldTime = latestPassedTime.addAndGet(costTime);
                    waitTime = oldTime - TimeUtil.currentTimeMillis();
                    if (waitTime > maxQueueingTimeMs) {
                        // （6）
                        latestPassedTime.addAndGet(-costTime);
                        return false;
                    }
                    // （7）
                    if (waitTime > 0) {
                        Thread.sleep(waitTime);
                    }
                    return true;
                } catch (InterruptedException e) {
                }
            }
        }
        return false;
    }

（1）计算队列中连续的两个请求的通过时间的间隔时长。

假设阈值QPS为200，那么连续的两个请求的通过时间间隔为5毫秒，每5毫秒通过一个请求就是匀速的速率，即每5毫秒允许通过一个请求。

（2）计算当前请求期望的通过时间。

请求通过的间隔时间加上最近一个请求通过的时间就是当前请求预期通过的时间。

（3）期望通过时间少于当前时间则当前请求可通过并且可以立即通过。

理想的情况是每个请求在队列中排队通过，那么每个请求都在固定的不重叠的时间通过。但在多核CPU的硬件条件下可能出现多个请求并行通过，这就是为什么说实际通过的QPS会超过限流阈值的QPS。

源码中给的注释：这里可能存在争论，但没关系。因并行导致超出的请求数不会超阈值太多，所以影响不大。

（4）预期通过时间如果超过当前时间那就休眠等待，需要等待的时间等于预期通过时间减去当前时间，如果等待时间超过队列允许的最大等待时间，则直接拒绝该请求。
（5）如果当前请求更新latestPassedTime为自己的预期通过时间后，需要等待的时间少于限定的最大等待时间，说明排队有效，否则自己退出队列并回退一个间隔时间。

此时latestPassedTime就是当前请求的预期通过时间，后续的请求将排在该请求的后面。这就是虚拟队列的核心实现，按预期通过时间排队。

（6）如果等待时间超过队列允许的最大排队时间则回退一个间隔时间，并拒绝当前请求。

回退一个间隔时间相当于将数组中一个元素移除后，将此元素后面的所有元素都向前移动一个位置。此处与数组移动不同的是，该操作不会减少已经在等待的请求的等待时间。

（7）休眠等待。

匀速流控适合用于请求突发性增长后剧降的场景。例如用在有定时任务调用的接口，在定时任务执行时请求量一下子飙高，但随后又没有请求的情况，这个时候我们不希望一下子让所有请求都通过，避免把系统压垮，但也不想直接拒绝超出阈值的请求，这种场景下使用匀速流控可以将突增的请求排队到低峰时执行，起到“削峰填谷”的效果。

在分析完源码后，我们再来看一个Issue，如下图所示。

11-01-qps1000失效-issue

为什么将QPS限流阈值配置超过1000后导致限流不生效呢？

计算请求通过的时间间隔算法如下：

long costTime = Math.round(1.0 * (acquireCount) / count * 1000);

假设限流QPS阈值为1200，当acquireCount等于1时，costTime = ¹⁄₁₂₀₀ * 1000，这个结果是少于1毫秒的，使用Math.round取整后值为1，而当QPS阈值越大，计算结果小于0.5时，Math.round取整后值就变为0。Sentinel支持的最小等待时间单位是毫秒，这可能是出于性能的考虑。当限流阈值超过1000后，如果costTime计算结果不少于0.5，则间隔时间都是1毫秒，这相当于还是限流1000QPS；而当costTime计算结果小于0.5时，经过Math.round取整后值为0，即请求间隔时间为0毫秒，也就是不排队等待，此时限流规则就完全无效了，配置等于没有配置。