阿里巴巴Sentinel关于自适应限流

这次阿里编程之夏，我选择的issue是对Sentinel做自适应流控（参考 #748），以下是最近这一个月的一些工作汇总，尤其是在自适应流控的想法上做了很多方面的探索，也欢迎大家思考和讨论。

一、在CommonFilter中支持对无需限流的网址的过滤

相关issue

解决了issue #287:

应用中的某些url不需要进行统计，比如spring boot 端点请求信息，能否增加相关的扩展点，可以过滤掉不想统计的url。

解决方法

由于已经有UrlCleaner接口，我们可以重用该接口并改进使用UrlCleaner统一资源名称的逻辑。如果开发人员要排除某些URL，他们可以在其UrlCleaner实现中将URL转换为空字符串“” ，并且CommonFilter我们可以检查已清理的资源名称是否为空。如果它是空的，那么它应该被排除，不会通过Sentinel的逻辑SphU.entry。

验证方法

我们可以通过ClusterBuilderSlot.getClusterNode(res)方法获取资源的统计节点，如果ClusterNode目标URL为空，那么我们认为它已被排除。

其他

在开源社区Sentinel中初次提交PR，更加熟悉了操作流程。

二、自适应限流的探索

在探索自适应限流的方法时，先学习了一些TCP拥塞控制的思路。并且还学习了控制的相关内容，如PID控制器。

1.并发限制算法Concurrency-limits

(1) TCP拥塞控制算法

    gradient = ( RTTnoload / RTTactual )
    newLimit = currentLimit × gradient + queueSize

该算法查看最小延迟之间的比率(表示没有排队最佳情况场景)以及时间采样延迟测量，作为确定队列已形成并导致延迟增加的代理。这个比率给出了延迟变化的梯度gradient。

值为1表示没有排队，可以增加限制，小于1的值表示已形成过多的队列，应降低限制。对于每个新样本，使用这个比率来调整限制，并用简单的公式添加允许队列的大小。

(2) Concurrency-limits

实现并集成来自TCP拥塞控制的概念，以自动检测服务的并发限制，以便以最佳延迟实现最佳吞吐量。
不应该考虑RPS，而应该考虑并发请求，我们应用排队论来确定服务在队列开始建立之前可以处理的并发请求数，延迟增加，服务最终耗尽限制，如CPU，内存，磁盘或网络。

    Limit = Average RPS * Average Latency

并发限制算法，根据当前平均RTT的变化梯度和长期指数平滑平均RTT调整限制。与传统的拥塞控制算法不同，使用平均值而不是最小值。

• 在各种因素的影响下（例如非同质请求处理复杂性以及数据大小的广泛分布），rpc方法可能是非常突发的。
• 使用最小值还会导致偏向于不切实际的低基RTT，从而导致过度的负载减少。

指数衰减方法用在基准RTT上，以使值保持稳定，可以适应于有延迟的特性长期变化的场景。

核心算法：

//计算限制范围[0.5,1.0]的梯度以过滤异常值
gradient = max(0.5, min(1.0, longtermRtt / currentRtt));

//通过应用渐变并允许某些排队来计算新限制
newLimit = gradient currentLimit + queueSize;

//使用平滑因子更新限制（默认值为0.2）
newLimit = currentLimit (1-smoothing) + newLimit smoothing;

Limit可能的三种主要状态：

• 稳态
  在这种状态下，平均RTT非常稳定，当前测量值在这个值附近徘徊，Limit有时会降低，有时会增加。



• 从稳态到负载状态
  在这种状态下，RPS和延迟都会飙升。由于系统无法处理的请求队列不断增长，因此梯度小于 1.0。低Limit导致过多的请求和拒绝数。通过指数衰减，基准RTT增长，但会比当前测量滞后，因此梯度保持在小于1.0，和低Limit水平。
  .

• 从负载状态到稳态
  在这种状态下，系统在长时间过载后会恢复稳定状态。请求不会被拒绝，取样到的RTT仍然很低。在此状态期间，longtermRtt可能需要一些时间才能恢复正常，并且可能比currentRtt高几倍。

总结
此方法对拥塞控制方法的RTTnoload和newLimit进行了新的探索和改进。对Limit做减半处理，是为了避免高负载情况的RTT导致的Limit急剧上升。
但为了避免Limit过低，不能让它低于queueSize。

(3) Concurrency-limits公式中用到的相关概念与Sentinel的对比

（标号的具体内容将在算法实现部分讨论）

2.TCP BBR

首先此处回顾下拥塞控制BBR算法：

