02.10.2 限流器与时间轮
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.10 设计类与手写题
覆盖范围
- 固定窗口计数器与滑动窗口日志
- 令牌桶与漏桶代码实现及对比
- 时间轮原理、层级时间轮
- Kafka 时间轮与 Netty HashedWheelTimer
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 02.10.2-001 | 固定窗口计数器限流实现 | 基础 | ★★★★ |
| 02.10.2-002 | 滑动窗口日志限流实现 | 进阶 | ★★★★ |
| 02.10.2-003 | 令牌桶限流代码实现 | 基础 | ★★★★★ |
| 02.10.2-004 | 漏桶限流代码实现 | 进阶 | ★★★★ |
| 02.10.2-005 | 令牌桶与漏桶的区别 | 基础 | ★★★★★ |
| 02.10.2-006 | 时间轮原理与层级时间轮 | 高级 | ★★★★ |
| 02.10.2-007 | Kafka 时间轮应用 | 进阶 | ★★★ |
| 02.10.2-008 | Netty HashedWheelTimer 实现 | 进阶 | ★★★ |
02.10.2-001 固定窗口计数器限流实现
频率 ★★★★ | 难度 基础
一句话结论
把时间分成固定窗口(如每秒),窗口内计数超过阈值则拒绝;实现最简单,但有窗口边界突刺问题(窗口最后 1ms + 下窗口最前 1ms 可能瞬间通过 2 倍流量)。
概念解释
- 窗口起点:每个固定周期(如每秒 00:00:00)开始计数。
- 阈值:窗口内最大请求数。
- 边界突刺:窗口交界处可能出现 2 倍瞬时流量。
原理流程
- 记录当前窗口起点和计数。
- 请求到来时判断是否跨窗口,跨窗口则重置起点和计数。
- 计数 < 阈值则放行并计数++,否则拒绝。
代码 / 示例
class FixedWindowRateLimiter {
private final int limit;
private final long windowMs;
private long windowStart;
private int count;
FixedWindowRateLimiter(int limit, long windowMs) {
this.limit = limit; this.windowMs = windowMs;
}
synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
if (now - windowStart >= windowMs) { windowStart = now; count = 0; }
if (count < limit) { count++; return true; }
return false;
}
}
常见误区
- 误区:固定窗口够用;正解:边界突刺可能让下游在 1ms 内承受 2 倍流量。
- 误区:窗口起点固定为整点;正解:起点可随首次请求滚动,效果相同。
追问 / 延伸
- Q:怎么缓解边界突刺? A:滑动窗口或令牌桶。
- Q:集群限流怎么做? A:分布式限流用 Redis + Lua 脚本保证原子性。
02.10.2-002 滑动窗口日志限流实现
频率 ★★★★ | 难度 进阶
一句话结论
用队列记录每个请求的时间戳,窗口内只保留最近 N 毫秒内的请求;请求到来时从队首淘汰超出窗口的时间戳,队列长度 < 阈值则放行;精度高但每个请求都要入队出队。
概念解释
- 时间戳队列:按时间升序记录请求时刻。
- 窗口:固定时长,滑动随当前时间移动。
- 精度:理论上精确到单次请求,无边界突刺。
原理流程
- 请求到来,记录当前时间 now。
- 从队首弹出所有早于 now - windowMs 的时间戳。
- 队列长度 < limit 则入队放行,否则拒绝。
代码 / 示例
class SlidingWindowLog {
private final int limit;
private final long windowMs;
private final java.util.Deque<Long> logs = new java.util.ArrayDeque<>();
SlidingWindowLog(int limit, long windowMs) {
this.limit = limit; this.windowMs = windowMs;
}
synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
while (!logs.isEmpty() && logs.peekFirst() < now - windowMs) logs.pollFirst();
if (logs.size() < limit) { logs.addLast(now); return true; }
return false;
}
}
常见误区
- 误区:滑动窗口和固定窗口一样;正解:滑动窗口无边界突刺,但内存开销大(每个请求一个时间戳)。
- 误区:队首淘汰用 while;正解:必须 while 不能 if,否则一次可能弹出多个。
追问 / 延伸
- Q:内存开销? A:每个请求一个 long,高频下内存大;可降级为滑动窗口计数(近似)。
- Q:滑动窗口计数近似怎么做? A:把窗口分成多个小格子,每个格子计数,滑动时加权合并。
02.10.2-003 令牌桶限流代码实现
频率 ★★★★★ | 难度 基础
一句话结论
以固定速率往桶里放令牌,桶满则溢出;每个请求取一个令牌,取到则放行;允许突发流量(桶里有令牌就可一次性通过多个),是 Guava RateLimiter 和 Sentinel 默认采用的模型。
概念解释
- 桶容量 capacity:最大突发量。
- 填令牌速率 rate:每秒补充多少令牌。
- 惰性填充:不单独起线程放令牌,而是在请求时按时间差计算应补充的令牌数。
原理流程
- 记录上次补充令牌时间 lastRefill 和当前令牌数 tokens。
- 请求到来,计算
(now - lastRefill) / 1000 * rate个应补充令牌,加到 tokens(不超过 capacity)。 - tokens >= 1 则 tokens-- 放行,否则拒绝。
代码 / 示例
class TokenBucket {
private final double capacity;
private final double ratePerSec;
private double tokens;
private long lastRefill;
TokenBucket(double capacity, double ratePerSec) {
this.capacity = capacity; this.ratePerSec = ratePerSec;
this.tokens = capacity; this.lastRefill = System.currentTimeMillis();
}
synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
double refill = (now - lastRefill) / 1000.0 * ratePerSec;
tokens = Math.min(capacity, tokens + refill);
lastRefill = now;
if (tokens >= 1.0) { tokens -= 1.0; return true; }
return false;
}
}
常见误区
- 误区:需要单独线程放令牌;正解:惰性填充即可,请求时计算,省线程。
- 误区:桶满时继续加令牌;正解:超过 capacity 部分丢弃,保证突发不超过 capacity。
追问 / 延伸
- Q:Guava RateLimiter 是哪种? A:令牌桶,且支持预热(warmup)模式,冷启动时速率逐渐提升。
- Q:突发流量多大? A:最多 capacity 个,因为桶里最多攒 capacity 个令牌。
02.10.2-004 漏桶限流代码实现
频率 ★★★★ | 难度 进阶
一句话结论
请求进入桶底,桶以固定速率滴水(放行);桶满则拒绝;出口速率恒定,平滑流量,但不允许突发。
概念解释
- 入口:请求进入队列。
- 出口:固定速率消费队列。
- 桶满:新请求被拒绝。
原理流程
- 请求到来,检查队列是否满,满则拒绝。
- 队列未满则入队。
- 后台线程(或惰性计算)按固定速率从队列取出放行。
代码 / 示例
class LeakyBucket {
private final int capacity;
private final double leakPerSec;
private int water;
private long lastLeak;
LeakyBucket(int capacity, double leakPerSec) {
this.capacity = capacity; this.leakPerSec = leakPerSec;
}
synchronized boolean tryAcquire() {
long now = System.currentTimeMillis();
water = Math.max(0, (int)(water - (now - lastLeak) / 1000.0 * leakPerSec));
lastLeak = now;
if (water < capacity) { water++; return true; }
return false;
}
}
常见误区
- 误区:漏桶和令牌桶一样;正解:漏桶出口恒定,令牌桶允许桶内攒令牌突发。
- 误区:漏桶需要后台线程;正解:惰性计算漏水量即可。
追问 / 延伸
- Q:漏桶适合什么场景? A:需要把突发流量平滑成恒定速率的场景,如调外部支付接口。
- Q:令牌桶适合什么场景? A:允许一定突发但长期受控的场景,如 API 网关限流。
02.10.2-005 令牌桶与漏桶的区别
频率 ★★★★★ | 难度 基础
一句话结论
令牌桶入口可变、出口可突发(桶里有令牌就一次取多个);漏桶入口可变、出口恒定(按固定速率滴);令牌桶允许突发,漏桶强制平滑。
概念解释
- 令牌桶:补令牌是入口,取令牌也是入口;桶满时令牌溢出,请求可一次性取多个。
- 漏桶:请求是入口,滴水是出口;出口速率固定,不管入口多急。
- 两者数学上可互相模拟,但语义不同。
原理流程
- 令牌桶:桶容量 + 填充速率,突发 = capacity。
- 漏桶:桶容量 + 漏水速率,出口恒定 = leakPerSec。
- 选模型:允许突发选令牌桶,强制平滑选漏桶。
代码 / 图示
令牌桶:补令牌(rate) -> 桶(cap) -> 请求取令牌
允许突发 capacity 个
漏桶: 请求 -> 桶(cap) -> 滴水(rate) -> 放行
出口恒定,突发被队列缓冲
常见误区
- 误区:令牌桶出口也恒定;正解:桶里有令牌时可一次取多个,出口突发。
- 误区:漏桶不能突发;正解:漏桶入口可突发(队列缓冲),但出口恒定。
追问 / 延伸
- Q:Sentinel 默认哪种? A:令牌桶(滑动窗口计数近似)。
- Q:Nginx limit_req 是哪种? A:漏桶模型(固定速率放行)。
02.10.2-006 时间轮原理与层级时间轮
频率 ★★★★ | 难度 高级
一句话结论
时间轮是一个环形数组,每个槽位挂一个定时器任务链表;一个指针每秒转动,转到某槽就执行该槽所有任务;层级时间轮在指针转完一圈后驱动上一层指针转动一格,解决跨度大的定时器。
概念解释
- 槽位:环形数组每个元素,对应一段时间区间(如 100ms)。
- 指针:currentIndex,每秒/每 tick 走一格。
- 任务链表:挂在槽位上,执行后从链表摘除。
- 层级:上层一个槽代表下层一整圈,类似时钟时/分/秒。
原理流程
- 定时器任务按延迟换算到槽位 index。
- 任务挂到对应槽位链表。
- 指针 tick 一次,执行当前槽所有任务;若任务延迟跨圈,记录剩余圈数,圈数减到 0 才执行。
- 单层转完一圈,上层指针走一格。
代码 / 图示
单层时间轮:
槽 0 -> 槽 1 -> 槽 2 -> ... -> 槽 N-1
^指针
层级时间轮(类似时钟):
秒轮:0-59,转一圈
分轮:0-59,秒轮转一圈走一格
时轮:0-23,分轮转一圈走一格
常见误区
- 误区:时间轮需要排序;正解:槽位按时间分布,任务挂链表,无需排序,插入 O(1)。
- 误区:层级时间轮每层独立;正解:上层转一格是下层转完一圈触发的。
追问 / 延伸
- Q:时间轮复杂度? A:插入/删除 O(1),执行按槽批量。
- Q:为什么不用最小堆? A:最小堆插入/删除 O(log n),时间轮 O(1),且批量执行友好。
02.10.2-007 Kafka 时间轮应用
频率 ★★★ | 难度 进阶
一句话结论
Kafka 用时间轮管理延迟请求(如生产重试、副本拉取超时),单层时间轮 + 可降级为层级时间轮;相比 JDK Timer 或 ScheduledThreadPoolExecutor,时间轮在大量定时任务时 O(1) 插入更高效。
概念解释
- Kafka 时间轮:底层是环形数组,每个槽位是一个 DelayedTaskQueue。
- 指针推进:由 SystemTimer 线程驱动,每次 tick 推进一格。
- 延迟任务:超过一圈的任务记录剩余圈数,圈数减到 0 才执行。
原理流程
- 延迟请求(如重试)包装成 DelayedTask。
- 按延迟时间换算到时间轮槽位,挂链表。
- 时间轮线程 tick,执行到期任务,未到期圈数--。
代码 / 图示
Kafka 时间轮参数:
tickMs = 1ms
wheelSize = 20
上层按需创建(HierarchicalTimingWheel)
常见误区
- 误区:Kafka 时间轮是为了管理消息消费;正解:管理内部延迟请求(重试、超时、心跳)。
- 误区:时间轮精度等于 tickMs;正解:精度是 tickMs,任务可能延迟一个 tickMs。
追问 / 延伸
- Q:Kafka 为什么不用 DelayQueue? A:DelayQueue 是最小堆,插入 O(log n),时间轮 O(1),Kafka 定时任务量大。
- Q:时间轮 tickMs 设多少? A:Kafka 默认 1ms,具体以源码版本为准。
02.10.2-008 Netty HashedWheelTimer 实现
频率 ★★★ | 难度 进阶
一句话结论
Netty 的 HashedWheelTimer 是单层时间轮实现:环形数组 + 一个 worker 线程按固定 tick 推进;任务用定时任务链表挂在槽位上,支持延迟任务;使用单线程模型,任务执行不能阻塞 worker。
概念解释
- 环形数组:每个槽位是一个 Set
。 - worker 线程:单线程,负责 tick 和执行任务。
- 任务状态:pending、expired、cancelled。
原理流程
- 调用 newTimeout(task, delay, unit) 把任务按延迟挂到对应槽位。
- worker 线程 sleep tickMs 后推进一格。
- 执行当前槽所有任务(圈数减到 0 的)。
- 任务执行完从槽位移除。
代码 / 示例
// Netty 用法(伪代码)
HashedWheelTimer timer = new HashedWheelTimer(100, TimeUnit.MILLISECONDS, 512);
timer.newTimeout(t -> {
System.out.println("task executed");
}, 1, TimeUnit.SECONDS);
常见误区
- 误区:任务在调用线程执行;正解:任务在 worker 线程执行,不能阻塞,否则所有定时任务延迟。
- 误区:HashedWheelTimer 支持层级;正解:Netty 是单层,延迟超过一圈的任务记录 remainingRounds。
追问 / 延伸
- Q:HashedWheelTimer 怎么优雅关闭? A:调用 stop(),返回未执行任务列表。
- Q:槽位大小怎么选? A:默认 512,越大槽位冲突越少但内存越大。
待整理清单
- [ ] Redis + Lua 分布式限流实现
- [ ] Sentinel 滑动窗口计数源码
- [ ] Guava RateLimiter 预热模式