Skip to content
←

필사 모드: 限流算法全面解析：固定窗口、滑动窗口、令牌桶与漏桶

中文
0%
정확도 0%
💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

引言 — 为什么要限制速度

限流(rate limiting)是指「在一定时间内限制所允许的请求数量」。乍一看像是让用户感到不便的机制，但实际上它是守护整个系统的安全装置。

限流的必要性有很多。它保护服务器资源免受突发流量或行为异常的客户端影响，防止暴力破解(brute-force)登录尝试或爬虫抓取之类的滥用，在多个用户之间公平分配资源，并按套餐强制执行付费 API 的用量上限。归根结底，这是为了稳定性与公平性而存在的机制。

问题在于，「统计请求数」这个简单的想法，实际实现起来却有多种方式。每种方式在准确性、内存占用、突发流量的处理方式上各有不同的取舍。本文将逐一对比几种具有代表性的算法，并进一步介绍分布式环境下的实现与客户端礼仪。如果想亲自体验这些概念，可以在本站的消息队列游乐场中直观地感受吞吐量与流量控制。

固定窗口计数器 — 最简单的方式

最直观的方法是把时间划分成固定的窗口(window)，在每个窗口内统计请求数。比如"每分钟 100 次"的限制，就在每分钟开始时把计数器重置为 0，每来一次请求就加 1。计数器一旦超过 100，就在这一分钟结束前拒绝请求。

  每分钟 100 次限制，固定窗口
  [00:00 ~ 00:59]  计数 0 -> 100（超出部分拒绝）
  [01:00 ~ 01:59]  计数重置，重新 0 -> 100

优点很明确：实现起来非常简单，需要保存的状态只有一个计数器，几乎不占用内存。但它有一个致命的弱点：窗口边界处的突发流量可能会翻倍。

举例来说，假设某个用户在 00:00:59 一口气发送了 100 次请求，紧接着在 01:00:01 又发送了 100 次。这两个时刻只相差 2 秒，但分属不同的窗口，因此两次都会被允许通过。结果是大约 2 秒内通过了约 200 次请求。名义上是每分钟 100 次的限制，实际上却在瞬间泄漏了两倍的流量。正是这个边界问题，催生了接下来的几种方式。

滑动窗口日志 — 精确但沉重

要从根本上消除边界问题，可以不再使用固定窗口，而是以"从此刻起过去的 1 分钟"作为基准。这就是滑动窗口日志(sliding window log)。做法是记录每一次请求的时间戳，每当有新请求到来时，统计"过去 1 分钟内进来的请求有多少个"。

  每当有请求到来时：
  1) 从日志中删除比（当前时间 - 60 秒）更早的时间戳
  2) 统计剩余日志的数量
  3) 数量 < 100 则允许，并添加当前时间戳；否则拒绝

这种方式完全精确。无论以哪个瞬间为基准，统计到的都正好是过去 1 分钟内的请求，不会在边界处出现翻倍的情况。

不过代价很大。因为必须保存每一次请求的时间戳，流量越大，内存占用就越是随请求数成比例增长。在每秒涌入数万次请求的 API 上，为每个用户维护这样一份日志是相当沉重的负担。所以尽管精确性最高，在大规模场景下，人们往往更青睐接下来要介绍的折中方案。

滑动窗口计数器 — 实用的折中

滑动窗口计数器(sliding window counter)是介于固定窗口的轻量与滑动日志的精确之间的一种实用折中。其思路是只保留当前窗口与上一个窗口这两个计数器，并按重叠比例对上一个窗口的计数做加权近似。

计算方式如下。只要知道当前窗口已经过去的比例，就能推算出上一个窗口还剩多少比例与当前窗口重叠。于是估计请求数如下：

  估计值 = 当前窗口计数
         + 上一个窗口计数 * (上一个窗口仍然重叠的比例)

  例：每分钟 100 次，当前窗口已过去 25%
      上一个窗口计数 = 80，当前窗口计数 = 30 时
      估计值 = 30 + 80 * (1 - 0.25) = 30 + 60 = 90
      90 < 100，因此允许

