秒杀场景如何选型？图解四种主流限流算法原理与实现

随着互联网业务的蓬勃发展，尤其在秒杀、大促活动或被恶意攻击等高并发场景下，系统的平稳运行面临着巨大挑战。为了应对瞬时洪峰流量，保护系统及下游服务，限流成为了一种关键的技术手段。除了限流，还有熔断、降级、隔离等方案，本文将聚焦于几种常见的限流算法，深入剖析其原理与实现。

所谓限流，就是对请求或并发数进行限制，通过控制单位时间内的请求量，来保障系统的核心服务能力。主流的限流算法包括计数器算法、滑动窗口计数算法、漏桶算法和令牌桶算法。

计数器算法

计数器算法是原理最简单的一种限流方式。其核心思想是：在一个固定的时间窗口内，通过计数器累加访问次数。我们预先设定一个周期（即时间窗口）内系统最多能处理的请求数量（即阈值）。当计数器达到该阈值时，便触发拒绝策略；待时间窗口结束，计数器归零，重新开始计数。因此，它也被称为固定窗口算法。

例如，假设系统设定的阈值是1秒内最多处理100个请求。在计数器算法中，我们需要将时间划分为固定大小的窗口（这里以1秒为一个窗口），并用一个计数器记录当前窗口内的请求数。一旦请求数超过100，后续请求将被直接拒绝，直到这1秒结束，计数器重置。

计数器算法的优点是实现简单、占用内存小、性能高。但它存在一个明显的缺陷：临界问题。由于时间窗口是固定的，流量在窗口内并非均匀分布。考虑一个极端情况：在 1.9秒 和 2.1秒 这两个时间点，系统分别遭受了 100次 并发请求。从 1.9秒 到 2.9秒 这1秒内，系统实际承受了 200次 请求，远超阈值。尽管 窗口2 和 窗口3 各自的计数器并未超标，但这瞬间的流量冲击仍可能导致系统崩溃。

以下是一个简单的Java实现Demo（其他语言可参考改写）：

public class MyFixedWindowRateLimiterDemo {
    // 阈值
    private static Integer QPS = 2;
    // 时间窗口（毫秒）
    private static long TIME_WINDOWS = 1000;
    // 计数器
    private static AtomicInteger counter = new AtomicInteger();

    //上一个窗口的开始时间
    private static long START_TIME = System.currentTimeMillis();

    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            counter.set(0);
            START_TIME = System.currentTimeMillis();
        }
        return counter.incrementAndGet() <= QPS;
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

滑动窗口计数算法

滑动窗口算法 源自网络传输层的流量控制技术，它是对固定窗口算法的一种优化，旨在解决其临界问题。该算法不再使用固定大小的窗口，而是将一个大的时间窗口进一步划分为多个更小的周期。每个小周期都独立记录请求次数。随着时间推移，窗口会向后“滑动”（每次移动一个小周期），并删除过期的周期数据。判断是否限流时，需要累加当前窗口内所有小周期的请求总数，再与阈值进行比较。

沿用上文的例子，我们将1秒的时间窗口划分为5个200毫秒的小周期。当在 1.9秒 和 2.1秒 分别出现100次请求时，滑动到第5个小周期时，请求量为100，未超阈值。但当窗口滑动到第6个小周期时，覆盖的请求量变为200，此时将触发限流。

滑动窗口划分得越细，窗口的滑动就越平滑，限流统计也越精确。但随之而来的是需要更多的存储空间来记录每个小周期的数据，实现上也比计数器算法更复杂一些。

以下是一个参考实现的Demo：

public class MySlidingWindowRateLimiterDemo {

    /** 队列id和队列的映射关系，队列里面存储的是每一次通过时候的时间戳，这样可以使得程序里有多个限流队列 */
    private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();

    //阈值
    private static int QPS = 2;
    //时间窗口总大小（毫秒）
    private static long WindowSize = 10 * 1000;

