第四章：设计一个限流器 (Design A Rate Limiter)

在网络系统中，速率限制器用于控制客户端或服务发送的流量速率。在HTTP世界中，速率限制器限制在特定时间段内允许客户端发送的请求数量。如果API请求数量超过速率限制器定义的阈值，所有超出的请求将被阻止。以下是几个示例：

用户每秒最多可以发表2篇帖子。
同一IP地址每天最多可以创建10个账户。
同一设备每周最多可以领取5次奖励。

在本章中，要求你设计一个速率限制器。在开始设计之前，我们先来看看使用API速率限制器的好处：

防止因拒绝服务（DoS）攻击 [1] 导致的资源耗尽。几乎所有大型科技公司发布的API都会实施某种形式的速率限制。例如，Twitter限制每3小时最多发300条推文 [2]。Google Docs API的默认限制为：每用户每60秒最多300次读取请求 [3]。速率限制器通过阻止超出请求，防止有意或无意的DoS攻击。
降低成本。限制过多的请求意味着需要的服务器更少，并且可以为高优先级API分配更多资源。对于使用付费第三方API的公司，速率限制至关重要。例如，对于以下外部API，您按每次调用付费：信用检查、支付、健康记录查询等。限制调用次数对于降低成本至关重要。
防止服务器过载。为了减少服务器负载，速率限制器用于过滤掉由机器人或用户不当行为导致的多余请求。

第 1 步 - 理解问题并确定设计范围

速率限制可以通过不同的算法实现，每种算法都有其优缺点。面试官和候选人之间的互动有助于澄清我们要构建的速率限制器的类型。

候选人：我们要设计哪种速率限制器？是客户端的速率限制器还是服务端API速率限制器？

面试官：好问题。我们重点关注服务端API速率限制器。

候选人：这个速率限制器是基于IP、用户ID还是其他属性来限制API请求？

面试官：速率限制器需要足够灵活，能够支持不同的限制规则。

候选人：系统的规模如何？是为初创公司构建，还是为拥有大量用户的大公司构建？

面试官：系统必须能够处理大量请求。

候选人：系统会在分布式环境中运行吗？

面试官：是的。

候选人：速率限制器是一个独立的服务，还是应该在应用代码中实现？

面试官：这是一个设计决策，由你来决定。

候选人：我们需要通知被限制的用户吗？

面试官：是的。

需求总结

以下是该系统的需求总结：

准确限制过多请求：系统必须有效地限制超出预期的请求量。
低延迟：速率限制器不应显著增加HTTP响应时间。
内存占用低：系统应尽可能减少内存使用。
分布式速率限制：速率限制器应该可以跨多个服务器或进程共享。
异常处理：在请求被限制时，向用户显示清晰的异常信息。
高容错性：如果速率限制器出现问题（例如缓存服务器离线），不会影响整个系统的正常运行。

理解这些要求是系统设计的第一步，确保设计的系统满足实际业务需求并具有良好的性能表现。

第 2 步 - 提出高层设计并获得认同

让我们保持简单，使用基本的客户端和服务器模型进行通信。

限流器应该放在哪里？

直观地说，限流器可以在客户端或服务器端实现。

客户端实现。一般而言，客户端是执行限流控制的不可靠场所，因为客户端请求可以很容易被恶意行为者伪造。此外，我们可能无法控制客户端的实现。
服务器端实现。图 4-1 显示了一个放置在服务器端的限流器

图4-1

除了客户端和服务器端的实现，还有另一种方法。我们可以创建一个限流器中间件，而不是将其放置在 API 服务器上，如图 4-2 所示，该中间件会对发送到 API 的请求进行限流。

图4-2

让我们使用图 4-3 中的示例来说明这种设计中的限流是如何工作的。假设我们的 API 允许每秒 2 次请求，而客户端在一秒钟内发送了 3 个请求。前两个请求被路由到 API 服务器。然而，限流中间件会限制第三个请求，并返回 HTTP 状态码 429。HTTP 429 响应状态码表示用户已发送过多请求。

图4-3

云微服务 [4] 已经变得非常流行，速率限制通常在一个叫做 API 网关的组件中实现。API 网关是一个完全托管的服务，支持速率限制、SSL 终止、身份验证、IP 白名单、服务静态内容等。目前，我们只需要知道 API 网关是一个支持速率限制的中间件。

