关于sentinel:sentinel滑动窗口流量统计

StatisticSlot 次要统计两类数据：

• 线程数
• 申请数，也就是 QPS

对于线程数统计比较简单，是通过外部保护 LongAdder 进行的以后线程数的统计，每进入一个线程加 1，线程执行完减 1，从而失去线程数。
对于 QPS 的统计则要简单点，其中用到了滑动窗口的原理。上面就来重点剖析下实现的详情。

Bucket

Sentinel 应用 Bucket 统计一个窗口工夫内的各项指标数据，这些指标数据包含申请总数、胜利总数、异样总数、总耗时、最小耗时、最大耗时等，而一个 Bucket 能够是记录 1s 内的数据，也能够是 10ms 内的数据，这个工夫长度称为窗口工夫。

public class MetricBucket {
    /**
     * 存储各事件的计数，比方异样总数、申请总数等
     */
    private final LongAdder[] counters;
    /**
     * 这段事件内的最小耗时
     */
    private volatile long minRt;
}

Bucket 记录一段时间内的各项指标数据用的是一个 LongAdder 数组，LongAdder 保障了数据批改的原子性，并且性能较 AtomicInteger 体现更好。数组的每个元素别离记录一个工夫窗口的申请总数、异样数、部耗时。
Sentinel 应用枚举类型 MetricEvent 的 ordinal 属性作为下标，当须要获取 Bucket 记录总的胜利申请数或异样总数、总的申请解决耗时，可依据事件类型 (MetricEvent) 从 Bucket 的 LongAdder 数组中获取对应的 LongAdder，并调用 sum 办法获取：

// 假如事件为 MetricEvent.SUCCESS
public long get(MetricEvent event) {// MetricEvent.SUCCESS.ordinal()为 1
    return counters[event.ordinal()].sum();}

须要记录申请数时操作如下：

// 假如事件为 MetricEvent.RT
public void add(MetricEvent event, long n) {// MetricEvent.RT.ordinal()为 2
     counters[event.ordinal()].add(n);
}

滑动窗口

咱们心愿晓得某个接口的每秒解决胜利申请数 (胜利 QPS)、申请均匀耗时(avg rt)，咱们只须要管制 Bucket 统计一秒钏的指标数据即可。Sentinel 是如何实现的呢？它定义了一个 Bucket 数组，依据工夫戳来定位到数组的下标。假如咱们须要统计每 1 秒解决的申请数，且只须要保留最近一分钟的数据，那么 Bucket 数组的大小就能够设置为 60，每个 Bucket 的 windowLengthInMs(窗口工夫) 大小就是 1000ms。
咱们不可能当然也不须要有限存储 Bucket，如果说只须要保留一分钟的数据，那咱们就能够将 Bucket 的大小设置为 60 并循环应用，防止频繁创立 Bucket。这种状况下如何定位 Bucket 呢？做法是将以后工夫戳去掉毫秒局部等到以后秒数，再将失去的秒数与数组长度取余，就能失去以后工夫窗口的 Bucket 在数组中的地位。
例如给定工夫戳计算数组索引：

private int calculateTimeIdx(long timeMillis) {
        /**
         * 假如以后工夫戳为 1577017699235
         * windowLengthInMs 为 1000 毫秒（1 秒）* 则
         * 将毫秒转为秒 => 1577017699
         * 而后对数组长度取余 => 映射到数组的索引
         * 取余是为了循环利用数组
         */
        long timeId = timeMillis / windowLengthInMs;
        return (int) (timeId % array.length());
    }

因为数组是循环应用的，以后工夫戳与一分钟之前的工夫戳与后一分钟的工夫戳都会映射到数组中的同一个 Bucket，因而，必须要可能判断获得的 Bucket 是否是统计以后工夫窗口内的指标数据，这便要数组每个元素都存储 Bucet 工夫窗口的开始工夫戳。那开始工夫如果计算呢？

    protected long calculateWindowStart(long timeMillis) {
        /**
         * 假如窗口大小为 1000 毫秒，即数组每个元素存储 1 秒钟的统计数据
         * timeMillis % windowLengthInMs 就是获得毫秒局部
         * timeMillis - 毫秒数 = 秒局部
         * 这就失去每秒的开始工夫戳
         */
        return timeMillis - timeMillis % windowLengthInMs;
    }

WindowWrap

因为 Bucket 本身并不保留工夫窗口信息，所以 Sentinel 给 Bucket 加了一个包装类 WindowWrap，用于记录 Bcuket 的工夫窗口。

public class WindowWrap<T> {
    /**
     * 窗口工夫长度（毫秒）*/
    private final long windowLengthInMs;
    /**
     * 开始工夫戳（毫秒）*/
    private long windowStart;
    /**
     * 工夫窗口的内容，在 WindowWrap 中是用泛型示意这个值的，* 但实际上就是 MetricBucket 类
     */
    private T value;
    public WindowWrap(long windowLengthInMs, long windowStart, T value) {
        this.windowLengthInMs = windowLengthInMs;
        this.windowStart = windowStart;
        this.value = value;
    }
}

