4. 滑动窗口日志算法：原理详解、精确限流的实现方式、内存开销与优化策略

滑动窗口日志算法（Sliding Window Log Algorithm）是固定窗口算法的进化版。它通过记录每个请求的精确时间戳，并维护一个动态的“日志”窗口，彻底解决了固定窗口在窗口边界处的流量突刺问题。本章将深入剖析其原理、实现方式及内存优化策略。

4.1 算法原理与核心数据结构

滑动窗口日志算法的核心思想是：为每个请求记录一个时间戳日志，并只保留当前时间窗口内的日志。当新请求到达时，算法会清除所有早于当前时间窗口起始点的过期日志，然后统计剩余日志的数量。如果数量小于阈值，则允许请求并记录日志；否则，拒绝请求。

其核心数据结构通常采用双端队列（Deque）或循环缓冲区（Circular Buffer）来存储时间戳。队列中的每个元素代表一个请求的到达时间戳（通常为毫秒级 Unix 时间戳）。

4.2 精确限流的实现方式

以下是一个基于 Java 的滑动窗口日志算法核心实现，使用 LinkedList 作为日志存储结构。

import java.util.LinkedList;
import java.util.Queue;

public class SlidingWindowLogRateLimiter {
    private final long windowSizeInMs;   // 窗口大小，单位毫秒
    private final int maxRequests;       // 窗口内允许的最大请求数
    private final Queue<Long> logQueue;  // 存储请求时间戳的队列

    public SlidingWindowLogRateLimiter(long windowSizeInMs, int maxRequests) {
        this.windowSizeInMs = windowSizeInMs;
        this.maxRequests = maxRequests;
        this.logQueue = new LinkedList<>();
    }

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        long windowStart = now - windowSizeInMs;

        // 1. 移除过期日志（早于窗口起点的请求）
        while (!logQueue.isEmpty() && logQueue.peek() < windowStart) {
            logQueue.poll();
        }

        // 2. 检查当前窗口内请求数是否已达阈值
        if (logQueue.size() < maxRequests) {
            logQueue.offer(now);  // 3. 记录新请求
            return true;          // 允许通过
        }
        return false;             // 拒绝请求
    }
}

4.3 内存开销分析

滑动窗口日志算法的精度与内存开销成正比。下表对比了不同场景下的内存占用情况。

4.4 优化策略

针对滑动窗口日志算法的内存开销问题，业界主要有以下三种优化策略。

4.4.1 策略一：使用循环缓冲区（Circular Buffer）

使用固定大小的数组代替链表，通过取模运算覆盖旧数据。这消除了对象创建和 GC 压力，但需要预先分配最大容量。

public class CircularBufferLogLimiter {
    private final long[] buffer;
    private final int capacity;
    private int head = 0;
    private int count = 0;

    public CircularBufferLogLimiter(int capacity) {
        this.capacity = capacity;
        this.buffer = new long[capacity];
    }

    public synchronized boolean tryAcquire(long now, long windowSizeMs) {
        long windowStart = now - windowSizeMs;
        // 清理过期数据
        while (count > 0 && buffer[head] < windowStart) {
            head = (head + 1) % capacity;
            count--;
        }
        if (count < capacity) {
            buffer[(head + count) % capacity] = now;
            count++;
            return true;
        }
        return false;
    }
}

4.4.2 策略二：采样与近似

不记录每一个请求，而是按一定概率（如 1%）进行采样记录，通过统计样本来估算整体流量。这大幅降低了内存开销，但会牺牲一定的精度，适用于对精度要求不高的场景。

4.4.3 策略三：分层时间轮（Hierarchical Timing Wheel）

借鉴操作系统中的时间轮算法，将时间戳按精度分层存储。例如，秒级精度使用一个 60 槽的轮子，毫秒级精度使用一个 1000 槽的轮子。通过层级嵌套，可以在 O(1) 时间内完成过期清理，且内存占用远小于全量日志。

4.5 三种算法对比总结