Sentinel滑动窗口实时统计原理：如何精确计算QPS？

前言

要深入理解Sentinel的限流实现原理，第一步就要搞清楚它的实时指标数据统计是怎么实现的。

你可能会好奇：Sentinel是怎么知道当前每秒有多少请求的？它是怎么统计异常率、平均响应时间的？为什么它能做到实时又准确？

答案就是——滑动窗口算法。

这篇文章，我就带大家一步步拆解滑动窗口的实现原理。为了方便理解，我们不会直接贴Sentinel的源码，而是用一个简化版的QPS统计工具来讲解，核心思想是一样的。

一、从一个简单的问题说起

先思考一个问题：如果让你实现一个QPS统计工具，你会怎么做？

QPS就是每秒请求数嘛，那最简单的办法：

• 搞一个计数器，每秒开始时清零
• 每来一个请求计数器加1
• 想看QPS直接读计数器的值

但这样有个大问题：误差太大了。比如第59秒来1000个请求，第61秒又来1000个请求，那第60秒的时候显示QPS是0，但实际上平均每秒有500个请求。

而且定时清零的方式，在并发场景下也不好处理。

那Sentinel是怎么解决这个问题的呢？答案就是：用滑动窗口。

二、Bucket：统计数据的基本单元

什么是Bucket

在Sentinel中，Bucket（桶） 是统计指标数据的基本单元。一个Bucket记录了一个窗口时间内的所有指标数据。

什么是窗口时间？就是这个Bucket统计多长时间的数据，可以是1秒，也可以是10毫秒，取决于你的配置。

一个Bucket里会统计哪些数据呢？常见的有：

• 请求总数
• 成功数
• 异常数
• 总耗时
• 最小耗时
• 最大耗时

我们简化一下，只统计三个核心指标：成功数、异常数、总耗时。

Bucket的实现

先看Bucket的核心代码：

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

这里用了一个 LongAdder 数组来存储各个指标的计数。

为什么用LongAdder而不是AtomicInteger？ 因为LongAdder在高并发场景下性能更好。它通过分段的思想，减少了CAS竞争，并发修改时性能比AtomicInteger高不少。

那数组的每个元素分别代表什么呢？我们用一个枚举来定义：

// 事件类型
public enum MetricEvent {
    EXCEPTION, // 异常  对应数组下标 0
    SUCCESS,   // 成功  对应数组下标 1
    RT         // 耗时  对应数组下标 2
}

用枚举的 ordinal() 值作为数组下标，从0开始递增，正好对应数组索引。

读写操作

往Bucket里写数据很简单，根据事件类型找到对应的LongAdder，然后add就好了：

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

读数据也类似，调用sum方法获取总数：

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

三、滑动窗口：让数据”动”起来

有了Bucket，我们就能统计一个时间窗口内的数据了。但怎么确保Bucket存的就是最近1秒的数据呢？

用数组实现滑动窗口

Sentinel的做法是：定义一个Bucket数组，根据时间戳来定位数组下标。

举个例子：假设我们要统计每秒的数据，只保留最近1分钟的数据。那：

• Bucket数组大小设为60
• 每个Bucket的窗口时间是1000毫秒（1秒）

如果数组是无限大的，那直接用当前时间戳（去掉毫秒部分）作为索引就行。但内存是有限的，我们只需要最近1分钟的数据，所以数组可以循环使用。

循环利用数组

怎么循环利用？很简单：取余数。

private int calculateTimeIdx(long timeMillis) {
    /**
     * 假设当前时间戳为 1577017699235
     * windowLengthInMs 为 1000 毫秒（1 秒）
     * 则：
     * 将毫秒转为秒 => 1577017699
     * 映射到数组的索引为 => 1577017699 % 60 = 19
     */
    long timeId = timeMillis / windowLengthInMs;
    return (int) (timeId % array.length());
}

用时间戳除以窗口大小，得到一个”时间ID”，再对数组长度取余数，就得到了数组索引。

窗口开始时间

但是光有索引还不够。因为数组是循环使用的，当前时间、一分钟前、一分钟后，可能都会映射到同一个数组位置。怎么知道这个Bucket是当前时间窗口的，还是上一轮的？

答案是：每个Bucket都要记录自己的时间窗口开始时间戳。

怎么计算窗口开始时间？也很简单：

protected long calculateWindowStart(long timeMillis) {
    /**
     * 假设窗口大小为 1000 毫秒
     * timeMillis % windowLengthInMs 就是取得毫秒部分
     * timeMillis - 毫秒数 = 秒部分
     * 这就得到每秒的开始时间戳
     */
    return timeMillis - timeMillis % windowLengthInMs;
}

比如时间戳是1577017699235，窗口大小1000毫秒：

• 毫秒部分是235
• 1577017699235 – 235 = 1577017699000
• 这就是当前窗口的开始时间

四、WindowWrap：给Bucket穿上”时间外衣”

Bucket本身不保存时间窗口信息，所以Sentinel给Bucket加了一个包装类——WindowWrap。

public class WindowWrap<T> {
    // 窗口时间长度（毫秒）
    private final long windowLengthInMs;
    // 开始时间戳（毫秒）
    private long windowStart;
    // 统计数据（就是Bucket）
    private T value;
    
    public WindowWrap(long windowLengthInMs, long windowStart, T value) {
        this.windowLengthInMs = windowLengthInMs;
        this.windowStart = windowStart;
        this.value = value;
    }
}

WindowWrap里存了三样东西：

• windowLengthInMs：窗口大小，比如1000毫秒
• windowStart：窗口开始时间戳，比如1577017699000
• value：真正的统计数据，也就是Bucket

有了开始时间和窗口大小，就能判断一个时间戳是否在这个窗口内：

/**
 * 检查给定的时间戳是否在当前 bucket 中
 */
