4. 限流基础算法(二)：滑动窗口日志算法原理、内存优化技巧、精度与性能权衡

滑动窗口日志算法（Sliding Window Log）是计数器算法的精确化演进。它通过记录每个请求的精确时间戳，在滑动时间窗口内动态计算请求总量，从而彻底消除固定窗口的“临界突变”问题。本章深入剖析其核心原理、内存瓶颈及工业级优化方案。

4.1 算法核心原理

滑动窗口日志算法维护一个按时间排序的请求日志列表。每当新请求到达时，执行以下步骤：

1. 记录时间戳：将当前请求的时间戳追加到日志尾部。
2. 清理过期记录：从日志头部移除所有早于 当前时间 - 窗口大小 的时间戳。
3. 计数判断：统计剩余日志条数，若小于阈值则放行，否则拒绝。

4.2 内存优化技巧

原始滑动窗口日志算法需要存储窗口内所有请求的时间戳，内存开销随QPS线性增长。对于高并发模型Serving场景（如每秒数万次推理请求），直接存储完整日志将导致OOM。以下是工业界常用的优化策略：

4.3 精度与性能权衡分析

滑动窗口日志算法的精度与性能存在直接矛盾。以下从三个维度进行量化分析：

• 时间戳粒度：毫秒级存储 vs 微秒级存储。毫秒级可满足大部分模型Serving场景（延迟抖动在10ms量级），微秒级存储会使内存膨胀10倍以上。
• 清理频率：惰性清理（请求到达时清理） vs 定时清理（后台线程定期清理）。惰性清理增加请求延迟约0.1~0.5μs，定时清理引入额外CPU开销但保持请求路径低延迟。
• 并发控制：全局锁 vs 分段锁 vs 无锁CAS。全局锁在1000QPS以下可接受；分段锁适用于1万~10万QPS；无锁CAS（如Java的LongAdder）适用于10万QPS以上场景。

4.4 工业级实现示例

以下是一个基于分桶聚合优化的滑动窗口日志算法实现（Go语言伪代码），展示如何在内存和精度之间取得平衡：

type SlidingWindowLog struct {
    mu          sync.Mutex
    buckets     [10]int32      // 10个100ms微桶
    bucketIndex int           // 当前桶索引
    lastTick    int64         // 上次更新的毫秒时间戳
    threshold   int32         // 限流阈值
}

func (swl *SlidingWindowLog) Allow() bool {
    swl.mu.Lock()
    defer swl.mu.Unlock()

    now := time.Now().UnixMilli()
    currentBucket := (now / 100) % 10  // 每100ms一个桶

    // 如果跨桶，清理过期桶
    if currentBucket != swl.bucketIndex {
        // 计算跳过的桶数，重置中间桶
        steps := (currentBucket - swl.bucketIndex + 10) % 10
        for i := 1; i < steps; i++ {
            idx := (swl.bucketIndex + i) % 10
            swl.buckets[idx] = 0
        }
        swl.bucketIndex = currentBucket
        swl.buckets[currentBucket] = 0
    }

    // 统计窗口内总请求数
    var total int32
    for _, count := range swl.buckets {
        total += count
    }

    if total >= swl.threshold {
        return false
    }

    swl.buckets[currentBucket]++
    return true
}

4.5 适用场景与选型建议