当前位置：首页 > news >正文

深入浅出限流算法（二）：更平滑的滑动窗口

news 2025/4/29 6:52:11

好的，接续上一篇关于固定窗口计数器的讨论，我们现在来看看它的改进版——滑动窗口算法，它旨在解决固定窗口那个恼人的“临界突变”问题。

在上一篇文章中，我们探讨了最简单的固定窗口计数器限流算法，并指出了它最大的缺陷——临界突变问题，即在窗口边界可能产生远超预期的瞬时流量。为了克服这个问题，工程师们设计出了更精妙的滑动窗口 (Sliding Window) 算法。

滑动窗口的核心思想

想象一下，你不是每分钟换一个全新的计数器，而是有一个总时长固定（比如 1 分钟）但由多个小格子组成（比如 6 个 10 秒的格子）的观察窗口。

细分窗口：时间被划分成连续的小格子（子窗口），每个格子记录自己时间段内的请求数。
滑动观察：你的观察窗口始终覆盖着最近的若干个格子（总时长固定，例如始终覆盖最近 6 个 10 秒的格子，构成一个 1 分钟的滑动窗口）。
计算总和：当新请求到来时，你计算当前观察窗口内所有格子计数器的总和。
检查限制：如果总和小于等于阈值（例如 QPS 限制），则允许请求，并将当前请求计入其所属的那个小格子。如果超过阈值，则拒绝请求。
时间推移：随着时间的流逝，观察窗口整体向前“滑动”：最老的一个格子（及其计数）滑出观察窗口，不再参与计算；最新的一个时间格子进入观察窗口。

通过这种方式，统计总是基于一个持续滑动的、固定长度的时间区间，避免了固定窗口在边界处的计数器突然清零，从而使得流量限制更加平滑。

Java 实现

下面是一个基于数组的滑动窗口限流器 Java 实现：

import java.time.LocalTime; // 这个 import 在代码中实际未使用，可以移除
import java.util.concurrent.atomic.AtomicInteger;public class RateLimiterSlidingWindow {private int qps = 2;               // 总的 QPS 限制 (每秒允许请求数)private long windowSize = 1000;    // 主窗口大小 (毫秒)，例如 1000ms = 1秒private int windowCount = 10;      // 子窗口（格子）的数量private WindowInfo[] windowArray; // 存储子窗口数据的数组// 内部类，用于存储每个子窗口的信息private static class WindowInfo {private Long time;          // 此子窗口最后一次被重置或更新的时间戳private AtomicInteger number; // 此子窗口内的请求计数器 (线程安全)// 构造函数public WindowInfo(long time, AtomicInteger number) {this.time = time;this.number = number;}// Getters and Setters (可以根据需要添加)public Long getTime() { return time; }public void setTime(Long time) { this.time = time; }public AtomicInteger getNumber() { return number; }}// 构造函数：初始化限流器public RateLimiterSlidingWindow(int qps, long windowSize, int windowCount) {this.qps = qps;this.windowSize = windowSize;this.windowCount = windowCount;this.windowArray = new WindowInfo[this.windowCount];long currentTimeMillis = System.currentTimeMillis();// 初始化所有子窗口，初始时间设为当前，计数设为0for (int i = 0; i < windowArray.length; i++) {windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));}}// 尝试获取一个请求许可 (核心方法)// 使用 synchronized 保证对 windowArray 状态修改的线程安全public synchronized boolean tryAcquire() {long currentTimeMillis = System.currentTimeMillis();// 1. 计算当前时间戳应该落在哪个子窗口 (格子)long subWindowSize = windowSize / windowCount; // 每个子窗口的时间跨度// 通过取模和除法，将当前时间映射到数组索引int currentIndex = (int)((currentTimeMillis % windowSize) / subWindowSize);// 2. 遍历所有子窗口：重置过期窗口 & 计算当前滑动窗口总数int sum = 0; // 当前滑动窗口内的总请求数for (int i = 0; i < windowArray.length; i++) {WindowInfo windowInfo = windowArray[i];// 检查子窗口是否已过期 (时间戳距离现在超过整个主窗口大小)if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {// 如果过期，重置计数器为 0，并更新其时间戳为当前时间// 这相当于让这个格子“重新进入”滑动窗口的循环利用windowInfo.getNumber().set(0);windowInfo.setTime(currentTimeMillis);}// 如果当前遍历到的格子就是本次请求所属的格子if (currentIndex == i) {// 先尝试将当前格子的计数加 1 (后面如果超限会撤销)windowInfo.getNumber().incrementAndGet();}// 累加所有未过期格子的计数sum = sum + windowInfo.getNumber().get();}// 3. 检查总数是否超过限制if (sum > qps) {// 如果总数超限，说明刚才对 currentIndex 的增加是无效的// 需要撤销 (回滚) 这个增加操作windowArray[currentIndex].getNumber().decrementAndGet();return false; // 拒绝请求} else {// 如果未超限，刚才的增加有效，请求被允许return true;}}// main 方法用于测试 (可以参考上一篇的测试方式)public static void main(String[] args) throws InterruptedException {// QPS=2, 窗口1秒, 分成10个格子 (每个100ms)RateLimiterSlidingWindow limiter = new RateLimiterSlidingWindow(2, 1000, 10);for (int i = 0; i < 10; i++) {// 模拟请求间隔，观察效果Thread.sleep(100); // 每 100ms 发一个请求// Thread.sleep(400); // 每 400ms 发一个请求// Thread.sleep(600); // 每 600ms 发一个请求long currentTimeMillis = System.currentTimeMillis();if (limiter.tryAcquire()) {System.out.println(currentTimeMillis + " 请求成功 -> ✅");} else {System.out.println(currentTimeMillis + " 请求失败 -> ❌");}}}
}