咱们只有晓得窗口的开始工夫和窗口工夫大小，给定一个工夫戳，就能晓得该工夫戳是否在 Bucket 的窗口工夫内。

/**
     * 查看给定的工夫戳是否在以后 bucket 中。*
     * @param timeMillis 工夫戳，毫秒
     * @return
     */
    public boolean isTimeInWindow(long timeMillis) {return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;}

通过工夫戳定位 Bucket

Bucket 用于统计各项指标数据，WindowWrap 用于记录 Bucket 的工夫窗口信息，记录窗口的开始工夫和窗口的大小，WindowWrap 数组就是一个滑动窗口。
当接管到一个申请时，可依据申请的工夫戳计算出一个数组索引，从滑动窗口 (WindowWrap) 中获取一个 WindowWrap，从而获取 WindowWrap 包装的 Bucket，调用 Bucket 的 add 办法记录相应的事件。

/**
     * 依据工夫戳获取 bucket
     *
     * @param timeMillis 工夫戳（毫秒）* @return 如果工夫无效，则在提供的工夫戳处显示以后存储桶项；如果工夫有效，则为空
     */
    public WindowWrap<T> currentWindow(long timeMillis) {if (timeMillis < 0) {return null;}
        // 获取工夫戳映射到的数组索引
        int idx = calculateTimeIdx(timeMillis);
        // 计算 bucket 工夫窗口的开始工夫
        long windowStart = calculateWindowStart(timeMillis);

        // 从数组中获取 bucket
        while (true) {WindowWrap<T> old = array.get(idx);
            // 个别是我的项目启动时，工夫未达到一个周期，数组还没有存储满，没有到复用阶段，所以数组元素可能为空
            if (old == null) {
                // 创立新的 bucket，并创立一个 bucket 包装器
                WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
                // cas 写入，确保线程平安，冀望数组下标的元素是空的，否则就不写入，而是复用
                if (array.compareAndSet(idx, null, window)) {return window;} else {Thread.yield();
                }
            }
            // 如果 WindowWrap 的 windowStart 正好是以后工夫戳计算出的工夫窗口的开始工夫，则就是咱们想要的 bucket
            else if (windowStart == old.windowStart()) {return old;}
            // 复用旧的 bucket
            else if (windowStart > old.windowStart()) {if (updateLock.tryLock()) {
                    try {
                        // 重置 bucket，并指定 bucket 的新工夫窗口的开始工夫
                        return resetWindowTo(old, windowStart);
                    } finally {updateLock.unlock();
                    }
                } else {Thread.yield();
                }
            }
            // 计算出来的以后 bucket 工夫窗口的开始工夫比数组以后存储的 bucket 的工夫窗口开始工夫还小，// 间接返回一个空的 bucket 就行
            else if (windowStart < old.windowStart()) {return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            }
        }
    }

protected WindowWrap<MetricBucket> resetWindowTo(WindowWrap<MetricBucket> w, long time) {
        // Update the start time and reset value.
        // 重置 windowStart
        w.resetTo(time);
        MetricBucket borrowBucket = borrowArray.getWindowValue(time);
        if (borrowBucket != null) {w.value().reset();
            w.value().addPass((int)borrowBucket.pass());
        } else {w.value().reset();}
        return w;
 }

下面代码通过以后工夫戳计算以后是的工夫窗口的 Bucket(new Bucket)在数组中的索引，以驻 Bucket 工夫窗口的开始工夫，通过索引从数组中获得 Bucket(old bucket)。

• 当索引处不存在 Bucket 时，创立一个新的 Bucket，并线程平安的写入到索引处，而后将 Bucket 返回
• 当 old Bucket 不为空时，且 old Bucket 工夫窗口的开始工夫与以后计算失去的 new Bucket 的工夫窗口开始工夫相等，则该 Bucket 就是以后要找的 Bucket，间接返回
• 当计算的 new Bucket 工夫窗口的开始工夫大于以后数组存储的 old Bucket 工夫窗口的开始工夫时，能够复用这个 old Bucket，以线程平安重置
• 当计算出 new Bucket 工夫窗口的开始工夫小于以后数组存储的 old Bucket 工夫窗口的开始工夫时，间接返回一个空的 Bucket。

如何获取以后工夫戳的前一个 Bucket 呢，答案是依据以后工夫戳计算以后 Bucket 的工夫窗口开始工夫，用以后 Bucket 的工夫窗口开始工夫减去一个窗口大小就能够定位出前一个 Bucket 了。
须要留神的时，数组是循环应用的，所以以后 Bucket 与计算出的 Bucket 可能相差一个滑动窗口也可能相差一个以上，所以须要依据 Bucket 的工夫窗口开始工夫与以后工夫戳进行比拟，如果跨了一个周期就是有效的。

总结

• WindowWrap 用于包装 Bucket，随着 Bucket 一起创立
• WindowWrap 数组实现滑动窗口，Bucket 只负责统计各项指标数据，WindowWrap 用于记录 Bucket 的工夫窗口信息
• 定位 Bucket 实际上是定位 WindowWrap，拿到 WindowWrap 就能够拿到 Bucket