public boolean isTimeInWindow(long timeMillis) {
    return windowStart <= timeMillis && timeMillis < windowStart + windowLengthInMs;
}

可以这样理解：Bucket负责”记账”，WindowWrap负责告诉我们”这是哪段时间的账”。

五、核心算法：如何根据时间戳定位Bucket

现在到了最关键的部分：给定一个时间戳，怎么找到对应的Bucket？

整个流程是这样的：

1. 根据时间戳算出数组索引
2. 根据时间戳算出窗口开始时间
3. 去数组里找对应的WindowWrap
4. 判断这个WindowWrap是不是当前时间窗口的
5. 如果不是，就重置或者新建

来看完整的代码实现：

/**
 * 根据时间戳获取 bucket
 */
public WindowWrap<T> currentWindow(long timeMillis) {
    if (timeMillis < 0) {
        return null;
    }
    // 1. 获取时间戳映射到的数组索引
    int idx = calculateTimeIdx(timeMillis);
    // 2. 计算 bucket 时间窗口的开始时间
    long windowStart = calculateWindowStart(timeMillis);

    // 3. 从数组中获取 bucket
    while (true) {
        WindowWrap<T> old = array.get(idx);
        
        // 情况一：数组位置为空（项目刚启动，还没填满）
        if (old == null) {
            // 创建新的 bucket 和包装器
            WindowWrap<T> window = new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
            // CAS写入，确保线程安全
            if (array.compareAndSet(idx, null, window)) {
                return window;
            } else {
                Thread.yield();
            }
        }
        // 情况二：正好就是当前时间窗口的 bucket
        else if (windowStart == old.windowStart()) {
            return old;
        }
        // 情况三：当前时间窗口比数组里存的要新，复用旧的 bucket
        else if (windowStart > old.windowStart()) {
            if (updateLock.tryLock()) {
                try {
                    // 重置 bucket，并设置新的时间窗口开始时间
                    return resetWindowTo(old, windowStart);
                } finally {
                    updateLock.unlock();
                }
            } else {
                Thread.yield();
            }
        }
        // 情况四：当前时间窗口比数组里存的还旧（时间倒退？不可能）
        else if (windowStart < old.windowStart()) {
            return new WindowWrap<T>(windowLengthInMs, windowStart, newEmptyBucket(timeMillis));
        }
    }
}

这段代码看起来有点长，但逻辑很清晰，一共四种情况：

情况	说明	处理方式
old == null	数组位置是空的（刚启动没填满）	新建一个，CAS写入
windowStart == old.windowStart()	正好就是当前窗口的Bucket	直接返回
windowStart > old.windowStart()	新窗口来了，旧的可以复用了	加锁重置，设置新的开始时间
windowStart < old.windowStart()	时间倒退了（不可能发生）	返回一个空的

这里用了while(true)循环 + CAS + 锁的方式，保证在高并发下也能正确获取Bucket。对于创建新Bucket用CAS，对于重置旧Bucket用显式锁，兼顾了性能和正确性。

六、获取前一个窗口的Bucket

有时候我们还需要获取前一个时间窗口的Bucket，比如计算QPS的时候可能要用。

怎么找前一个？很简单：

• 当前窗口开始时间 – 窗口大小 = 前一个窗口的开始时间
• 再用同样的方法去数组里找

但有个问题要注意：因为数组是循环使用的，前一个Bucket可能是上一轮的，已经过期了。所以拿到之后还要检查一下时间，确保是有效的。

比如当前窗口开始时间是1595974702000，前一个窗口应该是1595974701000。但因为数组循环，你拿到的可能是1595974641000（整整早了一分钟），那这个就是无效的。

七、整体结构回顾

到这里，滑动窗口的核心实现就讲完了。我们来梳理一下整体结构：

滑动窗口（WindowWrap数组）
   │
   ├── WindowWrap[0]：窗口开始时间xxx，包含一个Bucket
   ├── WindowWrap[1]：窗口开始时间xxx，包含一个Bucket
   ├── WindowWrap[2]：窗口开始时间xxx，包含一个Bucket
   │   ...
   └── WindowWrap[n-1]：窗口开始时间xxx，包含一个Bucket

每个Bucket里：
   ├── LongAdder[0]：异常数
   ├── LongAdder[1]：成功数
   └── LongAdder[2]：总耗时

三者的关系：

• Bucket：负责统计各项指标数据（记账）
• WindowWrap：包装Bucket，记录时间窗口信息（记时间）
• 滑动窗口：WindowWrap数组，循环使用（整体结构）

总结与思考

滑动窗口是Sentinel最核心的数据结构之一，理解了它，就理解了Sentinel指标统计的基础。

几个关键要点再回顾一下：

1. 用数组 + 取模实现循环：数组大小固定，用时间戳取模定位索引，实现循环利用
2. 时间窗口开始时间是关键：因为数组会循环使用，所以必须靠窗口开始时间来区分”这是哪一轮”的数据
3. WindowWrap包装Bucket：Bucket只管统计，WindowWrap管时间，职责分离
4. 并发安全很重要：高并发下获取Bucket，用CAS创建、用锁重置，保证正确性
5. LongAdder性能更优：相比AtomicInteger，LongAdder在高并发写场景下性能更好

思考一下：

• 为什么不直接用定时任务每秒新建一个Bucket？（误差大、并发问题、GC压力）
• 窗口大小设为多少合适？（太大不精确，太小开销大，要根据场景权衡）
• 如果我想统计最近10秒的QPS，怎么用这些Bucket算出来？（遍历连续的10个Bucket加起来）

这篇文章我们讲了滑动窗口的基本原理和核心数据结构。下一篇，我们将继续深入，看看Sentinel是怎么基于滑动窗口实现完整的指标统计的。