在设计速率限制器时，一个重要的问题是：速率限制器应该在服务器端还是在网关中实现？没有绝对的答案。这取决于您公司当前的技术栈、工程资源、优先级、目标等。以下是一些一般性指导原则：

评估您当前的技术栈，例如编程语言、缓存服务等。确保您当前的编程语言在服务器端实现速率限制时效率较高。
确定符合您业务需求的速率限制算法。当您在服务器端实现所有内容时，您可以完全控制算法。然而，如果您使用第三方网关，您的选择可能会受到限制。
如果您已经使用了微服务架构并在设计中包含了 API 网关以执行身份验证、IP 白名单等，您可以在 API 网关中添加速率限制器。
构建您自己的速率限制服务需要时间。如果您没有足够的工程资源来实现速率限制器，那么商业 API 网关是更好的选择。

限流算法 (Algorithms for rate limiting)

限流可以通过不同的算法来实现，每种算法都有其优点和缺点。尽管本章并不主要讨论算法，但理解它们的高层次概念有助于选择合适的算法或算法组合，以满足我们的使用场景需求。以下是一些常见的限流算法：

令牌桶（Token Bucket）
漏桶（Leaking Bucket）
固定窗口计数器（Fixed Window Counter）
滑动窗口日志（Sliding Window Log）
滑动窗口计数器（Sliding Window Counter）

令牌桶算法 (Token bucket algorithm)

令牌桶算法是限流中广泛使用的算法之一。它简单易懂，并且被互联网公司广泛应用。Amazon [5] 和 Stripe [6] 都使用该算法来限制其 API 请求。

令牌桶算法的工作原理如下：

令牌桶是一个具有预定义容量的容器。令牌按照预设的速率周期性地放入桶中。当桶满时，不再添加更多的令牌。如图 4-4 所示，令牌桶的容量为4。每秒填充器向桶中加入2个令牌。当桶满后，额外的令牌将会溢出。

图4-4

每个请求消耗一个令牌。当一个请求到达时，我们会检查桶中是否有足够的令牌。图 4-5 解释了其工作原理。
如果有足够的令牌，我们从桶中取出一个令牌，允许该请求通过。
如果没有足够的令牌，则该请求将被丢弃。

图4-5

图 4-6 说明了令牌的消耗、填充以及限流逻辑的工作方式。在这个例子中，令牌桶的容量为 4，填充速率为每分钟 4 个。

图4-6

令牌桶算法有两个参数：

桶的大小：桶内允许的最大令牌数量
填充速率：每秒放入桶中的令牌数量

我们需要多少个桶？这个数量取决于限流规则。以下是一些示例：

通常对于不同的 API 端点需要不同的桶。例如，如果用户每秒允许发布 1 篇帖子、每天添加 150 个朋友、每秒点赞 5 次，则每个用户需要 3 个桶。
如果需要根据 IP 地址进行限流，那么每个 IP 地址需要一个桶。
如果系统允许每秒最多 10,000 次请求，使用一个共享的全局桶来处理所有请求可能是合理的。

优点：

算法易于实现。
内存使用效率高。
令牌桶允许短时间内的突发流量。只要桶内有令牌，请求就可以通过。

缺点：

算法中的两个参数是桶的大小和令牌的填充速率。然而，正确调整这两个参数可能具有挑战性。

漏桶算法 (Leaking bucket algorithm)

漏桶算法与令牌桶类似，但请求的处理速率是固定的。它通常使用先进先出（FIFO）队列实现。算法的工作原理如下：

当请求到达时，系统检查队列是否已满。如果未满，请求被加入队列。
如果队列已满，请求将被丢弃。
请求以固定的时间间隔从队列中拉取并处理。

图 4-7 解释了该算法的工作原理。

图4-7

漏桶算法使用以下两个参数：

桶的大小：等同于队列的大小。队列用于存放将以固定速率处理的请求。
流出速率：定义可以以固定速率处理的请求数量，通常以秒为单位。

例如，电子商务公司 Shopify 使用漏桶算法来进行限流[7]。

优点：

由于队列大小有限，内存使用效率高。
请求以固定速率处理，因此适用于需要稳定输出速率的用例。

缺点：

