526互联

系统设计(架构师)指南4设计限速器

发布时间 2023-09-08 08:37:58作者: 磁石空杯

4 设计限速器

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

  • 用户每秒最多只能写2篇文章。

  • 同一IP地址每天最多只能创建10个账户。

  • 同一设备每周最多可申请5次奖励。

本章将要求您设计限速器。在开始设计之前，我们首先了解一下使用API限速器的好处：

  • 防止拒绝服务（DoS Denial of Service）攻击造成的资源枯竭。

几乎所有大型科技公司发布的API都会强制执行某种形式的速率限制。例如，Twitter将推文数量限制为每3小时 300条。Google docs API的默认限制如下：每个用户每60秒读取请求300次。限速器通过阻止多余的调用来防止有意或无意的DoS攻击。

  • 降低成本

限制过量请求意味着减少服务器数量，将更多资源分配给优先级高的API。对于使用付费第三方API的公司来说，速率限制极为重要。例如，以下外部应用程序接口按调用次数收费：检查信用、付款、检索健康记录等。限制调用次数对降低成本至关重要。

-防止服务器过载

为减少服务器负载，可使用限速器来过滤机器人或用户不当行为造成的多余请求。

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

速率限制可以使用不同的算法来实现，每种算法都有其优缺点。面试官和应聘者之间的互动有助于明确我们要构建的限速器类型。

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

面试官：问得好。我们的重点是服务器端API限速器。

候选人：限速器是根据IP、用户ID还是其他属性来限制API请求？

面试官：限速器应该足够灵活，以支持不同的节流规则。

应聘者：系统的规模有多大？是为初创公司还是拥有庞大用户群的大公司构建的？

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

应聘者：系统能否在分布式环境中运行？

面试官：可以。

应聘者：限速器是单独的服务，还是应该在应用程序代码中实现？

面试官：这取决于你的设计决定。

应聘者：我们需要通知被节流的用户吗？

面试官：需要。

要求

以下是系统要求的摘要：

  • 准确限制过多请求。
  • 低延迟。限速器不应减慢HTTP响应时间。
  • 使用尽可能少的内存。
  • 分布式速率限制。限速器可在多个服务器或进程中共享。
  • 异常处理。当用户的请求被节流时，向用户显示明确的异常。
  • 高容错性。如果限速器出现任何问题（例如，缓存服务器脱机），不会影响整个系统。

4.2 第2步 - 提出概要设计方案并获得支持

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

4.2.1 在哪里设置限速器？

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

  • 客户端

一般来说客户端是实施速率限制的不可靠的，因为客户端请求很容易被恶意行为者伪造。此外，我们可能无法控制客户端的实施。

  • 服务器端

假设我们的API允许每秒发出2个请求，而客户端在一秒钟内向服务器发送了3个请求。前两个请求被路由到API服务器。但是，限速器中间件会对第三个请求进行节流，并返回HTTP状态代码 429。HTTP429响应状态代码表示用户发送的请求过多。

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

速率限制器应该在哪里实施，是在服务器端还是在网关中？这个问题没有绝对的答案。这取决于贵公司当前的技术堆栈、工程资源、优先级、目标等。以下是几条一般指导原则：

评估当前的技术堆栈，如编程语言、缓存服务等。确保您当前的编程语言能够有效地在服务器端实施速率限制。

确定适合您业务需求的速率限制算法。在服务器端实施一切时，您可以完全控制算法。但是，如果使用第三方网关，您的选择可能会受到限制。

  • 如果您已经使用了微服务架构，并在设计中加入了API网关来执行身份验证、IP白名单等功能，您可以在API网关中添加速率限制器。

  • 创建自己的速率限制服务需要时间。如果没有足够的工程资源来实施速率限制器，商业API网关是更好的选择。

参考资料

4.2.2 限速算法

限速可以使用不同的算法来实现，每种算法都有明显的优缺点。尽管本章的重点不是算法，但从高层次了解这些算法有助于选择合适的算法或算法组合，以适应我们的使用情况。以下是常用算法的列表：

  • 令牌桶（Token bucket）
  • 泄漏桶（Leaking bucket）
  • 固定窗口计数器（Fixed window counter）
  • 滑动窗口日志（Sliding window log）
  • 滑动窗口计数器（Sliding window counter）

4.2.2.1 令牌桶算法

令牌桶算法广泛用于限速。它简单易懂，常用于互联网公司。亚马逊和都使用这种算法。

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

  • 令牌桶是一个具有预定容量的容器。令牌以预设的速率定期放入令牌桶。一旦桶满，就不再添加令牌。如图所示，令牌桶的容量为4，加油员每秒向桶中投入2枚令牌。一旦桶满，多余的代币就会溢出。

  • 每个请求消耗一个代币。当请求到达时，我们会检查桶中是否有足够的代币。
    • 如果有足够的令牌，我们会为每个请求取出令牌，然后请求通过。
    • 如果没有足够的令牌，请求就会被放弃。

