常见限流算法：计数器、滑动窗口、漏桶与令牌桶

限流算法是API高可用的地基。我见过不少团队，上来就选令牌桶，结果业务场景根本不匹配——限流效果差，还白白浪费性能。

今天我把四种主流算法掰开揉碎讲清楚。每种算法我都会说原理、画流程、给代码，最后再做个横向对比。你想想看，搞懂了这些，以后选型心里就有底了。

2.1 计数器算法

计数器是最朴素的限流方式。说白了，就是在一个时间窗口内数请求个数，超了就直接拒绝。

原理：

• 选定一个固定时间窗口（比如1秒）
• 维护一个计数器，每来一个请求就+1
• 如果计数器超过阈值，就拒绝后续请求
• 窗口结束时，计数器归零

// 计数器算法伪代码
public class CounterLimiter {
    private long windowStart = System.currentTimeMillis();
    private int counter = 0;
    private final int limit = 100;  // 每秒100个请求
    private final long windowSize = 1000L; // 1秒

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        if (now - windowStart > windowSize) {
            // 新窗口，重置
            windowStart = now;
            counter = 0;
        }
        if (counter < limit) {
            counter++;
            return true;
        }
        return false;
    }
}

致命缺陷：临界突变

计数器算法有个大坑——窗口边界处的流量尖刺。举个例子：

• 窗口1的最后100ms，来了100个请求（刚好满）
• 窗口2的前100ms，又来了100个请求（重置后也满）
• 实际上200ms内处理了200个请求，远超阈值

我在项目中遇到过这个坑。有一次线上告警，数据库连接池被打爆了。查了半天，发现就是计数器算法在窗口切换时产生了双倍流量。嗯，从那以后我再也不敢在核心链路上裸用计数器了。

2.2 滑动窗口算法

滑动窗口是计数器的改良版。它把一个大窗口切成多个小格子，用滑动的方式统计流量。这样能有效解决临界突变问题。

原理：

• 把时间窗口分成N个小片段（比如1秒分成10个100ms的格子）
• 每个格子独立计数
• 滑动窗口向前移动时，丢弃最旧的格子，加入最新的格子
• 统计当前窗口内所有格子的总和

// 滑动窗口算法伪代码
public class SlidingWindowLimiter {
    private final int windowSize = 10;  // 10个格子
    private final int[] counters = new int[windowSize];
    private int currentIndex = 0;
    private long lastTime = System.currentTimeMillis();
    private final int limit = 100;

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        long elapsed = now - lastTime;
        int slotsToMove = (int)(elapsed / 100); // 每个格子100ms
        
        // 滑动窗口
        for (int i = 0; i < slotsToMove && i < windowSize; i++) {
            currentIndex = (currentIndex + 1) % windowSize;
            counters[currentIndex] = 0;
        }
        lastTime = now;
        
        // 统计当前窗口总请求数
        int total = 0;
        for (int count : counters) {
            total += count;
        }
        
        if (total < limit) {
            counters[currentIndex]++;
            return true;
        }
        return false;
    }
}

格子越多，精度越高

滑动窗口的精度取决于格子数量。格子越多，统计越平滑，但内存开销也越大。我个人习惯在核心接口用20个格子（50ms粒度），非核心用5个格子就够了。

2.3 漏桶算法

漏桶算法的思路很形象——想象一个底部有洞的水桶。水流进来，从洞漏出去。如果水来得太快，桶满了就溢出（拒绝请求）。

核心特性：

• 恒定速率出水：无论进水多快，出水速率固定
• 桶容量有限：可以应对突发流量，但超过容量就丢弃
• 强制平滑：把不均匀的流量变成均匀的流量

// 漏桶算法伪代码
public class LeakyBucketLimiter {
    private long lastLeakTime = System.currentTimeMillis();
    private int water = 0;  // 当前水量
    private final int capacity = 100;  // 桶容量
    private final int leakRate = 10;   // 每秒漏10个

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 先漏水
        long elapsed = now - lastLeakTime;
        int leaked = (int)(elapsed * leakRate / 1000);
        water = Math.max(0, water - leaked);
        lastLeakTime = now;
        
        // 判断是否还能装水
        if (water < capacity) {
            water++;
            return true;
        }
        return false;
    }
}

适用场景：

漏桶最适合需要严格平滑流量的场景。比如数据库写入、消息队列生产、第三方API调用。我曾经在对接支付网关时用过漏桶——对方要求每秒不超过50笔，而且必须均匀分布。漏桶正好满足这个需求。

2.4 令牌桶算法

令牌桶是业界最常用的限流算法。它允许一定程度的突发，又能控制平均速率。很多开源框架（如Guava RateLimiter）都基于它。

原理：

• 以固定速率往桶里放令牌
• 每个请求需要消耗一个令牌
• 桶有容量上限，令牌满了就不再增加
• 请求来了，有令牌就通过，没有就等待或拒绝

// 令牌桶算法伪代码
public class TokenBucketLimiter {
    private long lastRefillTime = System.currentTimeMillis();
    private int tokens = 0;  // 当前令牌数
    private final int capacity = 100;  // 桶容量
    private final int refillRate = 10; // 每秒放10个令牌

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 补充令牌
        long elapsed = now - lastRefillTime;
        int newTokens = (int)(elapsed * refillRate / 1000);
        tokens = Math.min(capacity, tokens + newTokens);
        lastRefillTime = now;
        
        // 消耗令牌
        if (tokens > 0) {
            tokens--;
            return true;
        }
        return false;
    }
}

为什么令牌桶这么流行？

因为它兼顾了限流和突发。桶里攒的令牌可以应对短时流量高峰。比如系统平时空闲，桶里攒了100个令牌。突然来了一波流量，前100个请求可以瞬间通过，后续请求才被限流到平均速率。

我记得有一次双十一大促，核心接口的流量峰值是平时的20倍。我们用令牌桶配合预热策略，提前攒令牌，成功扛住了流量洪峰。如果当时用漏桶，估计早就被压垮了。

2.5 四种算法对比

下面这张表是我整理的对比，方便你快速选型：

特性	计数器	滑动窗口	漏桶	令牌桶
实现复杂度	极低	低	中	中
内存开销	O(1)	O(N)	O(1)	O(1)
突发处理	差	一般	差	好
流量平滑	无	一般	强制平滑	允许突发
临界突变	严重	轻微	无	无
适用场景	简单限流、非核心接口	一般业务接口	严格均匀流量	大多数API场景

2.6 算法选型决策树

为了帮你快速决策，我画了一张流程图：

2.7 我的选型建议

做了这么多年限流，我总结了几条经验：

1. 核心API用令牌桶——它最灵活，能应对突发，也能控制平均速率。Guava的RateLimiter直接拿来用，别自己造轮子。
2. 需要严格平滑用漏桶——比如对接外部系统，对方要求流量必须均匀。漏桶虽然牺牲了突发能力，但换来了确定性。
3. 非核心接口用滑动窗口——实现简单，效果够用。别为了一个日志接口去搞复杂的令牌桶。
4. 计数器尽量别用——除非你很清楚自己在做什么。临界突变这个坑，踩过的人都知道疼。