罗罗编程学习记录
本页内容 展开查看

09.2.1.1 固定窗口与滑动窗口

所属:全栈开发面试题库 / 09 高阶架构:高并发与分布式 / 09.2 流量治理 / 09.2.1 限流算法与实现

09.2.1.1-001 限流解决什么问题?保护谁?

一句话结论

限流通过限制单位时间内进入系统的请求数量,保护自身与下游依赖不被超出能力的流量压垮;保护对象包括应用线程池、DB、缓存、外部接口与整条链路的可用性。

概念解释

  • 限流入口:网关、应用接口、下游调用。
  • 保护目标:在能力范围内服务,超出部分快速失败或排队。
  • 与熔断区别:限流控制进入速率,熔断在下游故障时切断调用。

原理流程

到达请求 → 限流判定(计数/令牌/信号量)
  → 放行:进入处理
  → 超限:拒绝 / 排队 / 降级

常见误区

  • 误区:限流是为了拒绝用户。限流是容量保护,应配合降级与友好提示,目标是保核心链路。
  • 误区:限了流系统就不会故障。限流只控入口速率,下游已有积压仍需熔断与降级处理。

追问

  • 问:限流阈值由什么决定?答:下游与自身压测得出的安全能力,结合业务优先级与 SLO。
  • 问:限流可以放在哪几层?答:接入网关、应用接口、服务调用、DB/缓存访问,多层配合。

09.2.1.1-002 固定窗口计数器怎么实现?

一句话结论

把时间按固定长度(如 1 分钟)切成窗口,每个窗口一个计数器;请求到达计数 +1,超过阈值拒绝,窗口结束后计数清零;实现简单,计数与过期通过原子递增加过期时间完成。

概念解释

  • 窗口边界:按固定周期对齐(每分钟/每秒)。
  • 计数结构:key 含窗口编号。
  • 过期:窗口计数到期自动清除,避免无限堆积。

原理流程

window = floor(now / windowSize)
key = "rate:" + dimension + ":" + window
count = INCR key
if count == 1: EXPIRE key windowSize + 1s
if count > limit: reject else accept

常见误区

  • 误区:窗口结束手动清零计数。依赖 key 过期更稳妥,主动清理可能遗漏。
  • 误区:计数和过期可以分两步非原子执行。并发下先过期后递增会导致 key 永不过期,需用 Lua 或原子命令保证。

追问

  • 问:为什么 EXPIRE 要在 count==1 时设置?答:首次创建 key 时设定过期,后续递增不再重复刷新过期时间。
  • 问:固定窗口适合什么场景?答:阈值宽松、允许边界突刺、实现成本优先的内部接口。

09.2.1.1-003 固定窗口的临界突刺问题是什么?举例说明。

一句话结论

固定窗口在边界两侧各允许一次阈值流量,窗口交界处的短时间内可能出现接近两倍阈值的突发:例如阈值 100 QPS、窗口 1 秒,第 0.9 秒到 1 秒打满 100,第 1 秒刚过又打满 100,两秒交界的 200ms 内涌入约 200 请求。

概念解释

  • 突刺来自两个相邻窗口的计数互不影响。
  • 下游能力按单窗口阈值设计,交界突发可能击穿。
  • 窗口越大,边界突刺的相对影响越难被察觉。

原理流程

窗口 N:末尾 100 请求
窗口 N+1:开头 100 请求
交界 200ms 内 ≈ 200 请求 → 2 倍阈值突发

常见误区

  • 误区:把窗口调小就能消除突刺。窗口变小只是把突刺频率提高,交界处双倍问题依然存在。
  • 误区:突刺只影响限流本身。突发流量会压垮下游连接池与 DB,比计数超限后果更重。

追问

  • 问:什么算法能缓解临界突刺?答:滑动窗口平滑边界,令牌桶可控制突发总量,漏桶保证匀速流出。
  • 问:临界突刺在实际中何时危险?答:下游抗突发能力弱(DB 连接、线程池)或流量本身集中在整点/边界到达时。

