从零开始掌握限流技术：计数器、滑动窗口、漏桶与令牌桶详解

为什么需要限流呢？

🔹想象一下，你的服务器就像一个繁忙的餐馆，而你的应用就像是餐馆的服务员。餐馆里人山人海，每个人都在争先恐后地想要点餐。这时候，如果没有一个好的限流机制，会发生什么呢？

厨房厨师忙不过来:
- 如果没有限流，服务员会不停地接单，导致厨房里的厨师忙得团团转，最后可能连基本的炒菜都做不好了。
- 限流就像是给餐馆安装了一个“排队机”，确保顾客有序地排队等待点餐，这样厨师就能从容不迫地做好每一盘菜。
顾客体验变差:
- 如果不限制人数，餐馆可能会变得拥挤不堪，顾客需要等很久才能得到服务，甚至可能会有人因为等不及而离开。
- 限流就像是安排一个“领位员”，确保顾客不会等太久，每个人都能享受到愉快的用餐体验。
资源耗尽:
- 如果不限制人数，餐馆可能会消耗掉所有的食材，导致后面来的顾客无餐可吃。
- 限流就像是合理分配食材，确保每个人都能吃到美味的食物，而不是让少数人吃得太多，其他人饿肚子。
系统崩溃:
- 如果不限制请求，服务器可能会因为负载过高而崩溃，就像餐馆因为人太多而导致椅子、桌子倒塌一样。
- 限流就像是给餐馆加上一些结实的家具，确保即使有很多人也能保持稳定。

🔸总之，限流就像是给餐馆安装了一个智能的“门卫”系统，确保餐馆既能容纳足够的顾客，又能保证每个人都能获得良好的服务。而对于服务器来说，限流有助于保护资源，提升用户体验，避免系统过载，确保服务的稳定性和可靠性。

什么场景下需要限流？

随着互联网业务的发展，如秒杀活动、双十一促销等场景，系统经常会面临高并发流量的挑战。在这种情况下，如果不加以限制，系统可能会因为流量过大而崩溃。为了避免这种情况发生，就需要采取限流措施来保护系统。

限流是指在一定时间内对请求量或并发数进行限制，以保护系统免受过大的负载压力。这样可以确保系统在高并发的情况下仍然能够稳定运行，同时也能够防止恶意攻击。常见的限流算法，有计数器算法、滑动窗口计数算法、漏桶算法、令牌桶算法。

在这里插入图片描述

计数器算法

⭐️简介

计数器算法通过在一个固定周期内累加访问次数来限制请求数量。在这个算法中，系统会在设定的时间窗口内记录所有请求的次数，并设置一个最大阈值。当在一个时间窗口内的请求次数达到设定的阈值时，系统会触发拒绝策略，拒绝所有后续请求。每当时间窗口结束，计数器会自动重置为零，开始新的计数周期。

例如，如果我们设置系统在1秒内最多允许100次请求，那么在计数器算法中，这1秒就被划分为一个时间窗口（因此计数器算法也称为固定窗口算法Fixed Window）。在每个时间窗口中，计数器记录当前的请求数量。一旦请求数超过100次，所有后续请求将在这个时间窗口内被拒绝，直到1秒结束，计数器重新开始记录。

在这里插入图片描述

计数器算法虽然简单高效，但存在一个关键问题：它难以处理非均匀分布的流量峰值。例如，在一个1秒的时间窗口内，如果在第1.9秒和第2.1秒分别出现了100次的瞬时高并发请求，虽然这两个时间点分别落在不同的1秒窗口内，但实际上在很短的时间内系统承受了200次请求，超出了设定的阈值。尽管其他时间段的流量是正常的，这种短时间内超过阈值的情况仍然可能导致系统出现问题。

在这里插入图片描述

🔥代码实现（Java）

这段代码定义了一个 SimpleCounterRateLimiter 类，它可以用来限制每秒内的请求数量。当每秒内的请求数量达到或超过设定的最大值时，新的请求将被拒绝。

