06-限流策略有哪些，滑动窗口算法和令牌桶区别，使用场景？【Java面试题总结】

限流策略有哪些，滑动窗口算法和令牌桶区别，使用场景？

常见的限流算法有固定窗口、滑动窗口、漏桶、令牌桶等。

6.1 固定窗口

概念：固定窗口（又称计算器限流），对一段固定时间窗口内的请求进行一个计数，如果请求数量超过阈值，就会舍弃这个请求，如果没有达到设定阈值，就直接接受这个请求。

public class FixedWindowRateLimiter1 {private final int windowSize;private final int limit;private final AtomicInteger count;private final ReentrantLock lock;public FixedWindowRateLimiter1(int windowSize, int limit) {this.windowSize = windowSize;this.limit = limit;this.count = new AtomicInteger(0);this.lock = new ReentrantLock();}public boolean allowRequest() {lock.lock();try {long currentTimestamp = Instant.now().getEpochSecond();int currentCount = count.get();if (currentCount < limit) {count.incrementAndGet();return true;} else {return false;}} finally {lock.unlock();}}public static void main(String[] args) throws InterruptedException {FixedWindowRateLimiter1 rateLimiter = new FixedWindowRateLimiter1(5, 3);// 测试通过的请求for (int i = 0; i < 10; i++) {if (rateLimiter.allowRequest()) {System.out.println("Request " + (i + 1) + ": Allowed");} else {System.out.println("Request " + (i + 1) + ": Denied");}TimeUnit.SECONDS.sleep(1);}}
}

在上述代码中，我们引入了 ReentrantLock 和 AtomicInteger，分别用于保证线程安全的访问和原子的计数操作。通过在 allowRequest() 方法中使用 lock 对关键代码段进行加锁和解锁，确保同一时间只有一个线程能够进入关键代码段。使用 AtomicInteger 来进行计数操作，保证计数的原子性。

6.2 滑动窗口

概念：滑动窗口算法是一种基于时间窗口的限流算法，它将时间划分为固定大小的窗口，并统计每个窗口内的请求数量。算法维护一个滑动窗口，窗口内的位置表示当前时间片段，每个位置记录该时间片段内的请求数量。当请求到达时，算法会根据当前时间判断应该归入哪个时间片段，并检查该时间片段内的请求数量是否超过限制。

以滑动窗口算法为例，每秒最多允许通过3个请求

public class SlidingWindowRateLimiter {private final int limit; // 限流阈值private final int interval; // 时间窗口长度private final AtomicLong counter; // 计数器private final long[] slots; // 时间窗口内每个时间片段的请求数量private long lastTimestamp; // 上次请求时间private long currentIntervalRequests; // 当前时间窗口内的请求数量public SlidingWindowRateLimiter(int limit, int interval) {this.limit = limit;this.interval = interval;this.counter = new AtomicLong(0);this.slots = new long[interval];this.lastTimestamp = System.currentTimeMillis();this.currentIntervalRequests = 0;}public boolean allowRequest() {long currentTimestamp = System.currentTimeMillis();if (currentTimestamp - lastTimestamp >= interval) {// 超过时间窗口，重置计数器和时间窗口counter.set(0);slots[0] = 0;lastTimestamp = currentTimestamp;currentIntervalRequests = 0;}// 计算请求数量long currentCount = counter.incrementAndGet();if (currentCount <= limit) {// 未达到阈值，请求通过slots[(int) (currentCount - 1)] = currentTimestamp;currentIntervalRequests++;return true;}// 达到阈值，判断最早的时间片段是否可以通过long earliestTimestamp = slots[0];if (currentTimestamp - earliestTimestamp >= interval) {// 最早的时间片段超过时间窗口，重置计数器和时间窗口counter.set(0);slots[0] = 0;lastTimestamp = currentTimestamp;currentIntervalRequests = 0;return true;}return false;}public long getRequestsPerSecond() {return currentIntervalRequests * 1000 / interval;}
}

public class SlidingWindowRateLimiterTest {public static void main(String[] args) throws InterruptedException {// 创建一个限流器，限制每秒最多通过3个请求SlidingWindowRateLimiter rateLimiter = new SlidingWindowRateLimiter(3, 1000);// 模拟连续发送请求long startTime = System.nanoTime();for (int i = 1; i <= 10; i++) {if (rateLimiter.allowRequest()) {System.out.println("Request " + i + " allowed");} else {System.out.println("Request " + i + " blocked");}Thread.sleep(100); // 模拟请求间隔时间}System.out.println((System.nanoTime()-startTime)/1000000000.0);}
}

6.3 令牌桶算法

概念：令牌桶算法基于令牌的发放和消耗机制，令牌以固定的速率被添加到令牌桶中。每个请求需要消耗一个令牌才能通过，当令牌桶中的令牌不足时，请求将被限制。令牌桶算法可以平滑地限制请求的通过速率，对于突发流量有较好的处理能力。