09.2.1.1-004 固定窗口在窗口边界如何重置计数?

一句话结论

两种方式:按窗口编号生成新 key(天然从 0 开始),旧 key 靠过期清除;或单 key 到点清零。分布式实现常用“窗口编号 + key 过期”,避免跨节点清零的协调问题。

概念解释

  • 编号法:key 含窗口序号,新窗口即新 key。
  • 过期法:旧 key TTL 到期自动删除。
  • 清零法:到点重置同 key 计数,需考虑并发与时钟。

原理流程

编号法:key = 维度 + 窗口号
  新窗口 → 新 key 从 1 开始
  旧 key 过期回收

常见误区

  • 误区:用固定 key 手动清零没有并发风险。清零与递增并发时可能漏计或误清。
  • 误区:key 不过期也没关系。长期不用的维度 key 会持续占用存储。

追问

  • 问:窗口编号怎么生成?答:floor(当前时间 / 窗口长度),注意使用统一时钟口径。
  • 问:跨实例共享计数用什么?答:Redis 存窗口 key,配合过期与原子操作(见分布式限流页)。

09.2.1.1-005 滑动窗口(日志法)怎么实现?

一句话结论

为每个维度记录请求时间戳列表(日志),每次到达先剔除窗口外的旧时间戳,再判断列表长度是否达到阈值;窗口随请求滑动,精度高但需要存储每次请求的时间点。

概念解释

  • 数据结构:时间戳有序集合/队列。
  • 判定:now - 旧边界 之外的记录移除,剩余数量 < 阈值才放行。
  • 精度:接近实时,但每请求一条记录,内存成本高。

原理流程

remove all ts <= now - window
if len(timestamps) < limit:
    append now; accept
else:
    reject

常见误区

  • 误区:日志法可以无限保留时间戳。过期记录必须及时清理,否则集合随请求量无限增长。
  • 误区:日志法适合高维全量限流。海量用户/接口维度下存储与排序成本不可接受。

追问

  • 问:时间戳集合用什么结构?答:有序集合(按时间排序)或队列头部淘汰;Redis 可用 ZSET 按分数清理。
  • 问:日志法精度如何?答:每个请求都参与判定,窗口边界连续,无固定窗口的双倍突刺。

09.2.1.1-006 滑动窗口(分片计数器法)怎么实现?

一句话结论

把大窗口切成多个小槽位,每槽位一个计数器;当前计数 = 完整历史槽位之和 + 当前槽位 + 部分相邻槽位估算;用少量计数器替代逐条日志,内存与精度折中。

概念解释

  • 槽位:窗口/N 个小片段。
  • 求和:旧槽位全量 + 当前槽位;跨边界时按比例借邻槽估算。
  • 权衡:槽位越多越精确,计数与求和成本越高。

原理流程

window 分为 N 个 slot
count = Σ 过期前完整 slot + 当前 slot
(跨边界时结合上一 slot 做部分估算)

常见误区

  • 误区:分片法和日志法精度相同。分片在槽位边界存在估算误差,突刺控制不如日志法精确。
  • 误区:槽位越多越好。槽位过多增加求和与存储成本,收益递减。

追问

  • 问:槽位数量怎么定?答:在精度与成本间平衡,常见按窗口与判定粒度选择,按压测与流量特征调整。
  • 问:槽位计数怎么过期?答:整槽位随窗口滑出后清除,避免历史槽位长期占用。

09.2.1.1-007 日志法与分片法的内存/精度权衡是什么?

一句话结论

日志法每请求一条记录,精度高但内存与操作成本随请求量增长;分片法固定 N 个计数器,内存稳定,精度受槽位粒度限制;高维海量场景优先分片或桶算法,低维高精度场景可用日志法。

概念解释

方法 存储 精度 适用
日志法 每请求时间戳 高 维度少、精度要求高
分片法 固定槽位计数 中 维度多、成本敏感