这种近似依赖于一个假设：流量在窗口内的分布大致均匀。它并不完美，但在实践中误差很小，而且只需保存两个计数器，非常轻量。因此生产环境的限流器普遍采用这种方式，既能消除固定窗口的大部分边界突发问题，又能避免滑动日志的内存负担。

令牌桶 — 优雅地允许突发

到目前为止的方式都聚焦于统计"来了多少个"，而令牌桶(token bucket)则换了一个视角。它不去统计请求，而是发放令牌，也就是处理一次请求所需的权利。

具体的运作方式是这样的。令牌以固定速率被放入桶中（例如每秒 10 个）。桶有最大容量（例如 100 个）。请求到来时会取走一个令牌：有令牌则放行，没有则拒绝。

  令牌桶（容量 100，填充速率每秒 10 个）
   令牌以每秒 10 个的速度落入桶中并积累（最多 100 个）
       │
       ▼
   [ 桶：●●●●●●... 最多 100 个 ]
       │  每 1 个请求消耗 1 个令牌
       ▼
   有令牌则放行，没有则拒绝

令牌桶的精妙之处在于它能自然地允许突发流量。如果一段时间内没有请求，令牌就会在桶里逐渐积满（最多 100 个）。此后一旦请求突然涌入，就可以把积攒下来的令牌一次性全部放行。也就是说，它容许平时安静的客户端瞬间集中发送请求，同时把长期的平均速率限制在填充速率（每秒 10 个）之内。桶的容量决定了突发的上限，填充速率则决定了可持续的平均速率。

正因为这种灵活性，令牌桶成为实践中应用最广泛的算法之一。许多 API 网关和网络设备都采用这种方式。

漏桶 — 让流量平滑

漏桶(leaky bucket)顾名思义，是一个"会漏水的桶"。请求先进入桶中（相当于队列），再从底部的孔以恒定速率漏出并被处理。桶一旦装满，溢出的请求就会被丢弃。

  漏桶
   请求从上方涌入队列
       │
       ▼
   [ 队列：请求正在等待 ]
       │  从底部以恒定速率处理（例如每秒 10 次）
       ▼
   队列装满后，溢出的请求会被丢弃

令牌桶与漏桶经常被拿来比较，两者的核心区别在于输出的性质。

  • 令牌桶允许突发。如果令牌已经积累，就会在瞬间一次放行大量请求，输出可能会忽高忽低。
  • 漏桶让输出保持平滑。无论输入如何激增，都只会以底部孔的速率流出，因此处理速度是恒定的。代价是，要吸收瞬时的突发流量就得在队列里等待，可能因此产生延迟。

因此，选择取决于目的。如果想要"宽容地允许偶尔的突发，但只需守住平均速率"，令牌桶更合适；如果想要"为了保护下游服务而让处理速度保持恒定"，漏桶更合适。

算法对比表

把到目前为止的内容整理成一张表格如下。

算法内存精确性突发处理特点
固定窗口非常小低（边界问题）边界处泄漏 2 倍实现最简单
滑动日志大（与请求数成正比）完美无精确但沉重
滑动计数器小（2 个计数器）高（近似）几乎没有实用的折中
令牌桶小高允许至容量上限对突发宽容，限制平均速率
漏桶小（队列大小）高吸收后拉平输出速率恒定

分布式环境中的限流

到目前为止我们假设的是单台服务器。但实际的服务通常由多台服务器实例在负载均衡器后面共同处理请求，这就产生了一个问题：如果每个实例各自维护自己的计数器，总的限制就会随实例数量成倍膨胀。如果有 5 个实例，每个都允许每分钟 100 次，用户实际上就能用到每分钟 500 次。

解决办法是把计数器放到实例之外的共享存储中。承担这一角色最常用的是 Redis，一个支持原子操作和键过期（TTL）的高速内存存储。

来看一个用 Redis 实现固定窗口的简单例子。

  键：ratelimit:{user_id}:{当前分钟}
  1) INCR 键          -> 原子地把计数器加 1，并取得新值
  2) 若值为 1，则 EXPIRE 键 60   -> 设置 TTL，使该窗口过后自动删除
  3) 若值 > 100 则拒绝，否则允许

