Sentinel源码解析之滑动窗口

朴灿烈づ我的快乐病毒、 2022-12-31 02:29 154阅读 0赞

> 原创不易，转载请注明出处

### 文章目录 ###

*   *   *  前言
         *  1.sentinel滑动窗口实现原理
         *  2.sentinel使用滑动窗口都统计啥
         *  3.滑动窗口源码实现
         *   *  3.1 MetricBucket
             *  3.2 WindowWrap
             *  3.3 LeapArray

--------------------

### 前言 ###

本文主要是介绍下sentinel指标收集统计的一个重要基础组件那就是滑动窗口，将分为三个小节介绍，首先是大体介绍下sentinel滑动窗口的基本实现原理，心里先有个大概的印象，然后我们在看下sentinel使用这个滑动窗口用来统计哪些指标，最后就是进行源码剖析，看看代码是怎样实现，怎样写的。

### 1.sentinel滑动窗口实现原理 ###

这里我们先介绍下这个sentinel中的滑动窗口是怎么回事，然后在说下它是怎么实现的。  
滑动窗口可以先拆为滑动跟窗口两个词，先介绍下`窗口`，你可以这么理解，一段是时间就是窗口，比如说我们可以把这个1s认为是1个`窗口`  
这个样子我们就能将1分钟就可以划分成60个`窗口`了，这个没毛病吧。如下图我们就分成了60个`窗口`（这个多了我们就画5个表示一下）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_1_color_FFFFFF_t_70]  
比如现在处于第1秒上，那1s那个窗口就是`当前窗口`，就如下图中红框表示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70]  
好了，窗口就介绍完了，现在在来看下`滑动`，滑动很简单，比如说现在时间由第1秒变成了第2秒，就是从当前这个窗口---->下一个窗口就可以了，这个时候下一个窗口就变成了当前窗口，之前那个当前窗口就变成了上一个窗口，这个过程其实就是滑动。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 1]  
好了，介绍完了滑动窗口，我们再来介绍下这个sentinel的滑动窗口的实现原理。  
其实你要是理解了上面这个滑动窗口的意思，sentinel实现原理就简单了。  
先是介绍下窗口中里面都存储些啥。也就是上面这个小框框都有啥。

1.  它得有个开始时间吧，不然你怎么知道这个窗口是什么时候开始的
2.  还得有个窗口的长度吧，不然你咋知道窗口啥时候结束，通过这个开始时间+窗口长度=窗口结束时间，就比如说上面的1s，间隔1s
3.  最后就是要在这个窗口里面统计的东西，你总不能白搞些窗口，搞些滑动吧。所以这里就存储了一堆要统计的指标（qps，rt等等）

说完了这一个小窗口里面的东西，就得来说说是怎么划分这个小窗口，怎么管理这些小窗口的了，也就是我们的视野得往上提高一下了，不能总聚在这个小窗口上。

1.  要知道有多少个小窗口，在sentinel中也就是sampleCount，比如说我们有60个窗口。
2.  还有就是intervalInMs，这个intervalInMs是用来计算这个窗口长度的，intervalInMs/窗口数量= 窗口长度。也就是我给你1分钟，你给我分成60个窗口，这个时候窗口长度就是1s了，那如果我给你1s，你给我分2个窗口，这个时候窗口长度就是500毫秒了，这个1分钟，就是intervalInMs。
3.  再就是存储这个窗口的容器（这里是数组），毕竟那么多窗口，还得提供计算当前时间窗口的方法等等

最后我们就来看看这个当前时间窗口是怎么计算的。  
咱们就拿 60个窗口，这个60个窗口放在数组中，窗口长度是1s 来计算，看看当前时间戳的一个时间窗口是是在数组中哪个位置。比如说当前时间戳是1609085401454 ms  
算出秒 = 1609085401454 /1000（窗口长度）  
在数组的位置 = 算出秒 %数组长度