原理流程

日志法:请求记录时间戳 → 窗口内剔除过期记录 → 计数判定
分片法:请求落入当前槽位 → 窗口内各槽位求和 → 计数判定

常见误区

  • 误区:为了精度所有限流都上日志法。高并发高维下时间戳集合本身成为内存瓶颈。
  • 误区:分片法估算误差可以忽略。在突刺场景误差可能导致少量超限放行,需结合下游承受能力评估。

追问

  • 问:怎么估算日志法内存?答:单维度窗口内请求数 × 单时间戳大小;乘以维度数量,评估总占用。
  • 问:分片法误差来源?答:槽位内请求分布不均,整槽求和无法反映槽内节奏。

09.2.1.1-008 滑动窗口如何消除固定窗口的临界突刺?

一句话结论

滑动窗口的统计区间随时间连续移动,任何时刻回看的都是最近一个完整窗口内的请求数;相邻两次判定共享大部分历史请求,不存在两个独立窗口同时在边界打满的情况,因此突刺被平滑。

概念解释

  • 连续区间:判定口径始终是 [now-window, now]。
  • 旧请求滑出后才计入新窗口,不会双倍叠加。
  • 仍允许窗口内自然突发,只是不受固定边界放大。

原理流程

固定窗口:边界两侧独立计数 → 双倍突刺
滑动窗口:连续回看最近 window
  → 任意时刻计数 ≤ 阈值对应的窗口量

常见误区

  • 误区:滑动窗口完全不允许突发。窗口内短时间集中请求仍可能达到阈值,只是没有边界双倍放大。
  • 误区:滑动窗口实现没有成本。相比固定窗口,维护滑出与求和更复杂。

追问

  • 问:滑动窗口还剩什么突刺?答:窗口内瞬时突发;需要更平滑的控制时用漏桶匀速流出,或令牌桶限制桶容量。
  • 问:判定时点为什么重要?答:每次到达都重新统计最近窗口,而不是等到窗口结束再判断。

09.2.1.1-009 窗口大小与阈值怎么选?

一句话结论

阈值按下游安全能力与业务优先级定;窗口大小按需要控制的突发尺度选:短窗口控制瞬时速率,长窗口控制总量;窗口过短计数抖动敏感,过长则突刺缓冲能力弱、响应慢。

概念解释

  • 阈值:单位窗口允许请求数。
  • 窗口:控制节奏的时间尺度(秒/分/天)。
  • 组合:阈值/窗口 = 平均速率,另设桶容量限制瞬时突发。

原理流程

平均速率 = limit / window
例:1000 请求 / 10s = 100 QPS
窗口越短 → 越贴近瞬时控制
窗口越长 → 越偏总量配额

常见误区

  • 误区:阈值直接照抄其他系统。下游能力、接口成本与优先级不同,必须按本系统压测定。
  • 误区:窗口越长越稳。长窗口把突发攒在一起,到期前不报警,超限时已经积压。

追问

  • 问:秒级限流和分钟级限流如何配合?答:秒级控瞬时速率,分钟级控总量配额,两级计数叠加判定。
  • 问:写接口阈值和读接口一样吗?答:写接口成本高、下游约束强,阈值通常更保守。

09.2.1.1-010 计数超时未清理会有什么问题?

一句话结论

过期计数不清理会导致存储随维度和时间无限增长,key 残留还会让旧窗口计数污染新判定(若复用 key);必须为限流 key 设置 TTL,定时清理空维度记录。

概念解释

  • 残留来源:稀疏维度(临时用户/IP)请求后不再访问。
  • 风险:内存占用、误计数、扫描成本上升。
  • 清理:TTL 过期 + 惰性删除 + 定期兜底清理。

原理流程

每维度 key 设置窗口长度 + 余量 TTL
  → 过期自动删除
  → 空记录不保留

