📚 课程目录第4章滑动窗口算法详解

4. 滑动窗口算法详解：窗口划分、时间片统计、解决临界突变问题、在行情推送场景中的实践

滑动窗口算法是金融场景中应用最广泛的限流算法之一。它通过将时间窗口细分为多个时间片，并利用滑动统计的方式，有效解决了固定窗口算法在窗口边界处的“临界突变”问题，使得限流判断更加平滑和精确。

4.1 核心概念：窗口划分与时间片统计

滑动窗口算法的核心思想是将一个大的时间窗口（例如1秒）划分为若干个更小的时间片（例如10个100ms的时间片）。每个时间片独立统计请求计数，窗口整体则统计所有时间片的累计计数。随着时间推移，窗口整体向前滑动，丢弃最旧的时间片数据，纳入最新的时间片数据。

  关键参数定义：
  窗口大小（Window Size）： 限流的时间跨度，例如 1s、10s、1min。
时间片大小（Slot Size）： 窗口内最小统计单元，例如 100ms、200ms。
时间片数量（Slot Count）： 窗口大小 / 时间片大小，例如 1s / 100ms = 10 个时间片。
阈值（Threshold）： 整个窗口内允许的最大请求数。

4.2 解决临界突变问题

固定窗口算法在窗口切换的瞬间存在明显的缺陷：如果上一个窗口的后半段和下一个窗口的前半段都涌入了大量请求，虽然单个窗口内未超限，但两个窗口交界处的瞬时流量可能达到阈值的两倍，造成系统冲击。

滑动窗口算法通过以下机制解决此问题：

细粒度统计： 窗口内任意时刻的计数都是最近一个完整窗口大小的累计值，不存在“窗口重置”的突变点。
连续滑动： 判断是否限流时，总是基于当前时间点向前回溯一个窗口大小，统计该时间段内的总请求数。
平滑过渡： 请求的过期是逐个时间片发生的，而非整个窗口瞬间过期，流量曲线更加平滑。

对比维度	固定窗口算法	滑动窗口算法
窗口边界处理	窗口结束时计数清零，存在突变	窗口连续滑动，无清零突变
临界流量控制	边界处可能允许 2 倍阈值流量	任意时刻均严格限制在阈值内
统计精度	粗粒度，依赖窗口大小	细粒度，精度由时间片大小决定
内存开销	低，仅需一个计数器	较高，需维护多个时间片计数器

实践建议： 在金融行情推送场景中，建议将时间片大小设置为 50ms~200ms。时间片越小，限流精度越高，但内存和计算开销也越大。对于每秒万级以上的高并发行情，100ms 时间片（即 1 秒窗口划分为 10 个时间片）通常能在精度和性能之间取得良好平衡。

4.3 在行情推送场景中的实践

行情推送是金融系统中对限流要求最为苛刻的场景之一。行情数据（如股票实时价格、订单簿快照）通常以毫秒级频率推送，且要求推送延迟极低。滑动窗口算法在此场景下的实践要点如下：

4.3.1 场景需求分析

推送频率控制： 限制单个客户端每秒接收的行情推送条数，例如 100 条/秒。
突发流量容忍： 允许短时间内的微小突发，但整体不能超过阈值。
低延迟判断： 限流判断本身不能成为性能瓶颈，通常要求在微秒级完成。

4.3.2 实现架构

4.3.3 核心代码实现（伪代码）

// 滑动窗口限流器核心逻辑
class SlidingWindowRateLimiter {
    // 时间片数组，每个元素存储该时间片内的请求计数
    private int[] slotCounts;
    // 时间片数量
    private int slotCount;
    // 每个时间片的时长（毫秒）
    private long slotDurationMs;
    // 窗口总阈值
    private int threshold;
    // 当前窗口累计计数
    private int totalCount;
    // 当前时间片索引
    private int currentSlotIndex;
    // 上次滑动时间戳
    private long lastSlideTime;

    public SlidingWindowRateLimiter(int windowSizeMs, int slotCount, int threshold) {
        this.slotCount = slotCount;
        this.slotDurationMs = windowSizeMs / slotCount;
        this.threshold = threshold;
        this.slotCounts = new int[slotCount];
        this.totalCount = 0;
        this.currentSlotIndex = 0;
        this.lastSlideTime = System.currentTimeMillis();
    }

    // 每次请求到达时调用
    public synchronized boolean allowRequest() {
        long now = System.currentTimeMillis();
        slideWindow(now);  // 滑动窗口，更新计数

        if (totalCount < threshold) {
            // 允许请求，增加当前时间片计数
            slotCounts[currentSlotIndex]++;
            totalCount++;
            return true;
        } else {
            // 拒绝请求
            return false;
        }
    }

    // 滑动窗口：计算需要滑过的时间片数量，并更新累计计数
    private void slideWindow(long now) {
        long elapsedTime = now - lastSlideTime;
        int slotsToSlide = (int) (elapsedTime / slotDurationMs);

        if (slotsToSlide > 0) {
            // 限制最大滑动数量，防止长时间不请求后一次性滑过太多
            slotsToSlide = Math.min(slotsToSlide, slotCount);

            for (int i = 0; i < slotsToSlide; i++) {
                // 移动到下一个时间片
                currentSlotIndex = (currentSlotIndex + 1) % slotCount;
                // 减去被滑出的时间片计数
                totalCount -= slotCounts[currentSlotIndex];
                // 重置该时间片计数
                slotCounts[currentSlotIndex] = 0;
            }
            lastSlideTime = now;
        }
    }
}

4.3.4 性能优化技巧

优化方向	具体措施	效果
内存优化	使用环形数组（Circular Array）存储时间片计数，避免数组拷贝	O(1) 时间复杂度滑动，内存占用固定
计算优化	使用位运算替代取模运算（当 slotCount 为 2 的幂时）	减少 CPU 指令周期
并发优化	使用 LongAdder 或 Striped Lock 减少锁竞争	提升高并发下的吞吐量
批量处理	对于行情推送，可批量更新时间片计数，减少同步次数	降低锁开销

注意事项： 在行情推送场景中，限流器本身不能成为新的瓶颈。建议将限流逻辑内联到推送线程中，避免额外的线程切换。同时，对于超过阈值的请求，应采用“静默丢弃”策略，避免向客户端发送限流错误码，减少不必要的网络开销。

4.4 本章小结

滑动窗口算法通过时间片划分和连续滑动统计，有效解决了固定窗口算法的临界突变问题，在金融行情推送等高精度限流场景中得到了广泛应用。其核心在于平衡统计精度与计算开销，合理选择时间片大小和实现方式。在实际生产环境中，建议结合环形数组和批量更新技术，将单次限流判断的耗时控制在微秒级别，以满足金融系统对低延迟的严苛要求。