一文秒解四大经典限流算法

本文主要是介绍一文秒解四大经典限流算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

阅读前提：没有最好的算法，只有最适合的算法！

限流算法：

• 固定窗口限流算法

• 滑动窗口限流算法

• 漏桶限流算法

• 令牌桶限流算法

固定窗口限流算法

介绍

固定窗口限流算法（Fixed Window Rate Limiting Algorithm）是一种最简单的限流算法，其原理是在固定时间窗口(单位时间)内限制请求的数量。该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。具体来说，算法将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。

这个算法就是说：在一个固定时间段内，可以接收固定数量的请求。拒绝多余的请求。

实现

下面是用Java的实现：

我们可以根据自己需要来调整 maxRequests 和 windowTimeMillis 参数来设置限流策略。

import java.util.concurrent.atomic.AtomicInteger;
​
public class FixedWindowRateLimiter {private final int maxRequests; // 最大请求数量private final long windowTimeMillis; // 时间窗口大小（毫秒）private final long[] timestamps; // 存储时间戳的数组private final AtomicInteger count; // 记录当前请求数量的原子整数
​public FixedWindowRateLimiter(int maxRequests, long windowTimeMillis) {this.maxRequests = maxRequests;this.windowTimeMillis = windowTimeMillis;this.timestamps = new long[maxRequests];this.count = new AtomicInteger(0);}
​public synchronized boolean allowRequest() {long now = System.currentTimeMillis();int currentCount = count.get();if (currentCount < maxRequests) {// 如果当前请求数量未达到最大限制，允许该请求count.incrementAndGet();timestamps[currentCount] = now;return true;} else {// 检查窗口中最早的请求是否已经过期long oldestTimestamp = timestamps[0];if (now - oldestTimestamp > windowTimeMillis) {// 如果已过期，重置时间窗口并允许该请求resetWindow(now);count.incrementAndGet();timestamps[0] = now;return true;} else {// 如果未过期，则拒绝该请求return false;}}}
​private void resetWindow(long now) {// 重置时间窗口，即将时间戳向前移动并重置请求数量int currentCount = count.get();for (int i = 1; i < currentCount; i++) {timestamps[i - 1] = timestamps[i];}count.set(0);}
​public static void main(String[] args) {// 示例用法FixedWindowRateLimiter rateLimiter = new FixedWindowRateLimiter(5, 60000); // 每分钟限制5个请求for (int i = 0; i < 10; i++) {if (rateLimiter.allowRequest()) {System.out.println("请求 " + (i + 1) + ": 允许");} else {System.out.println("请求 " + (i + 1) + ": 拒绝");}try {Thread.sleep(1000); // 模拟请求之间的一些延迟} catch (InterruptedException e) {e.printStackTrace();}}}
}
​

优缺点分析

• 优点：算法简单，易于实现和理解。

• 缺点：存在明显的临界问题。比如说：我们设置的是1分钟内，可以接收10个请求。如果在59s的时候，突然来了10个请求，然后在下个一分钟的时候，又来了10个请求。相当于2s内来了20个请求，这使得并发量极高，这不明显的没有起到限流的作用吗？

滑动窗口限流算法

滑动窗口限流算法是一种常用的限流算法，用于控制系统对外提供服务的速率，防止系统被过多的请求压垮。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。它可以解决固定窗口临界值的问题。

个人理解：滑动窗口限流就是将一个时间段划分为多个小区间。比如说在一分钟内我们可以限流30个请求，然后我们将每2秒划分为一个小区间，来进行滑动窗口限流

实现

windowSize表示窗口大小（单位：秒），maxRequests表示每个窗口内允许的最大请求数量。使用Deque来存储请求时间戳队列。allowRequest方法用于判断是否允许请求通过，它会根据当前时间戳和窗口大小来判断请求是否在窗口内，并根据窗口内的请求数量来决定是否允许请求通过。

package com.pxl.test.sf;
​
import java.time.Duration;
import java.time.Instant;
import java.util.ArrayDeque;
import java.util.Deque;
​
/*** 滑动窗口限流算法实现*/
public class SlidingWindowRateLimiter {private final int windowSize; // 窗口大小（单位：秒）private final int maxRequests; // 每个窗口内允许的最大请求数量private final Deque<Instant> requestTimes; // 请求时间戳队列
​/*** 构造函数* @param windowSize 窗口大小（单位：秒）* @param maxRequests 每个窗口内允许的最大请求数量*/public SlidingWindowRateLimiter(int windowSize, int maxRequests) {this.windowSize = windowSize;this.maxRequests = maxRequests;this.requestTimes = new ArrayDeque<>();}
​/*** 判断是否允许请求通过* @return 如果允许请求通过返回true，否则返回false*/public synchronized boolean allowRequest() {Instant now = Instant.now();Instant windowStart = now.minusSeconds(windowSize);
​// 移除窗口外的请求时间戳while (!requestTimes.isEmpty() && requestTimes.peek().isBefore(windowStart)) {requestTimes.poll();}
​// 判断窗口内请求数量是否超过阈值if (requestTimes.size() < maxRequests) {requestTimes.offer(now);return true; // 允许请求通过} else {return false; // 拒绝请求}}
​/*** 主函数，用于测试滑动窗口限流算法* @param args 命令行参数*/public static void main(String[] args) {SlidingWindowRateLimiter rateLimiter = new SlidingWindowRateLimiter(5, 1); // 窗口大小为5秒，每个窗口内最多处理1个请求for (int i = 0; i < 20; i++) {if (rateLimiter.allowRequest()) {System.out.println("请求 " + (i + 1) + ": 允许");} else {System.out.println("请求 " + (i + 1) + ": 拒绝");}try {Thread.sleep(1000); // 模拟请求之间的延迟} catch (InterruptedException e) {e.printStackTrace();}}}
}

​

优缺点分析

• 优点

  • 简单易懂

  • 精度高（可调整时间窗口大小来实现不同的限流效果）

  • 可扩展性强（可以容易的与其他限流算法结合使用）

• 缺点

  • 突发流量无法处理（无法应对短时间内的大量请求，但是一旦到达限流后，请求都会直接暴力被拒绝。这样会导致我们损失一部分请求，这其实对于产品来说，并不太友好），需要合理调整时间窗口大小。

漏桶限流算法

介绍

漏桶限流算法（Leaky Bucket Algorithm）是一种流量控制算法，用于控制流入网络的数据速率，以防止网络拥塞。它的思想是将数据包看作是水滴，漏桶看作是一个固定容量的水桶，数据包像水滴一样从桶的顶部流入桶中，并通过桶底的一个小孔以一定的速度流出，从而限制了数据包的流量。

漏桶限流算法的基本工作原理是：对于每个到来的数据包，都将其加入到漏桶中，并检查漏桶中当前的水量是否超过了漏桶的容量。如果超过了容量，就将多余的数据包丢弃。如果漏桶中还有水，就以一定的速率从桶底输出数据包，保证输出的速率不超过预设的速率，从而达到限流的目的。

实现

我们可以根据需要调整 capacity（漏桶容量）和 ratePerSecond（漏桶速率）来设置限流策略。

import java.util.concurrent.atomic.AtomicLong;
​
public class LeakyBucketRateLimiter {private final long capacity; // 漏桶容量private final long ratePerSecond; // 漏桶速率（每秒处理请求数量）private long water; // 当前漏桶中的水量private long lastLeakTime; // 上一次漏水的时间
​public LeakyBucketRateLimiter(long capacity, long ratePerSecond) {this.capacity = capacity;this.ratePerSecond = ratePerSecond;this.water = 0;this.lastLeakTime = System.currentTimeMillis();}
​public synchronized boolean allowRequest() {long now = System.currentTimeMillis();// 计算当前时间距离上一次漏水的时间间隔long elapsedTime = now - lastLeakTime;// 计算漏桶在此时间间隔内漏掉的水量long leakedWater = elapsedTime * ratePerSecond / 1000;// 更新漏桶中的水量water = Math.max(0, water - leakedWater);// 更新上一次漏水的时间lastLeakTime = now;// 判断漏桶中的水量是否小于漏桶容量，如果小于则允许请求通过if (water < capacity) {water++;return true;} else {// 漏桶已满，拒绝请求return false;}}
​public static void main(String[] args) {// 示例用法LeakyBucketRateLimiter rateLimiter = new LeakyBucketRateLimiter(10, 2); // 漏桶容量为10，速率为每秒2个请求for (int i = 0; i < 20; i++) {if (rateLimiter.allowRequest()) {System.out.println("请求 " + (i + 1) + ": 允许");} else {System.out.println("请求 " + (i + 1) + ": 拒绝");}try {Thread.sleep(500); // 模拟请求之间的一些延迟} catch (InterruptedException e) {e.printStackTrace();}}}
}
​

优缺点分析

• 优点

  • 可以平滑限制请求处理速度，避免瞬间请求增多导致系统崩溃。

  • 可以控制请求处理速度，使系统可以适应不同的流量需求，避免过载或过度闲置。

  • 可以调整桶的大小和漏出速率来满足不同限流需求，灵活地适应不同场景。

• 缺点

  • 需要对请求进行缓存，增加服务器的内存消耗

  • 固定速率的处理请求

  • 不适应突发流量情况

适用于平滑流量、限制速率以及防止突发流量等场景。然而，在处理突发流量和动态调整处理速率等方面，漏桶算法存在一些局限性，需要根据具体的业务需求和系统特点进行选择和调整。

令牌桶限流算法

令牌桶算法是一种常用的限流算法，可以用于限制单位时间内请求的数量。该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入一定数量的令牌。当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，否则请求被拒绝。

实现

可以根据需要调整 capacity（令牌桶容量）和 ratePerSecond（令牌生成速率）来设置限流策略。

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
​
public class TokenBucketRateLimiter {private final int capacity; // 令牌桶容量private final int ratePerSecond; // 令牌生成速率（每秒生成令牌数量）private BlockingQueue<Object> tokens; // 令牌桶，使用阻塞队列实现
​public TokenBucketRateLimiter(int capacity, int ratePerSecond) {this.capacity = capacity;this.ratePerSecond = ratePerSecond;this.tokens = new LinkedBlockingQueue<>(capacity);// 初始化令牌桶，将令牌添加到队列中for (int i = 0; i < capacity; i++) {tokens.offer(new Object());}// 启动令牌生成线程，每秒生成指定数量的令牌new Thread(() -> {while (true) {try {Thread.sleep(1000 / ratePerSecond);tokens.offer(new Object());} catch (InterruptedException e) {e.printStackTrace();}}}).start();}
​public boolean allowRequest() {return tokens.poll() != null; // 尝试从令牌桶中取出一个令牌，如果成功取出则允许请求通过}
​public static void main(String[] args) {// 示例用法TokenBucketRateLimiter rateLimiter = new TokenBucketRateLimiter(10, 2); // 令牌桶容量为10，速率为每秒2个令牌for (int i = 0; i < 20; i++) {if (rateLimiter.allowRequest()) {System.out.println("请求 " + (i + 1) + ": 允许");} else {System.out.println("请求 " + (i + 1) + ": 拒绝");}try {Thread.sleep(500); // 模拟请求之间的一些延迟} catch (InterruptedException e) {e.printStackTrace();}}}
}
​

优缺点分析

• 优点

  • 稳定性高：令牌桶可以控制请求处理速度，使系统负载稳定

  • 灵活性好：令牌桶算法可以通过调整令牌生成速率来动态控制请求的处理速率，从而适应不同的流量情况和系统负载。

  • 允许突发流量：在令牌桶中存在一定数量的令牌，可以应对一定程度的突发流量，避免突发流量导致请求拒绝或排队等待。

• 缺点

  • 实现复杂：相对其他限流算法，令牌桶的实现较复杂。对短时间内大量请求到来，可能导致令牌桶中的令牌消耗完，从而限流。这种情况可以考虑漏桶算法。

  • 时间精度要求高：需要在固定时间间隔内生成令牌，因此要求时间精度高，如果系统时间不准，可能导致限流效果不佳。

• Guava的RateLimiter限流组件就是基于令牌桶实现。

这篇关于一文秒解四大经典限流算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---