常见误区

  • 误区:Redis 限流 key 不用管过期。不设 TTL 的热点/稀疏 key 会长期占用内存。
  • 误区:本地计数可以靠程序重启清理。长跑服务中泄漏计数不会自然消失。

追问

  • 问:TTL 设多长合适?答:略大于窗口长度,保证当前窗口计数有效,旧窗口及时回收。
  • 问:如何发现残留 key?答:监控 key 数量趋势与内存占用,扫描空计数 key 兜底删除。

09.2.1.1-011 窗口内突发超过阈值但被限流,判定时机是什么?

一句话结论

判定在请求到达时即时进行:先统计当前窗口内已有请求数,达到阈值即拒绝;不是等到窗口结束才统计,否则超限请求已经占用了下游资源。

概念解释

  • 实时判定:每请求到达时检查。
  • 计数先增后判或先判后增,语义不同(是否把当前请求计入)。
  • 拒绝请求不写入成功计数。

原理流程

到达 → 统计窗口内已放行数
  → 达到阈值 → 拒绝(不计入成功计数)
  → 未达阈值 → 计数 +1,放行

常见误区

  • 误区:先递增再判断导致拒绝请求也占计数。应明确口径:拒绝请求不计入放行配额,或按业务约定计入尝试量。
  • 误区:批量到达时统一在窗口末尾判定。批量突发会在判定前全部冲入下游。

追问

  • 问:计数顺序怎么定?答:常见做法先判断余量再递增;分布式下用 Lua 把判断与递增合并为原子操作。
  • 问:被拒请求要不要记录?答:记录拒绝维度与原因,用于限流命中率分析与阈值调优。

09.2.1.1-012 滑动窗口在分布式下状态放在哪里?

一句话结论

分布式计数放在共享存储(Redis),各实例读写同一份窗口计数;本地内存只做前置粗限,最终判定以共享计数为准;要保证判定与计数的原子性,并处理共享存储故障。

概念解释

  • 共享态:Redis 计数器/ZSET 保存窗口记录。
  • 本地态:提前拦截明显超限流量,降低 Redis 压力。
  • 一致性:多实例看到同一配额视图。

原理流程

请求 → 本地粗限(可选)
  → Redis 读取/更新窗口计数(原子)
    → 按结果放行/拒绝

常见误区

  • 误区:各实例本地计数相加即可代表总量。本地视图滞后且重复计算,无法得到准确全局配额。
  • 误区:共享计数没有故障兜底。Redis 不可用时应降级到本地限流或默认放行/拒绝策略。

追问

  • 问:窗口状态存 Redis 用什么结构?答:固定窗口用 String 计数 + TTL;日志法用 ZSET 时间戳;分片法用 Hash 槽位。
  • 问:时钟不一致影响什么?答:窗口边界与过期判定依赖时间,多实例应同步时钟(NTP)。

09.2.1.1-013 固定窗口适合什么业务场景?

一句话结论

适合配额宽松、抗突刺要求不高、实现极简的场景:如按天/按小时的总量配额、内部管理接口、低优先级任务;不适合对瞬时突发敏感的在线核心交易链路。

概念解释

  • 长周期配额:日/小时限额,边界突刺占比小。
  • 内部场景:下游可控,用户量有限。
  • 简单优先:计数实现与排查成本低。

原理流程

长窗口 + 宽松阈值 → 边界突刺影响有限
短窗口 + 核心链路 → 改用滑动窗口/桶算法

常见误区

  • 误区:固定窗口只能用于低级接口。长周期配额(如每日调用次数)用固定窗口完全合理。
  • 误区:简单算法一定落后。在匹配的场景下,简单可维护比过度精确更重要。

追问

  • 问:固定窗口两级怎么配合?答:外层长窗口控总量,内层短窗口控瞬时速率,都通过才放行。
  • 问:如何降低固定窗口突刺风险?答:叠加瞬时并发限制(信号量)或在入口做排队缓冲。

09.2.1.1-014 限流维度 key 如何构造?

一句话结论

