流量控制原理及实现

March 14, 2025 · View on GitHub

1. 背景

1.1 本质（What）

一种通过限制系统处理请求数来应对超额流量的保护机制。

1.2 场景（Why）

1）系统的 CPU、内存、网络资源有限，如果没有对请求量进行限制，在面对超额突发流量时，很有可能耗尽系统资源导致服务不可用。

2）同时可以根据业务场景，以用户、调用服务等维度设置限流策略，从而避免单个来源占据大部分系统资源，确保系统稳定性。

1.3 手段（How）

1）放行一部分请求，另一部分请求直接失败（429 Too Many Requests）或排队重试。

2）不同业务场景限流面向的对象不同，对于数据清洗、流媒体等 IO 密集型系统，通常针对消息的字节长度进行限流，而对于 Web 服务，更多是针对调用数限流。

2. 限流算法原理

2.1 固定窗口计数器

2.1.1 工作原理

1）将时间轴划分为固定大小的窗口（period），设定每个窗口所允许通过的最大请求数（limit）。

2）每个窗口都有独立的计数器，每当有请求到达，计数器 + 1。

3）当窗口已通过请求数超过设定的最大请求数时，拒绝请求。

4）下图给出一个具体示例：

  • 窗口大小为 1 min。
  • 1 min 内最多允许通过 3 个请求。
  • period-2 已接收 3 个请求，后续请求被拒绝。

2.1.2 优点

1）算法简单：只需要维护当前窗口的计数器，不需要复杂的数据结构和算法，易于理解和实现。 2）内存友好：由于只需要记录当前窗口的计数器值，对内存的占用非常小。即使在高并发的场景下，也不会给系统带来太大的内存压力。 3）处理高效：算法的计算复杂度较低，处理请求的速度快。

2.1.3 缺点

1）流量整形效果较差，无法平滑一个窗口内的流量，应对流量毛刺的效果一般。

2）窗口边缘的突增流量可能导致限流配额超限，如下示例：

  • 每个窗口开始期间，限流配额重置。
  • 在 period-1 后半段，通过 3 个请求，消耗完本窗口的配额。
  • 在 period-2 前半段，通过 3 个请求，消耗完本窗口的配额。
  • period-1 后半段 / period-2 前半段组成的 1 min 窗口，一共通过 6 个请求，是配额的 2 倍。

2.2 滑动窗口

2.2.1 工作原理

1）维护一个跟随时间移动，大小为 period 的窗口，设定窗口所允许通过的最大请求数（limit）。

2）对加入请求及其请求时间戳进行记录，删除离开窗口的过期请求。

3）当滑动窗口记录的请求数超过设定的最大请求数时，拒绝请求。

4）下图给出一个具体示例：

  • 窗口大小为 1min，窗口目前滑动到 period-1、period-2 中间。
  • 滑动窗口内最多允许有 3 个请求。
  • 当前时刻，滑动窗口已记录请求时间为 00:00:34、00:00:41、00:01:20 三个请求；00:20 已离开窗口，需要删除。
  • 00:01:25 进入一个请求，超过阈值，拒绝请求。

2.2.2 优点

  • 相比与「固定窗口计数器」，能保证在任意窗口内请求流量不会超过设定的阈值。

2.2.3 缺点

  • 需要记录每一个请求及其对应的时间戳，消耗大量内存。
  • 存在处理窗口滑动、记录请求、删除过期请求等操作，性能比「固定窗口计数器」差。

2.2.4 折衷版本

结合固定窗口，将滑动窗口划分为两部分：

  • 处于当前固定窗口的部分：请求数量已知。
  • 处于「上一个」固定窗口的部分：假定请求匀速到达，根据滑动窗口处于该固定窗口的比例，即可推算出请求数量。

从而得到滑动窗口当前请求数（预测值）的计算公式：当前请求数 = 上一个固定窗口请求数 x 滑动窗口占上一个固定窗口的比例 + 当前固定窗口请求数。

下图给出一个具体示例：

  • 当前请求数 = 滑动窗口占上一个固定窗口的比例（50%）x 上一个固定窗口请求数（4）+ 当前固定窗口请求数（1）= 3。
  • 又来了一个请求，被拒绝。

优点：折衷版本优化了内存开销，无需保存请求时间。

缺点：当实际请求分布不均匀时，可能存在限流误判。比如上面的例子，如果上一个窗口的请求都发生在前半部分，即滑动窗口内实际请求数并未超限，但也触发了限流。

2.3 令牌桶

2.3.1 工作原理

1）维护一个装有若干令牌（Token）的桶，桶具有「最大令牌容量」，以及「令牌产生速率」。

2）令牌会以预设的速率定期放到桶中，令牌累积达到桶的最大令牌容量后无法继续产生。

3）每个请求会消耗一定数量的令牌，当请求到达时：

  • 桶里有足够的令牌，取出和请求数量一致的令牌，放行。
  • 没有足够的令牌，拒绝请求。

4）下图给出一个具体示例：

  • 初始化：桶最大令牌容量为 4，每秒产生 1 个令牌，假设瞬间（一秒内）先后发生 a、b、c。
  • a：到达 1 个请求，消耗 1 个令牌，桶里剩余 3 个。
  • b：到达 3 个请求，消耗 3 个令牌，桶里剩余 0 个。
  • c：到达 1 个请求，未到令牌补充时间，此时没有足够的令牌，请求拒绝。

2.3.2 优点