记中间的拐点为A。在A点以后，数据包开始排队，A点处有着最大的带宽和最小的RTT。

之所以在此节提TCP BBR，是因为回调洪峰的处理后的图像，可以和TCP BBR很相似。在回调洪峰到来之前和到来之后，其实大致趋势也可以是类似图像。只不过纵坐标的RTT改为响应时间RT，横坐标的BDP改为请求超时前，漏桶所处理的容量。

但这里我们要探讨一下TCP的拥塞控制和流控的区别。

它们的场景其实是完全不同的：

• 对拥塞控制而言，发送方可以通过ACK来控制速率；
• 对流控而言，发送方不可控制。

简单举例，对TCP而言，你可以对发送方说：我们处理不了这么快，你们发慢点。但在流控时，你不能对用户说：双十一订单太多了，你少买点吧。

所以，对TCP来说，处理不了的只能先放到队列里，RTT的增大是一种被动行为。但是对流控回调洪峰场景来说，你等到系统崩掉就晚了，因此在必要的时候必须引入匀速器，致使RT增加。在这里，为了保护系统，RT的增加是一种主动行为。

因此对TCP BBR来说，最优解处就是中间的拐点，毕竟发再快了也只是多占用缓存空间，不能再加快处理速度。对流控而言，拿回调洪峰举例，最重要的目的则是“削峰填谷”，这一秒不能同时处理那么多，就放到下一秒处理，只要这类请求允许一定的延迟，那就没必要当下全部处理掉，把收敛点放后面些也没事。这样也有利于让更多系统资源抽身去处理其他的“洪峰”。

3.PID控制器思路

在提到PID控制器之前，先说下两种编程方式：命令式和声明式。

• 命令式编程：命令“机器”如何去做事情(how)，这样不管你想要的是什么(what)，它都会按照你的命令实现。
• 声明式编程：告诉“机器”你想要的是什么(what)，让机器想出如何去做(how)。
  而自适应的限流应该适合“声明式编程”的设计，告诉Sentinel系统应该达到什么状态，由系统自己调节。

因此，PID控制器的思想其实是契合的。

反馈理论的要素包括三个部分：测量、比较和执行。测量关键的是被控变量的实际值，与期望值相比较，用这个偏差来纠正系统的响应，执行调节控制。

(1) PID算法基本原理

PID算法的执行流程是非常简单的，即利用反馈来检测偏差信号，并通过偏差信号来控制被控量。而控制器本身就是比例、积分、微分三个环节的加和。其功能框图如下：

根据上图我们考虑在某个特定的时刻t，此时输入量为rin(t)，输出量为rout(t)，于是偏差就可计算为err(t)=rin(t)-rout(t)。于是PID的基本控制规律就可以表示为如下公式：

其中Kp为比例带，TI为积分时间，TD为微分时间。PID控制的基本原理就是如此。

(2) PID算法的离散化

上面简单介绍了PID算法的基本原理，但要在计算机上实现就必须将其离散化，接下来我们就说一说PID算法的离散化问题。在实现离散化之前，我们需要对比例、积分、微分的特性做一个简单的说明。

比例就是用来对系统的偏差进行反应，所以只要存在偏差，比例就会起作用。积分主要是用来消除静差，所谓静差就是指系统稳定后输入输出之间依然存在的差值，而积分就是通过偏差的累计来抵消系统的静差。而微分则是对偏差的变化趋势做出反应，根据偏差的变化趋势实现超前调节，提高反应速度。

在实现离散前，我们假设系统采样周期为T。假设我们检查第K个采样周期，很显然系统进行第K次采样。此时的偏差可以表示为err(K)=rin(K)-rout(K)，那么积分就可以表示为：err(K)+ err(K+1)+┈┈，而微分就可以表示为：(err(K)- err(K-1))/T。于是我们可以将第K次采样时，PID算法的离线形式表示为：

也可以记为：

三、自适应限流算法的实现

在这个月对自适应限流算法的实现时，其实也大致是按照上述探索流程一步步实现。针对限流场景，实现了比较经典的用户洪峰场景和回调洪峰场景。

1.用户洪峰

(1) 参考cocurrency-limits的实现

概述

在流量控制场景中我们会经常遇到流量洪峰的情况。例如双十一零点的情况，但这种场景又尽量不能有太长的延时。因此令牌桶限流是解决这种场景的流量洪峰的处理方法。这种洪峰我们一般称作用户洪峰。

用户洪峰需要考虑的因素：

