设计一个限流器 (Rate Limiter)

限流器(rate limiter)限制一个客户端在给定窗口内能发多少请求,保护你的服务免受滥用、意外的流量风暴,以及当某个租户耗尽共享资源后随之而来的级联故障。它听起来就是一个计数器加一条 if 语句,但设计很快变难:计数器必须在一队无状态服务器之间共享且一致,检查必须几乎不给热路径加延迟,算法要公平地处理突发和窗口边界,而且当它自己的后端存储出问题时整套东西还得继续工作——是 fail-open 还是 fail-closed,要经过深思熟虑地选择。本文走一遍各种算法(token bucket、leaky bucket、fixed 与 sliding window)、在 Redis 上的分布式实现、让并发计数正确的原子性保证,以及客户端依赖的 HTTP 语义(429、Retry-After、X-RateLimit-*)。

Step 1 — 厘清需求

限流器是一个看似简单实则很深的面试题,因为"限制请求"背后藏着十几个决策。画框图前先定范围。

功能需求

• 按某个 key 限流:按 API key、按 user ID、按 IP,或按 (user, endpoint) 元组。
• 支持多条规则——例如对同一客户端既限 10 req/s 突发又限 1,000 req/小时 持续。
• 被限流时给客户端一个清晰信号:带 Retry-After 提示的 429。
• 规则可配置、可热加载,无需重新部署服务。
• 对不同档位(免费 vs 付费)和不同端点(便宜的读 vs 昂贵的写)用不同上限。

非功能需求

• 低额外延迟——检查在每个请求上;目标 <1–2 ms p99 的开销。
• 并发下的准确性——当同一 key 的成千上万请求同时打到不同节点时,计数必须正确。
• 高可用——限流器不能成为单点故障;为它的后端存储宕机时的行为做决定。
• 分布式正确性——上限是在 负载均衡 后水平扩展的无状态服务器队上全局生效,而非每节点单独生效。
• 可扩展性——以余量处理平台的全部请求量(每秒数十万次检查)。

Step 2 — 容量估算

按它要守护的流量来给限流器定容。假设一个 API 平台峰值服务 50 万 请求/秒。

吞吐

• 每个请求触发一次限流检查 → 50 万 检查/秒。每次检查是一次 Redis 往返(或一次 Lua eval)。
• 单个 Redis 实例约能处理 10 万–20 万 简单 ops/秒。在 50 万/秒下你需要一个 分片 Redis 集群(计数器按 client key 分区),或用本地+全局的混合来削减 Redis 流量。
• 给网络留预算:同机房的 Redis 每次检查加约 0.2–0.5 ms。让 Redis 和网关在同一 AZ,避免热路径上跨 AZ 延迟。

内存

• 每个活跃计数 key 都很小:rl:{client}:{window} → 一个整数加 TTL,算上 Redis 开销 ≈ ~100 字节。
• 一个窗口内 1000 万 个不同活跃客户端 → 1000 万 × 100 B ≈ ~1 GB。轻松放进内存;TTL 自动驱逐过期窗口,内存不会无界增长。
• token-bucket 状态每客户端需两个字段(token 数 + 上次补充时间戳)——仍然很小,存为 Redis hash。

Step 3 — 限流器放在哪里

放置位置是一等的设计决策。同一个算法因位置不同表现差别很大。

标准答案是 API 网关:它是天然的单一入口,能在超额流量消耗下游资源前就拒绝它,且把规则集中在一处。网关自身无状态,查询一个共享存储(Redis)拿计数,所以网关水平扩展不会割裂上限。客户端限流仍值得作为一层礼貌(它减少浪费的往返),但绝不用于执行(enforcement)。

Step 4 — 规则与配置

上限是数据,不是代码。规则引擎让产品按档位和端点定义上限,并能不部署就重载。一种紧凑表示:

