sentinel滑动时间窗口算法学习

滑动时间窗口

先不说sentinel的算法实现，先说什么是滑动时间窗口，
我们在进行限流的时候，比如通过QPS进行限流，那假如我们以秒为单位，举个例子：
我设置了限流规则，qps是10

如果不使用滑动窗口算法，在统计qps的时候，就有可能会有问题，比如：
在0 - 500ms中的请求数是0，但是在500ms - 1000 ms的请求数是10；在1000ms - 1500ms 之间又进来了5个请求，此时只判断了1000ms - 2000 ms之间的请求数
因为没有把1S进行拆分多个窗口，所以在1000ms之后，请求进来的时候，统计的是1000ms - 2000ms之间的请求数
场景1：如果在1100ms的时候，进来了5个请求，此时统计1000ms - 2000ms 之间的QPS，满足10这个阈值，就会让请求进来；但是如果是从1100ms 往前算1000ms的话，实际上应该统计的是 100ms - 1100ms之间 这1S的请求数，此时会发现，100 - 1100ms之间的请求数，早就大于10了
所以，如果不使用滑动窗口算法，其实也没太大影响，只是统计的请求数会不是特别准确，对系统会有一定的压力

下面再来说，使用滑动窗口算法的情况
假如我们把2S拆分为4个窗口，每个窗口是500ms
还是上面的假设：在0 - 500ms中的请求数是0，但是在500ms - 1000 ms的请求数是10
场景1：如果当前1100ms请求进来，有3次请求，滑动时间窗口算法会统计500ms - 1500ms 这1S之内的值，会发现此时这个时间段内，请求数量已经达到10了，就会限流，具体的演变过程是这样的：

在1100ms，请求进来的时候，会计算一下，1100ms应该在哪个窗口中，因为只有两个窗口：

公式1：

1100ms / 500ms = 2
2 % 窗口数量2 = 0
1
2

得到当前应该在第0个窗口

接着会比较两个窗口的起始时间
现在0号窗口的起始时间是0ms，那1100ms所在窗口的起始时间怎么计算？

公式2：

1100ms - 1100ms % 500 = 1000ms
1

此时就会得到：1100ms所在窗口的起始时间是1000ms，但是实际0号窗口的起始时间是0ms
1000 > 0,此时就会把0-500ms这个窗口进行reset，然后将0号窗口的起始时间设置为1000ms

此时再来统计请求数量，就把两个窗口的请求数量累加即可，1100ms在请求进来的时候，会发现，已经达到了10的阈值，就会进行限流

这里只是把1S拆分为两个窗口来举例，如果我们把窗口拆的越多，理论上而言，统计会越准确，但是成本也会越大，因为这些数据存储在内存中，会有一定的消耗

sentinel滑动窗口算法的实现

StatisticNode在初始化的时候，有这么一行代码

private transient volatile Metric rollingCounterInSecond = new ArrayMetric(SampleCountProperty.SAMPLE_COUNT,
        IntervalProperty.INTERVAL);

第一个参数默认是2，第二个参数是1000ms；


public LeapArray(int sampleCount, int intervalInMs) {
   
    AssertUtil.isTrue(sampleCount > 0, "bucket count is invalid: " + sampleCount);
    AssertUtil
1
2
3
4
5
6
7
8
9