代码解读：

WindowInfo 内部类: 存储每个子窗口（格子）的时间戳和原子计数器。
windowArray: 一个 WindowInfo 对象的数组，数组大小即格子的数量 (windowCount)。
构造函数: 初始化 qps、windowSize、windowCount，并创建和初始化 windowArray。所有格子的初始时间戳设为当前时间，计数为 0。
tryAcquire() 核心逻辑:
- 计算 currentIndex: 确定当前请求应该落在哪一个格子里。通过 (当前时间 % 主窗口大小) / 子窗口大小的方式，巧妙地将无限的时间轴映射到有限的数组索引上，实现了循环使用数组格子的效果。
- 遍历 windowArray:
  - 重置过期格子: 对每个格子，检查其记录的时间戳 windowInfo.getTime() 是否已经“太旧”（距离当前时间超过了一个 windowSize）。如果是，说明这个格子代表的时间段已经完全滑出了当前的统计窗口，需要将其计数清零，并更新时间戳为当前时间，为后续循环利用做准备。
  - 增加当前格子计数: 如果遍历到的格子 i 正好是当前请求所属的格子 currentIndex，就先尝试将其计数原子地加 1。
  - 累加总数: 将所有（未过期的）格子的计数值累加到 sum 中。
- 检查并处理结果:
  - 如果 sum 超过了 qps 限制，说明刚才对 currentIndex 的增加导致了超限，需要调用 decrementAndGet() 将其撤销，并返回 false (拒绝)。
  - 如果 sum 未超过 qps，说明请求被允许，刚才的增加有效，返回 true。
线程安全: 同样使用了 synchronized 关键字来保证对共享数组 windowArray 的访问和修改是线程安全的。AtomicInteger 保证了单个格子计数的原子性。

优点

缓解临界突变：通过细化时间窗口并进行滑动统计，显著减少了固定窗口在边界处可能出现的流量突刺问题，使得流量控制更加平滑。
实现相对简单：相比更复杂的算法（如令牌桶），滑动窗口的概念和基于数组的实现仍然比较直观。

缺点与考量

并未完全消除突变：滑动窗口虽然平滑了流量，但仍然可能存在一定的突发性。例如，如果子窗口（格子）划分得不够细，在子窗口的边界处仍然可能出现小范围的流量聚集。精度取决于格子的数量，格子越多越平滑，但内存和计算开销也越大。
synchronized 性能瓶颈：在高并发场景下，synchronized 可能会成为性能瓶颈，因为它锁定了整个方法，限制了并发度。更优化的实现可能会采用更细粒度的锁或者无锁数据结构（但这会显著增加实现的复杂度）。
内存占用：相比固定窗口，需要存储多个子窗口的信息，内存占用有所增加。