# 限流规则,从配置服务热加载
rules:
  - match: { tier: free,  endpoint: "POST /api/*" }
    limit:  { requests: 10,   window: 1s,  algorithm: token_bucket, burst: 20 }
  - match: { tier: free,  endpoint: "*" }
    limit:  { requests: 1000, window: 1h,  algorithm: sliding_window }
  - match: { tier: paid,  endpoint: "*" }
    limit:  { requests: 100,  window: 1s,  algorithm: token_bucket, burst: 200 }
key_by:   api_key        # 或 user_id、ip、"user_id:endpoint"
on_fail:  allow          # 计数存储不可达时 fail-open

一个请求可能命中多条规则——一个免费用户打 POST /api/x 同时受 10/s 突发规则和 1,000/小时 持续规则约束。限流器评估所有命中的规则,任一超额就拒绝(最严格者胜)。把规则从最具体到最不具体排序,在第一个拒绝处短路以省 Redis 调用。

Step 5 — 算法全景

五种算法主导讨论。每种在准确性、内存和突发行为上权衡不同。

面试里,把 token bucket 说成默认,把 sliding window counter 说成当 fixed-window 边界泄漏要紧时的改进。只有当下游确实需要平滑、恒定的输出速率时(例如喂一个固定吞吐的 worker 池),leaky bucket 才是对的选择。接下来几步逐个深入。

Step 6 — Token Bucket

一个桶最多装 capacity 个 token,以每秒 refill_rate 个 token 的速度补充。每个请求拿走一个 token;桶空了请求就被拒。因为一个满桶能在一次突发里被抽干,token bucket 容忍最大到容量的突发,同时把长期平均限到补充速率——这正是大多数公开 API 想要的行为。

def allow(bucket, capacity, refill_rate, now):
    # 按流逝时间惰性补充——无需后台定时器
    elapsed = now - bucket.last_refill
    bucket.tokens = min(capacity, bucket.tokens + elapsed * refill_rate)
    bucket.last_refill = now

    if bucket.tokens >= 1:
        bucket.tokens -= 1
        return True          # 放行
    return False             # 拒绝 → 429

关键技巧是惰性补充(lazy refill):不用后台定时器加 token,而是从流逝时间算出自上次请求以来本应累积多少 token。这让每次检查 O(1),且两次调用之间除两个存储字段(tokens、last_refill)外无状态。在分布式场景里,这两个字段存在每客户端 key 的一个 Redis hash 里,整个 read-modify-write 必须原子(Step 10)。

Step 7 — Leaky Bucket

leaky bucket 把请求建模为倒进一个有洞的桶里的水:请求进入一个 FIFO 队列,以固定速率被处理(漏出)。队列满了,新请求溢出被拒。其定义性质是恒定的流出速率,无论输入多突发。

代价是延迟:leaky bucket 可以延迟一个请求(它待在队列里)而非拒绝它,这平滑了尖峰但增加尾延迟并需要队列内存。当你保护的东西——支付处理器、遗留系统、固定容量的 worker 池——需要稳定的滴流、且宁愿让调用方等也不愿看到尖峰时,用它。对大多数限流(拒绝而非延迟),token bucket 更合适。

Step 8 — Fixed Window 与 Sliding Window

窗口计数家族最容易在 Redis 之上实现,但在窗口边界藏着一个微妙的公平性 bug。

Fixed window

把时间切成固定区间(例如每个自然分钟)。每个 (client, minute) 保一个计数;每请求自增;超上限就拒;窗口结束让 key 过期。极简——一个 INCR——但它允许边界突发:客户端能在一个窗口的最后一刻发满上限,又在下一个窗口的第一刻再发满,在一个短于一个窗口的跨度里放行到 2 倍上限。

Sliding window log

在每客户端的一个有序集合里给每个请求存一个时间戳。每次请求时,丢掉早于 now - window 的时间戳,数剩下的;低于上限就放行。这是精确的且无边界泄漏——但它每请求存一条,所以一个做 10K req/s 的客户端每窗口要花 10K 个时间戳的内存。准确但昂贵。

Sliding window counter

务实的折中:为当前和上一个固定窗口各保一个计数,通过按上一个窗口与滑动窗口仍重叠的比例给它加权,来估计滚动计数。