    /**
     * 滑动时间窗口限流算法
     * 在指定时间窗口，指定限制次数内，是否允许通过
     *
     * @param listId     队列id
     * @param count      限制次数
     * @param timeWindow 时间窗口大小
     * @return 是否允许通过
     */
    public static synchronized boolean tryAcquire(String listId, int count, long timeWindow) {
        // 获取当前时间
        long nowTime = System.currentTimeMillis();
        // 根据队列id，取出对应的限流队列，若没有则创建
        List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
        // 如果队列还没满，则允许通过，并添加当前时间戳到队列开始位置
        if (list.size() < count) {
            list.add(0, nowTime);
            return true;
        }

        // 队列已满（达到限制次数），则获取队列中最早添加的时间戳
        Long farTime = list.get(count - 1);
        // 用当前时间戳 减去 最早添加的时间戳
        if (nowTime - farTime <= timeWindow) {
            // 若结果小于等于timeWindow，则说明在timeWindow内，通过的次数大于count
            // 不允许通过
            return false;
        } else {
            // 若结果大于timeWindow，则说明在timeWindow内，通过的次数小于等于count
            // 允许通过，并删除最早添加的时间戳，将当前时间添加到队列开始位置
            list.remove(count - 1);
            list.add(0, nowTime);
            return true;
        }
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 20; i++) {
            Thread.sleep(1000);
            LocalTime now = LocalTime.now();
            if (!tryAcquire("ip", QPS, WindowSize)) {// 任意10秒内，只允许2次通过;自定义限流规则“ip”
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

滑动窗口算法虽然解决了临界突变问题，但它依然存在一个特点：一旦窗口内流量达到阈值，后续请求会被瞬间切断。在实际生产环境中，我们更希望流量能平滑地进入系统，而非如此“粗暴”地被拒绝。

漏桶算法

漏桶算法 是一个非常形象的比喻。想象一个底部有孔的桶：水（代表请求/流量）从进水口（生产端）流入桶中（一个队列），桶会以恒定的速率漏水（消费端持续处理请求）。如果进水速度过快，超过了漏水速度，桶内的水就会逐渐累积。一旦桶的容量（固定的）被装满，后续流入的水就会溢出（请求被拒绝）。这种模型能很好地实现流量整形和平滑限流。

这里“漏水”的速率就是限流的阈值，例如QPS为100，表示系统每秒最多能处理100个请求。如果生产端的速率持续超过阈值，请求就会在桶中堆积，最终因桶满而触发拒绝策略。

漏桶算法的优点在于实现简单、易于理解，并且能严格限制请求的处理速率，有效防止网络拥塞和系统过载。但它也有明显的缺点：

1. 无论当前系统负载如何，请求都必须等待漏桶处理，这会导致固定的延迟，不适用于对实时性要求很高的场景。
2. 由于处理速率是恒定的，即使网络空闲，也无法充分利用系统资源处理突发流量。

以下是一个简化的漏桶算法Demo（生产环境慎用）：

public class MyLeakyBucketRateLimiterDemo {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int rate;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public MyLeakyBucketRateLimiterDemo(int rate, int capacity) {
        this.capacity = capacity;
        this.rate = rate;
    }

    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * rate);
        timeStamp = now;

        // 如果未满，则放行；否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws InterruptedException {
        MyLeakyBucketRateLimiterDemo limiterDemo = new MyLeakyBucketRateLimiterDemo(2,5);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(500);
            LocalTime now = LocalTime.now();
            if (!limiterDemo.tryAcquire()) {
                System.out.println(now + " 请求被限流");
            } else {
                System.out.println(now + " 请求通过");
            }
        }
    }
}

令牌桶算法

令牌桶算法 是漏桶算法的一种改进，也是网络流量整形和限流中最常用的算法。它同样有一个桶，但里面装的是固定数量的令牌。系统会以恒定的速率（阈值）向桶中投放令牌。当请求到达时，必须先从桶中获取一个令牌才能被处理，处理完毕后令牌被消耗。如果桶中没有令牌，则请求被拒绝或排队等待。投放令牌的过程是持续进行的，如果桶已满，新生成的令牌会被丢弃。

表面上看，令牌桶和漏桶一个“加令牌”，一个“漏水”，方向相反。但令牌桶算法的精髓在于，它在限制平均流量的同时，允许一定程度的突发流量。这在大多数场景中是非常实用的，因为系统通常可以承受小批量的瞬时高峰。

当系统流量较平缓时，令牌桶会持续累积冗余的令牌。一旦出现突发流量，这些预存的令牌可以立即被消耗，使得请求能够快速通过。只有当突发流量超过桶的令牌储备时，超出的请求才会被限流。这使得系统既能保持稳定，又能充分利用资源应对合理的高峰。

当然，令牌桶算法的实现比漏桶更复杂，需要精确控制令牌的生成与消耗，并消耗更多内存来存储令牌状态。

在单机环境下，强烈推荐使用（或参考）Google Guava库中的RateLimiter工具类。首先引入依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>30.0-jre</version>
</dependency>

然后可以非常方便地使用：

public class MyTokenBucketRateLimiterDemo {
    public static void main(String[] args) throws InterruptedException {
        // 每1s发放5个令牌到桶里
        RateLimiter rateLimiter = RateLimiter.create(5);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(100L);
            if(rateLimiter.tryAcquire()) {
                System.out.println("get one token");
            }else {
                System.out.println("no token");
            }
        }
    }
}

补充：分布式限流

以上示例均适用于单机场景。在分布式系统环境下，算法的核心思想不变，但需要将限流状态（如计数器、令牌数）存储到全局中间件中。常见方案有：

• 使用 Redis + Lua 脚本保证原子性操作来实现分布式限流。
• 使用 Redisson 等客户端，其内部封装了基于Redis的限流器。
• 使用 Sentinel 等专业的流量控制组件，它提供了更完善的监控和控制台。

此外，也可以在流量入口层利用 Nginx 进行限流，它提供了 ngx_http_limit_req_module（限制请求速率）和 ngx_http_limit_conn_module（限制连接数）两个模块。

总结

本文介绍了四种主流的限流算法：计数器算法简单但存在临界问题；滑动窗口算法优化了临界问题但实现稍复杂；漏桶算法能平滑流量但无法应对突发；令牌桶算法则兼具平滑限制和应对突发流量的能力，是最为常用的方案。

理解这些限流算法的工作原理和特性，是进行高并发系统设计的基础。在实际项目中，需要根据业务特点（如是否允许突发）、性能要求和技术栈（如是否已使用Redis）来选择合适的限流方案，甚至可以组合使用。对于大部分基于 Java 技术栈的项目，Guava的RateLimiter或分布式下的Redis方案都是不错的起点。

希望这篇图解能帮助你更好地理解限流。想了解更多关于系统架构和性能优化的实战内容，欢迎访问云栈社区进行交流探讨。

---

参考资料：

• https://en.wikipedia.org/wiki/Rate_limiting
• https://baike.baidu.com/item/%E6%BC%8F%E6%A1%B6%E7%AE%97%E6%B3%95
• https://www.cnblogs.com/dijia478/p/13807826.html