import java.time.LocalTime;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;public class MyFixedWindowRateLimiterDemo {// 阈值private static final int QPS = 2;// 计数器private static final AtomicInteger counter = new AtomicInteger();// 初始化调度器，定期重置计数器private static final ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(1);static {scheduler.scheduleAtFixedRate(() -> {counter.set(0);}, 0, 1, TimeUnit.SECONDS);  // 每1秒重置计数器}public static boolean tryAcquire() {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 + " 请求通过");}}scheduler.shutdown(); // 在程序结束时关闭调度器}
}

❄️利弊

计数器限流算法简单高效，易于实现且资源消耗低，但其主要缺点是在处理非均匀分布的突发流量时可能无法准确反映瞬时峰值，从而导致系统过载。

滑动窗口算法

⭐️简介

滑动窗口算法改进了固定窗口算法中的临界问题，通过将固定窗口进一步细分为多个小周期，并为每个小周期记录请求次数。随着窗口向前滑动，过期的小周期会被移除，而在判断是否限流时，需累加当前窗口内所有小周期的请求次数并与阈值进行比较。这种方法能更准确地捕捉瞬时流量峰值，避免系统过载。

在这里插入图片描述

为了应对固定窗口算法中的临界问题，我们采用滑动窗口算法，将1秒的时间窗口细分为5个200毫秒的小周期，并记录每个小周期内的请求次数。以之前的场景为例，在1.9秒和2.1秒的时间点分别发生了100次恶意并发请求。当滑动窗口到达第5个小周期时，该周期内的请求次数为100次，尚未达到阈值。然而，当窗口滑动到第6个小周期时，累计请求次数变为200次，这时超过了阈值，从而触发了访问限制。

🔥代码实现（Java）

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 + " 请求通过");}}}
}

❄️利弊

滑动窗口限流算法能够更精确地控制瞬时流量峰值，有效避免因突发请求而导致的系统过载，但其实现复杂度较高且资源消耗相较于简单计数器算法更大。

漏桶算法

⭐️简介

漏桶算法（Leaky Bucket） 是一个形象的比喻，它描述了一个桶（即队列）接收来自生产端的水（即请求或流量），并且这个桶底部有一个孔，以恒定的速度漏水（即消费端不断地处理队列中的请求）。如果水流入桶的速度超过了漏水的速度（即生产端的请求速率超过了消费端的处理能力），桶中的水就会逐渐积累。一旦桶内的水量超过了桶的容量，多余的水就会溢出（即请求被拒绝），从而实现了网络流量的整形和限流功能。

在这个模型中，漏水的速度代表了限流的阈值，即单位时间内系统可以处理的最大请求量。例如，如果QPS设置为100，则表示系统每秒最多可以处理100个请求。如果生产端的请求速率超过了这个阈值，请求就会在队列中堆积，最终导致超出桶的容量而被拒绝。

在这里插入图片描述

🔥代码实现（Java）

这个例子使用了一个 AtomicLong 作为桶中的水量，并使用 ScheduledExecutorService 来模拟桶漏水的过程。