# 对滚动窗口内请求数的加权估计
elapsed = now - current_window_start          # 进入当前窗口的秒数
weight  = (window_size - elapsed) / window_size  # 与上一个窗口的重叠

estimated = current_count + previous_count * weight
if estimated < limit:
    current_count += 1
    return True     # 放行
return False        # 拒绝 → 429

如果你进入当前分钟 25%,上一分钟仍贡献其计数的 75% 到滚动估计。这杀掉了边界突发,只花每 key 两个计数(O(1) 内存),实践中准确到不到一个百分点。这正是 Cloudflare 因这个原因推广的算法——fixed-window 的成本配 sliding-window 的公平。

Step 9 — Redis 里的分布式计数器

在负载均衡后限流器是无状态的,计数必须共享,所以计数器放在 Redis——单线程(无内部数据竞争)、内存(亚毫秒)、且自带原子 INCR 和每 key TTL。一个 fixed-window 限流器就是两条命令:

# key = rl:{client}:{window_id},如 rl:api_key_42:1719600000
INCR rl:api_key_42:1719600000        # 返回新计数
EXPIRE rl:api_key_42:1719600000 60   # TTL = 窗口大小;自动清理

# 应用逻辑:
#   count = INCR(key); if count == 1: EXPIRE(key, 60)
#   if count > limit: 拒绝 (429)

window id 由时间戳推出(floor(now / window_size)),所以 key 自动轮转、旧窗口经 TTL 过期——无需清扫任务。在 50 万 检查/秒下单个 Redis 节点超预算,所以把计数器跨一个分片集群分区:把 client key 哈希到一个分片。因为每个计数器都限定到一个 client key,按 client 分片让每个客户端的计数器留在单个节点上——无跨分片协调、无分布式事务。

Step 10 — 用 Lua 脚本保证原子性

朴素流程——读计数、比上限、再自增——是经典的 read-modify-write 竞态。同一 key 的两个请求同时到两个网关节点;都 GET 到 count=99,都判定自己在上限 100 之内,都 INCR 到 101。上限被突破。INCR 本身原子,但 token-bucket 和 sliding-window 的运算涉及读状态、计算、写回——多步骤不能交错。

Redis 用原子运行 Lua 脚本解决:整个脚本在 Redis 的单线程上作为一个不可分割的单元执行——中间不跑别的命令。读、上限检查、写要么一起发生、要么都不发生。

-- token bucket,经 EVAL 原子执行
-- KEYS[1]=bucket key  ARGV: capacity, refill_rate, now, requested
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or tonumber(ARGV[1])   -- 起始满桶
local ts     = tonumber(b[2]) or tonumber(ARGV[3])
local cap, rate, now, need = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3]), tonumber(ARGV[4])

tokens = math.min(cap, tokens + (now - ts) * rate)   -- 惰性补充
local allowed = tokens >= need
if allowed then tokens = tokens - need end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], 3600)
return allowed and 1 or 0

脚本在一个原子步骤里做完补充、检查、扣减和持久化,返回单个放行/拒绝。用 SCRIPT LOAD 上传一次,经 EVALSHA 按 SHA 调用,避免每次重发脚本体。替代方案——WATCH/MULTI 乐观事务——也行但在争用时要重试;对重并发下的一个热 key,Lua 方案更简单更快,因为它从不中止。

Step 11 — 同步 vs 异步与本地+全局

每个请求都查 Redis 是同步模型:完全准确,但把一次网络往返放在热路径上,并让 Redis 成为吞吐瓶颈和故障依赖。两个改进放松这点。

本地+全局(两层)

每个网关节点保一个小的进程内 token bucket,大小为全局上限中它该分到的份额,只周期性地与 Redis 对账。大多数请求在纳秒级本地放行或拒绝;Redis 被用来重分配余量,而非每次调用。这大幅削减 Redis 流量并能扛住短暂的 Redis 抖动,代价是轻微超额放行——节点本地的桶在一个同步间隔内可能合起来超过全局上限。对 10 个节点上 1,000/s 的上限,你可能短暂放行 1,050。通常可接受;调同步间隔以在准确性和 Redis 负载间权衡。

