Java面试必问：深入解析滑动窗口限流算法原理与实战
一、什么是滑动窗口限流？
滑动窗口限流是一种常见的限流算法，主要应用于防止系统过载，保证系统稳定运行。滑动窗口限流通过维护一个窗口，窗口内记录了一段时间内的请求情况，当请求超过设定的阈值时，则对请求进行限流。
二、滑动窗口限流算法原理
1. 窗口定义
滑动窗口限流算法中的窗口可以理解为时间窗口，它是一个固定大小的区间。在这个区间内，记录了请求的数量、时间戳等信息。
2. 窗口滑动
当窗口滑动时，窗口内的数据会根据时间戳进行更新。窗口滑动的时间间隔称为窗口大小，通常设置为一个固定的时间值，如1秒、5秒等。
3. 请求计数
在窗口内，对请求进行计数。当请求进入窗口时，计数加1；当窗口滑动时，计数减1。
4. 阈值判断
当窗口内的请求计数超过设定的阈值时，则对请求进行限流。限流的方式有：丢弃请求、排队等待、降级处理等。
三、滑动窗口限流算法实现
1. 基于数组实现
使用数组存储窗口内的请求计数，窗口滑动时，更新数组中的数据。以下是一个简单的滑动窗口限流算法实现：
```java
public class SlidingWindowRateLimiter {
private int[] counts;
private int windowSize;
private long startTime;
public SlidingWindowRateLimiter(int windowSize) {
this.windowSize = windowSize;
this.counts = new int[windowSize];
this.startTime = System.currentTimeMillis();
}
public boolean tryAcquire() {
long currentTime = System.currentTimeMillis();
int index = (int) ((currentTime - startTime) % windowSize);
counts[index]++;
if (counts[index] > 100) {
return false;
}
startTime = currentTime;
return true;
}
}
```
2. 基于环形缓冲区实现
使用环形缓冲区存储窗口内的请求计数，窗口滑动时，更新环形缓冲区中的数据。以下是一个基于环形缓冲区的滑动窗口限流算法实现：
```java
public class SlidingWindowRateLimiter {
private int[] counts;
private int windowSize;
private int count;
private int index;
public SlidingWindowRateLimiter(int windowSize) {
this.windowSize = windowSize;
this.counts = new int[windowSize];
this.count = 0;
this.index = 0;
}
public boolean tryAcquire() {
int index = (int) (System.currentTimeMillis() % windowSize);
counts[index]++;
if (counts[index] > 100) {
return false;
}
if (index == this.index) {
count++;
}
if (count > 100) {
return false;
}
this.index = index;
return true;
}
}
```
四、滑动窗口限流算法优缺点
1. 优点
（1）实现简单，易于理解。
（2）对系统资源的消耗较小。
（3）适用于高并发场景。
2. 缺点
（1）窗口大小设置不合理时，可能导致限流不精确。
（2）在窗口切换时，可能会出现短暂的限流失效。
五、实战案例分析
假设我们有一个系统，每秒最多处理100个请求。现在，我们使用滑动窗口限流算法来实现限流功能。
```java
public class SlidingWindowRateLimiter {
private int[] counts;
private int windowSize;
private int count;
private int index;
public SlidingWindowRateLimiter(int windowSize) {
this.windowSize = windowSize;
this.counts = new int[windowSize];
this.count = 0;
this.index = 0;
}
public boolean tryAcquire() {
int index = (int) (System.currentTimeMillis() % windowSize);
counts[index]++;
if (counts[index] > 100) {
return false;
}
if (index == this.index) {
count++;
}
if (count > 100) {
return false;
}
this.index = index;
return true;
}
public static void main(String[] args) {
SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(1000);
for (int i = 0; i < 2000; i++) {
boolean acquired = limiter.tryAcquire();
if (acquired) {
// 处理请求
System.out.println("Request " + i + " acquired.");
} else {
// 限流处理
System.out.println("Request " + i + " rejected.");
}
}
}
}
```
运行上述代码，我们可以看到，当请求数量超过100时，系统会进行限流处理。
总结
滑动窗口限流算法是一种简单有效的限流方式，适用于高并发场景。在实际应用中，我们需要根据业务需求，合理设置窗口大小、阈值等参数，以达到最佳的限流效果。同时，我们还需要关注限流算法的优缺点，以便在遇到问题时，能够及时调整和优化。
