题目重点：Oracle 全套面经明确出现 rolling-window 限流；本文声明训练接口，解释过期边界、拒绝请求是否计数及原子化。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版按 key 限流，任意半开窗口 (now−W,now] 内最多 L 次成功请求；拒绝请求不占配额。
- 单 key 调用时间非递减，单进程串行；并发或跨节点是设计追问。L 非负、W>0。
解题路线
- 每个 key 用 deque 保存尚在窗口内的成功请求时间。到达 now 时弹出 t≤now−W，明确左端点不在窗口。
- 若队列长度达到 L 则拒绝且不追加；否则追加 now 后允许。这个先检查再追加的顺序确保不会短暂超限。
- 在并发环境里，清理、检查和追加必须被同一锁或原子脚本保护；跨节点可用按 key 的 Redis Lua/有序集，但要明确统一时钟和存储故障策略。
- 对大量只出现一次的 key，另设空队列清理与空闲 key 回收，否则 last_time/key 表会持续增长。
手动走一遍
L=2、W=10：t=0、t=1 允许；t=5 拒绝；t=10 时 t=0 正好过期，故允许。此时窗口 (0,10] 内记录 t=1、10。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Exact per-key rolling window; rejected requests do not consume a slot."""
from collections import defaultdict, deque
class RollingWindowLimiter:
def __init__(self, limit: int, window_seconds: float):
if limit < 0 or window_seconds <= 0:
raise ValueError("invalid limit or window")
self.limit = limit
self.window = window_seconds
self.events = defaultdict(deque)
self.last_time = {}
def allow(self, key: str, now: float) -> bool:
if key in self.last_time and now < self.last_time[key]:
raise ValueError("timestamps for one key must be nondecreasing")
self.last_time[key] = now
history = self.events[key]
while history and history[0] <= now - self.window:
history.popleft()
if len(history) >= self.limit:
return False
history.append(now)
return True
复杂度
每个成功时间最多入队和出队一次，均摊每请求 O(1)；单次清理可能弹 O(L) 项。活跃 key 总空间 O(Σ窗口内成功请求数+key 数)，未回收的空闲 key 会继续占内存。
易错点与追问
容易失分的边界
- 用固定窗口计数冒充 rolling window，边界突发可接近两倍额度。
- 没有定义 t=now−W 是否仍有效。
- 多个线程分别检查空位再追加，导致超限。
- 把 的丢弃请求仍计入额度规则直接套到这篇；本帖未公开该规则。
继续深挖
- 若拒绝请求也要占用额度，队列逻辑如何改？
- 跨节点如何保持原子性及处理时钟漂移？
- 若用户数百万，如何回收长时间未使用的 key？
