Rate Limiting — 不只是「每秒 100 次」Token Bucket vs Leaky Bucket vs Sliding Window · Distributed Counters · The 429 Contract

问题场景与约束

设计一个公开 API 平台的限流系统（参考 Stripe / GitHub）。全网 10 万+ 第三方集成方、峰值 1M QPS、单 key 上限 100 req/s、平台总容量 500k QPS。一次糟糕的脚本可以瞬间占满所有 worker，把付钱的请求挤掉——这就是为什么 限流是保命底线，不是「防爬虫」附加功能。

• 公平性：一个 key 失控不能拖垮其他 key；高优请求（创建支付）不能被低优请求（导出报表）饿死。
• 精确性：100 req/s 的限制，秒边界不能让用户在 0.999s 和 1.001s 之间「合法地」发出 200 个请求。
• 低开销：限流本身的延迟必须远低于业务延迟，目标 p99 < 1ms。
• 多维度：按 user / IP / endpoint / org 分别限流，且可组合（最严的那一层生效）。
• 对 caller 友好：429 必须可被自动重试 —— Retry-After 头要存在且准确。
• 限流挂了不能挂业务：Redis 不可用时放行（fail-open）比挂全站好。

今天讲四件事：算法选型、分布式实现、精度 vs 性能、429 契约。

高层架构

