Sentinel核心算法设计与实现

这里我们先一起先了解一下下Sentinel的一些比较重要的概念 ,Sentinel 整体工作流程采用责任链模式，功能定义Slot，计数通过Node，在Slot中通过选用不同的Node实现不同的流控模式。

• Node 用于不同纬度的计数

• Slot 实现不同的功能

• Resource 受保护的资源

• Rule 保护资源规则

 

回顾完了Sentinel的基本概念那么我们一起开始Sentinel源码探索之旅吧。接下来我们会从

StatisticSlot开始去探索Sentinel实现限流的细节与思路。由于篇幅有限此次文章我们侧重于了解Sentinel的计数和限流，对于其他部分的源码大家如果感兴趣可以留言或者私信讨论。

 

计数原理

StatisticSlot 是限流的基石基本上后续限流所依赖的数据都在这里统计，下面我们只展开了 我们标红的两个计数，是因为下面的其他计数只是选取的计数node不同地层原理是一致的。

 

1. 并发数计数 这里没有使用AtomicLong而是使用 LongAdder 去做计数，虽然在低并法场景下两者性能相差不大，但在高并发场景下LongAdder情况下性能优于AtomicLong。限流大多时候都要面对高并发的场景， 所以Sentinel在很多地方都是使用的LongAdder计数的包括下面讲的滑动窗口计数。注意这里只做了计数没有计入线程与资源的关系，所以当一个线程重复进入一个资源时并发数计数会随着重入次数增多。

    

1. 请求数计数 时序图如下

 

上面时序图涉上基本上涵盖了Node计数涉及的核心类

• ArrayMetric 对外提供计数功能类，底层通过持有LeapArray的对象实现计数。

• LeapArray 时间窗口计数的的抽象类，通过数组指向时间窗WindowWrap实现滑动窗口

• WindowWrap 时间窗，T 为 为计数桶 MetricBucket

• MetricBucket 计数桶， 底层通过LongAdder类型数组数组的大小以及位置意义由枚举MetrciEvent 决定

  

 

继续node.addPassRequest发现Sentinel计数时使用了两个滑动窗口计数，一个秒级别的和一个分钟级别的。秒级别的这个时间窗口使用的是LeapArray的子类OccupiableBucketLeapArray，这个了类在LeapArray的基础上支持预约抢占令牌(底层依赖于一个专门用作预约计数的滑动窗口)稍后我们会展开讲解预占过程。

这里就到了我们上面讲到的滑动窗口计数了

 

首先获取系统当前系统的时间戳然后再通过时间戳去获取时间窗口，注意这里并没没有直接使用System.currentTimeMillis()获取系统时间，因为这样获取系统时间会涉及到用户态到内核态的切换，在高并发时性能损耗会变大， 使用TimeUtil获取时间，TimeUtil在类加载时会创建一个线程去维护时间的获取这个线程主要做两件事 检查系统空闲和在系统繁忙时维护一个时间，在系统空闲时使用System.currentTimeMillis()获取OS时间，在非空闲时使用程序维护的时间，其实一些高性能中间件都会有类似的设计比如Redis。

接下来就是用拿到时间戳去获取时间窗口，获取时间窗口的逻辑如下，注意这里看起来窗口的时间都是连续的，实际上在内存中有可能是不连续的，对于过期的窗口只有流量落在这个窗口时窗口才会更新。

1. 当前时间所落窗口不存在 通过时间戳计算应该落在LeapArray的位置构建时间窗 并记录时间窗的开始时间用于下面判断窗口过期复用。

1. 当前时间所落窗口存在且未过期 返回当前窗口

1. 当前时间所落窗口存在且已过期 窗口数据清空 返回复用对象 （一些高性能框架都会选 复用对象 比如disruptor netty

   

 

限流原理

通过对流量整形接口 TrafficShapingController 的实现去满足不同效果的限流

• DefaultController 快速失败流控效果实现

• RateLimiterController 排队等待流控效果实现

• WarmUpController 冷启动流控效果实现

• WarmUpRateLimiterController 冷启动排队等待流控效果实现

 

默认快速失败限流算法DefaultController

1. 获取当前已经使用的令牌，如果申请的令牌加上已经申请的令牌小于限流数则认为可以通过，否则进入下一步。

1. 如果阀值类型为qps限流且使用优先获取时会进行预约后面时间窗口的令牌

   

下图为5个桶的时间窗口在第900ms时限流为50需要获取25个令令牌

显然当前时间窗口无法提供25个令牌只有在滑过两个时间窗口后才能满足需求

 

预约成功后休眠到令牌可用后并抛PriorityWaitException（这个异常会在StatisticSlot中被统计但是不中断业务流程）

 