key 由算法类型 + 限流维度(用户/IP/接口/租户)+ 窗口编号拼接而成,保证同一维度共享计数、不同维度互不干扰;维度过多时要评估 key 数量与内存成本。

概念解释

  • 维度:接口、用户 ID、IP、租户、设备。
  • key 规范:rate:{algo}:{dimension}:{window}。
  • 高维组合:避免维度爆炸,按需组合。

原理流程

key = "rate:fw:" + api + ":" + userId + ":" + window

常见误区

  • 误区:所有维度用同一个 key。混在一起无法区分是某个用户超限还是接口整体超限。
  • 误区:维度组合无限细分。用户 × 接口 × 设备组合数巨大,key 与计数成本失控。

追问

  • 问:多维度限流怎么判定?答:分别统计各维度阈值,任一维度超限即拒绝,可叠加接口总配额。
  • 问:key 里为什么要带窗口?答:避免不同窗口计数复用,保证旧记录可过期清理。

09.2.1.1-015 计数型限流与排队型限流有什么区别?

一句话结论

计数型超限直接拒绝,不保留请求;排队型把超限请求放入队列按速率处理,用等待换放行;计数型实现简单、响应快,排队型平滑下游但增加延迟与队列成本。

概念解释

  • 计数型:判定通过/拒绝。
  • 排队型:有界队列 + 匀速消费。
  • 选择:能否接受等待、下游是否可缓冲。

原理流程

计数型:超限 → 快速失败
排队型:超限 → 入队 → 匀速消费 / 超时拒绝

常见误区

  • 误区:排队型不会超限。队列有界,满了仍要拒绝;队列只是把突发转为延迟。
  • 误区:所有请求都适合排队。强时效同步请求排队等待体验差,应快速失败走降级。

追问

  • 问:排队型对应哪种算法?答:漏桶 + 队列,出口匀速;令牌桶允许桶内突发后放行。
  • 问:队列等待超时怎么设?答:小于业务时效预算,超时拒绝并提示,避免占用槽位。

09.2.1.1-016 窗口边界时钟不一致有什么影响?

一句话结论

多实例时钟不一致会导致窗口划分错位、过期判定偏差,不同节点对“当前窗口”理解不同,计数边界出现空隙或重叠;分布式限流应通过 NTP 对齐时钟,并尽量由服务端统一生成窗口编号。

概念解释

  • 时钟漂移:本地时间偏差导致窗口错位。
  • 过期误判:TTL 与窗口边界依赖时间。
  • 缓解:时钟同步、中心化计数、算法对小漂移不敏感。

原理流程

节点 A 窗口边界 10:00:00,节点 B 偏差 2s
  → 交界处计数归属不一致
    → 局部超阈值或误拒绝

常见误区

  • 误区:服务器时间自动准确。虚拟机、容器时钟漂移常见,需监控时间同步状态。
  • 误区:用客户端时间做窗口判定。客户端时钟可随意调整,必须以服务端时间为准。

追问

  • 问:Redis 限流如何减少时钟依赖?答:由 Redis 服务端时间计算过期,应用只传窗口参数;窗口编号基于服务端时钟。
  • 问:漂移较大时怎么办?答:同步 NTP,必要时采用对窗口边界不敏感的令牌桶算法。

09.2.1.1-017 窗口内被拒请求要记录什么信息?

一句话结论

记录限流维度(用户/IP/接口/租户)、拒绝时间、所属窗口、阈值与当时计数、拒绝原因与处理策略;用于命中率分析、阈值调优、误伤排查与告警,不记录敏感凭据。

概念解释

  • 诊断字段:维度 key、命中规则、阈值、计数。
  • 观测:拒绝率趋势、热点超限对象。
  • 合规:不记密钥、令牌等敏感信息。

原理流程

拒绝事件:维度 + 规则 + 阈值 + 计数 + 时间
  → 指标聚合(拒绝率)+ 明细日志(排查)