令牌桶算法需要两个参数：

  • 令牌桶大小：令牌桶中允许的最大令牌数量

  • 填充率：每秒放入代币桶的代币数量

我们需要多少代币桶？这取决于限速规则。下面是几个例子。

  • 通常需要为不同的API端点设置不同的桶。例如，如果允许用户每秒发表1篇文章，每天添加150个好友，每秒喜欢5篇文章，那么每个用户需要3个桶。
  • 如果我们需要根据IP地址来限制请求，那么每个IP地址都需要一个桶。
  • 如果系统每秒最多允许 10,000 个请求，那么所有请求共享一个全局桶是合理的。

优点

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

缺点

  • 算法中的两个参数是代币桶大小和代币填充率。然而，对它们进行适当调整可能具有挑战性。

4.2.2.2 漏桶算法

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

  • 当请求到达时，系统会检查队列是否已满。如果队列未满，则将请求添加到队列中。
  • 否则，请求将被丢弃。
  • 从队列中取出请求，并定期进行处理。

泄漏桶算法需要以下两个参数：

  • 桶大小：等于队列大小。队列容纳以固定速率处理的请求。

  • 流出率：它定义了以固定速率（通常以秒为单位）处理的请求数量。

电子商务公司Shopify使用泄漏桶来限速。

优点

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

缺点

-突发流量会使队列中充满旧请求，如果不及时处理，最近的请求就会受到速率限制。
-算法中有两个参数。算法中有两个参数，可能不容易正确调整。

4.2.2.3 固定窗口计数器算法

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

  • 将时间线划分为固定大小的时间窗口，并为每个窗口分配一个计数器。

  • 每次请求都会使计数器递增1。

  • 一旦计数器达到预定义的阈值，新的请求就会被放弃，直到新的时间窗口开始。

下图中，时间单位为1秒，系统每秒最多允许3个请求。在每秒钟的窗口中，如果收到的请求超过3个，系统就会丢弃多余的请求。

这种算法的一个主要问题是，时间窗口边缘的突发流量可能会导致超过允许配额的请求通过。请考虑以下情况：

下图，系统每分钟最多允许5个请求，可用配额在人性化的整数分钟重置。如图所示，2:00:00至2:01:00之间有5个请求，2:01:00 至 2:02:00之间又有5个请求。在2:00:30和2:01:30之间的一分钟窗口中，有10个请求通过。这是允许请求数的两倍。

优点

-节省内存。
-易于理解。
-在单位时间窗口结束时重置可用配额，适合某些使用情况。

缺点

  • 窗口边缘的尖峰流量可能导致超过允许配额的请求通过。

4.2.2.4 滑动窗口日志算法

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

  • 该算法跟踪请求时间戳。时间戳数据通常保存在缓存中，如Redis的排序集。
  • 当有新请求时，删除所有过期的时间戳。过时的时间戳是指比当前时间窗口开始时间更早的时间戳。
  • 将新请求的时间戳添加到日志中。
    -如果日志大小与允许计数相同或更小，则接受请求。否则，请求将被拒绝。

在本例中，速率限制器允许每分钟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，因此请求被接受。

优点

  • 该算法实现的速率限制非常精确。在任何滚动窗口中，请求都不会超过速率限制。

缺点

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

4.2.2.5 滑动窗口计数器算法

滑动窗口计数器算法是一种混合方法，它结合了固定窗口计数器和滑动窗口日志。该算法可以通过两种不同的方法实现。我们将在本节中解释其中一种实现方法，并在本节末尾提供另一种实现方法的参考。下图展示了该算法的工作原理。

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

  • 当前窗口中的请求数 + 上一窗口中的请求数 * 滚动窗口与上一窗口的重叠百分比
  • 根据这一公式，我们得到 3 + 5 * 0.7% = 6.5 个请求。根据使用情况，该数字可以向上或向下舍入。在我们的例子中，四舍五入为6。

由于速率限制器每分钟最多允许7个请求，因此当前请求可以通过。不过，再收到一个请求后就会达到限制。

优点

  • 由于速率基于前一个窗口的平均速率，因此可以平滑流量峰值。
  • 节省内存。

缺点

  • 只适用于不太严格的回看窗口。它是实际速率的近似值，因为它假定前一个窗口中的请求是均匀分布的。不过，这个问题可能没有想象中那么严重。根据 Cloudflare 的实验，在 4 亿个请求中，只有 0.003% 的请求被错误地允许或限制了速率。

4.2.3 高层架构

