3、滑动窗口算法：滑动窗口原理、解决临界问题、窗口粒度与精度权衡

固定窗口算法简单，但有个硬伤——临界突变。我当年在做一个电商秒杀系统时，就因为这个吃了大亏。明明每秒限流100次，结果在窗口切换的那一瞬间，流量直接冲到了200。老板盯着监控问我怎么回事，我只能硬着头皮说「算法边界问题」。从那以后，我对滑动窗口就有了执念。

3.1 滑动窗口的核心原理

说白了，滑动窗口就是把一个大窗口切成多个小格子。每个格子独立计数，窗口整体向前滑动时，丢弃最旧的格子，加入最新的格子。这样统计的永远是一个「连续时间段」内的请求总数。

举个例子。假设我们设置1秒限流100次，把1秒切成10个格子，每个格子100毫秒。请求来了，落在哪个格子就加哪个格子的计数。判断是否限流时，把当前格子加上前面9个格子的总数，看看有没有超过100。

我习惯把滑动窗口理解成「移动的栅栏」。栅栏的宽度是窗口大小，栅栏的间距是格子粒度。栅栏每移动一格，就放掉一个旧格子，纳入一个新格子。这样统计窗口内的请求数，永远是最近N个格子的总和。

3.2 临界问题：固定窗口的「阿喀琉斯之踵」

为什么会发生临界问题？你想想看，固定窗口在00:00:00到00:00:01这个窗口内统计了100次请求，然后在00:00:01到00:00:02这个窗口内又统计了100次请求。如果这200次请求都集中在00:00:01这个时间点附近，那实际在1秒内就处理了200次请求。

这就是典型的「窗口边界突刺」。我在项目中遇到过最夸张的情况：固定窗口限流100次/秒，实际瞬时QPS冲到了接近200。监控图上那个尖峰，看着就让人心慌。

滑动窗口怎么解决这个问题的？它没有「重置」这个动作。每个格子独立计数，窗口只是「框住」最近N个格子。请求永远落在当前格子，统计永远基于最近N个格子。没有重置点，就没有边界突刺。

对比维度	固定窗口	滑动窗口
计数方式	整个窗口一个计数器	每个格子独立计数器
重置行为	窗口结束时清零	无重置，格子逐步淘汰
临界突刺	存在，可达2倍限流值	不存在，平滑统计
实现复杂度	低，一个计数器+一个时间戳	中等，需要维护格子数组
内存开销	O(1)	O(N)，N为格子数

3.3 窗口粒度与精度的权衡

这里有个很现实的问题：格子切得越细，精度越高，但代价也越大。我习惯用「格子数」来衡量这个权衡。格子数 = 窗口大小 / 格子粒度。

举个例子。1秒窗口，切10个格子，每个格子100毫秒。精度是100毫秒级别，内存开销是10个计数器。如果切100个格子，每个格子10毫秒，精度到了10毫秒级别，但内存开销是100个计数器。

具体怎么选？我一般按这个思路来：

• 高精度场景（如API网关、流量整形）：窗口大小1秒，格子数20~50，精度20~50毫秒
• 中等精度场景（如业务接口限流）：窗口大小1秒，格子数10~20，精度50~100毫秒
• 低精度场景（如后台任务限流）：窗口大小10秒，格子数10，精度1秒

嗯，这里要注意：格子数不是越多越好。格子数多了，每次判断限流时要遍历的格子就多，CPU开销就上去了。而且格子太细，统计结果反而容易受单个请求的干扰。

3.4 滑动窗口的代码实现

我习惯用环形数组来实现滑动窗口。为什么用环形数组？因为淘汰旧格子时不需要移动数据，只需要移动头指针。效率高，内存也稳定。

// 滑动窗口限流器 - 环形数组实现
public class SlidingWindowRateLimiter {
    // 格子数组，每个格子记录该时间片内的请求数
    private final AtomicInteger[] slots;
    // 格子数量
    private final int slotCount;
    // 每个格子的时间跨度（毫秒）
    private final long slotDurationMs;
    // 窗口总大小（毫秒）
    private final long windowDurationMs;
    // 窗口内允许的最大请求数
    private final int maxRequests;
    // 当前格子索引
    private volatile int currentSlotIndex;
    // 当前格子的起始时间
    private volatile long currentSlotStartTime;
    
    public SlidingWindowRateLimiter(int maxRequests, long windowDurationMs, int slotCount) {
        this.maxRequests = maxRequests;
        this.windowDurationMs = windowDurationMs;
        this.slotCount = slotCount;
        this.slotDurationMs = windowDurationMs / slotCount;
        this.slots = new AtomicInteger[slotCount];
        for (int i = 0; i < slotCount; i++) {
            slots[i] = new AtomicInteger(0);
        }
        this.currentSlotIndex = 0;
        this.currentSlotStartTime = System.currentTimeMillis();
    }
    
    public boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 1. 检查是否需要滑动到下一个格子
        advanceSlotIfNeeded(now);
        
        // 2. 计算当前窗口内的总请求数
        int totalRequests = 0;
        for (int i = 0; i < slotCount; i++) {
            totalRequests += slots[i].get();
        }
        
        // 3. 判断是否超过限流阈值
        if (totalRequests >= maxRequests) {
            return false; // 限流
        }
        
        // 4. 在当前格子计数
        slots[currentSlotIndex].incrementAndGet();
        return true;
    }
    
    private void advanceSlotIfNeeded(long now) {
        long elapsed = now - currentSlotStartTime;
        if (elapsed < slotDurationMs) {
            return; // 还在当前格子内，不需要滑动
        }
        
        // 计算需要滑动的格子数
        int slotsToAdvance = (int)(elapsed / slotDurationMs);
        // 限制最大滑动数，防止时间跳跃过大
        slotsToAdvance = Math.min(slotsToAdvance, slotCount);
        
        synchronized (this) {
            for (int i = 0; i < slotsToAdvance; i++) {
                currentSlotIndex = (currentSlotIndex + 1) % slotCount;
                slots[currentSlotIndex].set(0); // 重置新格子的计数
            }
            currentSlotStartTime += slotsToAdvance * slotDurationMs;
        }
    }
}

这段代码的核心逻辑就三步：检查是否需要滑动、统计窗口内总请求数、判断是否限流。注意看 advanceSlotIfNeeded 方法，它处理了时间跳跃的情况——比如系统暂停了一段时间后恢复，需要一次性滑动多个格子。

3.5 滑动窗口的变体与应用场景

实际项目中，滑动窗口有几个常见的变体：

• 精确滑动窗口：每个请求都记录时间戳，判断时统计窗口内所有请求。精度最高，但内存开销大（需要存储每个请求的时间戳）。适合请求量小的场景。
• 格子滑动窗口：就是上面代码实现的那种。精度取决于格子粒度，内存固定。适合大多数业务场景。
• 混合滑动窗口：结合精确和格子两种方式。热点时段用精确统计，非热点时段用格子统计。我曾在某个高并发项目里用过这种方案，效果不错。

我个人最推荐格子滑动窗口。它实现简单，内存可控，精度也够用。你想想看，对于1秒限流100次的场景，100毫秒的精度已经能挡住绝大多数突刺了。没必要为了那几十毫秒的精度提升，把系统搞复杂。

滑动窗口的适用场景很广：API网关限流、消息队列消费速率控制、数据库连接池保护、微服务熔断降级……只要是需要平滑限流的地方，滑动窗口都是首选。它不像令牌桶那样需要预占资源，也不像漏桶那样强制匀速，它只是「统计最近一段时间内的请求数」，简单直接。