1）算法实现简单，以下过程可以通过简单的运算得出，无需专有的工作线程来定期补充令牌。

  • 维护「上一次补充令牌时间」「剩余令牌数」。
  • 每次尝试获取令牌之前，根据「当前」与「上一次补充令牌时间」的时间差，计算出当前「剩余令牌数」。

2）占用内存少。

3）能积累一定的令牌数，用于应对瞬时突发流量。

4）令牌产生速率可控，流量整形效果好。

2.3.3 缺点

1）「最大令牌容量」「令牌产生速率」参数具有一定的理解和调试成本。

2.4 漏桶

2.4.1 工作原理

1）漏桶是一个缓冲队列模型，将请求到达视为「注水」，请求处理视为「漏水」。 2）当某一段时间「注水」过快时，桶可以作为缓冲区，容纳一定的未处理请求，同时不断「漏水」以释放桶的可用空间。 3）当一段时间内「注水量」大于「漏水量」，桶可能被灌满，溢出的水便是拒绝的请求。

漏桶有两种实现方式：

  • As a queue：通过 FIFO（先进先出队列），以固定速率处理桶里的请求。

  • As a meter：「漏水」非匀速，在处理请求的同时计算漏水量，本次请求若导致水溢出则拒绝。

As a queue 通常需要借助分布式消息队列来实现固定速率漏水，这意味着需要有多个 Worker 来扮演生产者 / 消费者。

throttled-py 更希望提供轻量、无额外服务进程 / 线程的限流功能，故基于「As a meter」实现漏桶算法，下文将介绍实现原理：

1）维护一个初始状态为空的桶，桶具有「最大令牌容量」，以及「令牌丢弃速率」。

2）令牌会以预设的速率定期被丢弃。

3）每个请求会往桶里放一个令牌，当请求到达时：

  • 根据当前时间及上一次请求时间，计算需要被丢弃的令牌数，更新剩余令牌数。
  • 当前请求放入桶中，不会导致桶溢出，请求放行。
  • 桶溢出，拒绝请求。

4）下图给出一个具体示例：

  • 当前状态：桶最大令牌容量为 4，每秒丢弃 1 个令牌，目前桶内有 2 个令牌，已丢弃 1 个令牌，假设「间隔 1 秒」先后发生 a、b、c。
  • a（时间：00:00）：到达 1 个请求，请求加入后没有溢出（1 + 2 = 3 <= 4），加入后桶里剩余 3 个 Token。
  • b（时间：00:01）：
    • 距离 a 已过去 1 秒，需要丢弃 1 个令牌，剩 2 个 Token（3 - 1 x 1 = 2）。
    • 到达 2 个请求，请求加入后没有溢出（2 + 2 <= 4），加入后桶里剩余 4 个 Token。
  • c（时间：00:02）：
    • 距离 b 已过去 1 秒，需要丢弃 1 个令牌，剩 3 个 Token（4 - 1 x 1 = 3）。
    • 到达 2 个请求，请求加入后桶会溢出（3 + 2 > 4），拒绝请求。

2.4.2 优点

1）「As a meter」是令牌桶算法的镜像实现，两者在限流效果上几乎等价，拥有令牌桶的所有优点。

2.4.3 缺点

1）「As a meter」相比于「As a queue」，缺少固定速率处理请求的能力，不适用于需要严格控制请求速率的场景。

2）「As a queue」需要额外的工作进程来回调业务请求以实现「漏水」，这意味着需要时刻确保进程存活，否则可能会因为桶溢出，导致请求被错误限流。

2.5 GCRA

通用信元限流算法（GCRA） 是一种漏桶算法变体，旨在提供一种无需额外「漏水」工作进程的稳定算法。

2.5.1 工作原理

GCRA 和令牌桶算法非常相似，按一定的速率填充令牌，通过维护 tat（理论到达时间），来判断某次请求是否超限。

1）GCRA 有以下概念：

  • T：令牌填充间隔，填充 1 个令牌所需时间（假设每分钟填充 60 个 Token，则 T = 60 / 60 = 1 s）。
  • bt：排放间隔，将桶填满所需时间，（假设桶的容量为 10，T = 1，则 bt = 10 / T = 10 s）。
  • last_tat：上一次理论到达时间，处理完上一次请求后，所处的理论到达时间（tat）。
  • tat：理论到达时间，在不考虑桶具有缓存容量的情况下，准备好应对某个请求所消耗令牌的时间点。
    • 假设某次请求需消耗 cost 个令牌，填充令牌耗时 = T x cost。
    • 基于上一次的理论到达时间，推算当前 tat，可得：tat = last_tat + T x cost。
  • allow_at：实际到达时间（实际准备好令牌的时间）。
    • 桶具有一定容量以应对突发流量，相当于已经花费 bt 提前准备好了一些令牌，相当于 tat 可以提前，即 allow_at = tat - bt。

2）a、b 为请求允许通过的情况：

  • now >= allow_at，说明此时令牌已经准备好，请求允许放行。

  • 放行请求需要消耗令牌，需要更新 tat 为 tat = last_tat + T x cost。

3）c 为限流的情况：now < allow_at，令牌还需要耗费 allow_at - now 才能准备好，触发限流。

2.5.2 优点

1）内存友好：只需维护 tat（理论到达时间），对内存的占用非常小。

2）算法高效：计算复杂度较低，处理请求的速度快。

3）在相同限流效果下，GCRA 有着比「令牌桶算法」更优的性能，后者需同时维护「上一次补充令牌时间」「剩余令牌数」。

3. 限流算法实现

todo...

4. 限流算法对比

todo...

last. Reference