限流算法 (Rate Limiting)

引言：“吵闹的邻居”

想象你提供一个免费 API。某个用户写了一个脚本，结果不小心每秒发送了 10,000 个请求。你的数据库瞬间瘫痪，导致其他所有正常用户都无法访问。

限流 (Rate Limiting) 指的是限制一个用户（或服务）在给定时间内可以发送的请求数量。它是防御 DDoS 攻击、暴力破解登录以及防止“猪队友”脚本跑飛的第一道防线。

算法要解决什么问题？

• 输入： 来自不同用户的请求流。
• 输出： 接收 (Accept) 或 拒绝 (Reject / 429 Too Many Requests)。
• 承诺： 公平性（单个用户不能霸占所有资源）和稳定性（即使在高负载下，系统也能存活）。

核心算法

1. 令牌桶 (Token Bucket)

• 逻辑： 想象一个装“令牌”的桶。每个请求消耗一个令牌。系统以固定速率（如 10 个/秒）向桶里放入令牌。如果桶空了，请求就被拒绝。
• 优点： 允许 突发流量 (Bursts)。如果用户一段时间没发请求，桶里的令牌会攒起来，允许他们瞬间发出一小波请求。
• 适用： 最流行；被 AWS, Stripe 和 Spring Cloud 广泛采用。

2. 漏桶 (Leaky Bucket)

• 逻辑： 想象一个底部有个小孔的桶。请求像水一样以任意速度进入，但只能以 固定的速度 从底部漏出。如果桶满了，多出来的水就会溢出（请求被丢弃）。
• 优点： 完美平滑流量。不允许任何突发，处理速度极其稳定。
• 适用： 网络路由器的流量整形。

3. 固定窗口计数 (Fixed Window Counter)

• 逻辑： 将时间划分为固定窗口（如 1 分钟）。每个窗口设一个计数器。
• 缺点： “临界点问题”。如果用户在 00:59 发 100 个，01:01 发 100 个，虽然每分钟没超 100，但在 2 秒内发了 200 个，可能瞬间压垮系统。

4. 滑动窗口日志/计数 (Sliding Window)

• 逻辑： 记录每个请求的精确时间戳。
• 优点： 最准确；解决了临界点问题。
• 缺点： 内存开销大（需要存储每个时间戳）。

典型业务场景

• ✅ API 分级计费： 限制“免费版”每天 100 次，“专业版”每天 10,000 次。
• ✅ 登录保护： 防止黑客每秒尝试 1,000 次密码（暴力破解）。
• ✅ 外部服务保护： 如果你调用 OpenAI 的 API，你会限制自己的发送速率以匹配对方的配额。

性能与复杂度总结

• 时间： $O(1)$ (令牌桶可以通过简单的数学计算实现，无需定时器)。
• 空间： 每个用户 $O(1)$。

小结：一句话记住它

“限流是 API 的‘安全阀’。令牌桶给系统留了一点‘冲动’的空间（突发），而漏桶则追求绝对的‘冷静’与‘平滑’。”