import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;public class LeakyBucketRateLimiter {private final AtomicLong bucket = new AtomicLong(0L);private final long capacity;private final long leakRate;private final ScheduledExecutorService scheduler = Executors.newSingleThreadScheduledExecutor();private final Runnable leakAction = this::leakBucket;public LeakyBucketRateLimiter(long capacity, long leakRate) {this.capacity = capacity;this.leakRate = leakRate;scheduleLeak();}public synchronized boolean allowRequest() {long currentWaterLevel = bucket.get();// 如果桶满了，拒绝请求if (currentWaterLevel >= capacity) {return false;}// 否则，添加一个单位的水bucket.addAndGet(1);return true;}private void leakBucket() {long currentWaterLevel = bucket.getAndAdd(-leakRate);if (currentWaterLevel - leakRate < 0) {bucket.set(0);}}private void scheduleLeak() {scheduler.scheduleAtFixedRate(leakAction, 1, 1, TimeUnit.SECONDS);}public static void main(String[] args) {LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(200, 10); // 容量200，每秒漏10个单位// 模拟客户端请求ExecutorService executor = Executors.newFixedThreadPool(10);for (int i = 0; i < 500; i++) {int requestId = i;executor.submit(() -> {if (rateLimiter.allowRequest()) {System.out.println("Request " + requestId + " is allowed.");} else {System.out.println("Request " + requestId + " is denied.");}});}executor.shutdown();}
}

❄️利弊

漏桶算法能够平滑输入流量并确保系统负载稳定，但其主要缺点在于无法区分突发流量和持续高负载，可能导致正常突发流量被错误地限制。

令牌桶算法

⭐️简介

令牌桶算法是漏桶算法的一种改进版本，常用于网络流量整形和限流。它同样使用一个桶，但桶中存放的是固定数量的令牌。算法以一定的速率（阈值）向桶中发放令牌。每当一个请求到来时，必须先从桶中获取一个令牌才能继续处理，处理完成后令牌被丢弃；如果没有可用令牌，则执行拒绝策略（如直接拒绝或排队等待）。此外，向桶中发放令牌的动作是持续不断的，如果桶满则令牌会被丢弃。

在这里插入图片描述

表面上看，令牌桶算法和漏桶算法是相反的，一个"进水"，一个是"漏水"。但与漏桶算法实际不同的是，令牌桶不仅能够在限制客户端请求流量速率的同时还能允许一定程度的突发流量。限流和允许瞬时流量其实并不矛盾，在大多数场景中，小批量的突发流量系统是完全可以接受的。

在令牌桶算法中，令牌是持续不断地生成并存入到一个“桶”中。当网络流量相对平缓时，这个桶可以积累额外的令牌作为储备。一旦出现突发的大流量（即流量尖峰），这些储备的令牌就可以立即用于处理这些额外的请求，确保它们能够被快速处理而不必等待。

只有当流量超过了预设的最大阈值时，也就是桶中的令牌被耗尽之后，新的请求才会因为拿不到令牌而被延迟处理或直接拒绝。这种方式有助于保护后端系统免受流量峰值的影响，保持其稳定运行。

🔥代码实现（Java）

这里提供一下代码实现，单机下推荐使用(或者仿写)Google Guava自带的限流工具类RateLimiter

先引入依赖：

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

设置发放令牌的速率，然后直接调用tryAcquire，大家感兴趣的可以看看其源码实现：

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");}}}
}

❄️利弊

与漏桶算法相比，令牌桶算法的实现更为复杂。它不仅需要维护令牌的生成和消耗过程，还需要有精确的时间控制来确保令牌的生成速率符合预期，并且还需要一定的内存空间来存储这些令牌。 尽管如此，令牌桶算法提供了更灵活的流量控制机制，允许一定程度上的突发流量处理，而不仅仅是简单地丢弃超出限制的数据包。

小结

算法名称	优点	缺点	主要应用场景
漏桶算法	- 实现简单 - 适用于简单的流量控制	- 无法处理突发流量 - 可能导致数据丢失	- 网络流量控制 - 基础的限流策略
令牌桶算法	- 支持突发流量 - 可以调整速率	- 实现较复杂 - 需要更多内存	- API调用频率限制 - 网络流量控制 - 高级限流策略
固定窗口算法	- 实现简单 - 易于理解和维护	- 在窗口切换时可能会导致瞬时的流量突变	- 简单的API调用频率限制 - 基础的限流策略
滑动窗口算法	- 能够平滑流量突变 - 提供更精确的限流	- 实现复杂度较高 - 需要维护更多的状态信息	- 高精度的API调用频率限制 - 网络流量控制 - 复杂的限流策略