异步回写(write-behind)

基于本地读放行,然后把自增异步推给 Redis。最低延迟,最弱准确性——计数滞后、超额放行增大。把它留给软上限(approximate 即可,如分析限流),而非硬安全上限。

Step 12 — 429 响应与头部

当请求被限流时,返回 429 Too Many Requests 并告诉客户端怎么做。好的头部把盲目重试风暴变成礼貌退避。

HTTP/1.1 429 Too Many Requests
Retry-After: 2                  # 客户端可重试前等待的秒数
X-RateLimit-Limit: 100           # 本窗口的上限
X-RateLimit-Remaining: 0          # 此刻剩余 token
X-RateLimit-Reset: 1719600062     # 窗口补满的 epoch 时间
Content-Type: application/json

{ "error": "rate_limited",
  "message": "Too many requests. Retry after 2s." }

• 429 是正确状态码——与 503(服务器过载)区分,让客户端能对限流单独处理。
• Retry-After 是最有用的单个头部:它把客户端重试逻辑从猜测变成精确等待,防止把限流变成宕机的那种重试风暴。
• X-RateLimit-* 让规矩的客户端在撞墙之前就自我调速——在成功响应上也返回它们,客户端就能实时看到剩余预算。
• 服务端上限要配上客户端的指数退避 + 抖动(jitter),这样一群同时撞上限的客户端不会同步成惊群一起重试。

Step 13 — 边界情形与失败模式

面试深度都在这里——区分教科书答案和生产答案的那些情形。

• 计数存储宕机——决定 fail-open(放行;限流器宕机不该变成整体宕机——常见默认)还是 fail-closed(拒绝;用于保护脆弱或安全关键资源的上限)。健壮设计在 Redis 不可达时回退到一个保守的本地内存上限,既不放洪水也不全黑。
• 时钟偏移——token-bucket 惰性补充和 window id 都依赖时间。在 Lua 脚本里用 Redis 服务端时间(TIME 命令)作为单一时钟,而非各网关的本地时钟,以避免跨节点偏移。
• 窗口边界突发——fixed-window 的 2 倍泄漏(Step 8);用 sliding window counter 修。
• 竞态——并发的先查后增超额放行;用 Lua 原子脚本修(Step 10)。
• 分布式超额计数——本地+全局两层在同步期间超额放行有界;对软上限可接受,对硬上限不可。
• 热 key——一个客户端猛打单个分片;用本地第一层桶或子 key 拆分缓解。
• 按什么身份做 key——IP 可伪造且共享(NAT、企业代理会让同一 IP 下许多用户连坐);优先用已认证的 API key 或 user ID,仅对未认证流量回退到 IP。
• 重试风暴——没有 Retry-After 和带抖动的退避,被限的客户端会齐步猛打;限流器必须塑造客户端行为,而非只拒绝。

Step 14 — 扩展与容错

在平台规模下,限流器自身必须高可用且可水平扩展。

扩展检查路径

网关无状态——在负载均衡后水平扩展它们。共享状态是 Redis;通过按 client 把计数器跨 Redis Cluster 分片来扩展它。加上本地+全局层(Step 11)把每请求的 Redis 往返削减一个数量级,让 Redis 远在其 ops 上限之下。

容错

• Redis 故障——让 Redis 带副本和自动故障转移(Sentinel 或 Cluster)。在故障转移窗口里,限流器遵循其 on_fail 策略:大多数端点 fail-open 配本地回退桶,安全关键端点 fail-closed。
• 网关故障——无状态,所以负载均衡直接绕开宕掉的节点;计数状态不丢,因为它在 Redis 里。
• 区域故障——每区域跑一个 Redis 集群并按区域限流。真正跨区域的全局上限需要跨区域复制并接受最终一致;大多数设计按区域限流,因为跨区域同步计数会给热路径加不可接受的延迟。

Step 15 — 关键取舍