常见限流算法及实现

1. 固定窗口计数器（Fixed Window Counter）

• 原理：在固定时间窗口（如1分钟）内统计请求数，超过阈值则拒绝后续请求。
• 优点：实现简单，内存占用低。
• 缺点：存在窗口切换时的流量突增问题（如相邻窗口边界处可能允许双倍流量）。

/*** @description: 固定窗口限流* @Author: whopxx* @CreateTime: 2025-03-16*/
public class FixedWindowLimiter {private final int limit;      // 窗口内最大请求数private final long windowMs;  // 窗口时间（毫秒）private final AtomicInteger counter = new AtomicInteger(0);private volatile long windowStart = System.currentTimeMillis();public FixedWindowLimiter(int limit, long windowMs) {this.limit = limit;this.windowMs = windowMs;}public boolean tryAcquire() {long now = System.currentTimeMillis();if (now - windowStart > windowMs) {synchronized (this) {if (now - windowStart > windowMs) {windowStart = now;counter.set(0);}}}return counter.incrementAndGet() <= limit;}public static void main(String[] args) {FixedWindowLimiter fixedWindowLimiter = new FixedWindowLimiter(5, 1000);for (int i = 0; i < 100; i++) {boolean b = fixedWindowLimiter.tryAcquire();System.out.println(b);try {Thread.sleep(100);} catch (InterruptedException e) {throw new RuntimeException(e);}}}
}

---

2. 滑动窗口计数器（Sliding Window Counter）

• 原理：将时间分割为更细粒度的子窗口（如每分钟分为60个1秒窗口），统计最近完整时间窗口内的请求总数。
• 优点：缓解固定窗口的临界问题，限流更平滑。
• 缺点：实现较复杂，需存储子窗口的请求记录。

/*** @description: 滑动窗口限流* @Author: whopxx* @CreateTime: 2025-03-16*/
public class SlidingWindowLimiter {private final long windowMs;          // 窗口总时间（毫秒）private final int subWindowCount;     // 子窗口数量private final long subWindowMs;       // 子窗口时间（毫秒）private final int limit;              // 窗口内最大请求数private final AtomicInteger[] counters;private final long[] windowStartTimes; // 每个子窗口的起始时间private final ReentrantLock lock = new ReentrantLock();public SlidingWindowLimiter(int limit, long windowMs, int subWindowCount) {this.limit = limit;this.windowMs = windowMs;this.subWindowCount = subWindowCount;this.subWindowMs = windowMs / subWindowCount;this.counters = new AtomicInteger[subWindowCount];this.windowStartTimes = new long[subWindowCount];for (int i = 0; i < subWindowCount; i++) {counters[i] = new AtomicInteger(0);windowStartTimes[i] = System.currentTimeMillis() - i * subWindowMs;}}public boolean tryAcquire() {long now = System.currentTimeMillis();lock.lock();try {// 1. 清理所有过期的子窗口int expiredCount = 0;for (int i = 0; i < subWindowCount; i++) {if (now - windowStartTimes[i] > windowMs) {expiredCount += counters[i].getAndSet(0);windowStartTimes[i] = now - (now % subWindowMs); // 对齐时间窗口}}// 2. 计算当前子窗口索引int currentSubIdx = (int) ((now % windowMs) / subWindowMs);// 3. 统计当前窗口内总请求数int total = expiredCount;for (int i = 0; i < subWindowCount; i++) {total += counters[i].get();}if (total >= limit) {return false;}// 4. 写入当前子窗口counters[currentSubIdx].incrementAndGet();return true;} finally {lock.unlock();}}public static void main(String[] args) throws InterruptedException {// 测试：限制1秒内最多2次请求，窗口分为5个子窗口（每个200ms）SlidingWindowLimiter limiter = new SlidingWindowLimiter(2, 1000, 5);for (int i = 0; i < 10; i++) {System.out.println("Request " + (i + 1) + ": " + (limiter.tryAcquire() ? "OK" : "Limited"));Thread.sleep(150); // 模拟请求间隔150ms}}
}