我们再来计算下 某个时间戳对应窗口的起始时间，还是以1609085401454 来计算  
窗口startTime = 1609085401454 - 1609085401454%1000（窗口长度）  
这里1609085401454%1000（窗口长度） 能算出来它的毫秒值，也就是454 ， 减去这个后就变成了1609085401000

好了，sentinel 滑动窗口原理就介绍完成了。

### 2.sentinel使用滑动窗口都统计啥 ###

我们来介绍下使用这个滑动窗口都来统计啥

public enum MetricEvent { 
        /** * Normal pass. */
        PASS,// 通过
        /** * Normal block. */
        BLOCK,// 拒绝的
        EXCEPTION,// 异常
        SUCCESS,//成功
        RT,// 耗时
        /** * Passed in future quota (pre-occupied, since 1.5.0). */
        OCCUPIED_PASS
    }

这是最基本的指标，然后通过这些指标，又可以计算出来比如说最大，最小，平均等等的一些指标。

### 3.滑动窗口源码实现 ###

我们先来看下这个窗口里面的统计指标的实现 MetricBucket

#### 3.1 MetricBucket ####

这个MetricBucket 是由LongAdder数组组成的，一个LongAdder就是一个MetricEvent ，也就是第二小节里面的PASS ，BLOCK等等。  
我们稍微看下就可以了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 2]  
可以看到它在实例化的时候创建一个LongAdder 数据，个数就是那堆event的数量。这个LongAdder 是jdk8里面的原子操作类，你可以把它简单认为AtomicLong。然后下面就是一堆get 跟add 的方法了，这里我们就不看了。  
接下来再来看看那这个窗口的实现WindowWrap类

#### 3.2 WindowWrap ####

先来看下这个成员  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 3]  
窗口长度，窗口startTime ，指标统计的 都有了，下面的就没啥好看的了，我们再来看下的一个方法吧  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 4]  
就是判断某个时间戳是不是在这个窗口中  
时间戳要大于等于窗口开始时间 && 小于这个结束时间。

接下来再来看下这个管理窗口的类LeapArray

#### 3.3 LeapArray ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 5]  
看下它的成员， 窗口长度， 样本数sampleCount 也就是窗口个数， intervalInMs ，再就是窗口数组  
看看它的构造方法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 6]  
这个构造方法其实就是计算出来这个窗口长度，创建了窗口数组。  
再来看下一个很重要的方法

