sentinel之滑动窗口实现

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

知识点

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

什么是滑动窗口协议

在聊滑动窗口之前,我们要先看一下固定窗口是什么,这里我直接引用掘金上叫 yz 的作者一张图:
sentinel之滑动窗口实现_第1张图片
从图中我们可以看到就是将窗口分成固定大小的若干块,在每一块中都受到阈值的限制。但是这里存在一个缺点:如果请求是在 16t 到 26t 之间超过阈值的,固定窗口是识别不出来的。

正是因为固定窗口存在这种缺陷,所以才有了滑动窗口的出现。在网络中,滑动窗口就是用于网络流量的控制的。它就是随着时间不停向前移动,保证单位时间周期内的流量不会超过阈值。

滑动窗口原理

下面我们来看一下滑动窗口的实现原理,先上图:
sentinel之滑动窗口实现_第2张图片
以这张图来介绍,对于固定窗口,我们知道如果有请求跨两个窗口并且在每个窗口中又没有达到阈值,则实际相加可能会超过阈值。而滑动窗口顾明思义是随着时间不断滑动的,如上图,当一次请求在0-500ms块中近300ms的时候一次发起60并发请求,窗口就会滑动到以300ms作为开始位置向后取1000ms单位的时间作为新窗口,也就是300-1300ms,然后在此时间窗口中的请求都会统计起来和阈值做比较判断,这样就解决了固定窗口请求超出阈值的问题。最方便的理解就是:以当前时间作为截止时间,向前取单位时间窗口的长度作为一个窗口,然后不停向前滑动。

sentinel是如何实现的

为什么要讲sentinel是如何实现的,因为我最近在看sentinel源码,并且发现好像不是按照上面那个滑动窗口的思路实现的,先发一下我看到的结果
sentinel之滑动窗口实现_第3张图片
我看了好几篇文章都是提到改进,其实 就是说原来的滑动窗口算法耗资源、性能不好,所以做了一些优化,但是在我看来是一种取舍,优化的结果就是没法完全精细化统计单位窗口内的请求,看来看去我发现还是这幅图比较符合我的思路。下面上源码(基于1.6.0版本)

我们知道 sentinel 用责任链模式连接所有插槽,每个规则对应一个插槽,其他逻辑都不看了,和限流无关,直接看FlowSlot,这个插槽就是作用流控的
sentinel之滑动窗口实现_第4张图片
这里就点一下,其他逻辑不多介绍,直接看滑动窗口实现。先看下这个类com.alibaba.csp.sentinel.node.StatisticNode,这个类就是对请求的信息进行收集统计,这里要关注一下rollingCounterInSecondrollingCounterInMinute,分别是每秒、没分钟进行滚动统计的变量,都是ArrayMetric类型。
image.png
看下ArrayMetric
sentinel之滑动窗口实现_第5张图片
这个data是非常重要的,它是个LeapArray类型,实际用的是OccupiableBucketLeapArray,看下构造函数
sentinel之滑动窗口实现_第6张图片
可以看到这里设置了时间窗口大小以及块数,这个就是滑动窗口的设置,默认是 2 块,每块 500ms 。
sentinel之滑动窗口实现_第7张图片
我们在qps限流的时候会先去获取当前时间窗口的所有已经通过的qps,然后去和阈值做比较。这里的data.currentWindow()非常重要,sentinel 滑动窗口的实现原理就在这里
image.png
这里的TimeUtil.currentTimeMillis()可不是直接获取当前时间,它是准实时的
sentinel之滑动窗口实现_第8张图片
这里我也有点懵,不知道为什么不直接获取System.currentTimeMillis(),而要通过一个线程不停去更新时间,知道原因的朋友可以留言。继续往下看
sentinel之滑动窗口实现_第9张图片
之前我们说过 sentinel 默认将时间窗口分为 2 块,calculateTimeIdx就是计算当前时间应该属于哪一块,找对应的下标。这是滑动的核心逻辑
sentinel之滑动窗口实现_第10张图片
timeId % array.length()这里用到了除模运算,将值固定在 array.length() 的范围内。calculateWindowStart用于计算当前时间对应的块的起始时间。我把注释删掉,继续往下看
sentinel之滑动窗口实现_第11张图片
这里有4种情况:
1)当前块不存在,新建一个;
2)当前时间属于当前块,直接返回;
3)当前时间计算出的理论起始时间大于当前块起始时间,重置当前块为当前时间并返回;
4)当前时间计算出的理论起始时间小于当前块起始时间,时间倒退,返回一个新块,一般不会发生,除非自己手动修改服务器时间之类的操作;

关键看第1、3两种。
第一种不存在的情况下,会用WindowWrap来把当前窗口包装起来,并用CAS进行设置。WindowWrap比较简单,就是记录了窗口块时间大小、起始时间以及相关数据统计,主要看newEmptyBucket,这里创建了一个新块
sentinel之滑动窗口实现_第12张图片
这个块本身就是MetricBucket
sentinel之滑动窗口实现_第13张图片
所有请求的指标事情都用LongAdder来统计,包含这些事件
sentinel之滑动窗口实现_第14张图片
比如我们获取已通过的的请求,则是获取PASS这个事件对应的数据。
再来看下第三种情况,这里会去重置窗口块
sentinel之滑动窗口实现_第15张图片
把块起始时间设置为当前计算出来的块起始时间,然后通过reset把所有事件的统计信息重置为0
sentinel之滑动窗口实现_第16张图片

问题

这里是我看滑动窗口这块逻辑发现的问题,仅做探讨,先抛一副图来说
sentinel之滑动窗口实现_第17张图片
比如我们在第0、1块的时候持续请求进来,假设每块都是 50 笔,此时已经生成2块了,随着时间进行,在 1100ms 时又有 50 笔请求进来,此时的请求会将第0块给重置到第二块中,由于第一块记录的50笔加上第二块新来的50笔总和并没有超过阈值100,所以不会被限流,但是实际上有可能第0块还有部分请求没处理完(假设有 30 笔是在 400ms 的时候进来的),那么理论上 400-1100ms(周期 700ms)这个时间段通过的请求就有 130 笔,超过了阈值,这就出现了固定窗口的问题。所以在 sentinel 代码中也指明了精度问题
sentinel之滑动窗口实现_第18张图片
是不是我们得根据实际情况设置更多的块,细化时间窗口以达到更高的精读?欢迎留言给出你们的意见和想法。

总结

sentinel 源码的我们认为比较难的应该在限流这一块了,通过对源码的阅读学会了用除模运算来控制范围,知道如何实现滑动窗口。当然还是有一些精度的疑问存在的。
参考资料
https://juejin.cn/post/698285...

你可能感兴趣的