排队等待限流算法RateLimiterController

RateLimiterController 是通过和计算的预期时间比对实现流量整型。因为逻辑比较简单直接看代码吧。

注意上面标红部分当限流值超过2000时限流会完全失效

 

冷启动限流算法WarmUpController

冷启动限流算法主要用于系统长期处于低水位的情况下，当流量突然增加时，直接把系统拉升到高水位可能瞬间把系统压垮。通过"冷启动"，让通过的流量缓慢增加，在一定时间内逐渐增加到阈值上限，给冷系统一个预热的时间，避免冷系统被压垮的情况，要想看懂Sentinel的冷启动限流算法，这里得先了解一下Guava SmoothWarmingUp的设计

在坐标系中横坐标为此时存储的令牌permit，纵坐标是允许通过请求的时间间隔interval也就是1/count。随着时间的推移放置的 令牌=tcount, t=intevalpermit 整个过程K线会随着时间放置permit右移随着permit消耗左移。当K线在maxPermits和thresholdsPermits之间时流量处于Warm Up状态这个时间就是warmupPeriod在图像中就是梯形的面积。随着继续消耗K线会介于thresholdsPermits之间这时流量已经完成Warm Up。

梯形的面积=warmupPeriod=(coldFactor-1)*距形面积。当coldFactor等于3时会有以下推倒。

//矩形的面积公式

thresholdPermits = 0.5 * warmupPeriod / stableInterval.

//梯形的面积公式

maxPermits = thresholdPermits + 2 * warmupPeriod / (stableInterval + coldInterval).

//红色部分斜率 slope

slope = (coldIntervalMicros - stableIntervalMicros) / (maxPermits - thresholdPermits);

//当K线在thresholdsPermits在maxPermits之间时任意x=K时

interval=(K-thresholdsPermits)*slope+stableIntervalMicros

根据上述面积为时间结论当消费从左向右推时单位时间内越向左interval跨度会变大允许通过的流量跨多也就越大，可得限流会曲线会更陡峭整体曲线如下图。

Sentinel实现WarmUp限流其实是参照Guava SmoothWarmingUp的实现，我们先看一下构造方法

Sentinel在构造方法里并没有使用Interval而是使用了count count=1/Interval，thresholdsPermits被命名为warningToken，maxPermits被命名为maxToken。以Sentinel概念图像如下。

1. 计算K线的位置在Sentinel中叫做restToken

1. 判断K线所处的空间，当处于Warm Up区间时根据斜率计算限流值，当不在这个区间内时直接使用count值。

 

排队等待冷启动限流算法WarmUpRateLimiterController

正如这个名字一样这个算法是WarmUp限流算法和RateLimiter结合体，下面我们一起学习一下这个算法是怎么实现的吧。

这个类继承与WarmUpController并在基础上多了两个变量，timeoutInMs 用于记录等待超时时间

latestPassedTime用于记录上个请求通过的时间。

查看限流逻辑其实很容易发现，这里计算限流值的方式基本上和我们上面WarmUpController一样，但是需要在计算完限流值后把限流值转换为请求间隔，转换到时间间隔后的逻辑就到了计算等待时间了，关于计算等待时间间隔部分不能说和RateLimiterController不能十分相似，也可以说一摸一样了，都是判断当前时间是否大于预期通过时间，只是这个时间间隔时会WARM UP的。

系统自适应限流

系统自适应限流其实和上面的算法其实不是一个纬度的，但是在我们写文章的时候有同学想了解相关内容，所以我们就在文章最后加个餐。系统保护规则是从应用级别的对入口流量进行控制，主要针对机器的 Load、RT、入口 QPS 和线程数四个维度监控指标，让系统尽可能跑在最大吞吐量的同时保证系统整体的稳定性。

1. 全局流量相关（qps rt 并发数）指标依赖于一个特殊的全局入口Node计数实现，当这个计数超过设定阀值时就会限流，注意这里对流量限流是无差别的后续我们其实是可以结合上面讲的优先级参数对流量进行分级处理的。

1. 对于CPU Load 指标的获取，这里出于对性能的考虑没有选择实时获取，而是使用秒级定时任务去定时获取计算，计算值主要依赖于OperatingSystemMXBean

1. 使用Load指标作为限流时这个限流参数会存在一定的自适应过程，当前线程数小于整个窗口内成功所需要的最小线程数时，即使Load达到阀值时流量仍然可以通过，在系统没有恶化时rt不会变化，随着线程数的增加成功流量的qps会变大，数所以允许通过的线程也会随之变大，随着流量变大到达系统瓶颈时rt会增加成功的qps也会随着rt的增加而降低，允许通过的线程数会趋于一个稳定值，这个值基本上可以认为是系统的吞吐量。