常见限流算法及实现

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个令牌，桶容量为5
        for (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();
            }
        }
    }
}

对比总结