限流算法详解：令牌桶、漏桶与计数器算法及 Java 实现

漏桶算法

想象一个底部有漏洞的'漏桶'，水（请求 / 数据包）从顶部流入桶中，桶底以固定速率漏水（处理请求）。无论流入速度多快（突发流量），漏水速度始终保持不变，从而限制了输出速率。如果流入速度超过漏水速度，桶会逐渐装满，当桶满后，多余的水会溢出（丢弃请求）。

关键概念：

• 漏桶容量（b）：桶最多能容纳的请求数（或数据量），决定了允许的最大突发流量缓冲。
• 漏水速率（r）：每秒从桶中处理的请求数（固定速率，控制长期输出速率）。
• 流入速率：请求到达的速率（可变，可能突发）。

令牌桶算法是'漏桶算法'的改进版：漏桶算法仅限制输出速率，不允许突发流量；令牌桶允许突发，但长期速率受控。

特点：

• 平滑输出：无论输入流量如何突发，输出速率始终保持固定（由漏水速率决定）。
• 限制突发：桶容量限制了最大缓冲请求数，超过容量的突发流量会被丢弃。
• 无累积令牌：与令牌桶不同，漏桶不会累积'处理能力'，仅被动缓冲和匀速处理。

/**
 * 漏桶限流算法
 */
public class LeakyBucketLimiter {
    // 漏桶的容量
    private final int capacity;
    // 漏水速率 (个/秒)
    private final int rate;
    // 当前桶中的请求数量
    private final AtomicInteger water = new AtomicInteger(0);

    /**
     * 构造函数
     * @param capacity 漏桶的容量
     * @param rate 漏水速率 (个/秒)
     */
    public LeakyBucketLimiter(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        // 启动漏水线程
        startLeaker();
    }

    /**
     * 启动一个定时任务，以固定速率从桶中'漏水'（处理请求）
     */
    private void startLeaker() {
        ScheduledExecutorService scheduledThreadPool = Executors.newSingleThreadScheduledExecutor();
        // 延迟 0 秒后开始执行，每隔 1 秒执行一次
        scheduledThreadPool.scheduleAtFixedRate(() -> {
            // 每次漏水，尝试将当前水量减少 rate 个
            // getAndUpdate 是原子操作，确保线程安全
            water.getAndUpdate(current -> {
                int newWaterLevel = current - rate;
                // 不能让水量小于 0
                return Math.max(0, newWaterLevel);
            });
            // System.out.println("漏水后，当前水量：" + water.get());
            // 用于调试
        }, 0, 1, TimeUnit.SECONDS);
    }

    /**
     * 尝试添加一个请求到漏桶中
     * @return 如果添加成功（桶未满）则返回 true，否则返回 false（桶满，请求被丢弃）
     */
    public boolean tryAddRequest() {
        return tryAddRequest(1);
    }

    /**
     * 尝试添加指定数量的请求到漏桶中
     * @param numberOfRequests 需要添加的请求数量
     * @return 如果添加成功（桶未满）则返回 true，否则返回 false（桶满，请求被丢弃）
     */
    public boolean tryAddRequest(int numberOfRequests) {
        if (numberOfRequests <= 0) {
            throw new IllegalArgumentException("请求数量必须大于 0");
        }
        while (true) {
            int currentWaterLevel = water.get();
            // 检查添加后是否会溢出
            if (currentWaterLevel + numberOfRequests > capacity) {
                return false; // 桶满，拒绝请求
            }
            // 尝试原子地增加水量
            if (water.compareAndSet(currentWaterLevel, currentWaterLevel + numberOfRequests)) {
                return true; // 添加成功
            }
            // 如果 compareAndSet 失败，则循环重试
        }
    }

    /**
     * 获取当前桶中的请求数量 (主要用于调试和监控)
     * @return 当前水量
     */
    public int getCurrentWaterLevel() {
        return water.get();
    }
}

计数器算法

计数器算法的核心思想非常简单：在一个固定的时间窗口内，统计请求的数量，如果请求数超过了预设的阈值，就拒绝后续的请求。

