滑动窗口限流算法解析：解决固定窗口边界突刺问题与Java实现

在核心接口的压测中，有时会遇到一个令人困惑的现象：系统监控显示的QPS尚未达到预设的阈值，限流却已提前触发，导致正常请求被误拦截。这背后，一个常见的原因是简单计数器在时间窗口切换时存在致命缺陷，而解决方案正是滑动窗口限流。本文将深入剖析其原理，提供手写实现，并探讨其应用场景。

一、从“一刀切”到“精细化”：限流算法的演进

为了理解滑动窗口的必要性，我们先回顾几种经典的限流算法及其局限性。

1. 计数器固定窗口算法：简单的陷阱
这是最基础的限流实现。例如，限制每秒最多处理100个请求。

public class FixedWindowRateLimiter {
    // 当前窗口的请求计数
    private final AtomicInteger counter = new AtomicInteger(0);
    // 窗口大小（毫秒）
    private final long windowSizeInMillis = 1000;
    // 当前窗口的开始时间
    private volatile long windowStart = System.currentTimeMillis();
    // 阈值
    private final int threshold = 100;

    public boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        // 关键！判断是否进入下一个时间窗口
        if (currentTime - windowStart > windowSizeInMillis) {
            // 重置窗口和计数器
            windowStart = currentTime;
            counter.set(0);
        }
        // 判断是否超过阈值
        return counter.incrementAndGet() <= threshold;
    }
}

该实现简单直观，但存在著名的边界突刺问题。假设每秒限流100次，如果在第0.9秒至第1.0秒内涌入100个请求，紧接着在第1.0秒至第1.1秒内又涌入100个请求。虽然两个独立的1秒窗口都未超限，但在实际0.2秒的时间跨度内，系统却承受了双倍阈值的流量冲击，可能导致系统过载。

2. 漏桶与令牌桶：平滑但不够“实时”

• 漏桶算法以恒定速率处理请求，能平滑流量，但面对突发流量时缺乏灵活性。
• 令牌桶算法允许一定程度的突发，但其设计更侧重于长期平均速率控制。

那么，为什么还需要滑动窗口？其核心价值在于，它在保持相对简单实现的同时，提供了比固定窗口更精确的实时流量统计能力，特别适用于需要对最近一段时间（而非上一个完整周期）流量进行严格控制的场景，如API网关、实时监控等。

二、滑动窗口限流：像“地铁闸机”一样工作

可以借助一个比喻来理解滑动窗口：

• 固定窗口：工作人员每分钟统计一次进站人数，超限则关闭闸机。这无法阻止在59秒和61秒（分属不同窗口）的瞬间高峰。
• 滑动窗口：系统实时统计最近一分钟内的进站人数。这个“一分钟”的窗口是滑动的，每秒都在更新。只要这个滑动窗口内人数超限，就立即限流，控制显然更为精准。

在技术实现上，滑动窗口主要有两种思路：

1. 基于小时间片的滑动窗口：将一个大窗口（如1分钟）划分为多个小时间片（如6个10秒）。请求到来时，清理掉窗口外的时间片，统计剩余时间片内的总请求数。此法平衡了精度与内存开销。
2. 基于请求时间戳队列的滑动窗口：记录每个请求的时间戳。判断时，移除队列中超出窗口的旧时间戳，然后检查当前队列长度。此方法非常精确，但在高并发下维护队列的开销较大。

以下我们以实现更常见、性能更优的基于时间片的滑动窗口为例。

三、手把手实现一个滑动窗口限流器

我们实现一个线程安全的滑动窗口限流器。它将1秒（1000毫秒）的窗口划分为10个时间片（每个100毫秒），每个时间片独立计数。

/**
 * 基于时间片的滑动窗口限流器
 */
public class SlidingWindowRateLimiter {
    // 核心结构 - 使用循环数组存储每个时间片的计数
    private final AtomicInteger[] timeSlices;
    // 窗口内时间片的数量
    private final int sliceCount;
    // 每个时间片的长度（毫秒）
    private final long sliceMillis;
    // 窗口总大小（毫秒）
    private final long windowMillis;
    // 限流阈值
    private final int threshold;
    // 当前时间片索引（在循环数组中的位置）
    private final AtomicInteger cursor = new AtomicInteger(0);
    // 上一次访问的时间戳
    private volatile long lastTimestamp = System.currentTimeMillis();