常见误区

  • 误区:被拒请求不用留痕。无记录无法判断是阈值过紧、攻击流量还是配置错误。
  • 误区:日志记录完整请求体。可能含隐私数据,只记必要维度与判定结果。

追问

  • 问:拒绝率高怎么分析?答:先看分布在哪些维度/接口,区分攻击、突增流量与阈值偏低。
  • 问:限流告警看什么?答:拒绝率、被拒 QPS、热点 key,结合入口流量与下游水位。

09.2.1.1-018 分片计数器的槽位数量怎么定?

一句话结论

槽位数量在精度与成本间折中:槽位越多窗口内分布越接近连续统计,但每次判定求和与维护成本越高;按窗口长度、判定粒度与流量波动选择,常见每槽位数百毫秒到数秒,具体按压测调整。

概念解释

  • 精度:槽位粒度决定边界误差范围。
  • 成本:槽位数影响存储与求和操作。
  • 流量:波动大的场景需要更细槽位。

原理流程

N 槽位 → 单槽 = window / N
误差量级 ≈ 单槽内请求分布

常见误区

  • 误区:槽位越多算法越好。槽位过细带来更多计数操作与 key 维护,收益递减。
  • 误区:槽位数量固定不用调。流量模式变化后应复核粒度是否仍合适。

追问

  • 问:槽位计数存什么结构?答:本地可用数组;分布式用 Redis Hash 存各槽位计数,当前槽位递增,旧槽位随窗口滑出清除。
  • 问:跨边界怎么求和?答:剔除已滑出槽位,汇总剩余完整槽位与当前槽位计数。

09.2.1.1-019 固定窗口两级限流(分钟 + 秒)怎么配合?

一句话结论

两级独立计数:秒级窗口控制瞬时速率,分钟级窗口控制总量配额;请求必须两级都未超限才放行;两级分别统计,拒绝时记录命中的是哪一级,便于调优。

概念解释

  • 秒级:抗瞬时突发,保护线程池/下游。
  • 分钟级:防长时间占用配额,保护整体容量。
  • 判定:AND 关系,任一级超限拒绝。

原理流程

check 秒窗口:count_1s < limit_1s?
check 分钟窗口:count_1m < limit_1m?
两者都通过 → 放行并分别递增

常见误区

  • 误区:两级阈值互相推导即可。两级保护目标不同,需分别按瞬时能力与总量配额设定。
  • 误区:只记最终拒绝不分级。不区分命中级别就无法判断该调哪级阈值。

追问

  • 问:两级计数都要原子维护吗?答:分布式下各自用原子操作/Lua 更新,避免并发超限。
  • 问:哪一级更容易先触发?答:突发流量先打满秒级;持续高负载会先耗尽分钟级配额。

09.2.1.1-020 窗口类算法与桶类算法怎么对比选型?

一句话结论

窗口类(固定/滑动)按时间计数,回答“最近窗口内有多少请求”;桶类(令牌桶/漏桶)按速率与容量控制,回答“还能放多少、流出多快”;需要平滑匀速选漏桶,需要允许受控突发选令牌桶,简单总量配额选窗口算法。

概念解释

  • 窗口:计数视角,判定总量。
  • 令牌桶:生成令牌,桶容量限制突发。
  • 漏桶:入口缓冲,出口匀速。

原理流程

总量配额 → 窗口计数
允许受控突发 → 令牌桶
严格匀速 → 漏桶 + 队列

常见误区

  • 误区:一种算法通吃所有限流场景。突发控制、匀速流出、总量配额的需求不同,算法应搭配使用。
  • 误区:算法选对就不用调参数。桶容量、速率、窗口大小决定实际效果,需结合压测。

追问

  • 问:接口层常用哪种?答:令牌桶兼顾突发与平滑,网关与应用层最常用;匀速削峰用漏桶。
  • 问:可以组合吗?答:可以,如令牌桶控制入口 + 漏桶队列控制下游流出,分层防护。