这里的关键在于原子性(atomicity)。如果"读取、比较、递增"这个过程被拆分成多个步骤，并发到来的请求之间就会产生竞态条件（race condition），从而超出限制。Redis 的 INCR 本身就是原子的，更复杂的逻辑（滑动窗口或令牌桶）则用 Lua 脚本把多条命令捆绑成一个原子单元来实现。Redis 会把 Lua 脚本作为单线程原子执行，因此可以避免竞态条件。

分布式限流还有一点需要考虑。如果每次请求都要访问共享存储，会带来延迟和负载，因此也有一些设计会牺牲一点精确性，改为在本地做近似统计并定期同步。精确性与性能之间的取舍，在这里同样会反复出现。

429 与 Retry-After — 如何恰当地传达拒绝

一旦限流器决定拒绝某个请求，就应该把这一点清楚地告诉客户端。用于此的是 HTTP 状态码 429 Too Many Requests。这个状态码以标准化的方式传达"你的请求次数太多了"这一含义。

仅仅发送 429 还不够。好的限流器还会一并告知客户端什么时候可以再次尝试。用于此的头部是 Retry-After，其值可以是以秒为单位的等待时间，也可以是一个具体的时刻。

HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json

{ "error": "rate limit exceeded", "retry_after": 30 }

许多 API 还会额外提供告知当前剩余配额的头部，例如 RateLimit-Limit（总配额）、RateLimit-Remaining（剩余次数）、RateLimit-Reset（距重置的剩余时间）。有了这些信息，客户端就能在真正撞墙之前提前调整速率。如果想了解 429 等状态码的确切含义，可以在HTTP 状态码图鉴中逐一查阅。

客户端的退避礼仪

限流不只是服务器一方的事。客户端在收到 429 后如何反应，对整个系统的健康状况也有很大影响。一收到 429 就立刻重试的客户端，只会让服务器更加难堪。

正确的做法是退避(backoff)，也就是让重试间隔逐渐拉长。

  • 指数退避(exponential backoff)：每次重试都把等待时间翻倍，1 秒、2 秒、4 秒、8 秒……这样可以给服务器留出恢复的时间。
  • 加入抖动(jitter)：如果多个客户端都以相同的间隔重试，这些重试就会同时涌入，再次冲击服务器，造成"惊群(thundering herd)"问题。因此需要在等待时间上加入一点随机性，把重试时刻分散开。
  • 尊重 Retry-After：如果服务器已经通过 Retry-After 告知了等待时间，礼貌的做法是优先遵循这个值，而不是按自己的计算行事。
  • 设置上限：设定最大重试次数或最大等待时间，避免无限重试下去。
  收到 429 时：
   等待时间 = min(基础值 * 2^重试次数, 上限) + 随机抖动
   若存在 Retry-After 头部，则优先采用其值

概括来说，设计良好的限流是服务器的拒绝与客户端的克制相互咬合而成的。服务器用 429 和 Retry-After 清晰地发出信号，客户端则用指数退避和抖动礼貌地退让。

结语

限流的目标很简单，统计请求数，但在实现上，围绕精确性、内存、突发处理这三条轴线存在多种取舍。固定窗口简单，却在边界处泄漏；滑动日志精确，却很沉重；滑动计数器则是两者之间的实用平衡。令牌桶优雅地允许突发，漏桶则让输出保持平滑。

除此之外，分布式环境需要 Redis 这样的共享存储与原子操作，客户端一侧则需要围绕 429 与 Retry-After 的礼貌退避。核心不在于"哪种算法才是正确的"，而在于"这个系统想要守护的是什么"。一旦确定了答案，该选择哪种工具自然也就水到渠成。

参考资料

현재 단락 (1/92)

限流(rate limiting)是指「在一定时间内限制所允许的请求数量」。乍一看像是让用户感到不便的机制，但实际上它是守护整个系统的安全装置。

작성 글자: 0자원문 글자: 5,238자작성 단락: 0/92