说说什么是滑动窗口算法？

滑动窗口算法是一种限流算法，通过将较大的时间周期（如1分钟）划分为多个更小的时间周期（如10秒），分别记录每个小周期内的访问次数，并根据时间滑动删除过期的小周期。这种方式能够平滑限流效果，避免固定窗口算法的临界问题。 #### 实现原理 滑动窗口算法的核心是将一个大时间窗口划分为多个小窗口，每个小窗口统计访问次数，并根据当前时间滑动窗口，动态计算最近一个大时间窗口内的总访问次数。这样可以更精确地控制请求速率，避免短时间内大量请求涌入导致的瞬时流量过大问题。 #### 实现示例 假设我们将1分钟时间窗口划分为6个10秒的小窗口，限流值为100。 1. **滑动窗口结构**：使用一个数据结构（如队列或数组）存储每个小窗口的访问次数。 2. **统计访问次数**：每次请求时，更新当前小窗口的访问次数。 3. **滑动窗口**：根据当前时间，滑动窗口，删除过期的小窗口，并计算最近1分钟的总访问次数。 4. **限流判断**：如果总访问次数超过限流值，则触发限流策略。 **Java实现示例**： ```java import java.util.LinkedList; import java.util.Queue; public class SlidingWindowRateLimiter { private static final int LIMIT = 100; private static final int WINDOW_SIZE = 60; // in seconds private static final int SLIDE_INTERVAL = 10; // in seconds private Queue<Integer> windows; private int currentCount; private long lastSlideTime; public SlidingWindowRateLimiter() { this.windows = new LinkedList<>(); this.currentCount = 0; this.lastSlideTime = System.currentTimeMillis() / 1000; } public synchronized boolean isAllowed() { long currentTime = System.currentTimeMillis() / 1000; slideWindow(currentTime); if (currentCount < LIMIT) { currentCount++; return true; } else { return false; } } private void slideWindow(long currentTime) { long elapsed = currentTime - lastSlideTime; if (elapsed >= SLIDE_INTERVAL) { int windowsToRemove = (int) (elapsed / SLIDE_INTERVAL); for (int i = 0; i < windowsToRemove; i++) { if (!windows.isEmpty()) { currentCount -= windows.poll(); } windows.add(0); } lastSlideTime = currentTime; } } } ``` #### 优点 - **平滑限流**：滑动窗口算法能够平滑统计请求次数，避免瞬时流量过大的问题。 - **更精确**：通过划分多个小窗口，限流统计更加精确，能够更好地控制请求速率。 #### 缺点 - **内存开销**：需要存储多个小窗口的数据，可能会增加内存开销。 - **计算复杂度**：需要在每次请求时进行滑动窗口操作，计算复杂度较高。 ### 总结 滑动窗口算法通过将大时间窗口划分为多个小窗口，并根据时间滑动窗口，动态计算总访问次数，能够有效解决固定窗口算法的临界问题，提供更平滑、更精确的限流效果。适用于需要精确控制请求速率，避免瞬时流量过大的场景。