限流算法
本文将分析常见的限流算法以及优缺点
固定窗口
原理
将时间划分为固定长度的窗口（如1秒），统计每个窗口内的请求数
若窗口内请求数超过阈值，则拒绝后续请求；窗口结束时重置计数器
优点
实现简单，内存占用少
缺点
临界问题：窗口切换时可能出现突发流量，例如时间窗口为1秒，前1秒的后500ms和后1秒的前500ms可能共同通过2 * threshold的请求.
这样实际在1s通过了2 * threshold的请求数量，没有限流住
适用场景
- 低频接口（如后台管理系统）
- 对限流精度要求不高的场景
代码实现
public class FixedWindowCounter {
/**
* 限流阈值
*/
private final int threshold;
/**
* 窗口时间(毫秒)
*/
private final long windowMs;
/**
* 上次重置时间
*/
private long lastResetTime;
/**
* 计数器
*/
private AtomicLong counter;
public FixedWindowCounter(int threshold, long windowMs) {
this.windowMs = windowMs;
this.threshold = threshold;
this.lastResetTime = System.currentTimeMillis();
this.counter = new AtomicLong(0);
}
public boolean allowRequest() {
long now = System.currentTimeMillis();
if (now > lastResetTime + windowMs) {
lastResetTime = now;
counter.set(0);
}
return counter.incrementAndGet() <= threshold;
}
}
限流测试
public static void main(String[] args) throws Exception {
FixedWindowCounter counter = new FixedWindowCounter(3, 1000);
// 模拟第1秒内的请求
System.out.println("===== 第1秒发送5次请求 =====");
for (int i = 1; i <= 5; i++) {
System.out.printf("请求 %d: %s\n", i, counter.allowRequest() ? "通过" : "被限流");
}
// 等待1秒，进入下一个窗口
TimeUnit.SECONDS.sleep(1);
// 模拟第2秒内的请求
System.out.println("===== 第2秒发送5次请求 =====");
for (int i = 6; i <= 10; i++) {
System.out.printf("请求 %d: %s\n", i, counter.allowRequest() ? "通过" : "被限流");
}
}
滑动窗口
原理
将时间窗口划分为更细粒度的子窗口（如将1秒分为10个100ms的子窗口）
统计滑动窗口内所有子窗口的请求总数，动态清理过期的子窗口
滑动窗口是为了解决固定窗口临界窗口切换的问题
优点
比固定窗口更精准，可以缓解临界问题
缺点
- 内存占用过高:每个请求的时间戳都需要记录，高QPS场景下内存压力大
- 细粒度滑动窗口实现复杂
适用场景
-
需要较高限流精度的场景（如API网关）。
-
流量波动较大但QPS适中的场景（如每秒数千次请求）。
代码实现
public class SlidingWindow {
/**
* 限流阈值（窗口内最大请求数）
*/
private final int threshold;
/**
* 窗口时间(毫秒)
*/
private final long windowMs;
/**
* 请求时间戳队列
*/
private final ConcurrentLinkedDeque<Long> window;
/**
* 当前窗口中的请求计数（避免频繁计算size）
*/
private final AtomicInteger counter;
private final Lock lock;
/**
* 上次清理时间
*/
private long lastCleanupTime;
/**
* @param threshold 限流阈值（窗口内最大请求数）
* @param windowMs 窗口时间(毫秒)
*/
public SlidingWindow(int threshold, long windowMs) {
this.threshold = threshold;
this.windowMs = windowMs;
this.window = new ConcurrentLinkedDeque<>();
this.counter = new AtomicInteger(0);
this.lock = new ReentrantLock();
this.lastCleanupTime = System.currentTimeMillis();
}
public boolean allowRequest() {
long now = System.currentTimeMillis();
if (now - lastCleanupTime > windowMs / 10) {
cleanup(now);
}
if (counter.get() < threshold) {
lock.lock();
// 双重检查
try {
if (counter.get() < threshold) {
window.add(now);
counter.incrementAndGet();
return true;
}
} finally {
lock.unlock();
}
}
return false;
}
private void cleanup(long now) {
lock.lock();
try {
int removed = 0;
while (!window.isEmpty() && now - window.peek() > windowMs) {
window.poll();
removed++;
}
if (removed > 0) {
counter.addAndGet(-removed);
}
lastCleanupTime = now;
} finally {
lock.unlock();
}
}
/**
* 获取当前窗口内的请求数
*
* @return 窗口内请求数
*/
public int getCurrentWindowCount() {
// 清理过期数据后再返回计数
cleanup(System.currentTimeMillis());
return counter.get();
}
/**
* 获取窗口容量
*
* @return 窗口最大请求数
*/
public int getThreshold() {
return threshold;
}
/**
* 获取窗口时间
*
* @return 窗口时间(毫秒)
*/
public long getWindowMs() {
return windowMs;
}
/**
* 重置滑动窗口
* <p>
* 清空所有请求记录
*/
public void reset() {
lock.lock();
try {
window.clear();
counter.set(0);
lastCleanupTime = System.currentTimeMillis();
} finally {
lock.unlock();
}
}
}
限流测试
private static void testBasicThrottling() {
System.out.println("\n===== 测试1: 基本限流功能 =====");
// 创建一个每秒最多允许5个请求的滑动窗口限流器
SlidingWindow limiter = new SlidingWindow(5, 1000);
System.out.println("窗口大小: 1秒, 阈值: 5个请求");
System.out.println("\n发送10个连续请求...");
for (int i = 0; i < 10; i++) {
boolean allowed = limiter.allowRequest();
System.out.printf("请求 %2d: %s (窗口内请求数: %d)%n", (i + 1), (allowed ? "通过" : "拒绝"), limiter.getCurrentWindowCount());
}
System.out.println("\n结果验证: 前5个请求应该通过，后5个应该被拒绝");
}
漏桶算法
原理
请求像水一样以任意速率流入漏桶，桶以固定速率（如每秒5000次）漏水（处理请求）
若桶满（水量超过容量），则拒绝新请求
优点
流量整形：强制恒定速率
缺点
无法应对突发流量：漏出速率固定，无法利用系统空闲时的处理能力
适用场景
- 需要平滑流量的场景（如数据库写入保护）
- 严格限制处理速率的场景（如支付系统）
代码实现
public class LeakyBucket {
/**
* 桶容量（最大请求数）
*/
private final long capacity;
/**
* 漏水速率（请求/秒）
*/
private final double leakRatePerSecond;
/**
* 当前水量（当前累积的请求数）
*/
private double waterLevel;
/**
* 上次漏水时间（毫秒）
*/
private long lastLeakTimeMs;
/**
* 构造漏桶限流器
*
* @param capacity 桶容量（最大请求数）
* @param leakRatePerSecond 每秒漏水速率（请求/秒）
*/
public LeakyBucket(long capacity, double leakRatePerSecond) {
this.capacity = capacity;
this.leakRatePerSecond = leakRatePerSecond;
this.waterLevel = 0;
this.lastLeakTimeMs = System.currentTimeMillis();
}
/**
* 尝试获取请求许可
*
* @return true表示请求被允许，false表示请求被限流
*/
public synchronized boolean allowRequest() {
long currentTimeMs = System.currentTimeMillis();
// 计算距离上次漏水的时间（秒）
double timeElapsedSeconds = (currentTimeMs - lastLeakTimeMs) / 1000.0;
// 计算漏出的水量: 时间(秒) * 漏水速率(请求/秒)
double leakedWater = timeElapsedSeconds * leakRatePerSecond;
// 更新水位，不能低于0
waterLevel = Math.max(0, waterLevel - leakedWater);
// 更新上次漏水时间
lastLeakTimeMs = currentTimeMs;
// 如果新请求加入后水位不超过容量，则接受请求
if (waterLevel + 1 <= capacity) {
waterLevel++;
return true;
}
return false;
}
/**
* 获取当前水位（用于测试和监控）
*
* @return 当前水位
*/
public double getCurrentWaterLevel() {
return waterLevel;
}
/**
* 获取剩余容量
*
* @return 桶的剩余容量
*/
public double getRemainingCapacity() {
return capacity - waterLevel;
}
}
限流测试
public static void main(String[] args) throws InterruptedException {
System.out.println("\n===== 测试1: 基本限流功能 =====");
// 创建一个容量为5，每秒漏2个请求的漏桶
LeakyBucket bucket = new LeakyBucket(5, 2.0);
System.out.println("桶容量: 5, 漏水速率: 2请求/秒");
System.out.println("\n发送10个连续请求...");
for (int i = 0; i < 10; i++) {
boolean allowed = bucket.allowRequest();
System.out.printf("请求 %2d: %s (水位: %.2f)%n",
(i + 1),
(allowed ? "通过" : "拒绝"),
bucket.getCurrentWaterLevel());
}
System.out.println("\n等待2秒后再尝试...");
Thread.sleep(2000);
for (int i = 0; i < 3; i++) {
boolean allowed = bucket.allowRequest();
System.out.printf("请求 %2d: %s (水位: %.2f)%n",
(i + 1),
(allowed ? "通过" : "拒绝"),
bucket.getCurrentWaterLevel());
}
}
令牌算法
原理
系统以固定速率向桶中添加令牌，每个请求需消耗一个令牌
若桶中有令牌，则允许请求；若桶空，则拒绝请求
优点
- 允许突发流量
- 长期平均速率可控
缺点
- 实现复杂度较高
- 突发可能对下游造成压力
使用场景
- 需要应对突发流量的场景（如消息队列、API网关）
- 长期平均速率需严格控制的场景（如云服务API限流）
代码实现
public class TokenBucket {
/**
* 令牌桶的容量
*/
private final long capacity;
/**
* 令牌添加速率（令牌/秒）
*/
private final double refillRatePerSecond;
/**
* 当前令牌数
*/
private double tokens;
/**
* 上次添加令牌的时间（毫秒）
*/
private long lastRefillTimeMs;
/**
* @param capacity 令牌桶容量（最大令牌数）
* @param refillRatePerSecond 令牌添加速率（令牌/秒）
*/
public TokenBucket(long capacity, double refillRatePerSecond) {
this.capacity = capacity;
this.refillRatePerSecond = refillRatePerSecond;
this.tokens = capacity; // 初始时桶是满的
this.lastRefillTimeMs = System.currentTimeMillis();
}
/**
* 尝试获取一个令牌
*
* @return true表示获取成功，false表示获取失败
*/
public synchronized boolean allowRequest() {
return tryAcquire(1);
}
/**
* 尝试获取指定数量的令牌
*
* @param tokensRequired
* @return
*/
public synchronized boolean tryAcquire(long tokensRequired) {
refillTokens();
if (tokens >= tokensRequired) {
tokens -= tokensRequired;
return true;
}
return false;
}
private void refillTokens() {
long currentTimeMs = System.currentTimeMillis();
double elapsedSeconds = (currentTimeMs - lastRefillTimeMs) / 1000.0;
double tokensToAdd = elapsedSeconds * refillRatePerSecond;
if (tokensToAdd > 0) {
tokens = Math.min(capacity, tokens + tokensToAdd);
lastRefillTimeMs = currentTimeMs;
}
}
public synchronized double getTokens() {
refillTokens();
return tokens;
}
}
限流测试
public static void main(String[] args) throws Exception {
System.out.println("\n===== 测试1: 基本限流功能 =====");
// 创建容量为5，每秒生成2个令牌的限流器
TokenBucket limiter = new TokenBucket(5, 2);
System.out.println("令牌桶容量: 5, 填充速率: 2令牌/秒");
System.out.println("\n发送10个连续请求...");
for (int i = 0; i < 10; i++) {
boolean allowed = limiter.allowRequest();
System.out.printf("请求 %2d: %s (剩余令牌: %.2f)%n", (i + 1), (allowed ? "通过" : "拒绝"), limiter.getTokens());
}
System.out.println("\n结果验证: 由于初始桶是满的，前5个请求应该通过，后5个应该被拒绝");
}