---

3. 漏桶算法（Leaky Bucket）

• 原理：请求像水一样进入桶中，桶以固定速率“漏水”（处理请求），桶满则拒绝新请求。
• 优点：强制恒定速率处理，适合平滑突发流量。
• 缺点：无法灵活应对突发流量（即使系统空闲时也无法瞬时处理大量请求）。

/*** @description: 漏桶限流器* @Author: whopxx* @CreateTime: 2025-03-16*/
public class LeakyBucketLimiter {private final long capacity;     // 桶容量private final long rate;         // 流出速率,每秒rate个private AtomicLong water = new AtomicLong(0);          // 当前水量private long lastLeakTime = System.currentTimeMillis();public LeakyBucketLimiter(long capacity, long rateMsPerReq) {this.capacity = capacity;this.rate = rateMsPerReq;}public synchronized boolean tryAcquire() {if (water.get() == 0){lastLeakTime = System.currentTimeMillis();water.set(1);return true;}water.set(water.get() - (System.currentTimeMillis() - lastLeakTime) / 1000 * rate);water.set(water.get() < 0 ? 0 : water.get());lastLeakTime += (System.currentTimeMillis() - lastLeakTime) / 1000 * 1000;if (water.get() >= capacity) {return false;} else {water.set(water.get() + 1);return true;}}public static void main(String[] args) {LeakyBucketLimiter limiter = new LeakyBucketLimiter(5, 1); // 容量为5，流出速率为1个/秒for (int i = 0; i < 100; i++) {boolean b = limiter.tryAcquire();System.out.println(b);try {Thread.sleep(200);} catch (InterruptedException e) {throw new RuntimeException(e);}}}
}

---

4. 令牌桶算法（Token Bucket）

• 原理：系统以固定速率生成令牌存入桶，请求需获取令牌才能处理，无令牌时触发限流。
• 优点：允许突发流量（桶内积累的令牌可一次性使用），更灵活。
• 缺点：需维护令牌生成逻辑，实现较复杂。
• 典型应用：Guava的RateLimiter、Nginx限流模块。

/*** @description: 令牌桶限流算法* @Author: whopxx* @CreateTime: 2025-03-16*/
public class TokenBucketLimiter {//桶的容量private final long capacity;//放入令牌的速率 每秒放入的个数private final long rate;//上次放置令牌的时间private static long lastTime = System.currentTimeMillis();//桶中令牌的余量private static AtomicLong tokenNum = new AtomicLong();public TokenBucketLimiter(int capacity, int permitsPerSecond) {this.capacity = capacity;this.rate = permitsPerSecond;tokenNum.set(capacity);}public synchronized  boolean tryAcquire() {//更新桶中剩余令牌的数量long now = System.currentTimeMillis();tokenNum.addAndGet((now - lastTime) / 1000 * rate);tokenNum.set(Math.min(capacity, tokenNum.get()));//更新时间lastTime += (now - lastTime) / 1000 * 1000;//桶中还有令牌就放行if (tokenNum.get() > 0) {tokenNum.decrementAndGet();return true;} else {return false;}}//测试public static void main(String[] args) {TokenBucketLimiter limiter = new TokenBucketLimiter(3, 2); // 允许每秒放入2个令牌，桶容量为5for (int i = 0; i < 100; i++) {if (limiter.tryAcquire()) {System.out.println("成功请求");} else {System.out.println("请求失败");}try {Thread.sleep(300); // 模拟请求间隔} catch (InterruptedException e) {e.printStackTrace();}}}
}

---

对比总结

方式	适用场景
固定窗口	简单低频场景
滑动窗口	需平滑限流的场景
漏桶算法	恒定速率处理（如流量整形）
令牌桶算法	允许突发的场景（如秒杀）