2005年，卡内基梅隆大学的研究人员进行了一项有趣的实验。他们在校园网络的边缘路由器上部署了四种不同的限流算法，然后用真实流量和Blaster蠕虫攻击数据进行测试。结果令人意外：表现最差的算法错误率高达30%，而表现最好的算法错误率低于1%。
这篇发表在并行数据实验室的论文揭示了一个重要事实：限流算法的选择远比大多数人想象的更关键。错误的算法不仅会让恶意流量溜过，还会误伤正常用户。更糟糕的是，分布式环境下的实现复杂性往往被低估——race condition、时钟漂移、内存溢出等问题随时可能导致限流失效。
两种比喻，两种哲学
限流算法的研究可以追溯到上世纪八十年代的电信网络。Jonathan S. Turner在1986年的IEEE论文中首次描述了漏桶算法，用于ATM网络的流量整形。三十年后，这些来自电信领域的技术成为了现代互联网API保护的基石。
理解限流算法，首先要理解两个核心比喻：令牌桶和漏桶。它们听起来相似，但代表了两种完全不同的流量管理哲学。
令牌桶：允许合理的突发
令牌桶算法的工作方式像一个自动贩卖机：系统以固定速率向桶中投放令牌，每个请求必须消耗一个令牌才能被处理。如果桶里有令牌，请求立即通过；如果桶空了，请求被拒绝或等待。
关键特性在于桶的容量。假设系统配置为每秒产生10个令牌，桶容量为100。当系统空闲一段时间后，桶会积累满100个令牌。此时如果突然涌入100个请求，它们全部可以被立即处理。这种"突发允许"的设计非常符合真实世界的流量模式——网页加载会同时触发多个资源请求，用户操作往往带有自然的聚集性。
Google Guava库的RateLimiter就是令牌桶的典型实现。其SmoothBursty类允许设置maxBurstSeconds参数，控制桶最多能存储多少秒的令牌。源码中的关键变量包括：
double storedPermits; // 当前存储的令牌数
double maxPermits; // 最大存储令牌数
double stableIntervalMicros; // 令牌添加间隔
long nextFreeTicketMicros; // 下一个令牌可用时间
当调用acquire()方法时，Guava会先调用resync()函数根据时间差计算新产生的令牌，然后尝试从桶中取令牌。如果令牌不足，它采用"预消费"机制：当前线程不等待，而是让下一个线程承担等待时间。这种设计减少了线程阻塞，但要求开发者理解其语义。
漏桶：强制平滑输出
漏桶算法的设计哲学截然不同。想象一个底部有小孔的水桶：水（请求）从上方流入，从下方以恒定速率流出。如果流入太快，桶会溢出，多余的请求被丢弃。
漏桶的核心是队列+FIFO调度。请求先进入队列，然后由处理器以固定速率从队列中取出处理。这保证了输出流量的绝对平滑——无论输入多么突发，输出始终恒定。
Nginx的limit_req模块就是漏桶算法的实现。配置示例：
limit_req_zone $binary_remote_addr zone=mylimit:10m rate=10r/s;
location /login/ {
limit_req zone=mylimit burst=20 nodelay;
}
这里rate=10r/s定义了"漏水速率"，burst=20定义了桶的容量（队列长度）。nodelay参数是一个有趣的优化：它允许队列中的请求立即被处理，但会标记这些"槽位"已被占用，后续请求需要等待槽位释放。
Wikipedia对漏桶算法有两种描述：作为流量整形的队列，和作为流量监管的计数器。后者实际上是令牌桶的镜像——两者在数学上等价，只是描述角度不同。这导致了业界长期以来的混淆：很多人把漏桶当作队列理解，却在实现时使用了计数器模式。
时间窗口的边界陷阱
令牌桶和漏桶都来自电信领域，适合处理连续的数据流。但API限流场景有所不同：我们更关心"在某个时间窗口内允许多少次请求"这类离散计数问题。这引出了基于时间窗口的算法系列。
固定窗口：简单但危险
固定窗口计数是最直观的方法：将时间划分为固定长度的窗口（如1分钟），每个窗口维护一个计数器。请求到来时，如果当前窗口计数未超限，就加1并放行；否则拒绝。
问题出在窗口边界。假设限流规则是"每分钟100次请求"。一个用户在第59秒发送了100个请求，然后在第61秒（新窗口开始）又发送100个请求。从系统角度看，任何一分钟都没有超过100次；但从用户角度看，他在2秒内发送了200次请求——这是限流规则本应禁止的行为。
这种边界效应在真实系统中会产生严重后果。某电商平台曾因此遭受抢购脚本攻击：脚本精确计算窗口边界，在两个窗口交界处发起大量请求，成功绕过了限流保护。
滑动窗口日志：精确但昂贵
滑动窗口日志算法试图解决边界问题。它不使用固定窗口，而是记录每个请求的时间戳。当新请求到来时，计算当前时间向前推一个窗口长度的时间点，统计该时间点之后的请求数量。
这种方法完全消除了边界效应，但代价是高昂的内存和计算开销。每个用户需要维护一个时间戳列表，每次请求都需要遍历列表清理过期记录并计数。在高并发场景下，Redis中的Sorted Set虽然可以高效实现，但内存消耗仍然可观。
滑动窗口计数器：Cloudflare的选择
Cloudflare在2017年的技术文章中介绍了他们的选择：滑动窗口计数器。这是一种混合方案，结合了固定窗口的低开销和滑动窗口的准确性。
核心思想是利用当前窗口和上一个窗口的计数来估算滑动窗口内的请求数：
rate = previous_count × overlap_weight + current_count
假设窗口大小为1分钟，当前时间在新窗口的第15秒（即25%位置），上一个窗口有42个请求，当前窗口有18个请求：
rate = 42 × 0.75 + 18 = 49.5
Cloudflare对4亿个请求的分析表明，这种近似算法的错误率极低：
- 仅0.003%的请求被错误允许或拒绝
- 实际速率与估算速率平均偏差6%
- 没有误杀情况（假阳性率为0）
更重要的是，这种算法只需要存储两个数字：上一个窗口的计数和当前窗口的计数。相比存储完整的时间戳列表，内存开销降低了几个数量级。
分布式的挑战
以上讨论都假设限流器运行在单个节点上。但在真实的生产环境中，限流通常需要在多个服务器间协同工作。
Redis的原子性陷阱
最常见的分布式限流方案是使用Redis作为共享存储。但一个容易踩的坑是race condition。考虑这个简单的计数器实现：
count = redis.get(key)
if count and int(count) >= limit:
return False
else:
redis.incr(key)
redis.expire(key, window)
return True
在高并发下，两个请求可能同时执行get操作，都看到计数未超限，然后都执行incr。结果是限流失效——实际请求数可能远超限制。
解决方案是使用Redis的Lua脚本，利用其原子执行特性：
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local current = redis.call("GET", key)
if current and tonumber(current) >= limit then
return 0
else
if current then
redis.call("INCR", key)
else
redis.call("SET", key, 1, "EX", window)
end
return 1
end
Stripe的技术文章特别强调了这一点：他们的限流器在检测到Redis故障时，会自动"fail open"——放行所有请求，而不是拒绝所有请求。这是一种权衡：短暂的限流失效优于完全的服务中断。
Cloudflare的边缘架构
Cloudflare面临更极端的挑战：他们需要在遍布全球的边缘节点上为数百万域名提供限流服务。集中式的Redis计数器在这里完全不可行——跨洲的数据中心延迟太高。
他们的解决方案巧妙地利用了Anycast网络的特性：来自同一IP地址的流量，在正常情况下会被路由到同一个PoP（Point of Presence）。因此，限流计数可以局限在每个PoP内部，不需要全局同步。
在每个PoP内部，Cloudflare使用Twemproxy构建了一个memcached集群。每个服务器既是应用服务器，也是存储集群的一个分片。滑动窗口计数器的计算只需要两个GET命令和一个简单的数学运算，延迟极低。
更进一步，他们实现了异步计数：请求先被处理，计数操作异步执行。只有当某个IP触发限流后，系统才会在请求路径中检查限流状态。这种设计使得正常请求几乎不受限流模块的性能影响。
生产环境的多层防护
Stripe的工程团队在2017年分享了他们生产环境中运行的四层限流架构，这是一个很好的生产实践参考。
第一层：请求速率限制器
最基本的限流：每个用户每秒最多N个请求。Stripe使用令牌桶算法，允许一定程度的突发流量。他们特别强调测试环境和生产环境使用相同的限流规则，避免开发阶段脚本"跑得好好的"，上线就触发限流。
第二层：并发请求限制器
某些API端点特别消耗资源（如复杂的数据库查询）。单纯的速率限制无法防止这类场景：用户可能在一秒内发起20个并发请求，虽然速率限制通过了，但后端服务已经不堪重负。
并发请求限制器统计"正在处理中的请求数"，而非"单位时间内的请求数"。用户被告知"你最多同时有20个请求在处理中"，这促使他们采用更合理的请求模式。
第三层：集群使用率负载卸载器
当整个系统负载过高时，需要有选择地丢弃低优先级请求。Stripe将API调用分为"关键"和"非关键"两类，始终预留20%的容量给关键请求。如果非关键请求超过了80%的配额，就会被拒绝。
第四层：工作线程利用率负载卸载器
这是最后的防线。当工作线程队列开始积压时，系统会按优先级逐步丢弃请求：先丢弃测试环境流量，再丢弃GET请求，最后丢弃POST请求，始终保护关键业务操作。
这套架构的关键在于渐进式响应：只有在必要时才启用更激进的限流策略，避免过度限制正常用户。
算法选择的决策框架
没有"最好"的限流算法，只有"最适合"的算法。以下是选择时的考量维度：
突发容忍度：如果业务需要容忍合理的突发流量（如网页加载、批量操作），令牌桶是首选。如果后端对流量平滑度有严格要求（如数据库写入、第三方API调用），漏桶更合适。
精确度要求：固定窗口的边界效应在某些场景下可能不可接受（如支付系统）。滑动窗口计数器提供了很好的平衡点，在大多数情况下足够精确。
分布式需求：单机限流可以使用Guava RateLimiter等内存实现。分布式限流需要考虑Redis等共享存储，并妥善处理race condition。超大规模系统可能需要Cloudflare式的边缘架构。
用户公平性：多租户系统需要分层限流——租户级限制防止单个大客户占满资源，用户级限制防止单个用户影响同租户其他用户。
降级策略：限流器故障时怎么办？fail open（放行）保护可用性但牺牲保护；fail closed（拒绝）保护系统但影响用户。Stripe选择了前者，这对支付系统更合理。
从代码到系统
限流算法的实现细节往往决定了其有效性。Guava的预消费机制、Nginx的nodelay参数、Redis的Lua脚本——这些细节在压力来临时会成为系统是否稳定的关键。
CMU的研究人员在论文结尾写道：“DNS行为的限流比其他方法准确得多。“这是一个有趣的结论：最佳的限流策略往往结合了业务语义。一个针对蠕虫扫描的限流器，使用DNS查询作为判断依据，比单纯统计连接数更有效。
在设计限流系统时，从业务场景出发，理解流量模式，选择合适的算法组合，然后才能写出可靠的代码。这不是一个"配置几个参数"的问题，而是需要深入理解系统行为的设计决策。
参考文献
- Wong, C., Bielski, S., Studer, A., & Wang, C. (2005). On the Effectiveness of Rate Limiting Mechanisms. Carnegie Mellon University Parallel Data Laboratory.
- Turner, J. (1986). New directions in communications (or which way to the information age?). IEEE Communications Magazine, 24(10), 8-15.
- Stripe. (2017). Scaling your API with rate limiters. Stripe Blog.
- Cloudflare. (2017). How we built rate limiting capable of scaling to millions of domains. Cloudflare Blog.
- Redis. (2024). Build 5 Rate Limiters with Redis: Algorithm Comparison Guide. Redis Documentation.
- Wikipedia. Token bucket. Retrieved 2024.
- Wikipedia. Leaky bucket. Retrieved 2024.
- NGINX. Rate Limiting with NGINX. NGINX Blog.
- AlgoMaster. (2024). Rate Limiting Algorithms Explained with Code.
- Diachenko, R. (2024). Sliding Window Rate Limiting and its Memory-Optimized Variant.