可以想象成一个收费站，在一个小时内（时间窗口）最多允许 100 辆车通过（阈值）。当第 101 辆车到达时，收费站就会关闭栏杆，拒绝其通过。等到下一个小时开始，计数器清零，栏杆重新打开。

优点：

• 实现简单：逻辑非常清晰，代码容易编写和理解。
• 高效：只涉及简单的时间比较和计数操作，性能开销极小。

缺点（临界问题）：

最严重的问题是'临界区'或'突刺流量'问题。假设时间窗口是 1 秒，阈值是 100。如果在第 0.9 秒时来了 100 个请求，全部被允许。然后在第 1.1 秒时（进入了新的窗口），又来了 100 个请求，也全部被允许。那么在 0.9 秒到 1.1 秒这短短 0.2 秒内，系统实际上处理了 200 个请求，这可能会瞬间压垮下游服务。

这个问题的根源在于时间窗口的切换是瞬间完成的，没有平滑过渡。

/**
 * 计数器限流算法
 */
public class CounterLimiter {
    // 一个时间窗口内的最大请求数
    private final int maxRequests;
    // 时间窗口大小（毫秒）
    private final long windowSize;
    // 当前窗口的请求计数器
    private final AtomicInteger currentCount = new AtomicInteger(0);
    // 当前窗口的起始时间戳（毫秒）
    private final AtomicLong windowStartTime = new AtomicLong(System.currentTimeMillis());

    /**
     * 构造函数
     * @param maxRequests 一个时间窗口内的最大请求数
     * @param windowSize 时间窗口大小（秒）
     */
    public CounterLimiter(int maxRequests, int windowSize) {
        this.maxRequests = maxRequests;
        this.windowSize = windowSize * 1000L; // 转换为毫秒
        // 启动一个定时任务，定期检查并重置窗口，避免长时间不请求导致的窗口不更新问题
        startWindowResetTask();
    }

    /**
     * 尝试获取一个请求许可
     * @return 如果获取成功则返回 true，否则返回 false
     */
    public boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 1. 检查是否进入了新的时间窗口，如果是则重置计数器和窗口起始时间
        // 使用 compareAndSet 确保重置操作的原子性
        if (now - windowStartTime.get() > windowSize) {
            // 尝试原子地将窗口起始时间更新为当前时间
            // 只有当当前窗口起始时间仍然是 oldStartTime 时才会更新成功
            // 这可以防止多个线程同时重置窗口
            long oldStartTime = windowStartTime.get();
            if (windowStartTime.compareAndSet(oldStartTime, now)) {
                // 重置计数器
                currentCount.set(0);
                System.out.println("时间窗口已重置，新窗口起始时间：" + now);
            }
        }
        // 2. 检查当前窗口内的请求数是否已超限，并原子地增加计数
        int current = currentCount.getAndIncrement();
        return current < maxRequests;
    }

    /**
     * 启动一个定时任务，定期检查窗口是否过期。
     * 这是一个守护线程，主要用于在长时间没有请求的情况下，也能保证窗口能被重置。
     */
    private void startWindowResetTask() {
        ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();
        // 每隔 windowSize/2 的时间检查一次，确保窗口能及时重置
        scheduler.scheduleAtFixedRate(() -> {
            long now = System.currentTimeMillis();
            if (now - windowStartTime.get() > windowSize) {
                windowStartTime.set(now);
                currentCount.set(0);
                // System.out.println("定时任务触发窗口重置");
                // 用于调试
            }
        }, this.windowSize / 2, this.windowSize / 2, TimeUnit.MILLISECONDS);
    }
}

可以通过 Redis + Lua 来实现计数器算法的功能。典型的场景就是用户登录场景，可以用计数器 + 验证码的功能来实现削峰，降低并发量。可以设定时间窗口为 1s，请求根据具体业务设置请求数阈值，每当发出一个用户登录请求就通过 Lua 脚本在 Redis 中更新计数器。如果达到了阈值就使当前请求进入验证码流程，然后重置计数器。