高可用之限流-06-slide window 滑动窗口 sentinel 源码

时间：2024-10-18 14:01:58

限流系列

开源组件 rate-limit: 限流

高可用之限流-01-入门介绍

高可用之限流-02-如何设计限流框架

高可用之限流-03-Semaphore 信号量做限流

高可用之限流-04-fixed window 固定窗口

高可用之限流-05-slide window 滑动窗口

高可用之限流-06-slide window 滑动窗口 sentinel 源码

高可用之限流-07-token bucket 令牌桶算法

高可用之限流 08-leaky bucket漏桶算法

高可用之限流 09-guava RateLimiter 入门使用简介 & 源码分析

sentinel 构建滑动时间窗口

上文介绍过通过调用LeadArray的currentWindow方法返回时间窗口，下面来仔细分析。

public WindowWrap<T> currentWindow() {
    //参数是当前时间
    return currentWindow(TimeUtil.currentTimeMillis());
}

public WindowWrap<T> currentWindow(long time) {
    // 1、根据当前时间，算出该时间的timeId，timeId就是在整个时间轴的位置
    long timeId = time / windowLengthInMs;
    // 2、据timeId算出当前时间窗口在采样窗口区间中的索引idx
    int idx = (int)(timeId % array.length());
    // 3、根据当前时间算出当前窗口应该对应的窗口开始时间time，以毫秒为单位
    time = time - time % windowLengthInMs;
    //4、循环判断直到获取到一个当前时间窗口
    while (true) {
        //5、根据索引idx，在采样窗口数组中取得一个时间窗口old
        WindowWrap<T> old = array.get(idx);
        //6、如果old为空，说明该时间窗口还没有创建、则创建一个时间窗口，并将它插入到array的第idx个位置
        if (old == null) {
            //创建时间窗口，参数：窗口大小，开始时间，桶（保存统计值）
            WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, time, newEmptyBucket());
             // 通过CAS将新窗口设置到数组中去
            if (array.compareAndSet(idx, null, window)) {
                return window;
            } else {
                Thread.yield();
            }
          //7、如果当前窗口的开始时间time与old的开始时间相等，那么说明old就是当前时间窗口，直接返回old
        } else if (time == old.windowStart()) { 
            return old;
        } 
          //8、如果当前窗口的开始时间time大于old的开始时间，则说明old窗口已经过时了，将old的开始时间更新为最新值:time，下一个循环中在第7步返回
        else if (time > old.windowStart()) {
            if (updateLock.tryLock()) {
                try {
                    // if (old is deprecated) then [LOCK] resetTo currentTime.
                    // 重置窗口，重新设置窗口的开始时间，以及把统计值重置
                    return resetWindowTo(old, time);
                } finally {
                    updateLock.unlock();
                }
            } else {
                Thread.yield();
            }
        //这个条件不可能存在,time是当前的时间
        } else if (time < old.windowStart()) {
            // Cannot go through here.
            return new WindowWrap<T>(windowLengthInMs, time, newEmptyBucket());
        }
    }
}

以上就是创建时间窗口的核心的代码了，解释都在代码上面。

分析后可以发现：获取时间窗口原理就是找到当前时间所在的窗口，若窗口不存在则创建，若窗口过时了则重置。

窗口分析

通过分析 rollingCounterInSecond 的监控指标来分析时间窗口，

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

在StatisticNode类中，rollingCounterInSecond创建可以发现windowLengthInMs：时间窗口是500ms，

intervalInSec：时间区间是1s。所以在时间区间是1s内最多只有两个时间窗口，每个窗口长度是500ms；

时间窗口的创建过程如图：

image

1、现在假设当前时间是2018-12-15 14:30:00，对应毫秒是：1544855400000ms，所以timeId = 1544855400000 / 500为：3089710800，对应的idx为0，窗口开始时间time为 time - time % windowLengthInMs还是1544855400000；

2、初始化的时候old为空，所以创建了一个window；

3、倘若过了300ms后，time为1544855400700，这个时候old就是先前窗口了，就会直接返回old窗口：currentWindow；

4、时间继续往前走，又过了400ms后，如图：

image

5、这个时候获取到的timeId为3089710801，对应的idx=为3089710801%2为1，窗口开始时间time为 1544855400500；

6、由于是新的时间窗口，old为空，则重新创建。

7、倘若过了400ms，time为1544855401100：现在得到idx时0，这个时候old是有值的，但是old的windowStart小于time的StartTime，所以需要重置idx0窗口。

8、以此类推：随着时间的流逝，时间窗口也在变化，但是窗口只会在初始化的过程中创建两次，后面若窗口过期了则是重置。

核心流程

1、根据当前时间，算出该时间的timeId，timeId就是在整个时间轴的位置

2、据timeId算出当前时间窗口在采样窗口区间中的索引idx

3、根据当前时间算出当前窗口应该对应的窗口开始时间time，以毫秒为单位

4、循环判断直到获取到一个当前时间窗口

5、根据索引idx，在采样窗口数组中取得一个时间窗口old

如果old为空，说明该时间窗口还没有创建、则创建一个时间窗口，并将它插入到array的第idx个位置

如果当前窗口的开始时间time与old的开始时间相等，那么说明old就是当前时间窗口，直接返回old

如果当前窗口的开始时间time大于old的开始时间，则说明old窗口已经过时了，将old的开始时间更新为最新值:time； 。

参考资料

限流技术总结

固定窗口和滑动窗口算法了解一下

Sentinel之滑动时间窗口设计（二）

限流滑动窗口

限流算法之固定窗口与滑动窗口

限流--基于某个滑动时间窗口限流

【限流算法】java实现滑动时间窗口算法

谈谈高并发系统的限流

漏铜令牌桶

漏桶算法&令牌桶算法理解及常用的算法

流量控制算法——漏桶算法和令牌桶算法

Token Bucket 令牌桶算法

华为-令牌桶算法

简单分析Guava中RateLimiter中的令牌桶算法的实现

相关文章