我们需要一个计数器来跟踪来自同一用户、IP 地址等的请求数量。如果计数器大于限制，请求就会被禁止。

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

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

  • 客户端向限速中间件发送请求。
  • 限速中间件从Redis中相应的桶中获取计数器，并检查是否达到限制。
    • 如果达到限制，则拒绝请求。
    • 如果未达到限制，则将请求发送到API服务器。同时，系统会递增计数器并将其保存回Redis。

4.3 第3步 - 深入设计

上图中的高层设计没有回答以下问题：

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

4.3.1 限速规则

Lyft将其速率限制组件开源在https://github.com/lyft/ratelimit。我们将深入了解该组件，并举例说明一些速率限制规则：

domain: messaging

descriptors:

  - key: message_type

    Value: marketing

    rate_limit:

      unit: day

      requests_per_unit: 5

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

domain: auth

descriptors:

  - key: auth_type

    Value: login

    rate_limit:

      unit: minute

      requests_per_unit: 5

这条规则规定，1 分钟内客户端登录次数不得超过5次。规则一般写入配置文件并保存在磁盘上。

4.3.2 限速

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

4.3.3 速率限制器标头

客户端如何知道自己是否被节流？客户端又如何知道被节流前允许的剩余请求数？答案就在HTTP响应头中。速率限制器会向客户端返回以下HTTP头信息：

  • X-Ratelimit-Remaining：窗口内允许的剩余请求数。
  • X-Ratelimit-Limit：表示客户端在每个时间窗口内可进行的调用次数。
  • X-Ratelimit-Retry-After： 在不被节流的情况下再次发出请求前需要等待的秒数。

当用户发送的请求过多时，会向客户端返回429请求过多错误和X-Ratelimit-Retry-After头信息。

4.3.4 详细设计

  • 规则存储在磁盘上。工作站经常从磁盘中提取规则并将其存储到缓存中。
  • 当客户端向服务器发送请求时，请求会首先发送到限速器中间件。
  • 限速器中间件从缓存中加载规则。它从Redis缓存中获取计数器和上次请求的时间戳。根据响应，速率限制器决定
  • 如果请求不受速率限制，则将其转发给API服务器。
  • 如果请求有速率限制，速率限制器会向客户端返回429请求过多错误信息。同时，请求会被丢弃或转发到队列中。

4.3.5 分布式环境中的限速器

建立能在单服务器环境中运行的速率限制器并不困难。但是，将系统扩展到支持多台服务器和并发线程则是另一回事。这其中有两个难题：

  • 竞赛条件
  • 同步问题

如前所述，速率限制器的高级工作原理如下：

  • 从Redis读取计数器值。
  • 检查(counter + 1)是否超过阈值。
  • 如果没有，则将Redis中的计数器值递增 1。

在高并发环境中可能会出现竞赛条件。

假设Redis中的计数器值为3，如果两个请求同时读取计数器值，然后再写回计数器值，那么每个请求都会将计数器值递增 1，然后写回计数器值，而不会检查其他线程。两个请求（线程）都会认为自己的计数器值是 4。然而，正确的计数器值应该是5。

锁是解决竞赛条件最明显的方法。但是，加锁会大大降低系统运行速度。通常有两种策略可以解决这个问题：Lua脚本 和 Redis中的排序集数据结构。

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

一种可能的解决方案是使用粘性会话，允许客户端向同一个速率限制器发送流量。这种解决方案并不可取，因为它既不可扩展，也不灵活。更好的办法是使用Redis等集中式数据存储。

4.3.6 性能优化

性能优化是系统设计访谈中的一个常见话题。我们将从两个方面进行改进。

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

第二，使用最终一致性模型同步数据。

4.3.7 监控

设置速率限制器后，收集分析数据以检查速率限制器是否有效非常重要。首先，我们要确保

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

例如，如果速率限制规则过于严格，许多有效请求就会被丢弃。在这种情况下，我们希望稍微放宽规则。再比如，我们发现当流量突然增加（如闪购）时，我们的速率限制器就会失效。在这种情况下，我们可以更换算法来支持突发流量。令牌桶就是一个很好的选择。

4.4 步骤4 - 总结

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

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

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

  • 硬性与软性速率限制。

    • 硬性：请求数不能超过阈值。
    • 软：请求数可以在短时间内超过阈值。

  • 不同级别的速率限制。在本章中，我们只讨论了应用层（HTTP：第 7 层）的速率限制。也可以在其他层应用速率限制。例如，可以使用 Iptables （IP：第 3 层）按 IP 地址限制速率。

  • 避免速率受限。以最佳实践设计客户端：

  • 使用客户端缓存，避免频繁调用API。

  • 了解限制，不要在短时间内发送过多请求。

  • 包含捕获异常或错误的代码，以便客户端可以从容地从异常中恢复。

  • 为重试逻辑添加足够的后退时间。