乐趣区

关于sentinel:sentinel之滑动窗口实现

本章次要来聊一下限流神奇 sentinel 的滑动窗口逻辑,来看看它是如何实现限流的。

知识点

  • 什么是滑动窗口协定
  • 滑动窗口原理
  • sentinel 如何实现的

什么是滑动窗口协定

在聊滑动窗口之前,咱们要先看一下固定窗口是什么,这里我间接援用掘金上叫 yz 的作者一张图:

从图中咱们能够看到就是将窗口分成固定大小的若干块,在每一块中都受到阈值的限度。然而这里存在一个毛病:如果申请是在 16t 到 26t 之间超过阈值的,固定窗口是辨认不进去的。

正是因为固定窗口存在这种缺点,所以才有了滑动窗口的呈现。在网络中,滑动窗口就是用于网络流量的管制的。它就是随着工夫不停向前挪动,保障单位工夫周期内的流量不会超过阈值。

滑动窗口原理

上面咱们来看一下滑动窗口的实现原理,先上图:

以这张图来介绍,对于固定窗口,咱们晓得如果有申请跨两个窗口并且在每个窗口中又没有达到阈值,则理论相加可能会超过阈值。而滑动窗口顾明思义是随着工夫一直滑动的,如上图,当一次申请在 0 -500ms 块中近 300ms 的时候一次发动 60 并发申请,窗口就会滑动到以 300ms 作为开始地位向后取 1000ms 单位的工夫作为新窗口,也就是 300-1300ms,而后在此工夫窗口中的申请都会统计起来和阈值做比拟判断,这样就解决了固定窗口申请超出阈值的问题。最不便的了解就是:以以后工夫作为截止工夫,向前取单位工夫窗口的长度作为一个窗口,而后不停向前滑动。

sentinel 是如何实现的

为什么要讲 sentinel 是如何实现的,因为我最近在看 sentinel 源码,并且发现如同不是依照下面那个滑动窗口的思路实现的,先发一下我看到的后果

我看了好几篇文章都是提到改良,其实 就是说原来的滑动窗口算法耗资源、性能不好,所以做了一些优化,然而在我看来是一种取舍,优化的后果就是没法齐全精细化统计单位窗口内的申请,看来看去我发现还是这幅图比拟合乎我的思路。上面上源码(基于 1.6.0 版本)

咱们晓得 sentinel 用责任链模式连贯所有插槽,每个规定对应一个插槽,其余逻辑都不看了,和限流无关,间接看 FlowSlot,这个插槽就是作用流控的

这里就点一下,其余逻辑不多介绍,间接看滑动窗口实现。先看下这个类 com.alibaba.csp.sentinel.node.StatisticNode,这个类就是对申请的信息进行收集统计,这里要关注一下rollingCounterInSecondrollingCounterInMinute,别离是每秒、没分钟进行滚动统计的变量,都是 ArrayMetric 类型。

看下 ArrayMetric

这个 data 是十分重要的,它是个 LeapArray<MetricBucket> 类型,理论用的是 OccupiableBucketLeapArray,看下构造函数

能够看到这里设置了工夫窗口大小以及块数,这个就是滑动窗口的设置,默认是 2 块,每块 500ms。

咱们在 qps 限流的时候会先去获取以后工夫窗口的所有曾经通过的 qps,而后去和阈值做比拟。这里的 data.currentWindow() 十分重要,sentinel 滑动窗口的实现原理就在这里

这里的 TimeUtil.currentTimeMillis() 可不是间接获取以后工夫,它是准实时的

这里我也有点懵,不晓得为什么不间接获取 System.currentTimeMillis(),而要通过一个线程不停去更新工夫,晓得起因的敌人能够留言。持续往下看

之前咱们说过 sentinel 默认将工夫窗口分为 2 块,calculateTimeIdx就是计算以后工夫应该属于哪一块,找对应的下标。这是滑动的外围逻辑

timeId % array.length() 这里用到了除模运算,将值固定在 array.length() 的范畴内。calculateWindowStart用于计算以后工夫对应的块的起始工夫。我把正文删掉,持续往下看

这里有 4 种状况:
1)以后块不存在,新建一个;
2)以后工夫属于以后块,间接返回;
3)以后工夫计算出的实践起始工夫大于以后块起始工夫,重置以后块为以后工夫并返回;
4)以后工夫计算出的实践起始工夫小于以后块起始工夫,工夫倒退,返回一个新块,个别不会产生,除非本人手动批改服务器工夫之类的操作;

要害看第 1、3 两种。
第一种不存在的状况下,会用 WindowWrap 来把以后窗口包装起来,并用 CAS 进行设置。WindowWrap比较简单,就是记录了窗口块工夫大小、起始工夫以及相干数据统计,次要看 newEmptyBucket,这里创立了一个新块

这个块自身就是 MetricBucket

所有申请的指标事件都用 LongAdder 来统计,蕴含这些事件

比方咱们获取已通过的的申请,则是获取 PASS 这个事件对应的数据。
再来看下第三种状况,这里会去重置窗口块

把块起始工夫设置为以后计算出来的块起始工夫,而后通过 reset 把所有事件的统计信息重置为 0

问题

这里是我看滑动窗口这块逻辑发现的问题,仅做探讨,先抛一副图来说

比方咱们在第 0、1 块的时候继续申请进来,假如每块都是 50 笔,此时曾经生成 2 块了,随着工夫进行,在 1100ms 时又有 50 笔申请进来,此时的申请会将第 0 块给重置到第二块中,因为第一块记录的 50 笔加上第二块新来的 50 笔总和并没有超过阈值 100,所以不会被限流,然而实际上有可能第 0 块还有局部申请没解决完(假如有 30 笔是在 400ms 的时候进来的),那么实践上 400-1100ms(周期 700ms)这个时间段通过的申请就有 130 笔,超过了阈值,这就呈现了固定窗口的问题。所以在 sentinel 代码中也指明了精度问题

是不是咱们得依据理论状况设置更多的块,细化工夫窗口以达到更高的精读?欢送留言给出你们的意见和想法。

总结

sentinel 源码的咱们认为比拟难的应该在限流这一块了,通过对源码的浏览学会了用除模运算来管制范畴,晓得如何实现滑动窗口。当然还是有一些精度的疑难存在的。
参考资料
https://juejin.cn/post/698285…

退出移动版