理解虾皮二面面试中的常见限流算法：如固定窗口、滑动窗口、漏桶和令牌桶
今天分享在虾皮面试过程中，一个关于限流算法的常见面试真题。
1. 限流概述
限流是对请求或并发数量的控制，目的是在特定时间窗口内限制请求量，以确保系统的稳定性。如果我们的服务资源有限，处理能力不足，就需要对上游请求进行适当限制，以免服务因资源耗尽而中断。
在限流中，有两个重要概念需要理解：
- 阈值：允许在单位时间内的最大请求量，例如，若 QPS（每秒请求数）限制为10，表示每秒最多接受10次请求。
- 拒绝策略：针对超过阈值的请求所采取的拒绝策略，常见的包括直接拒绝或排队等待。
2. 固定窗口算法
固定窗口算法，亦称为计数器算法，是一种简单且易于实现的限流算法。其主要通过一个支持原子操作的计数器来累积1秒内的请求次数。当计数达到设定的限流阈值时，会触发拒绝策略。每经过1秒，计数器会重置为0，重新开始计数。
2.1. 代码实现
以下是一个简单的代码实现，QPS 限制为2。在该实现中，未单独开线程每隔1秒重置计数器，而是通过每次调用时的时间间隔计算是否需要重置计数器。
public class RateLimiterSimpleWindow {
// 阈值
private static Integer QPS = 2;
// 时间窗口（毫秒）
private static long TIME_WINDOWS = 1000;
// 计数器
private static AtomicInteger REQ_COUNT = new AtomicInteger();
private static long START_TIME = System.currentTimeMillis();
public synchronized static boolean tryAcquire() {
if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
REQ_COUNT.set(0);
START_TIME = System.currentTimeMillis();
}
return REQ_COUNT.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 + " 做点什么");
}
}
}
}
运行结果如下：
20:53:43.038922 做点什么
20:53:43.291435 做点什么
20:53:43.543087 被限流
20:53:43.796666 做点什么
20:53:44.050855 做点什么
20:53:44.303547 被限流
20:53:44.555008 被限流
20:53:44.809083 做点什么
20:53:45.063828 做点什么
20:53:45.314433 被限流
从结果可以看出，每秒大约执行3次请求，但由于设置QPS限制为2，因此平均每秒会被限流一次。然而，这种简单的限流方式在遇到临界时间窗口时存在问题，例如，在1秒内的后500毫秒和第2秒的前500毫秒，尽管总时间为1秒，却可以接收4次请求。
固定窗口算法的缺陷测试
可以通过对测试代码进行简单的修改来验证这种缺陷：
// 先休眠400ms，可以更快地到达时间窗口。
Thread.sleep(400);
for (int i = 0; i < 10; i++) {
Thread.sleep(250);
if (!tryAcquire()) {
System.out.println("被限流");
} else {
System.out.println("做点什么");
}
}
输出结果显示连续4次请求间隔250毫秒却未被限制：
20:51:17.395087 做点什么
20:51:17.653114 做点什么
20:51:17.903543 做点什么
20:51:18.154104 被限流
20:51:18.405497 做点什么
20:51:18.655885 做点什么
20:51:18.906177 做点什么
20:51:19.158113 被限流
20:51:19.410512 做点什么
20:51:19.661629 做点什么
3. 滑动窗口算法
滑动窗口算法是对固定窗口算法的改进。固定窗口算法在处理时间窗口的临界突变时存在不足，因此，滑动窗口算法通过在临界窗口之间调整时间窗口来解决此问题。
以下是滑动窗口的示意图。
在示例中，每500毫秒滑动一次窗口，可以发现窗口滑动的间隔越短，时间窗口的临界突变问题发生的概率越小，但只要存在时间窗口，仍然可能出现临界突变问题。
3.1. 代码实现
以下是基于滑动窗口思路实现的简单滑动窗口限流工具类。
package com.wdbyte.rate.limiter;
import java.time.LocalTime;
import java.util.concurrent.atomic.AtomicInteger;
public class RateLimiterSlidingWindow {
private int qps = 2; // 阈值
private long windowSize = 1000; // 时间窗口总大小（毫秒）
private Integer windowCount = 10; // 子窗口数量
private WindowInfo[] windowArray = new WindowInfo[windowCount];
public RateLimiterSlidingWindow(int qps) {
this.qps = qps;
long currentTimeMillis = System.currentTimeMillis();
for (int i = 0; i < windowArray.length; i++) {
windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
}
}
public synchronized boolean tryAcquire() {
long currentTimeMillis = System.currentTimeMillis();
int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
int sum = 0;
for (int i = 0; i < windowArray.length; i++) {
WindowInfo windowInfo = windowArray[i];
if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
windowInfo.getNumber().set(0);
windowInfo.setTime(currentTimeMillis);
}
if (currentIndex == i && windowInfo.getNumber().get() < qps) {
windowInfo.getNumber().incrementAndGet();
}
sum += windowInfo.getNumber().get();
}
return sum <= qps;
}
private class WindowInfo {
private Long time; // 窗口开始时间
private AtomicInteger number; // 计数器
public WindowInfo(long time, AtomicInteger number) {
this.time = time;
this.number = number;
}
// get...set...
}
}
以下是测试用例，设置QPS为2，测试次数为20次，每次间隔300毫秒，预计成功次数约为12次。
public static void main(String[] args) throws InterruptedException {
int qps = 2, count = 20, sleep = 300, success = count * sleep / 1000 * qps;
System.out.println(String.format("当前QPS限制为:%d, 当前测试次数:%d, 间隔:%dms, 预计成功次数:%d", qps, count, sleep, success));
success = 0;
RateLimiterSlidingWindow myRateLimiter = new RateLimiterSlidingWindow(qps);
for (int i = 0; i < count; i++) {
Thread.sleep(sleep);
if (myRateLimiter.tryAcquire()) {
success++;
if (success % qps == 0) {
System.out.println(LocalTime.now() + ": success, ");
} else {
System.out.print(LocalTime.now() + ": success, ");
}
} else {
System.out.println(LocalTime.now() + ": fail");
}
}
System.out.println();
System.out.println("实际测试成功次数:" + success);
}
测试结果如下：
当前QPS限制为:2, 当前测试次数:20, 间隔:300ms, 预计成功次数:12
16:04:27.077782: success, 16:04:27.380715: success,
16:04:27.684244: fail
16:04:27.989579: success, 16:04:28.293347: success,
16:04:28.597658: fail
16:04:28.901688: fail
16:04:29.205262: success, 16:04:29.507117: success,
16:04:29.812188: fail
16:04:30.115316: fail
16:04:30.420596: success, 16:04:30.725897: success,
16:04:31.028599: fail
16:04:31.331047: fail
16:04:31.634127: success, 16:04:31.939411: success,
16:04:32.242380: fail
16:04:32.547626: fail
16:04:32.847965: success,
实际测试成功次数:11
4. 滑动日志算法
滑动日志算法是实现限流的另一种方法，逻辑较为简单。核心思想是记录所有请求的时间点，新的请求到来时判断最近指定时间范围内的请求数量是否超出限流阈值。因此，这种方式克服了时间窗口突变问题，限流较为准确，但由于需要记录每次请求的时间点，可能占用相对较多的内存。
4.1. 代码实现
以下是一个简单实现的滑动日志算法，设定QPS为2。
package com.wdbyte.rate.limiter;
import java.time.LocalTime;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;
public class RateLimiterSildingLog {
private Integer qps = 2; // 阈值
private TreeMap<Long, Long> treeMap = new TreeMap<>(); // 记录请求时间戳及数量
private long claerTime = 60 * 1000; // 清理请求记录间隔，60秒
public RateLimiterSildingLog(Integer qps) {
this.qps = qps;
}
public synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
// 清理过期数据，最长60秒清理一次
if (!treeMap.isEmpty() && (treeMap.firstKey() - now) > claerTime) {
Set<Long> keySet = new HashSet<>(treeMap.subMap(0L, now - 1000).keySet());
for (Long key : keySet) {
treeMap.remove(key);
}
}
// 计算当前请求次数
int sum = 0;
for (Long value : treeMap.subMap(now - 1000, now).values()) {
sum += value;
}
// 超过QPS限制，直接返回false
if (sum + 1 > qps) {
return false;
}
// 记录本次请求
if (treeMap.containsKey(now)) {
treeMap.compute(now, (k, v) -> v + 1);
} else {
treeMap.put(now, 1L);
}
return sum <= qps;
}
public static void main(String[] args) throws InterruptedException {
RateLimiterSildingLog rateLimiterSildingLog = new RateLimiterSildingLog(3);
for (int i = 0; i < 10; i++) {
Thread.sleep(250);
LocalTime now = LocalTime.now();
if (rateLimiterSildingLog.tryAcquire()) {
System.out.println(now + " 做点什么");
} else {
System.out.println(now + " 被限流");
}
}
}
}
设定QPS为3，运行可以得到如下日志：
20:51:17.395087 做点什么
20:51:17.653114 做点什么
20:51:17.903543 做点什么
20:51:18.154104 被限流
20:51:18.405497 做点什么
20:51:18.655885 做点什么
20:51:18.906177 做点什么
20:51:19.158113 被限流
20:51:19.410512 做点什么
20:51:19.661629 做点什么
5. 漏桶算法
漏桶算法以漏桶为比喻，使用生产者消费者模式进行说明。每个请求就像一滴水，加入到一个队列（漏桶）中，而桶底有个孔，不断漏出水滴，消费速率等于限流阈值。例如，QPS为2，则每1s / 2= 500ms消费一次。漏桶有大小限制，当请求堆积超过指定容量时，会触发拒绝策略。
以下是漏桶算法的示意图：
漏桶模式的优点在于消费处理总是以恒定的速度进行，能够有效保护系统不被突如其来的流量冲垮。然而，它的缺点是当两个请求同时到达时，可能无法同时处理，因为每1s / 2= 500ms只能处理一个请求。
6. 令牌桶算法
令牌桶算法是实现限流的另一种常见思路。Google 的 Java 开发工具包 Guava 中的限流工具类 RateLimiter 就是令牌桶的一种实现。其实现思路类似于生产者与消费者的关系。系统服务作为生产者，按照指定频率向桶中添加令牌；请求执行作为消费者，每个请求都需要从桶中获取一个令牌。
以下是令牌桶限流算法的示意图：
令牌桶的设计要点包括：
- 每秒生成的令牌数 = 1s / 确定的阈值（QPS）。
- 桶的容量等于限流的阈值，当达到阈值时不再添加。
- 能适应流量突发，多个请求可同时获取令牌继续处理。
- 启动时令牌桶为空，而若此时有大批请求，则会触发拒绝策略，但RateLimiter已经对此进行了优化。
6.1. 代码实现
使用Guava的RateLimiter进行测试如下：
引入依赖：
<exclusion>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</exclusion>
使用RateLimiter进行限流体验：
// qps 2
RateLimiter rateLimiter = RateLimiter.create(2);
for (int i = 0; i < 10; i++) {
String time = LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
System.out.println(time + ":" + rateLimiter.tryAcquire());
Thread.sleep(250);
}
代码设定的QPS为2，即每隔500毫秒生成一个令牌。因程序每隔250毫秒请求一次令牌，因此每两次请求中只有一次会成功：
17:19:06.797557:true
17:19:07.061419:false
17:19:07.316283:true
17:19:07.566746:false
17:19:07.817035:true
17:19:08.072483:false
17:19:08.326347:true
17:19:08.577661:false
17:19:08.830252:true
17:19:09.085327:false
6.2. 令牌添加方式思考
尽管演示了Guava工具包中的RateLimiter实现，但需要思考的是，令牌的添加方式。若按指定间隔添加令牌，需启动一个线程定时添加，若有多个接口，那么线程数会随之增加，显然不是一个好的解决方案。Google的RateLimiter在每次令牌获取时才计算令牌是否足够，优化了性能。
以下是Guava中RateLimiter类子类SmoothRateLimiter的resync()方法的代码分析：
void resync(long nowMicros) { // 当前微秒时间
if (nowMicros > this.nextFreeTicketMicros) {
double newPermits = (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
this.nextFreeTicketMicros = nowMicros;
}
}
7. Redis 分布式限流
Redis是一个开源的内存数据库，可以用作数据库、缓存、消息中间件等。由于Redis是单线程的，并在内存中操作，因此其速度极快，因此使用Redis实现限流工具非常方便。
以下示例基于Spring Boot项目，并需要以下依赖：
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>
配置Redis信息：
spring:
redis:
database: 0
password:
port: 6379
host: 127.0.0.1
lettuce:
shutdown-timeout: 100ms
pool:
min-idle: 5
max-idle: 10
max-active: 8
max-wait: 1ms
7.1. 固定窗口限流
Redis中的固定窗口限流使用incr命令来实现，incr命令通常用来自增计数。我们可以使用时间戳作为key来统计每秒的请求量，从而实现限流。
注意以下两点：
- 对于不存在的 key，第一次新增时value始终为1。
- INCR和EXPIRE命令操作应该在一个原子操作中提交，以确保每个key都正确设置了过期时间。
由于Redis中实现事务的复杂性，以下直接使用lua脚本来实现原子操作。以下是lua脚本内容：
local count = redis.call("incr", KEYS[1])
if count == 1 then
redis.call('expire', KEYS[1], ARGV[2])
end
if count > tonumber(ARGV[1]) then
return 0
end
return 1
以下是使用Spring Boot中RedisTemplate实现的lua脚本调用测试代码：
@SpringBootTest
class RedisLuaLimiterByIncr {
private static String KEY_PREFIX = "limiter_";
private static String QPS = "4";
private static String EXPIRE_TIME = "1";
@Autowired
private StringRedisTemplate stringRedisTemplate;
@Test
public void redisLuaLimiterTests() throws InterruptedException, IOException {
for (int i = 0; i < 15; i++) {
Thread.sleep(200);
System.out.println(LocalTime.now() + " " + acquire("user1"));
}
}
public boolean acquire(String key) {
key = KEY_PREFIX + key + System.currentTimeMillis() / 1000;
DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
redisScript.setResultType(Long.class);
redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter.lua")));
return stringRedisTemplate.execute(redisScript, Arrays.asList(key), QPS, EXPIRE_TIME) == 1;
}
}
虽然限制了QPS为4，但由于这种限流实现是将毫秒时间戳作为key，因此会出现临界窗口突变的问题。以下是运行结果，可以看到由于时间窗口的变化，导致QPS超过了限制值4。
17:38:23.122044 true
17:38:23.695124 true
17:38:23.903220 true
# 此处有时间窗口变化，所以下面继续 true
17:38:24.106206 true
17:38:24.313458 true
17:38:24.519431 true
17:38:24.724446 true
17:38:24.932387 false
17:38:25.137912 true
17:38:25.355595 true
17:38:25.558219 true
17:38:25.765801 true
17:38:25.969426 false
17:38:26.176220 true
17:38:26.381918 true
7.3. 滑动窗口限流
基于incr命令实现的Redis限流方式，已发现固定窗口限流带来的问题。滑动窗口限流的优势在于能大幅降低由于窗口临界突变带来的问题。那么如何使用Redis实现滑动窗口限流？
这里使用ZSET有序集合来实现滑动窗口限流，ZSET集合具有以下特点：
- ZSET集合中的key值可以自动排序。
- ZSET集合中的value不能重复。
- ZSET集合可以方便地使用ZCARD命令获取元素个数。
- ZSET集合可以使用ZREMRANGEBYLEX命令移除指定范围内的key值。
以下是基于ZSET的滑动窗口限流lua脚本：
-- KEYS[1]: 限流 key
-- ARGV[1]: 时间戳 - 时间窗口
-- ARGV[2]: 当前时间戳（作为score）
-- ARGV[3]: 阈值
-- ARGV[4]: score对应的唯一value
-- 1. 移除时间窗口之前的数据
redis.call('zremrangeByScore', KEYS[1], 0, ARGV[1])
-- 2. 统计当前元素数量
local res = redis.call('zcard', KEYS[1])
-- 3. 是否超过阈值
if (res == nil) or (res < tonumber(ARGV[3])) then
redis.call('zadd', KEYS[1], ARGV[2], ARGV[4])
return 1
else
return 0
end
以下是使用Spring Boot中RedisTemplate实现的lua脚本调用测试代码：
@SpringBootTest
class RedisLuaLimiterByZset {
private String KEY_PREFIX = "limiter_";
private String QPS = "4";
@Autowired
private StringRedisTemplate stringRedisTemplate;
@Test
public void redisLuaLimiterTests() throws InterruptedException, IOException {
for (int i = 0; i < 15; i++) {
Thread.sleep(200);
System.out.println(LocalTime.now() + " " + acquire("user1"));
}
}
public boolean acquire(String key) {
long now = System.currentTimeMillis();
key = KEY_PREFIX + key;
String oldest = String.valueOf(now - 1000);
String score = String.valueOf(now);
String scoreValue = score;
DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
redisScript.setResultType(Long.class);
redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter2.lua")));
return stringRedisTemplate.execute(redisScript, Arrays.asList(key), oldest, score, QPS, scoreValue) == 1;
}
}
代码中限制QPS为4，运行结果信息如下：
17:36:37.150370 true
17:36:37.716341 true
17:36:37.922577 true
17:36:38.127497 true
17:36:38.335879 true
17:36:38.539225 false
17:36:38.745903 true
17:36:38.952491 true
17:36:39.159497 true
17:36:39.365239 true
17:36:39.570572 false
17:36:39.776635 true
17:36:39.982022 true
17:36:40.185614 true
17:36:40.389469 true
以上介绍了Redis实现限流的两种方式，当然Redis也可以实现漏桶和令牌桶两种限流算法，感兴趣的读者可以自行研究。
8. 总结
本文介绍了几种实现限流的方法，主要是窗口算法和桶算法，两者各有优劣。
- 窗口算法逻辑清晰实现简单，可以直观得出当前的QPS情况，但存在时间窗口的临界突变问题，且不像桶算法有缓冲队列。
- 桶算法稍显复杂，QPS统计不易，但也具备一些优势：
- 漏桶模式的消费速率是恒定的，能有效保护系统，对流量进行整形，但无法快速响应突发流量。
- 令牌桶模式可以快速响应突发流量，但启动时会有缓慢加速的过程，常用的开源工具已对此进行优化。
单机限流与分布式限流
上述代码形式的窗口算法和桶算法适用于单机限流，若需分布式限流可以结合注册中心或负载均衡计算每个服务的限流阈值，但会降低精度。如果对精度要求不高，可以考虑使用此方法。
Redis具有单机特性，适合分布式限流。使用Redis可实现多种限流算法，如果觉得麻烦，还可以使用如redisson等开源工具，已封装了基于Redis的限流。
其他限流工具
文中提及的Guava限流工具是单机的，开源社区中还有许多分布式限流工具，例如阿里开源的Sentinel，提供流量控制、熔断降级、系统负载保护等多维度服务保护。
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
最近发布