• 允许访问的速率：令牌发放的速度r
• 系统承受的最大洪峰：当令牌桶满的时候，洪峰到达，这时候应用承受最大的QPS冲击 = 桶的容量 + 该秒令牌桶发放的速度r
• 洪峰爆发的间隔时间：下一次洪峰爆发前，尽量填满令牌桶

而如果想做到自适应的处理，与往常开发者设置这些限流指标不同，我们要做到用开发者的期望指标来代替。如期望的RT、吞吐量等。

在开发中，主要的考虑是通过用户期望RT和通过比率来调节令牌发放速度；根据往常最大的请求数和令牌桶速率调节令牌桶容量。

核心算法如下：

// 计算限制范围[1.0, 5.0]的梯度
// 实际通过率越小，梯度值越大，以增加后续通过数
double gradientRatio = Math.max(1.0, Math.min(2.0, targetRatio / ratio));

// 计算限制范围[0.5, 1.0]的梯度以过滤异常值
// 实际 avgRt 越大，梯度值越小，说明需要限制通过数
double needRt = Math.min(longTermRt, expectRt);
gradientRt = Math.max(0.5, Math.min(1.0, needRt / avgRt));

// 最后的令牌发放速度由通过率和 Rt 共同决定
newCount = (long)(gradientRatio * gradientRt * currentCount);
// 使用平滑因子更新令牌发放速度（默认为0.2）
newCount = (long)(currentCount * (1 - smoothing) + newCount * smoothing);

// 计算令牌桶最大容量
long newMaxToken = Math.max(newCount, (long)(previousTotalQps * targetRatio));
long oldMaxToken = maxTokens.get();
if (newMaxToken > oldMaxToken) {    maxTokens.compareAndSet(oldMaxToken, newMaxToken);
}

Demo示例

AdaptiveDemo演示了如何使用自适应限流算法。

1. AdaptiveRule()通过设置下列参数，构建了一个流控规则：

AdaptiveRule rule = new AdaptiveRule();rule.setResource(KEY);
rule.setTargetRatio(0.5);
rule.setExpectRt(0.5);

其中，设置目标通过50%的请求，目标的RT不超过0.5。

1. StableTask()是模拟小流量的情况。
2. RunTask1()和RunTask2()是模拟了两段大流量的情况。
3. 观察输出：

85 send qps is: 5
1564124570560, total:5, pass:5, block:0
84 send qps is: 2
1564124571560, total:2, pass:2, block:0
83 send qps is: 1
1564124572561, total:1, pass:1, block:0
82 send qps is: 8
1564124573560, total:8, pass:8, block:0
81 send qps is: 1
1564124574561, total:1, pass:1, block:0
80 send qps is: 56850
1564124575596, total:56850, pass:6111, block:50739
79 send qps is: 131744
1564124576597, total:131744, pass:17604, block:114140
78 send qps is: 138365
1564124577597, total:138365, pass:21124, block:117241
77 send qps is: 141735
1564124578597, total:141735, pass:25349, block:116386
76 send qps is: 141881
1564124579599, total:141881, pass:30417, block:111464
75 send qps is: 142156
1564124580600, total:142156, pass:32622, block:109534
74 send qps is: 143874
1564124581600, total:143874, pass:39146, block:104728
73 send qps is: 145346
1564124582599, total:145346, pass:39147, block:106199
72 send qps is: 142118
1564124583601, total:142118, pass:46975, block:95144
71 send qps is: 146782
1564124584602, total:146782, pass:56357, block:90424
70 send qps is: 149184
1564124585604, total:149184, pass:67627, block:81557

可以看到从第 80 秒开始，大流量到达，允许通过的数量逐渐在接近用户的目标。

45 send qps is: 3
1564124610616, total:3, pass:3, block:0
44 send qps is: 3
1564124611616, total:3, pass:3, block:0
43 send qps is: 3
1564124612616, total:3, pass:3, block:0
42 send qps is: 2
1564124613617, total:2, pass:2, block:0
41 send qps is: 3
1564124614618, total:3, pass:3, block:0
40 send qps is: 122091
1564124615619, total:122091, pass:60573, block:61518
39 send qps is: 141463
1564124616619, total:141463, pass:50784, block:90680
38 send qps is: 145550
1564124617620, total:145550, pass:58280, block:87270
37 send qps is: 141654
1564124618619, total:141654, pass:69462, block:72191
36 send qps is: 146492
1564124619619, total:146492, pass:84673, block:61819

后面模拟了第二段大流量的到来，可以看到由于在第一次大流量到来时计算了比较准确的桶的容量，因此在第 40 秒刚刚到来大流量时，就已经可以满足用户制定的 50% 通过率的目标。

