外观
27 - 限流算法实战:固定窗口、滑动窗口、漏桶与令牌桶
前置阅读:01 - 时间复杂度如何决定系统上限。
本文负责算法语义与单机验证;多实例配额、Redis/Lua、降级和客户端重试治理见分布式 14 - 限流算法与容量保护。并发许可见Semaphore 并发许可与资源保护。
摘要
接口收到的请求超过处理能力时,可以先由限流器判断是否放行,避免所有请求都进入下游。最基本的模型是:请求到达,限流器根据时间和当前状态检查额度;有额度就更新状态并放行,没有额度就拒绝,或按设计进入等待队列。
“每秒 100 次”仍不够明确。配额是允许通过的请求数量;突发是短时间内集中到达的一批请求。是否允许突发、是否要求下游匀速处理,以及按用户还是按实例统计,决定了该用哪种算法。本文先解释四类限流器的状态如何变化,再用单机代码比较它们,并说明限流与并发隔离的区别。
1. 固定窗口
固定窗口把时间划成固定长度的区间,例如每秒一个窗口,每个窗口最多放行 100 次。它只需保存窗口起点和已放行次数:请求到达时,先判断是否进入新窗口;若进入,就清零计数,再检查是否还有配额。
问题出在相邻窗口分别计数。前一个窗口的额度即使用在最后一刻,也不影响后一个窗口重新获得完整额度,因此边界两侧可能在极短时间内通过两倍配额:
text
第 1 秒末 100 次 + 第 2 秒初 100 次两个固定窗口都没有超额,下游却可能短时间内收到 200 次请求。因此,“每个固定的一秒最多 100 次”不等于“任意连续一秒最多 100 次”。后面的教学实现由首次请求确定窗口起点,跨过边界后的首个请求开启新窗口,并非按自然秒对齐。
2. 滑动窗口
滑动窗口在每次请求到达时,重新统计最近一段时间内的放行数量。窗口随当前时间向前移动,不会在某个固定边界一次性恢复全部额度。
精确实现保存每次已放行请求的时间戳。设窗口长度为 window,当前时间为 now,只保留 (now-window, now] 内的记录:左端点不包含,右端点包含。先删除过期记录,再检查剩余数量;达到配额就拒绝,否则记录本次请求。这样,旧请求逐个离开窗口,额度也逐个恢复。
另一种实现把时间切成多个小桶,每个桶只保存计数,再汇总最近窗口覆盖的桶。这能减少逐条保存时间戳的内存开销,但窗口边缘可能落在桶内部,统计会有近似误差。分桶越细,通常越接近精确窗口,维护的桶也越多。精确滑动窗口比固定窗口更严格地约束最近区间,但仍允许剩余额度在同一时刻集中使用,并不保证匀速输出。
3. 漏桶
可以把漏桶理解为容量有限的等待队列:请求先进入队列,再以固定速率取出并交给下游。桶容量决定最多能积压多少请求,漏出速率决定下游接收请求的节奏;桶满后,新请求被拒绝或丢弃。
这种排队式漏桶能接住一定规模的输入突发,却不会让这批请求立即全部进入下游,代价是等待时间增加。它适合平滑输出,不适合要求突发请求立即通过的场景。
第 5 节的 LeakyBucket 只用“积水量”模拟是否还能接收请求,没有保存或定速取出实际请求。因此,它的 allow 返回 true 只表示准入成功,不能据此认为下游已经获得匀速流量。
4. 令牌桶
令牌是放行许可。系统按固定速率补充令牌,最多保存到桶容量;每次请求消耗一个令牌,没有足够令牌就拒绝。容量控制空闲后最多能集中放行多少请求,补充速率控制额度恢复的速度,二者是不同参数。
例如容量为 2、每秒补充 1 个令牌,满桶时可以立即放行两个请求,之后需要等待令牌恢复。空闲时间再长也不会积累超过容量的令牌。与排队式漏桶不同,有令牌的请求可以立即通过,不必等待固定的出队节奏。
下面是没有运行入口的 Java 教学片段。tokens 保存当前令牌数,lastRefill 保存上次补充时间;tryAcquire 先补充再扣减。调用方应提供至少为 1 的容量和正的有限补充速率,片段本身没有参数校验。
java
class TokenBucket {
private final long capacity;
private final double tokensPerNanos;
private double tokens;
private long lastRefill;
TokenBucket(long capacity, double tokensPerSecond) {
this.capacity = capacity;
this.tokens = capacity;
this.tokensPerNanos = tokensPerSecond / 1_000_000_000d;
this.lastRefill = System.nanoTime();
}
synchronized boolean tryAcquire() {
refill();
if (tokens < 1) return false;
tokens -= 1;
return true;
}
private void refill() {
long now = System.nanoTime();
tokens = Math.min(capacity, tokens + (now - lastRefill) * tokensPerNanos);
lastRefill = now;
}
}这里没有后台线程持续生成令牌,而是在请求到达时用“经过时间 × 补充速率”计算新增额度。System.nanoTime() 用于计算经过时间,不表示日历时间;synchronized 将同一个对象上的补充、检查和扣减串行执行,避免多个线程同时消费同一份额度。生产还要考虑浮点精度、并发竞争、配置热更新、公平性(不同请求获得额度的机会)和时钟行为。
5. 完整可运行示例:四种单机限流器
下面是完整入口类 RateLimiterDemo,仅使用 JDK 标准库;源文件应命名为 RateLimiterDemo.java。
接口 allow(nowMillis) 用传入的毫秒时间判断本次请求,true 表示放行,false 表示拒绝。窗口参数使用正整数;桶容量至少为 1,速率为正的有限数值。示例时间从 0 开始且不倒退,避免与表示“尚未初始化”的特殊值 -1 冲突。令牌桶和漏桶显式拒绝时间倒退,两个窗口实现没有相同的检查,不能假设它们也会抛出异常。
java
import java.util.ArrayDeque;
import java.util.Deque;
/**
* 可运行示例:限流算法实战:固定窗口、滑动窗口、漏桶与令牌桶。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class RateLimiterDemo {
interface Limiter {
boolean allow(long nowMillis);
}
static class FixedWindow implements Limiter {
final long window;
final int limit;
long start = -1;
int count;
FixedWindow(long window, int limit) {
if (window <= 0 || limit <= 0) throw new IllegalArgumentException();
this.window = window;
this.limit = limit;
}
public synchronized boolean allow(long now) {
// 首次请求或越过窗口边界时,开启一个新窗口并清零计数。
if (start < 0 || now - start >= window) {
start = now;
count = 0;
}
// 被拒绝的请求不计入已通过数量,避免 count 无限制增长。
if (count >= limit) return false;
count++;
return true;
}
}
static class SlidingWindow implements Limiter {
final long window;
final int limit;
final Deque<Long> requests = new ArrayDeque<>();
SlidingWindow(long window, int limit) {
if (window <= 0 || limit <= 0) throw new IllegalArgumentException();
this.window = window;
this.limit = limit;
}
public synchronized boolean allow(long now) {
// 删除窗口左边界之外的历史请求。
while (!requests.isEmpty() && requests.peekFirst() <= now - window)
requests.pollFirst();
// 队列只保存当前窗口内已通过的请求时间。
if (requests.size() >= limit) return false;
requests.offerLast(now);
return true;
}
}
static class TokenBucket implements Limiter {
final double capacity, perMillis;
double tokens;
long last = -1;
TokenBucket(double capacity, double perSecond) {
if (capacity < 1 || perSecond <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
tokens = capacity;
perMillis = perSecond / 1000d;
}
public synchronized boolean allow(long now) {
if (last < 0) last = now;
if (now < last) throw new IllegalArgumentException(
"time moved backwards"
);
// 按经过时间补充令牌,并限制令牌数不超过桶容量。
tokens = Math.min(capacity, tokens + (now - last) * perMillis);
last = now;
if (tokens < 1) return false;
// 每个请求消费一个令牌;也可扩展为按请求成本消费多个令牌。
tokens--;
return true;
}
}
static class LeakyBucket implements Limiter {
final double capacity, leakPerMillis;
double water;
long last = -1;
LeakyBucket(double capacity, double perSecond) {
if (capacity < 1 || perSecond <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
leakPerMillis = perSecond / 1000d;
}
public synchronized boolean allow(long now) {
if (last < 0) last = now;
if (now < last) throw new IllegalArgumentException(
"time moved backwards"
);
// 先按固定速率漏水,再判断新请求是否还能进入桶。
water = Math.max(0, water - (now - last) * leakPerMillis);
last = now;
if (water + 1 > capacity) return false;
// 通过的请求增加一单位积水,桶满后新请求被拒绝。
water++;
return true;
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
for (Limiter l : new Limiter[] {
new FixedWindow(1000, 2),
new SlidingWindow(1000, 2),
new TokenBucket(2, 1),
new LeakyBucket(2, 1),
}) {
System.out.println(
l.getClass().getSimpleName() +
": " +
l.allow(0) +
"," +
l.allow(0) +
"," +
l.allow(0) +
"," +
l.allow(1000)
);
}
}
}传入时间让测试不必实际等待一秒:调用方可以直接推进到边界时间,得到可重复的判断,这就是确定性测试。生产实现应使用单调时间源,即用于测量时间间隔、不会因校准日历时间而回拨的时钟,并处理并发、公平性与分布式一致性。代码中的同步只保护同一个限流器对象,不会协调其他对象或进程的额度。
5.1 同一组请求为何结果不同
先看 main 中的参数:两个窗口都是 1000ms 内最多放行 2 个;两个桶都是容量 2、每秒恢复 1 单位额度。请求发生在 0ms、0ms、0ms、1000ms。下面是按代码静态推演的预期结果,并非运行记录:
| 算法 | 前三个请求 | 1000ms 请求 | 原因 |
|---|---|---|---|
| 固定窗口 | 通过、通过、拒绝 | 通过 | 新窗口直接重置 |
| 精确滑动窗口 | 通过、通过、拒绝 | 通过 | 0ms 记录已移出 (0,1000] |
| 令牌桶(容量2、每秒1) | 通过、通过、拒绝 | 通过 | 1 秒补充 1 个令牌 |
| 漏桶(容量2、每秒1) | 通过、通过、拒绝 | 通过 | 1 秒漏出 1 单位积水 |
这组请求的结果恰好相同,不能用它证明四种算法等价。要看出差异,可以保持上述参数不变,为每种算法重新创建一个限流器,依次判断 0ms、500ms、1000ms、1000ms 的四个请求。同一时刻的请求也按表中顺序逐个处理。以下仅按代码静态推演,并非实测,也不修改 main:
| 算法 | 0ms | 500ms | 第一个 1000ms 请求 | 第二个 1000ms 请求 |
|---|---|---|---|---|
| 固定窗口 | 通过 | 通过 | 通过 | 通过 |
| 精确滑动窗口 | 通过 | 通过 | 通过 | 拒绝 |
| 令牌桶(容量2、每秒1) | 通过 | 通过 | 通过 | 拒绝 |
| 漏桶(容量2、每秒1) | 通过 | 通过 | 通过 | 拒绝 |
前两个请求均通过,但到 1000ms 时,四种实现恢复额度的方式不同:
- 固定窗口:
0ms开启的窗口已结束,计数清零,新窗口有完整的 2 个配额,因此两个1000ms请求都通过。 - 精确滑动窗口:当前区间是
(0,1000],只删除0ms的记录,500ms的记录仍占用一个配额。第一个1000ms请求通过后,窗口内已有 2 条记录,第二个被拒绝。 - 令牌桶:
0ms请求后剩 1 个令牌;到500ms补充 0.5 个并消费 1 个,剩 0.5 个;到1000ms再补充 0.5 个。第一个请求用完这 1 个令牌,同一时刻没有新增令牌,第二个被拒绝。 - 漏桶:
0ms请求后积水为 1;到500ms漏出 0.5 单位,再接收请求后积水为 1.5;到1000ms再漏出 0.5 单位。第一个请求使积水达到容量 2,同一时刻没有继续漏水,第二个被拒绝。
因此,固定窗口可以在 500ms 至 1000ms 这段短时间内放行 3 个请求,而本组输入下其他三种实现只放行其中 2 个。差异来自各自的额度恢复规则,不能只用“每秒 2 个”概括这些参数:窗口的配额是 2,而桶的补充或漏出速率是每秒 1 单位。
两个桶在这里都通过额度增减判断准入,也都能在初始时刻接收两个请求。代码没有漏桶的出队器,因此这组输出只能比较准入结果,不能比较真实的输出节奏。
5.2 核心不变量
不变量是每次状态更新后仍应成立的约束,可用于检查实现。以下按正常有限参数、非负且不倒退的输入时间理解;浮点误差和极端数值仍需单独测试。
- 固定窗口:当前窗口内
0 <= count <= limit。 - 滑动窗口:队列中的时间戳都位于
(now-window, now],且只记录已放行请求。 - 令牌桶:
0 <= tokens <= capacity,时间推进只增加令牌,放行只减少令牌。 - 漏桶:
0 <= water <= capacity,时间推进降低积水,放行增加积水。
5.3 成本与选型
- 固定窗口每次
O(1)、空间O(1),适合容忍边界突发的粗粒度保护。 - 精确滑动窗口摊还
O(1),空间O(limit):每个放行记录只入队、出队一次,所以按一系列请求平均,维护成本为常数;但一次调用可能清理多条记录,最坏为O(limit)。高配额时可考虑分桶计数,以近似误差换取较低内存。 - 令牌桶和漏桶每次
O(1)、空间O(1),浮点实现需评估长期精度误差。
这些复杂度描述的是状态维护成本,不包含等待同步锁的时间。选型时先确定时间窗口、允许突发量和输出节奏,再评估状态成本;资源占用与跨实例配额分别见下面两节。
6. 限流不等于并发隔离
QPS(每秒请求数)描述到达或处理速率,并发数描述同一时刻尚未完成的请求数量。即使 QPS 很低,只要每个请求占用线程或连接的时间足够长,新请求到达时旧请求仍未结束,就可能逐渐占满资源。
限流控制进入速率;并发隔离限制同时占用资源的数量。Semaphore(信号量)用有限许可控制同时进入受保护区域的请求数,线程池和连接池则约束相应资源的使用。需要保护慢下游时,通常要同时设置速率额度和并发上限,不能用其中一个替代另一个。
7. 分布式限流
多个服务实例若各自限 100 QPS,且没有共享额度,总可用额度会随实例数增长;扩容后单机仍不超额,全局流量却可能超过下游容量。因此必须同时明确统计维度(用户、租户或接口等)和状态共享范围(单实例或跨实例全局)。
全局限流可在网关统一执行,或使用 Redis 保存共享状态、由 Lua 脚本完成协调。关键是把读取额度、判断和更新作为不可分割的操作,避免两个实例读到同一份剩余额度后都放行。集中协调也会引入网络延迟、热点和可用性问题。
具体 Redis 命令、脚本复制、Cluster Key 路由(状态键在集群中的节点归属)和服务端时间行为依赖产品及版本,本文不把教学代码扩展为分布式实现。生产协议还需要定义:
- 限流服务不可用时,是 fail-open(继续放行)还是 fail-closed(拒绝请求);
- 配额变更是否重置令牌,如何避免多实例同时满桶;
- 被拒绝请求是否可重试,提示客户端等待多久再重试的
Retry-After如何计算; - 高基数维度,即不同用户或租户等标识数量很大的统计维度,如何设置状态过期,避免存储无限增长。
这些内容由分布式限流文章统一负责。
8. 验证与排障
验证时应先检查单机状态与边界,再观察实际流量和下游资源:
- 使用可注入的单调时间源做确定性边界测试;
- 验证令牌桶长时间空闲后的瞬时放行量不超过容量;排队式漏桶还需验证队列容量和实际出队节奏;
- 并发压测通过量,确认同步或原子更新没有超发;
- 覆盖连续拒绝、配置热更新和多租户隔离,确认拒绝不会错误扣减额度,配置变化不会意外恢复整份额度;
- 同时观察放行率、拒绝率、等待时间、在途数(已进入但尚未完成的请求数)和下游饱和度,即资源接近容量上限的程度;
- 被限流但下游仍过载时,检查慢请求占用时间和并发上限,而不只检查 QPS;
- 多实例总量超标时,核对限流作用域和配额分配,而不是调小单机参数猜测。
9. 容易踩的坑
- 使用墙上时钟(表示日历时间、可能因校时而回拨的时钟)计算间隔,导致窗口异常;单机耗时测量优先单调时钟。
- 只限制平均 QPS,不控制允许突发量。
- 限流拒绝没有
Retry-After或明确错误码,客户端无法判断何时重试。 - Redis 的额度检查与扣减分成多步执行,且没有原子性保证,导致并发请求重复使用额度。
- 所有接口共用一个桶,低价值流量挤占核心请求。
- 把教学版漏桶的准入判断当成真实的异步定速出队器。
10. 总结
限流算法选择取决于是否允许突发、是否要求平滑以及统计范围。
- 固定窗口简单但有边界突刺,滑动窗口更精确但成本更高。
- 漏桶平滑输出,令牌桶允许有限突发。
- 限流控制速率,并发隔离控制资源占用,两者不能互相替代。
分布式治理继续阅读限流算法与容量保护;需要稳定 Key 路由时继续阅读一致性哈希与缓存扩缩容。