/** * Get bucket item at provided timestamp. * * * 获取某个时间的窗口 * @param timeMillis a valid timestamp in milliseconds * @return current bucket item at provided timestamp if the time is valid; null if time is invalid */
        public WindowWrap<T> currentWindow(long timeMillis) { 
            if (timeMillis < 0) { 
                return null;
            }
            // 计算出窗口在哪个 元素位置处
            int idx = calculateTimeIdx(timeMillis);
            // 计算当前时间的bucket 的开始时间
            // Calculate current bucket start time.
            long windowStart = calculateWindowStart(timeMillis);
    
            /* * Get bucket item at given time from the array. * * (1) Bucket is absent, then just create a new bucket and CAS update to circular array. * (2) Bucket is up-to-date, then just return the bucket. * (3) Bucket is deprecated, then reset current bucket and clean all deprecated buckets. */
            while (true) { 
    
                // 获取这个位置的一个时间窗口
                WindowWrap<T> old = array.get(idx);
    
                // 说明之前没有过
                if (old == null) { 
                    /* * B0 B1 B2 NULL B4 * ||_______|_______|_______|_______|_______||___ * 200 400 600 800 1000 1200 timestamp * ^ * time=888 * bucket is empty, so create new and update * * If the old bucket is absent, then we create a new bucket at {@code windowStart}, * then try to update circular array via a CAS operation. Only one thread can * succeed to update, while other threads yield its time slice. */
    
                    // 创建窗口
                    WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
                    if (array.compareAndSet(idx, null, window)) { 
                        // Successfully updated, return the created bucket.
    
                        /// 设置成功，就返回创建的bucket
                        return window;
                    } else { 
                        // Contention failed, the thread will yield its time slice to wait for bucket available.
                        //线程将提供它的时间片来等待桶可用
                        Thread.yield();
                    }
    
    
                    // 老得窗口起始时间 与 现在的窗口起始时间一致，说明这个是一个窗口
                } else if (windowStart == old.windowStart()) { 
                    /* * B0 B1 B2 B3 B4 * ||_______|_______|_______|_______|_______||___ * 200 400 600 800 1000 1200 timestamp * ^ * time=888 * startTime of Bucket 3: 800, so it's up-to-date * * If current {@code windowStart} is equal to the start timestamp of old bucket, * that means the time is within the bucket, so directly return the bucket. */
                    return old;
    
                    // 现在的窗口时间 大于之前的窗口起始时间
                } else if (windowStart > old.windowStart()) { 
                    /* * (old) * B0 B1 B2 NULL B4 * |_______||_______|_______|_______|_______|_______||___ * ... 1200 1400 1600 1800 2000 2200 timestamp * ^ * time=1676 * startTime of Bucket 2: 400, deprecated, should be reset * * If the start timestamp of old bucket is behind provided time, that means * the bucket is deprecated. We have to reset the bucket to current {@code windowStart}. * Note that the reset and clean-up operations are hard to be atomic, * so we need a update lock to guarantee the correctness of bucket update. * * The update lock is conditional (tiny scope) and will take effect only when * bucket is deprecated, so in most cases it won't lead to performance loss. */
    
                    /// 获取锁
                    if (updateLock.tryLock()) { 
                        try { 
                            // Successfully get the update lock, now we reset the bucket.
                            // 重置这个窗口 并返回
                            return resetWindowTo(old, windowStart);
                        } finally { 
                            /// 释放锁
                            updateLock.unlock();
                        }
                    } else { 
                        // Contention failed, the thread will yield its time slice to wait for bucket available.
                        Thread.yield();
                    }
    
                    /// 如果当前的一个时间窗口要小于之前的窗口开始时间
                } else if (windowStart < old.windowStart()) { 
                    // Should not go through here, as the provided time is already behind.
                    //不应该通过这里，因为提供的时间已经落后了。
                    return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
                }
            }
        }

获取某个时间的窗口方法。  
先是计算出来这个时间戳对应窗口在窗口数组索引位置，以及窗口的起始时间。计算方法就是第一小节里面介绍的。  
接着就是从这个窗口数组中获取这个位置的窗口，然后判断是不是等于null，如果等于null的话，说明之前没有过，就创建一个新的窗口，然后塞到数组中，返回就可以了，如果这个窗口不是null的话，先比较下这个窗口起始时间是否相等，如果相等的话，直接返回，如果是你要获取窗口时间 比 现在有的那个起始时间要小的话，说明你要的那个东西已经过期了，直接new一个给你了，如果是你要获取的时间比现在的那个起始时间要大的话，说明数组中那个比较老了，这个时候加锁，重置一下窗口，其实就是将里面的统计值重置成0 ，然后重置一下窗口起始时间就可以了，然后释放锁就可以了。  
好了，到这我们sentinel的滑动窗口就解析完成了，其实这里面还有很多代码，这里我们就不一一看了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_1_color_FFFFFF_t_70]: /images/20221120/575bff4ac8964b9ea71bb937e1fdd9a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70]: /images/20221120/276d7dae9db247f784bfa15781593671.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 1]: /images/20221120/7a85ebfa85924a27a9f2d7ba885a3410.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 2]: /images/20221120/69b1b034de2f46b88d59877274b87bcd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 3]: /images/20221120/f888c9a5408c47bda087c5b7f7701078.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 4]: /images/20221120/db7d52564a0a4a75834dc5d3e2b6e2fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 5]: /images/20221120/e6a42e79e12641e7985ed39bb48e6ceb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3l1YW5zaGFuZ3NoZW5naHVv_size_16_color_FFFFFF_t_70 6]: /images/20221120/d5f14d572c7945a5bfe93600addf86b1.png