4. 限流算法（三）：滑动窗口计数器（分桶）算法原理、精度与性能权衡、Go实现

固定窗口计数器在窗口边界处存在流量突刺的缺陷：若请求集中在窗口末尾与下一窗口开头，瞬间流量可达阈值的两倍。滑动窗口计数器通过将时间窗口细分为多个“桶”，让窗口以更细粒度平滑滑动，从而大幅提升限流精度。

4.1 核心原理：从“整窗跳跃”到“逐桶滑动”

滑动窗口计数器将固定时间窗口 T 划分为 N 个等长的时间片（桶），每个桶独立记录该时间片内的请求计数。窗口的滑动不再是整窗跳跃，而是每次前进一个桶的时长，窗口覆盖最新的 N 个桶。

上图中，窗口大小为 6 个桶。当时间推进一个桶的时长后，窗口丢弃最旧的桶 1，加入最新的桶 8，始终保持覆盖最新的 6 个桶。桶的粒度越细，窗口滑动越平滑，限流精度越高。

4.2 精度与性能的权衡

桶的数量 N 是滑动窗口算法的核心参数，直接决定了精度与内存/计算开销的平衡。

4.3 Go 语言实现：分桶滑动窗口

以下实现使用环形数组存储桶计数，避免每次滑动时移动数据。通过互斥锁保证并发安全。

package slidingwindow

import (
    "sync"
    "time"
)

// SlidingWindow 分桶滑动窗口限流器
type SlidingWindow struct {
    mu          sync.Mutex
    buckets     []int64   // 环形数组，每个桶存储该时间片内的请求数
    bucketSize  time.Duration // 每个桶的时间跨度
    windowSize  int64     // 窗口总大小（纳秒）
    bucketCount int       // 桶的数量
    head        int       // 当前最旧桶的索引
    lastTime    time.Time // 上次更新时间
    threshold   int64     // 窗口内允许的最大请求数
}

// NewSlidingWindow 创建滑动窗口限流器
// window: 窗口总时长，如 1s
// bucketCount: 桶的数量，推荐 10
// threshold: 窗口内允许的最大请求数
func NewSlidingWindow(window time.Duration, bucketCount int, threshold int64) *SlidingWindow {
    return &SlidingWindow{
        buckets:     make([]int64, bucketCount),
        bucketSize:  window / time.Duration(bucketCount),
        windowSize:  window.Nanoseconds(),
        bucketCount: bucketCount,
        head:        0,
        lastTime:    time.Now(),
        threshold:   threshold,
    }
}

// Allow 判断是否允许当前请求通过
func (sw *SlidingWindow) Allow() bool {
    sw.mu.Lock()
    defer sw.mu.Unlock()

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

    // 计算当前窗口内总请求数
    var total int64
    for i := 0; i < sw.bucketCount; i++ {
        total += sw.buckets[i]
    }

    if total >= sw.threshold {
        return false
    }

    // 将请求计入当前桶
    currentBucket := (sw.head + sw.bucketCount - 1) % sw.bucketCount
    sw.buckets[currentBucket]++
    return true
}

// advance 推进窗口，丢弃过期的桶
func (sw *SlidingWindow) advance(now time.Time) {
    elapsed := now.Sub(sw.lastTime).Nanoseconds()
    if elapsed < sw.bucketSize.Nanoseconds() {
        return
    }

    // 计算需要跳过的桶数
    skipBuckets := int(elapsed / sw.bucketSize.Nanoseconds())
    if skipBuckets > sw.bucketCount {
        skipBuckets = sw.bucketCount // 最多跳过所有桶
    }

    for i := 0; i < skipBuckets; i++ {
        sw.head = (sw.head + 1) % sw.bucketCount
        sw.buckets[sw.head] = 0 // 清空被丢弃的桶
    }

    sw.lastTime = now
}

4.4 实现要点与边界处理

• 环形数组索引： head 指向最旧的桶，新请求写入 (head + bucketCount - 1) % bucketCount，避免数据搬移。
• 时间跳跃处理： 若两次请求间隔超过一个窗口，advance 会跳过所有桶，重置整个窗口，防止计数残留。
• 桶大小对齐： bucketSize = window / bucketCount 必须整除，否则最后一个桶的时间跨度不一致，影响精度。
• 原子操作替代锁： 高并发场景可使用 sync/atomic 配合无锁环形队列，但实现复杂度显著增加。

4.5 滑动窗口 vs 固定窗口：精度对比