突发流量会填满队列，使旧请求堆积，如果未及时处理，最近的请求将会被限流。
算法中有两个参数，调优可能不容易。

固定窗口计数器算法 (Fixed window counter algorithm)

固定窗口计数器算法的工作原理如下：

算法将时间线划分为固定大小的时间窗口，并为每个窗口分配一个计数器。
每个请求使计数器加 1。
一旦计数器达到预定义的阈值，新的请求将在当前窗口结束前被丢弃，直到新的时间窗口开始。

我们通过一个具体的例子来解释其工作原理。在图 4-8 中，时间单位为 1 秒，系统每秒最多允许 3 个请求。在每一个 1 秒的窗口中，如果收到超过 3 个请求，多余的请求将被丢弃，如图 4-8 所示。

图4-8

该算法的一个主要问题是，在时间窗口边缘出现的流量突发可能会导致通过的请求数量超过允许的配额。举个例子：

图4-9

在图 4-9 中，系统允许每分钟最多 5 个请求，且可用配额在每个整分钟时重置。如图所示，在 2:00:00 和 2:01:00 之间有 5 个请求，在 2:01:00 和 2:02:00 之间又有 5 个请求。在 2:00:30 到 2:01:30 的 1 分钟窗口内，有 10 个请求通过。这是允许请求的两倍。

优点：

内存高效。
容易理解。
在单位时间窗口结束时重置可用配额适合某些使用场景。

缺点：

在窗口边缘的流量激增可能导致超过允许配额的请求通过。

滑动窗口日志算法 (Sliding window log algorithm)

如前所述，固定窗口计数算法存在一个主要问题：它在窗口边缘允许更多请求通过。滑动窗口日志算法解决了这一问题，其工作原理如下：

算法会跟踪请求的时间戳。时间戳数据通常存储在缓存中，例如 Redis 的有序集合[8]。
当一个新请求到达时，移除所有过期的时间戳。过期的时间戳定义为早于当前时间窗口开始时间的记录。
将新请求的时间戳添加到日志中。
如果日志的大小等于或小于允许的请求数量，则接受该请求。否则，拒绝该请求。

我们用图 4-10 中的一个例子来解释该算法的工作原理。

图4-10

在这个例子中，速率限制器允许每分钟 2 个请求。通常情况下，Linux 时间戳会存储在日志中。然而，为了更好地可读性，我们的示例中使用了人类可读的时间表示。

当新的请求在 1:00:01 到达时，日志为空，因此该请求被允许。
在 1:00:30 时，新请求到达，时间戳 1:00:30 被插入到日志中。插入后，日志大小为 2，不超过允许的数量。因此，该请求被允许。
在 1:00:50 时，新请求到达，时间戳被插入到日志中。插入后，日志大小为 3，超过允许的大小 2。因此，这个请求被拒绝，尽管时间戳仍然保留在日志中。
在 1:01:40 时，新请求到达。在最新的时间范围内，范围 [1:00:40, 1:01:40) 的请求是有效的，但在 1:00:40 之前发送的请求是过期的。两个过期的时间戳 1:00:01 和 1:00:30 从日志中移除。经过移除操作后，日志大小变为 2，因此该请求被接受。

优点：

通过该算法实现的速率限制非常准确。在任何滑动窗口内，请求不会超过速率限制。

缺点：

该算法消耗大量内存，因为即使请求被拒绝，其时间戳仍可能存储在内存中。

滑动窗口计数算法 (Sliding window counter algorithm)

滑动窗口计数算法是一种混合方法，它结合了固定窗口计数和滑动窗口日志。该算法可以通过两种不同的方法来实现。本节将解释一种实现方式，并在本节结束时提供另一种实现的参考。图 4-11 说明了该算法的工作原理。

图4-11

假设速率限制器允许每分钟最多 7 个请求，在上一个分钟内有 5 个请求，而在当前分钟内有 3 个请求。对于在当前分钟的 30% 位置到达的新请求，滚动窗口中的请求数量通过以下公式计算：

当前窗口中的请求 + 上一个窗口中的请求 * 滚动窗口与上一个窗口的重叠百分比

使用这个公式，我们得到 3 + 5 x 0.7 = 6.5 个请求。根据具体用例，这个数字可以向上或向下舍入。在我们的示例中，向下舍入为 6。由于速率限制器允许每分钟最多 7 个请求，因此当前请求可以通过。然而，在接收到一个额外请求后，限制将会达到。

