深入浅出限流算法（三）：追求极致精确的滑动日志

在限流的世界里，精度往往是关键。我们已经讨论过固定窗口（简单但有突刺）和滑动窗口（更平滑但仍有格子边界）。如果我们需要更精确的控制，滑动日志 (Sliding Log) 算法便登场了。

核心思想：记录每一笔“交易”

想象一下，你不再关心“格子”，而是为每一个到达的请求都记下精确的时间戳，就像一本详细的日志。

当新请求到来时：

1. 回顾日志：查看过去固定时间窗口（例如 1 秒）内的所有时间戳记录。

2. 清理旧账：忽略（或删除）所有超出这个时间窗口的旧记录。

3. 计数：统计窗口内剩余记录的数量。

4. 决策：

   • 如果数量小于限制，接受请求，并将新请求的时间戳加入日志。
   • 如果数量达到或超过限制，拒绝请求。

这种方式理论上能提供最精确的限流，因为它关注的是每个单独的请求事件。

Java 实现：用 TreeMap​ 优化内存

直接存储每个请求的时间戳在高并发下可能导致内存爆炸。一个常见的优化是按时间单位（如毫秒）分组，记录每个单位时间内到达的请求数。Java 的 TreeMap<Long, Long>​ 非常适合这个任务：

• Key (Long): 时间戳（毫秒）。TreeMap​ 自动保持时间排序。
• Value (Long): 该毫秒到达的请求数量。

// 简化版核心逻辑示意
public synchronized boolean tryAcquire() {
    long now = System.currentTimeMillis();
    long windowStart = now - 1000; // 1秒窗口起点

    // 1. (可选) 清理非常旧的数据，防止 Map 无限增长
    // treeMap.headMap(now - cleanupInterval).clear();

    // 2. 高效计算窗口内总数 (利用 TreeMap 的 subMap)
    long sum = treeMap.subMap(windowStart, true, now, true)
                      .values().stream().mapToLong(Long::longValue).sum();

    // 3. 检查限制
    if (sum >= QPS) {
        return false; // 超限，拒绝
    }

    // 4. 记录当前请求 (对当前毫秒的计数 +1)
    treeMap.compute(now, (k, v) -> (v == null) ? 1L : v + 1L);
    return true; // 允许
}

​TreeMap​ 的 subMap​ 操作能高效地提取出所需时间窗口内的数据进行求和。

优点

• 极高精度：几乎完全消除了窗口边界效应，限流非常精确。
• 概念清晰简单。

缺点

• 内存消耗大：即使按毫秒分组，存储时间戳和计数的 TreeMap​ 仍然比简单的计数器或固定数组占用更多内存，尤其是在高 QPS 下。
• 并发性能：简单的 synchronized​ 实现可能在高并发下成为瓶颈。

总结

滑动日志算法提供了无与伦比的限流精度，是追求严格控制流量速率场景下的有力武器。然而，这种精度是以更高的内存消耗为代价的。在选择它时，需要仔细权衡精度需求与系统资源限制。