graph LR
    C["Client / 第三方应用"]
    GW["API Gateway
(Envoy / Kong / 自研)"]
    L1["本地令牌桶
(per worker)"]
    L2["集中计数
Redis + Lua"]
    SHED["Load Shedder
(优先级丢弃)"]
    APP["业务服务"]

    C -->|"req + API key"| GW
    GW -->|"①快路径: 90% 拒绝/放行"| L1
    L1 -->|"②慢路径: 周期同步"| L2
    GW -.过载.-> SHED
    GW -->|✓| APP
    GW -.->|"✗ 429 + Retry-After"| C

    classDef edge fill:#0e2030,stroke:#64c8ff,color:#e8eef5
    classDef store fill:#1a1a30,stroke:#ffb450,color:#e8eef5
    classDef origin fill:#2a1530,stroke:#ff7ab6,color:#e8eef5
    class GW,L1 edge
    class L2 store
    class APP,SHED origin

网关用本地令牌桶扛快路径，Redis 做集中真值，决策永远在 1ms 内返回

关键技术点

1. 算法选型：Token Bucket vs Leaky Bucket vs Sliding Window vs GCRA

原理：四种算法各自回答一个不同的问题——允许突发吗？输出能匀速吗？窗口怎么滚？

# Token Bucket 核心 (Python 伪代码)
def allow(key, capacity, refill_rate):
    now = time.time()
    tokens, last = state.get(key, (capacity, now))
    # 懒计算：本次取令牌时,按经过时间补充
    tokens = min(capacity, tokens + (now - last) * refill_rate)
    if tokens >= 1:
        state[key] = (tokens - 1, now)
        return True
    state[key] = (tokens, now)
    return False   # 拒绝, retry_after = (1 - tokens) / refill_rate

2. 分布式限流：Redis 中心化 vs 本地分摊 vs 异步聚合

原理：在一台机器上 token bucket 是平凡的；问题在于全网共享同一个 key 的配额时怎么协调。

-- Redis 原子 token bucket (Lua, Stripe 风格)
-- KEYS[1]=桶 key  ARGV={capacity, refill_rate, now, cost}
local cap, rate, now, cost = tonumber(ARGV[1]), tonumber(ARGV[2]),
                              tonumber(ARGV[3]), tonumber(ARGV[4])
local data = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(data[1]) or cap
local last = tonumber(data[2]) or now
tokens = math.min(cap, tokens + (now - last) * rate)
local allowed = tokens >= cost and 1 or 0
if allowed == 1 then tokens = tokens - cost end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('EXPIRE', KEYS[1], math.ceil(cap / rate) * 2)
return {allowed, tokens}     -- 原子,无 race

3. 多维度限流与优先级抛弃

原理：单一维度限不住真实流量。一个 key 可能正常，但所有 key 加起来打爆 endpoint；某 endpoint 正常但下游 DB 挂了。要按 多个维度同时检查、最严的胜出。

# 多维度组合 (伪代码)
def admit(req):
    keys = [
        ("key", req.api_key, 100, 1),
        ("ip", req.ip, 10, 1),
        ("ep", f"{req.api_key}:{req.path}", endpoint_limit(req.path), 1),
    ]
    for kind, k, cap, cost in keys:
        if not bucket_allow(f"{kind}:{k}", cap, refill_for(cap), cost):
            return reject(retry_after_from(cap, k), reason=kind)
    if global_inflight() > SHED_THRESHOLD and priority(req) < HIGH:
        return reject(retry_after=30, reason="overload")
    return ALLOW

4. 429 响应契约：让 caller 优雅退避

原理：限流不只是「拒绝」，是给 caller 一个机器可读的退避说明书。否则客户端只能死循环重试，把你二次打爆。

扩展与优化

• 热 key 突破 Redis 单节点：把单个高流量 key 在多个 Redis shard 上分散（key:0..15），每 shard 一份子配额，client 哈希落 shard。代价：精度损失（局部超额）。
• 从硬限流到自适应限流：用下游 latency / 错误率作信号动态调整（Netflix concurrency-limits、Google SRE 中的 adaptive throttling）—— 「健康时多放、生病时少放」。
• 跨区域全局配额：每区一份本地配额 + 跨区每秒一次异步对账。多区强一致全局配额代价巨大且没必要。
• 计算成本权重：不是每个请求都「一个令牌」，按 endpoint CPU 成本扣不同分（GraphQL query complexity = 扣的分；CPU-heavy endpoint 扣 10 分）。
• Fail-open vs fail-close：限流系统挂了应该放行（避免限流故障变业务故障），但下游会瞬间暴露。配合 circuit breaker。

常见陷阱 / 面试追问

1. 「为什么不用 sliding window log？」 — 内存代价。1M user × 100 req = 1 亿条 timestamp ≈ 几 GB；用 counter 近似就够，误差 < 5%。
2. 「Redis 挂了怎么办？」 — fail-open + circuit breaker；Stripe 工程博客明确把这作为铁律。
3. 「同一 user 多个进程并发请求，本地 token bucket 怎么共享？」 — 进程内桶不行，必须用 Redis；或用「本地子配额 + 异步对账」。
4. 「429 vs 503，何时用哪个？」 — 429 = 客户端超限（用户自己的问题）；503 = 服务过载（你的问题）。错用会让客户端的重试策略错。
5. 「Retry-After 怎么算？」 — token bucket 下 = (1 - tokens) / refill_rate；sliding window 下 = 到下一秒还有几毫秒；并且服务端必须加 jitter。
6. 「为什么 token bucket 比 leaky bucket 更主流？」 — 公开 API 客户端往往天然「攒着发」（cron job 一次发 50 个），token bucket 允许这种合理 burst；leaky bucket 严格匀速反而对正常用户不友好。

深入资源

• Stripe Engineering Blog — 「Scaling your API with rate limiters」（Paul Tarjan）：四类限流器、Redis Lua 实现、fail-open 原则，配套 GitHub gist 有可跑 Ruby 代码。
• Cloudflare Engineering Blog — 「How we built rate limiting capable of scaling to millions of domains」：边缘节点分布式限流，本地决策 + 异步聚合。
• Brandur Leach — 「Rate Limiting, Cells, and GCRA」（brandur.org）：GCRA 算法最易懂的讲解，配 Redis 实现。
• Google SRE Book — Ch 21 「Handling Overload」：自适应限流、优先级抛弃、客户端侧的 retry budget。
• Marc Brooker — 「Caution: Decreasing TCP MSS Doesn't Help」 系列分布式文章：理解 fail-open 与 backpressure 的本质思考。

深入思考（点击展开思路）