3. 限流算法（二）：滑动窗口日志算法原理、内存开销分析、Go实现

固定窗口算法在窗口边界存在“突刺”问题——流量可以在窗口切换瞬间集中涌入，导致后端瞬时过载。滑动窗口日志算法（Sliding Window Log）通过记录每个请求的时间戳，在滑动的时间区间内精确计数，从根本上消除了边界突刺。

3.1 算法原理

滑动窗口日志算法的核心思想是：维护一个有序的时间戳日志，每次请求到达时，移除窗口范围之外的所有过期时间戳，然后判断剩余时间戳数量是否超过阈值。

算法步骤：

1. 记录请求：每个请求到达时，将其时间戳追加到日志尾部。
2. 清理过期：从日志头部移除所有 timestamp < now - windowSize 的记录。
3. 计数判断：统计日志中剩余时间戳数量，若 count < limit 则允许通过，否则拒绝。

3.2 内存开销分析

滑动窗口日志算法的精度优势以内存开销为代价。每个请求都需要在内存中保留一个时间戳，对于高并发场景，内存占用可能成为瓶颈。

3.3 Go 实现：基础版

以下实现使用 sync.Mutex 保护并发安全，时间戳存储为 int64 毫秒值，采用惰性删除策略。

package slidingwindow

import (
    "sync"
    "time"
)

// SlidingWindowLog 滑动窗口日志限流器
type SlidingWindowLog struct {
    mu         sync.Mutex
    timestamps []int64   // 有序时间戳列表（毫秒）
    limit      int       // 窗口内允许的最大请求数
    window     int64     // 窗口大小（毫秒）
}

// NewSlidingWindowLog 创建滑动窗口日志限流器
func NewSlidingWindowLog(limit int, window time.Duration) *SlidingWindowLog {
    return &SlidingWindowLog{
        timestamps: make([]int64, 0, limit),
        limit:      limit,
        window:     window.Milliseconds(),
    }
}

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

    now := time.Now().UnixMilli()
    boundary := now - s.window

    // 1. 清理过期时间戳（惰性删除）
    // 利用二分查找找到第一个未过期的时间戳位置
    left := 0
    right := len(s.timestamps)
    for left < right {
        mid := left + (right-left)/2
        if s.timestamps[mid] < boundary {
            left = mid + 1
        } else {
            right = mid
        }
    }
    s.timestamps = s.timestamps[left:]

    // 2. 判断是否超过阈值
    if len(s.timestamps) >= s.limit {
        return false
    }

    // 3. 记录当前请求时间戳
    s.timestamps = append(s.timestamps, now)
    return true
}

3.4 Go 实现：优化版（对象池 + 预分配）

基础版在高并发下存在两个性能问题：切片频繁扩容和大量短生命周期对象。优化版引入 sync.Pool 和预分配策略。

package slidingwindow

import (
    "sync"
    "time"
)

// OptimizedSlidingWindowLog 优化版滑动窗口日志限流器
type OptimizedSlidingWindowLog struct {
    mu         sync.Mutex
    timestamps []int64
    limit      int
    window     int64
    pool       sync.Pool
}

// NewOptimizedSlidingWindowLog 创建优化版限流器
func NewOptimizedSlidingWindowLog(limit int, window time.Duration) *OptimizedSlidingWindowLog {
    return &OptimizedSlidingWindowLog{
        timestamps: make([]int64, 0, limit),
        limit:      limit,
        window:     window.Milliseconds(),
        pool: sync.Pool{
            New: func() interface{} {
                // 预分配与 limit 等长的切片，减少扩容
                buf := make([]int64, 0, limit)
                return &buf
            },
        },
    }
}

// Allow 判断请求是否允许通过（优化版）
func (o *OptimizedSlidingWindowLog) Allow() bool {
    o.mu.Lock()
    defer o.mu.Unlock()

    now := time.Now().UnixMilli()
    boundary := now - o.window

    // 二分查找清理过期时间戳
    left := 0
    right := len(o.timestamps)
    for left < right {
        mid := left + (right-left)/2
        if o.timestamps[mid] < boundary {
            left = mid + 1
        } else {
            right = mid
        }
    }

    // 复用底层数组，避免内存分配
    if left > 0 {
        copy(o.timestamps, o.timestamps[left:])
        o.timestamps = o.timestamps[:len(o.timestamps)-left]
    }

    if len(o.timestamps) >= o.limit {
        return false
    }

    o.timestamps = append(o.timestamps, now)
    return true
}

// Reset 重置限流器（释放内存）
func (o *OptimizedSlidingWindowLog) Reset() {
    o.mu.Lock()
    defer o.mu.Unlock()
    o.timestamps = make([]int64, 0, o.limit)
}

3.5 性能对比与选型建议

3.6 边界情况与注意事项

• 时间戳溢出：int64 毫秒时间戳在公元 292 年之前不会溢出，可安全使用。
• 时钟回拨：如果服务器时钟发生回拨，清理逻辑可能失效。建议在检测到 now < lastTimestamp 时清空日志并重置。
• 并发安全：所有公开方法必须加锁，Allow() 方法应保持原子性。
• 窗口边界精度：毫秒级精度已足够应对绝大多数场景。如果需要纳秒级精度，需考虑性能开销。