而大流量突然的到来会导致一瞬间的RT超过用户需求的 0.5 的值，因此在 40 s以后的通过率为了满足RT的需求有所降低，但后面系统稳定后又开始逐步提升通过率。

(2) 参考PID控制器的算法实现（未完成调参）

// 根据PID控制器算法，控制令牌桶发放令牌的速率
protected long syncCountByPid(ClusterNode node, double expectRt) {
    // 参数初始化
    double Kp = 1000, Ki =5, Kd = 0;
    // 把稳定用户设定的Rt作为目标
    double errNum = expectRt - node.avgRt();

    // 每次积分值、差值的计算必须是线程安全的，但只有AtomicLong类型
    // 没有相应double类型，因此需要将double和long类型互转
    err.compareAndSet(err.get(), Double.doubleToLongBits(errNum));
    double integralNum = Double.longBitsToDouble(integral.get()) + errNum;

    integral.compareAndSet(integral.get(), Double.doubleToLongBits(integralNum));
    double countNum = Kp * errNum + Ki * integralNum + Kd * (errNum - Double.longBitsToDouble(err_last.get()));

    err_last.compareAndSet(err_last.get(), Double.doubleToLongBits(errNum));
    return (long)countNum;
}

但为了得到更好的表现，还需要进一步调参。

2.回调洪峰

参考TCP-BBR的流控算法设计

这种方法还没有具体实现，因为发现了一些问题，而且与cocurrency-limits都属于对TCP拥塞控制算法的思想借鉴。因此在实现了上一种方法后，预计先实现PID控制器思路，如PID控制器思路的可行性低于TCP拥塞控制思路，再去着手借鉴TCP-BBR算法尝试效果。

这里可以先把设计的算法和遇到的问题一并解说。设计的算法如下：

• 启动阶段与稳定阶段
  这个阶段可以根据TCP BBR算法，根据实际系统情况，不断调节增益系数，来计算处理速率。

  TCP BBR算法流程图示如下：

  

  那么启动与稳定阶段的算法流程也可类似设计：

  

  启动阶段的增益系数G，TCP BBR算法为 ，是根据 做拟合得到，那么在流控场景中的增益系数，也可以根据CPU使用率的情况做拟合。

  启动阶段过后的稳定阶段：

  • 若CPU使用率未达到规定上限，也全部通过，则说明此阶段流量水位低。
  • 若CPU使用率已达到规定上限，则QPS阈值已达到，设为。当然，针对回调洪峰场景而言，在洪峰到来之前普遍流量水位偏低，这种情况很少达到。

• 回调洪峰阶段
  此时若判断为回调洪峰，开始匀速器模式。根据请求允许的最大延时，以及洪峰的请求量，计算。

  • 若之前CPU使用率未达到规定上限，则先要根据增益系数G不断向上调，
    • 当 时，CPU使用率仍未到上限，则可以按照作为漏桶速度；
    • 当 且 时，说明已达到CPU使用率上限，漏桶速度最大只能为。
  • 若之前CPU使用率已达到规定上限，则漏桶速度最大为。

遇到要思考的问题如下：

原计划是计算洪峰请求量的大小requestQps，然后根据用户设置的maxRt来计算count，但是后来发现难以统计。首先，这个请求量一定不可能是让用户来设定，大多数场景下用户也不知道请求量会有多少。其次，如何界定“突发”的标准也是一个问题，是算20ms内的请求数算突发流量，还是50ms，100ms……？

假设周期标准可以定下来，算出了第一个周期的request，那么第二个周期又到来了一波流量，第二个周期的request是不是要加上上个周期的流量，直到这几个周期加起来是1s才能算出requestQps。但这个计算的时间又会导致请求一直在等待，浪费了一定的时间。

或者用每个周期的request估算requestQps，但又会造成这个估计极大的不准确。

因此，若想使用这个方法来做回调洪峰场景的自适应流控，可能还需要进一步的设计，或彻底改变之前的流控check实现方式，引入队列等等。

与用户洪峰对应的令牌桶方法不同的是，不能通过观察Rt的变化来判断阈值，因为在匀速排队方法下，排队时间占总Rt的大部分，无法衡量系统情况。

目前的先实现了一个比较简单的方法，如果发现超时情况就对count（阈值）加倍,直到cpuUsage不符合要求。

以上就是这个月所做探索的一些思考和总结，下个月会继续自适应限流算法的优化，如有更新的思路，欢迎大家一起讨论。