由于空间限制，这里不讨论其他实现。有兴趣的读者可以参考参考文献 [9]。这个算法并不完美，具有优缺点。

优点

由于速率基于上一个窗口的平均速率，它能够平滑流量峰值。
内存高效。

缺点

仅适用于不那么严格的回溯窗口。它是实际速率的一个近似值，因为它假设上一个窗口中的请求是均匀分布的。然而，这个问题可能没有看起来那么严重。根据 Cloudflare [10] 的实验，在 4 亿个请求中，只有 0.003% 的请求被错误地允许或被限速。

高层架构 (High-level architecture)

速率限制算法的基本思想很简单。从高层次来看，我们需要一个计数器来跟踪来自同一用户、IP 地址等的请求数量。如果计数器的值大于限制，则请求被拒绝。

我们应该将计数器存储在哪里？使用数据库并不是一个好的主意，因为磁盘访问速度较慢。选择内存缓存是因为它速度快且支持基于时间的过期策略。例如，Redis [11] 是一个实现速率限制的流行选项。它是一个内存存储，提供两个命令：INCR 和 EXPIRE。

INCR：将存储的计数器增加 1。
EXPIRE：为计数器设置超时。如果超时到期，计数器会自动删除。

图 4-12 显示了速率限制的高层架构，其工作原理如下：

图4-12

客户端向速率限制中间件发送请求。
速率限制中间件从 Redis 中相应的桶中获取计数器，并检查是否达到了限制。
如果达到了限制，请求被拒绝。
如果没有达到限制，请求将发送到 API 服务器。与此同时，系统增加计数器并将其保存回 Redis。

第 3 步 - 深入设计

高层设计在图 4-12 中并没有回答以下问题：

如何创建速率限制规则？规则存储在哪里？
如何处理被速率限制的请求？

在本节中，我们将首先回答有关速率限制规则的问题，然后讨论处理被速率限制请求的策略。最后，我们将讨论在分布式环境中的速率限制、详细设计、性能优化和监控。

速率限制规则

Lyft 开源了他们的速率限制组件[12]。我们将深入了解该组件并查看一些速率限制规则的示例：

yaml

domain: messaging
descriptors:
  - key: message_type
    value: marketing
rate_limit:
  unit: day
  requests_per_unit: 5

在上述示例中，系统配置为每天最多允许发送 5 条营销消息。以下是另一个示例：

yaml

domain: auth
descriptors:
  - key: auth_type
    value: login
rate_limit:
  unit: minute
  requests_per_unit: 5

该规则表明客户端在一分钟内不能登录超过 5 次。规则通常写在配置文件中并保存在磁盘上。

超过速率限制

如果请求被速率限制，API 会向客户端返回 HTTP 响应代码 429（请求过多）。根据用例，我们可以将被速率限制的请求放入队列以便稍后处理。例如，如果由于系统过载而限制了一些订单，我们可以将这些订单保留，以便稍后处理。

速率限制器头部

客户端如何知道它是否正在被限流？以及客户端如何知道在被限流之前还剩下多少个允许的请求？答案在于 HTTP 响应头。速率限制器会向客户端返回以下 HTTP 头部：

X-Ratelimit-Remaining：在窗口内允许的剩余请求数量。
X-Ratelimit-Limit：指示客户端在每个时间窗口内可以进行多少次调用。
X-Ratelimit-Retry-After：在被限流之前，需要等待多少秒才能再次发起请求。

当用户发送了过多请求时，系统会返回 429（请求过多）错误以及 X-Ratelimit-Retry-After 头部。

详细设计

图 4-13 展示了系统的详细设计。

图4-13

规则存储在磁盘上。工作节点频繁从磁盘中拉取规则，并将其存储在缓存中。
当客户端向服务器发送请求时，请求首先会被发送到速率限制中间件。
速率限制中间件从缓存中加载规则，并从Redis缓存中获取计数器和上次请求的时间戳。根据响应，速率限制器决定：
- 如果请求没有被速率限制，则将其转发给API服务器。
- 如果请求被速率限制，速率限制器将向客户端返回429请求过多的错误。同时，请求要么被丢弃，要么被转发到队列中。

分布式环境中的速率限制器

