经典限流算法计数器算法Sentinel 中默认实现的 QPS 限流算法和 THREADS 限流算法都属于计数器算法。QPS 限流的默认算法是通过判断当前时间窗口1 秒的 pass被放行的请求数量指标数据判断如果 pass 总数已经大于等于限流的 QPS 阈值则直接拒绝当前请求每通过一个请求当前时间窗口的 pass 指标计数加 1。THREADS 限流的实现是通过判断当前资源并行占用的线程数是否已经达到阈值是则直接拒绝当前请求每通过一个请求 THREADS 计数加 1每完成一个请求 THREADS 计数减 1。漏桶算法Leaky Bucket漏桶就像在一个桶的底部开一个洞不控制水放入桶的速度而通过底部漏洞的大小控制水流失的速度当水放入桶的速率小于或等于水通过底部漏洞流出的速率时桶中没有剩余的水而当水放入桶的速率大于漏洞流出的速率时水就会逐渐在桶中积累当桶装满水时若再向桶中放入水则放入的水就会溢出。我们把水换成请求往桶里放入请求的速率就是接收请求的速率而水流失就是请求通过水溢出就是请求被拒绝。令牌桶算法Token Bucket令牌桶不存放请求而是存放为请求生成的令牌Token只有拿到令牌的请求才能通过。原理就是以固定速率往桶里放入令牌每当有请求过来时都尝试从桶中获取令牌如果能拿到令牌请求就能通过。当桶放满令牌时多余的令牌就会被丢弃而当桶中的令牌被用完时请求拿不到令牌就无法通过。流量效果控制器TrafficShapingControllerSentinel 支持对超出限流阈值的流量采取效果控制器控制这些流量流量效果控制支持直接拒绝、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 选出来的 NodeStatisticNode、DefaultNode、ClusterNode。acquireCount与并发编程 AQS#tryAcquire 方法的参数作用一样Sentinel 将需要被保护的资源包装起来这与锁的实现是一样的需要先获取锁才能继续执行acquireCount 表示申请占用共享资源的数量只有申请到足够的共享资源才能执行。例如线程池有 200 个线程当前方法执行需要申请 3 个线程才能执行那么 acquireCount 就是 3。acquireCount 的值一般为 1当限流规则配置的限流阈值类型为 threads 时表示需要申请一个线程当限流规则配置的限流阈值类型为 qps 时表示需要申请放行一个请求。prioritized表示是否对请求进行优先级排序SphU#entry 传递过来的值是 false。controlBehavior 的取值与使用的 TrafficShapingController 对应关系如下表格所示control_BehaviorTRAFFIC_SHAPING_controllerCONTROL_BEHAVIOR_WARM_UPWarmUpControllerCONTROL_BEHAVIOR_RATE_LIMITERRateLimiterControllerCONTROL_BEHAVIOR_WARM_UP_RATE_LIMITERWarmUpRateLimiterControllerCONTROL_BEHAVIOR_DEFAULTDefaultControllerDefaultControllerDefaultController 是默认使用的流量效果控制器直接拒绝超出阈值的请求。当 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 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如下图所示。为什么将 QPS 限流阈值配置超过 1000 后导致限流不生效呢计算请求通过的时间间隔算法如下long costTime Math.round(1.0 * (acquireCount) / count * 1000);假设限流 QPS 阈值为 1200当 acquireCount 等于 1 时costTime1⁄1200*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 毫秒也就是不排队等待此时限流规则就完全无效了配置等于没有配置。
深入理解Sentinel：08 限流降级与流量效果控制器（中）
经典限流算法计数器算法Sentinel 中默认实现的 QPS 限流算法和 THREADS 限流算法都属于计数器算法。QPS 限流的默认算法是通过判断当前时间窗口1 秒的 pass被放行的请求数量指标数据判断如果 pass 总数已经大于等于限流的 QPS 阈值则直接拒绝当前请求每通过一个请求当前时间窗口的 pass 指标计数加 1。THREADS 限流的实现是通过判断当前资源并行占用的线程数是否已经达到阈值是则直接拒绝当前请求每通过一个请求 THREADS 计数加 1每完成一个请求 THREADS 计数减 1。漏桶算法Leaky Bucket漏桶就像在一个桶的底部开一个洞不控制水放入桶的速度而通过底部漏洞的大小控制水流失的速度当水放入桶的速率小于或等于水通过底部漏洞流出的速率时桶中没有剩余的水而当水放入桶的速率大于漏洞流出的速率时水就会逐渐在桶中积累当桶装满水时若再向桶中放入水则放入的水就会溢出。我们把水换成请求往桶里放入请求的速率就是接收请求的速率而水流失就是请求通过水溢出就是请求被拒绝。令牌桶算法Token Bucket令牌桶不存放请求而是存放为请求生成的令牌Token只有拿到令牌的请求才能通过。原理就是以固定速率往桶里放入令牌每当有请求过来时都尝试从桶中获取令牌如果能拿到令牌请求就能通过。当桶放满令牌时多余的令牌就会被丢弃而当桶中的令牌被用完时请求拿不到令牌就无法通过。流量效果控制器TrafficShapingControllerSentinel 支持对超出限流阈值的流量采取效果控制器控制这些流量流量效果控制支持直接拒绝、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 选出来的 NodeStatisticNode、DefaultNode、ClusterNode。acquireCount与并发编程 AQS#tryAcquire 方法的参数作用一样Sentinel 将需要被保护的资源包装起来这与锁的实现是一样的需要先获取锁才能继续执行acquireCount 表示申请占用共享资源的数量只有申请到足够的共享资源才能执行。例如线程池有 200 个线程当前方法执行需要申请 3 个线程才能执行那么 acquireCount 就是 3。acquireCount 的值一般为 1当限流规则配置的限流阈值类型为 threads 时表示需要申请一个线程当限流规则配置的限流阈值类型为 qps 时表示需要申请放行一个请求。prioritized表示是否对请求进行优先级排序SphU#entry 传递过来的值是 false。controlBehavior 的取值与使用的 TrafficShapingController 对应关系如下表格所示control_BehaviorTRAFFIC_SHAPING_controllerCONTROL_BEHAVIOR_WARM_UPWarmUpControllerCONTROL_BEHAVIOR_RATE_LIMITERRateLimiterControllerCONTROL_BEHAVIOR_WARM_UP_RATE_LIMITERWarmUpRateLimiterControllerCONTROL_BEHAVIOR_DEFAULTDefaultControllerDefaultControllerDefaultController 是默认使用的流量效果控制器直接拒绝超出阈值的请求。当 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 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如下图所示。为什么将 QPS 限流阈值配置超过 1000 后导致限流不生效呢计算请求通过的时间间隔算法如下long costTime Math.round(1.0 * (acquireCount) / count * 1000);假设限流 QPS 阈值为 1200当 acquireCount 等于 1 时costTime1⁄1200*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 毫秒也就是不排队等待此时限流规则就完全无效了配置等于没有配置。
