4. 滑动窗口限流算法：环形数组实现高效计数器

滑动窗口算法是限流领域最常用的精确控制手段之一。它解决了固定窗口算法在窗口边界突发流量时的“临界突变”问题，通过将时间窗口细分为多个小格子，让限流判断更加平滑和准确。本节将深入剖析滑动窗口原理，并给出基于环形数组的 Go 语言高效实现。

4.1 滑动窗口核心原理

滑动窗口的核心思想是：将固定时间窗口（如 1 秒）划分为 N 个等长的小区间（slot），每个 slot 独立记录请求计数；窗口整体随着时间推移，每次向前移动一个 slot 的步长，并丢弃最旧的 slot 数据，从而形成“滑动”效果。

对比维度 固定窗口算法 滑动窗口算法
窗口边界 整点对齐，如 00:00~00:01 随当前时间动态对齐
突发容忍度 窗口后半段可突发至 2 倍阈值 任意时刻不超过阈值
精度 粗粒度，依赖窗口大小 细粒度，精度由 slot 数量决定
实现复杂度 低，仅需一个计数器 中，需维护多个 slot 和指针
适用场景 对精度要求不高的简单限流 需要精确控制 QPS 的核心接口
精度与性能的权衡： slot 数量越多，限流精度越高，但内存占用和计算开销也越大。通常将 1 秒划分为 10~100 个 slot 即可满足大部分业务场景。

4.2 环形数组数据结构

滑动窗口的底层存储最适合使用环形数组（Ring Buffer）。环形数组通过固定大小的数组和两个指针（头指针、尾指针）实现循环复用，避免频繁的内存分配和释放。

环形数组优势：
  • O(1) 插入和删除： 只需移动指针，无需数据搬移。
  • 固定内存： 预分配数组，运行时无 GC 压力。
  • 天然支持滑动： 指针循环移动即代表窗口滑动。
环形数组滑动窗口结构图 slot[0] slot[1] slot[2] slot[3] slot[4] slot[5] slot[6] head (最旧) tail (最新) 时间滑动方向 → 说明： 绿色 slot 为当前窗口有效数据；橙色 slot 为即将过期数据；红色 slot 为已过期数据。 head 指向最旧有效 slot，tail 指向最新 slot。每次滑动时 head 前移，新数据覆盖旧 slot。

4.3 Go 语言高效实现

下面给出一个基于环形数组的滑动窗口计数器实现，核心数据结构包含：

  • slots []int64： 环形数组，每个元素存储对应 slot 内的请求计数。
  • windowSize int64： 窗口总时长，单位毫秒。
  • slotCount int： slot 数量。
  • slotDuration int64： 每个 slot 的时长 = windowSize / slotCount。
  • head int： 当前窗口最旧 slot 的索引。
  • lastTime int64： 上次操作的时间戳（毫秒），用于计算滑动步数。
package slidingwindow

import (
    "sync"
    "time"
)

// SlidingWindow 基于环形数组的滑动窗口计数器
type SlidingWindow struct {
    mu           sync.Mutex
    slots        []int64
    windowSize   int64 // 毫秒
    slotCount    int
    slotDuration int64 // 毫秒
    head         int   // 最旧 slot 索引
    lastTime     int64 // 上次操作时间戳（毫秒）
}

// NewSlidingWindow 创建滑动窗口
// windowSize: 窗口大小，如 1000ms
// slotCount: slot 数量，如 10
func NewSlidingWindow(windowSize time.Duration, slotCount int) *SlidingWindow {
    return &SlidingWindow{
        slots:        make([]int64, slotCount),
        windowSize:   windowSize.Milliseconds(),
        slotCount:    slotCount,
        slotDuration: windowSize.Milliseconds() / int64(slotCount),
        head:         0,
        lastTime:     time.Now().UnixMilli(),
    }
}

// Incr 增加一次请求计数，返回当前窗口总计数
func (sw *SlidingWindow) Incr() int64 {
    sw.mu.Lock()
    defer sw.mu.Unlock()

    now := time.Now().UnixMilli()
    sw.advance(now)

    // 计算当前时间对应的 slot 索引
    tail := (sw.head + int((now-sw.lastTime)/sw.slotDuration)) % sw.slotCount
    sw.slots[tail]++

    // 累加当前窗口所有 slot 计数
    var total int64
    for i := 0; i < sw.slotCount; i++ {
        total += sw.slots[i]
    }
    return total
}

// advance 推进窗口，清理过期 slot
func (sw *SlidingWindow) advance(now int64) {
    elapsed := now - sw.lastTime
    if elapsed < sw.slotDuration {
        return // 时间未跨越一个 slot，无需滑动
    }

    // 计算需要滑动的 slot 数
    steps := int(elapsed / sw.slotDuration)
    if steps > sw.slotCount {
        steps = sw.slotCount // 最多滑动整个窗口
    }

    for i := 0; i < steps; i++ {
        sw.head = (sw.head + 1) % sw.slotCount
        sw.slots[sw.head] = 0 // 清空过期 slot
    }

    sw.lastTime = now
}
并发安全： 上述实现使用 sync.Mutex 保证线程安全。在高并发场景下，可考虑使用 atomic 操作或分段锁进一步优化性能。

4.4 滑动窗口限流完整示例

将滑动窗口计数器与限流逻辑结合，实现一个完整的限流器：

// RateLimiter 滑动窗口限流器
type RateLimiter struct {
    window *SlidingWindow
    limit  int64 // 窗口内允许的最大请求数
}

func NewRateLimiter(windowSize time.Duration, slotCount int, limit int64) *RateLimiter {
    return &RateLimiter{
        window: NewSlidingWindow(windowSize, slotCount),
        limit:  limit,
    }
}

// Allow 判断当前请求是否允许通过
func (rl *RateLimiter) Allow() bool {
    total := rl.window.Incr()
    return total <= rl.limit
}

4.5 性能对比与选型建议

实现方式 内存占用 单次操作耗时 精度 推荐场景
固定窗口 ~16 字节 < 10 ns 低 非关键路径、日志限流
滑动窗口（环形数组） ~80 + N*8 字节 ~50 ns（N=10） 高 API 网关、核心业务限流
令牌桶 ~48 字节 ~20 ns 中 允许突发、平滑流量
漏桶 ~64 字节 ~30 ns 中 严格整形、削峰填谷
工程建议： 对于大多数微服务限流场景，推荐使用滑动窗口算法，slot 数量设为 10~20 即可在精度和性能之间取得良好平衡。如果对内存极度敏感（如嵌入式环境），可退化为固定窗口或令牌桶。

4.6 边界情况与避坑指南

  • 时间回拨： 如果系统时间发生回拨，advance 方法中的 elapsed 可能为负值。建议在 advance 开头增加 if elapsed < 0 { sw.lastTime = now; return } 处理。
  • slot 数量选择： slot 数量过少（如 2 个）会导致精度退化接近固定窗口；过多（如 1000 个）则每次累加开销增大。推荐 10~50 个。
  • 窗口初始化： 首次请求时，所有 slot 均为 0，head 指向 slot[0]，lastTime 为当前时间，无需特殊处理。
  • 高并发累加： 如果单 slot 内计数极高，可将 slots 类型改为 []atomic.Int64，减少锁竞争。

滑动窗口算法以其精确的限流能力和适中的实现复杂度，成为生产环境中最常用的限流方案之一。结合环形数组的 Go 实现，可以在保证高性能的同时，有效抵御突发流量对后端服务的冲击。

← 上一章 📖 返回目录 下一章 →