在单服务器环境中构建一个速率限制器并不困难。然而，将系统扩展以支持多个服务器和并发线程则是另一回事。这里有两个挑战：

竞争条件
同步问题

竞争条件

如前所述，速率限制器的高层工作方式如下：

从Redis读取计数器值。
检查 (计数器 + 1) 是否超过阈值。
如果没有，将计数器值在Redis中加1。

在高度并发的环境中，可能会发生竞争条件，如图4-14所示。

图4-14

假设Redis中的计数器值为3。如果两个请求并发地在任何一个请求写回值之前读取计数器值，则每个请求将计数器加一并写回，而不检查其他线程。两个请求（线程）都认为自己拥有正确的计数器值4。然而，正确的计数器值应该是5。

锁是解决竞争条件的最明显的解决方案。然而，使用锁会显著减慢系统速度。为了解决这个问题，通常使用两种策略：Lua脚本 [13] 和Redis [8] 中的有序集合数据结构。对于对这些策略感兴趣的读者，可以参考相关的参考材料 [8] [13]。

同步问题

在分布式环境中，同步是另一个重要的考虑因素。为了支持数百万用户，一个速率限制器服务器可能不足以处理流量。当使用多个速率限制器服务器时，就需要进行同步。例如，在图4-15的左侧，客户端1向速率限制器1发送请求，而客户端2向速率限制器2发送请求。由于Web层是无状态的，客户端可以像图4-15右侧所示，向不同的速率限制器发送请求。如果没有发生同步，速率限制器1将不会包含有关客户端2的任何数据。因此，速率限制器无法正常工作。

图4-15

一种可能的解决方案是使用粘性会话，允许客户端将流量发送到同一个速率限制器。然而，这种解决方案并不推荐，因为它既不具备可扩展性，也不够灵活。更好的方法是使用像Redis这样的集中式数据存储。该设计如图4-16所示。

图4-16

性能优化

性能优化是系统设计面试中的一个常见话题。我们将讨论两个改进的领域。

首先，多数据中心设置对速率限制器至关重要，因为对于位于数据中心远处的用户，延迟较高。大多数云服务提供商在全球范围内建立了许多边缘服务器位置。例如，截至2020年5月20日，Cloudflare拥有194个地理分布的边缘服务器 [14]。流量会自动路由到最近的边缘服务器，以减少延迟。

图4-17

其次，使用最终一致性模型来同步数据。如果你不清楚最终一致性模型，请参考《第6章：设计一个键值存储》中的“一致性”部分。

监控

在实施速率限制器之后，收集分析数据以检查速率限制器的有效性是很重要的。我们主要希望确保：

速率限制算法是有效的。
速率限制规则是有效的。

例如，如果速率限制规则过于严格，许多有效请求会被丢弃。在这种情况下，我们希望稍微放宽规则。另一个例子是，当流量突然增加（例如闪购）时，我们注意到速率限制器变得无效。在这种情况下，我们可以更换算法以支持突发流量。令牌桶算法在这里是一个不错的选择。

第 4 步 - 总结

在本章中，我们讨论了不同的速率限制算法及其优缺点。讨论的算法包括：

令牌桶
漏桶
固定窗口
滑动窗口日志
滑动窗口计数器

接着，我们讨论了系统架构、分布式环境中的速率限制器、性能优化和监控。与任何系统设计面试问题类似，如果时间允许，还有一些额外的讨论点可以提到：

硬速率限制 vs 软速率限制：
- 硬速率限制：请求数量不能超过阈值。
- 软速率限制：请求可以在短时间内超过阈值。
不同层级的速率限制。在本章中，我们只讨论了应用层（HTTP：第7层）的速率限制。实际上，可以在其他层应用速率限制。例如，可以使用Iptables [15] 基于IP地址进行速率限制（IP：第3层）。
注：开放系统互连模型（OSI模型）有7层 [16]：第1层：物理层，第2层：数据链路层，第3层：网络层，第4层：传输层，第5层：会话层，第6层：表示层，第7层：应用层。
避免被速率限制。通过最佳实践设计客户端：
- 使用客户端缓存，避免频繁调用API。
- 了解限制，不要在短时间内发送过多请求。
- 包含捕获异常或错误的代码，以便客户端能够从异常中平稳恢复。
- 在重试逻辑中增加足够的退避时间。