    public SlidingWindowRateLimiter(int windowMillis, int sliceCount, int threshold) {
        this.windowMillis = windowMillis;
        this.sliceCount = sliceCount;
        this.threshold = threshold;
        this.sliceMillis = windowMillis / sliceCount;
        this.timeSlices = new AtomicInteger[sliceCount];
        // 初始化循环数组
        for (int i = 0; i < sliceCount; i++) {
            timeSlices[i] = new AtomicInteger(0);
        }
    }

    public synchronized boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        int currentIndex = cursor.get();
        // 核心逻辑 - 计算自上次请求以来经过的时间
        long elapsedTime = currentTime - lastTimestamp;

        if (elapsedTime >= windowMillis) {
            // 情况1：距离上一次请求已超过一个完整窗口，所有时间片清零
            for (int i = 0; i < sliceCount; i++) {
                timeSlices[i].set(0);
            }
            cursor.set(0);
            lastTimestamp = currentTime;
            currentIndex = 0;
        } else if (elapsedTime > sliceMillis) {
            // 情况2：滑过了若干个完整的时间片
            int moveSteps = (int) (elapsedTime / sliceMillis);
            int newIndex = (currentIndex + moveSteps) % sliceCount;
            // 将滑过的过期时间片计数清零
            for (int i = 1; i <= moveSteps; i++) {
                int clearIndex = (currentIndex + i) % sliceCount;
                timeSlices[clearIndex].set(0);
            }
            cursor.set(newIndex);
            lastTimestamp = lastTimestamp + moveSteps * sliceMillis;
            currentIndex = newIndex;
        }
        // 情况3：仍在当前时间片内，无需滑动

        // 统计当前整个滑动窗口内的总请求数
        int sum = 0;
        for (AtomicInteger counter : timeSlices) {
            sum += counter.get();
        }
        // 判断是否超过阈值
        if (sum < threshold) {
            // 未超限，当前时间片计数+1
            timeSlices[currentIndex].incrementAndGet();
            return true;
        } else {
            // 超限，拒绝请求
            return false;
        }
    }
}

实现要点：

• AtomicInteger[] timeSlices：使用循环数组模拟时间片的滑动，避免数组拷贝。
• elapsedTime >= windowMillis分支：处理长时间无请求后，窗口需完全重置的情况。
• 统计sum：累加所有未过期时间片的计数，得到滑动窗口内的瞬时总请求数。

性能考量：上述实现使用synchronized保证tryAcquire方法的原子性。在单机QPS极高的场景下，这可能成为瓶颈。生产环境中可考虑使用LongAdder替代AtomicInteger，或采用分桶（Striped）机制减少锁竞争。对于分布式场景，则需借助如Redis等外部存储。

四、滑动窗口的实战应用与进阶思考

1. 在API网关中的应用
现代API网关（如Spring Cloud Gateway）是滑动窗口限流的主战场。其内置的限流过滤器常支持滑动窗口模式，用于精确控制每个路由、服务或用户在单位时间内的访问次数。

2. 混合限流策略
在实际系统中，通常采用分层、混合的限流策略以取得最佳效果：

• 第一层（全局/API级）：使用滑动窗口进行精确的秒级/分钟级流量控制。
• 第二层（用户/资源级）：使用令牌桶对特定用户或资源进行平滑限流，允许合理突发。
• 第三层（系统保护级）：使用漏桶或信号量在最底层进行隔离保护，防止级联故障。

3. 分布式滑动窗口挑战与实现
在分布式系统中实现滑动窗口，核心挑战在于状态共享与时钟同步。一个经典的方案是借助Redis的sorted set（ZSET）数据结构：

• 将请求时间戳作为score，请求标识作为member存入ZSET。
• 每次请求时，使用ZREMRANGEBYSCORE命令移除窗口外的旧数据。
• 使用ZCARD命令统计当前窗口内的请求数。
• 通过设置合适的key过期时间来自动清理数据。

五、滑动窗口限流核心要点总结

• 问题本质：固定窗口限流在时间窗口切换边界存在“双倍流量”突刺的风险。
• 解决方案：滑动窗口限流通过实时统计最近N秒/分钟内的请求量来实现更精准的控制。
• 实现关键：
  1. 将大窗口划分为小时间片或记录请求时间戳队列。
  2. 每次请求时，清理滑动窗口之前的过期数据。
  3. 统计剩余有效数据的总和并与阈值比较。
• 生产考量：高并发下需注意单机实现的性能优化（如使用LongAdder）；分布式场景下可基于Redis的ZSET实现。
• 算法选型：滑动窗口适用于需要精确控制短时实时流量的场景；若需平滑突发，可结合令牌桶；若需严格恒定速率，则可考虑漏桶。