四、设计速率限制器
在网络系统中，速率限制器用于控制客户端或服务发送流量的速率。在 HTTP 世界中，速率限制器限制了在特定时间段内允许发送的客户端请求的数量。如果 API 请求计数超过速率限制器定义的阈值，所有超出的调用都会被阻塞。下面举几个例子:
一个用户每秒最多只能写 2 篇文章。
您每天最多可以从同一个 IP 地址创建 10 个账户。
同一台设备每周可申领奖励不超过 5 次。
本章要求你设计一个限速器。在开始设计之前，我们首先来看看使用 API 速率限制器的好处:
防止拒绝服务(DoS)攻击造成的资源饥饿[1]。几乎所有大型科技公司发布的 API 都实施了某种形式的速率限制。例如，Twitter 将推文数量限制为每 3 小时 300 条[2]。Google docs APIs 有如下默认限制:每用户每 60 秒 300 个读取请求[3]。速率限制器通过阻止过量呼叫来防止有意或无意的 DoS 攻击。
降低成本。限制过多的请求意味着更少的服务器和分配更多的资源给高优先级的 API。速率限制对于使用付费第三方 API 的公司来说极其重要。例如，您需要为以下外部 API 的每次调用付费:检查信用、付款、检索健康记录等。限制通话次数对降低成本至关重要。
防止服务器过载。为了减少服务器负载，速率限制器用于过滤掉由机器人或用户不当行为引起的过量请求。
第一步——了解问题并确定设计范围
速率限制可以使用不同的算法来实现，每种算法都有其优缺点。面试官和候选人之间的互动有助于澄清我们试图建立的限速器的类型。
候选 : 我们要设计什么样的限速器？是客户端速率限制器还是服务器端 API 速率限制器？
采访者 :好问题。我们关注服务器端 API 速率限制器。
候选人 : 速率限制器是否基于 IP、用户 ID 或其他属性来限制 API 请求？
采访者 :限速器应该足够灵活，以支持不同的节流规则。
候选 : 系统的规模是多少？是为创业公司打造，还是为用户基数大的大公司打造？
面试官 :系统必须能够处理大量的请求。
候选 : 系统会在分布式环境下工作吗？
面试官 :是的。
候选 : 速率限制器是一个独立的服务还是应该在应用程序代码中实现？
采访者 :这是你的设计决定。
候选 : 我们需要通知被节流的用户吗？
面试官 :是的。
要求
以下是对系统要求的总结:
准确限制过分的要求。
低潜伏期。速率限制器不应该减慢 HTTP 响应时间。
尽量少用内存。
分布式限速。速率限制器可以在多个服务器或进程之间共享。
异常处理。当用户的请求被限制时，向用户显示明确的异常。
容错性高。如果速率限制器出现任何问题(例如，缓存服务器离线)，不会影响整个系统。
第二步——提出高水平的设计并获得认同
让我们保持简单，使用基本的客户端和服务器模型进行通信。
限速器放哪里？
直观地说，你可以在客户端或服务器端实现速率限制器。
客户端实现。一般来说，客户端是一个不可靠的实施速率限制的地方，因为客户端请求很容易被恶意参与者伪造。此外，我们可能无法控制客户端的实现。
服务器端实现。图 4-1 显示了放置在服务器端的速率限制器。
除了客户端和服务器端的实现，还有另一种方法。我们没有在 API 服务器上设置速率限制器，而是创建了一个速率限制器中间件，来抑制对 API 的请求，如图 4-2 所示。
让我们用图 4-3 中的例子来说明速率限制在这个设计中是如何工作的。假设我们的 API 允许每秒 2 个请求，一个客户机在一秒钟内向服务器发送 3 个请求。前两个请求被路由到 API 服务器。然而，速率限制器中间件抑制了第三个请求，并返回一个 HTTP 状态代码 429。HTTP 429 响应状态代码表示用户发送了太多请求。
云微服务[4]已经变得非常流行，速率限制通常在一个名为 API gateway 的组件中实现。API gateway 是一种完全托管的服务，支持速率限制、SSL 终止、身份验证、IP 白名单、静态内容服务等。现在，我们只需要知道 API 网关是一个支持速率限制的中间件。
在设计速率限制器时，我们要问自己的一个重要问题是:应该在哪里实现速率限制器，在服务器端还是在网关中？没有绝对的答案。这取决于您公司当前的技术堆栈、工程资源、优先级、目标等。这里有几个通用的准则:
评估你目前的技术栈，比如编程语言、缓存服务等。确保您当前的编程语言能够有效地在服务器端实现速率限制。
确定适合您业务需求的速率限制算法。当你在服务器端实现一切时，你就完全控制了算法。但是，如果您使用第三方网关，您的选择可能会受到限制。
如果你已经使用了微服务架构，并且在设计中包含了 API 网关来执行认证、IP 白名单等。，您可以向 API 网关添加速率限制器。
自建费率 限制服务需要时间。如果您没有足够的工程资源来实现速率限制器，商业 API 网关是一个更好的选择。
限速算法
速率限制可以使用不同的算法来实现，每种算法都有明显的优缺点。尽管本章并不关注算法，但从高层次理解它们有助于选择合适的算法或算法组合来适应我们的用例。下面是流行算法的列表:
令牌桶
漏桶
固定窗口计数器
滑动窗口日志
推拉窗计数器
令牌桶算法
令牌桶算法广泛用于速率限制。简单易懂，互联网公司常用。Amazon [5]和 Stripe [6]都使用这种算法来抑制他们的 API 请求。
令牌桶算法工作如下:
令牌桶是具有预定义容量的容器。令牌以预设的速率定期放入桶中。一旦桶满了，就不再添加令牌。如图 4-4 所示，令牌桶容量为 4。加油员每秒钟往桶里放 2 个代币。一旦桶满了，额外的代币就会溢出。
每个请求消耗一个令牌。当请求到达时，我们检查桶中是否有足够的令牌。图 4-5 解释了它是如何工作的。
如果有足够的令牌，我们为每个请求取出一个令牌，请求通过。
如果没有足够的令牌，请求被丢弃。
图 4-6 说明了代币消费、 、 和速率限制逻辑是如何工作的。在此示例中，令牌桶大小为 4，再填充速率为每 1 分钟 4 次。
令牌桶算法采用两个参数:
桶大小:桶中允许的最大令牌数
充值率:每秒钟投入桶中的代币数量
我们需要多少桶？这是不同的，它取决于限速规则。这里有几个例子。
对于不同的 API 端点，通常需要有不同的桶。例如，如果允许用户每秒发 1 篇帖子，每天添加 150 个朋友，每秒 5 篇帖子，则每个用户需要 3 个桶。
如果我们需要根据 IP 地址限制请求，每个 IP 地址都需要一个桶。
如果系统允许每秒最多 10，000 个请求，那么让所有请求共享一个全局桶是有意义的。
优点:
该算法易于实现。
记忆高效。
令牌桶允许短时间的流量爆发。只要还有令牌，请求就可以通过。
缺点:
算法中的两个参数是桶大小和令牌再填充率。然而，对它们进行适当的调优可能是一个挑战。
漏桶算法
泄漏桶算法类似于令牌桶，只是请求以固定速率处理。它通常用先进先出(FIFO)队列来实现。算法工作如下:
当请求到达时，系统检查队列是否已满。如果未满，请求将被添加到队列中。
否则，请求被放弃。
请求被从队列中取出并定期处理。
图 4-7 解释了算法的工作原理。
漏桶算法取以下两个参数:
桶大小:等于队列大小。该队列以固定的速率保存要处理的请求。
流出率:它定义了以固定的速率可以处理多少个请求，通常以秒为单位。
电子商务公司 Shopify 使用漏桶进行限速[7]。
优点:
给定有限队列大小的内存效率。
请求以固定速率处理，因此适用于需要稳定流出速率的用例。
缺点:
突发流量用旧请求填满队列，如果不及时处理，最近的请求将受到速率限制。
算法中有两个参数。正确地调整它们可能不容易。
固定窗口计数器算法
固定窗口计数器算法工作如下:
该算法将时间轴分为固定大小的时间窗口，并为每个窗口分配一个计数器。
每个请求都使计数器加 1。
一旦计数器达到预定义的阈值，新的请求就会被丢弃，直到新的时间窗口开始。
让我们用一个具体的例子来看看它是如何工作的。在图 4-8 中，时间单位是 1 秒，系统允许每秒最多 3 次请求。在每个第二个窗口中，如果收到 3 个以上的请求，多余的请求将被丢弃，如图 4-8 所示。
此算法的一个主要问题是，时间窗口边缘的流量突发可能会导致超过允许配额的请求通过。考虑以下情况:
在图 4-9 中，系统允许每分钟最多 5 个请求，可用配额在人性化的整数分钟重置。如图所示，在 2:00:00 和 2:01:00 之间有五个请求，在 2:01:00 和 2:02:00 之间还有五个请求。对于 2:00:30 到 2:01:30 之间的一分钟窗口，有 10 个请求通过。这是允许请求的两倍。
优点:
记忆高效。
通俗易懂。
在单位时间窗口结束时重置可用配额适合某些用例。
缺点:
窗口边缘的流量峰值可能会导致超过允许配额的请求通过。
滑动窗口日志算法
如前所述，固定窗口计数器算法有一个主要问题:它允许更多的请求在窗口边缘通过。滑动窗口日志算法解决了这个问题。其工作原理如下:
该算法跟踪请求时间戳。时间戳数据通常保存在缓存中，例如 Redis 的排序集[8]。
当一个新的请求进来时，删除所有过时的时间戳。过时的时间戳被定义为比当前时间窗口的开始时间更早的时间戳。
将新请求的时间戳添加到日志中。
如果日志大小等于或小于允许的计数，则接受请求。否则，它被拒绝。
我们用一个如图 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；因此，请求被接受。
优点:
该算法实现的速率限制非常精确。在任何滚动窗口中，请求都不会超过速率限制。
缺点:
该算法消耗大量内存，因为即使请求被拒绝，其时间戳仍可能存储在内存中。
滑动窗口计数器算法
滑动窗口计数器算法是一种结合了固定窗口计数器和滑动窗口日志的混合方法。该算法可以通过两种不同的方法来实现。我们将在本节中解释一个实现，并在本节的最后为另一个实现提供参考。图 4-11 说明了这种算法是如何工作的。
假设速率限制器每分钟最多允许 7 个请求，前一分钟有 5 个请求，当前分钟有 3 个请求。对于在当前分钟到达 30%位置的新请求，使用以下公式计算滚动窗口中的请求数:
请求当前窗口 + 请求前一窗口 * 滚动窗口与前一窗口的重叠百分比
利用这个公式，我们得到 3 + 5 * 0.7% = 6.5 的请求。根据使用情况，该数字可以向上或向下取整。在我们的例子中，它被向下舍入到 6。
由于速率限制器允许每分钟最多 7 个请求，当前请求可以通过。但是，在再收到一个请求后，将达到限制。
由于篇幅限制，我们在这里不讨论其他实现。感兴趣的读者应该参考参考资料[9]。这个算法并不完美。它有利有弊。
优点
它平滑流量峰值，因为速率是基于前一窗口的平均速率。
记忆高效。
缺点
只对不那么严格的回望窗有效。这是实际速率的近似值，因为它假设前一个窗口中的请求是均匀分布的。然而，这个问题可能没有看起来那么糟糕。根据 Cloudflare [10]所做的实验，在 4 亿个请求中，只有 0.003%的请求被错误地允许或速率受限。
高层建筑
速率限制算法的基本思想很简单。在高层，我们需要一个计数器来跟踪从同一个用户、IP 地址等发出了多少请求。如果计数器大于限制值，则不允许请求。
我们应该把柜台放在哪里？由于磁盘访问缓慢，使用数据库不是一个好主意。选择内存缓存是因为它速度快，并且支持基于时间的过期策略。例如，Redis [11]是实现利率限制的一个流行选项。它是一个内存存储，提供两个命令:INCR 和过期。
INCR:存储的计数器加 1。
到期:设置计数器超时。如果超时，计数器将自动删除。
图 4-12 显示了速率限制的高级架构，其工作原理如下:
客户端向限速中间件发送请求。
限速中间件从 Redis 中相应的桶中取出计数器，检查是否达到限额。
如果达到限制，请求被拒绝。
如果没有达到限制，请求被发送到 API 服务器。同时，系统递增计数器并将其保存回 Redis。
第三步——设计深潜
图 4-12 中的高层设计没有回答以下问题:
限速规则是如何创建的？规则存储在哪里？
如何处理速率受限的请求？
在本节中，我们将首先回答有关速率限制规则的问题，然后讨论处理速率限制请求的策略。最后，我们将讨论分布式环境中的速率限制、详细设计、性能优化和监控。
限速规则
Lyft 开源了他们的限速组件[12]。我们将查看组件内部，并查看一些速率限制规则的示例:
域 : 消息传递
描述符 :
--按键-:-消息 _ 类型
价值 :营销
利率 _ 限额 :
单位 : 日
请求 _ 每单位 : 5
在上述示例中，系统被配置为每天最多允许 5 条营销消息。下面是另一个例子:
域名 : 认证
描述符 :
--键-:-auth _ type
值 :登录
利率 _ 限额 :
单位 :分钟
请求 _ 每单位 : 5
该规则显示，客户端不允许在 1 分钟内登录 5 次以上。规则通常写在配置文件中并保存在磁盘上。
超过速率限制
如果请求是速率受限的，API 会向客户端返回一个 HTTP 响应代码 429(请求太多)。根据用例的不同，我们可能会将速率受限的请求排入队列，以便稍后处理。例如，如果一些订单由于系统过载而受到费率限制，我们可能会将这些订单留待以后处理。
限速器标题
客户端如何知道它是否被节流？客户端如何知道在被节流之前允许的剩余请求的数量？答案就在 HTTP 响应头中。速率限制器向客户端返回以下 HTTP 报头:
X-rate limit-Remaining:窗口内允许请求的剩余数量。
X-Ratelimit-Limit: 表示客户在每个时间窗口内可以拨打多少个电话。
X-rate limit-Retry-After:等待的秒数，直到可以再次发出请求而不被限制。
当用户发送过多请求时，向客户端返回 429 过多请求错误和X-rate limit-Retry-After报头。
详细设计
图 4-13 展示了系统的详细设计。
规则存储在磁盘上。工作人员经常从磁盘中提取规则，并将它们存储在缓存中。
当客户端向服务器发送请求时，请求首先被发送到限速器中间件。
限速器中间件从缓存中加载规则。它从 Redis 缓存中获取计数器和上次请求时间戳。基于该响应，速率限制器决定:
如果请求没有速率限制，则转发给 API 服务器。
如果请求是速率受限的，速率限制器向客户端返回 429 过多请求错误。与此同时，请求要么被丢弃，要么被转发到队列。
分布式环境中的限速器
构建一个在单一服务器环境中工作的速率限制器并不困难。然而，扩展系统以支持多个服务器和并发线程是另一回事。有两个挑战:
比赛条件
同步发布
比赛状态
如前所述，速率限制器在高层工作如下:
从 Redis 中读取 计数器 的值。
检查 ( 计数器+1)是否超过阈值。
如果不是，Redis 中的计数器值加 1。
如图 4-14 所示，竞争条件可能发生在高度并发的环境中。
假设 Redis 中的 计数器 的值为 3。如果两个请求同时读取 计数器 的值，在它们中的任何一个写回该值之前，每个请求都将把 计数器 加 1，并写回该值，而不检查另一个线程。两个请求(线程)都认为它们拥有正确的 计数器 值 4。然而，正确的 计数器的 值应该是 5。
锁是解决竞争状况的最明显的解决方案。但是，锁会显著降低系统速度。有两种策略常用来解决这个问题:Lua 脚本[13]和 Redis 中的有序集数据结构[8]。对这些策略感兴趣的读者，可以参考相应的参考资料[8] [13]。
同步发布
同步是分布式环境中需要考虑的另一个重要因素。为了支持数百万用户，一台限速服务器可能不足以处理流量。当使用多个速率限制器服务器时，需要同步。例如，在图 4-15 的左侧，客户端 1 向速率限制器 1 发送请求，客户端 2 向速率限制器 2 发送请求。由于 web 层是无状态的，客户端可以向不同的速率限制器发送请求，如图 4-15 右侧所示。如果没有同步发生，速率限制器 1 不包含关于客户端 2 的任何数据。因此，限速器不能正常工作。
一种可能的解决方案是使用粘性会话，允许客户端向同一个速率限制器发送流量。这种解决方案是不可取的，因为它既不可伸缩也不灵活。更好的方法是使用像 Redis 这样的集中式数据存储。设计如图 4-16 所示。
性能优化
性能优化是系统设计面试中的常见话题。我们将从两个方面进行改进。
首先，多数据中心设置对于速率限制器至关重要，因为对于远离数据中心的用户来说，延迟很高。大多数云服务提供商在世界各地建立了许多边缘服务器。例如，截至 20 20 年 5 月 20 日，Cloudflare 拥有 194 台地理位置分散的边缘服务器[14]。流量被自动路由到最近的边缘服务器，以减少延迟。
第二，用最终的一致性模型同步数据。如果您不清楚最终的一致性模型，请参考“第 6 章:设计键值存储”中的“一致性”一节
监控
实施限速器后，收集分析数据以检查限速器是否有效非常重要。首先，我们要确保:
限速算法有效。
限速规则有效。
例如，如果速率限制规则太严格，许多有效请求会被丢弃。在这种情况下，我们希望稍微放宽一些规则。在另一个例子中，我们注意到当流量突然增加时，如闪购，我们的限速器变得无效。在这种情况下，我们可以替换算法来支持突发流量。令牌桶很适合这里。
第四步——总结
在本章中，我们讨论了不同的速率限制算法及其优缺点。讨论的算法包括:
令牌桶
漏桶
固定窗口
滑动窗口日志
推拉窗计数器
然后，我们讨论了系统架构、分布式环境中的速率限制器、性能优化和监控。与任何系统设计面试问题类似，如果时间允许，您还可以提及其他话题:
硬 vs 软限速。
硬:请求数量不能超过阈值。
软:请求可以在短时间内超过阈值。
分级限速。在本章中，我们只讨论了应用层(HTTP:第 7 层)的速率限制。有可能在其他层应用速率限制。例如，您可以使用 Iptables [15] (IP:第 3 层)通过 IP 地址应用速率限制。注:开放系统互连模型(OSI 模型)有 7 层[16]:第 1 层:物理层，第 2 层:数据链路层，第 3 层:网络层，第 4 层:传输层，第 5 层:会话层，第 6 层:表示层，第 7 层:应用层。
避免被费率限制。用最佳实践设计您的客户端:
使用客户端缓存避免频繁的 API 调用。
了解限制，不要在短时间内发送太多请求。
包含捕捉异常或错误的代码，以便您的客户端能够从容地从异常中恢复。
添加足够的回退时间以重试逻辑。
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
【1】限速策略与技巧:https://cloud . Google . com/solutions/Rate-limiting-strategies-techniques
【3】谷歌文档使用限制:【https://developers.google.com/docs/api/limits】
[4] IBM 微服务:https://www.ibm.com/cloud/learn/microservices
[5]抑制 API 请求以提高吞吐量:
【7】Shopify REST Admin API 费率限制:https://help . Shopify . com/en/API/reference/REST-Admin-API-rate-limits
【8】Redis 排序集合更好的限速:https://engineering . classdojo . com/blog/2015/02/06/rolling-Rate-limiter/
【9】系统设计—速率限制器及数据建模:https://medium . com/@ saisandeepmopuri/System-Design-Rate-limiter-and-Data-modeling-9304 b0d 18250
[10]我们如何构建能够扩展到数百万个域的速率限制:https://blog . cloud flare . com/counting-things-a-lot-of-different-things/
[11] Redis 网站:https://redis.io/
[13]使用速率限制器扩展您的 API:https://gist . github . com/ptar Jan/e 38 f 45 F2 dfe 601419 ca 3 af 937 fff 574d #请求速率限制器
【14】什么是边缘计算:https://www . cloud flare . com/learning/server less/glossary/What-is-edge-computing/
【15】带 Iptables 的速率限制请求:https://blog . programster . org/Rate-Limit-Requests-with-Iptables
【16】OSI 模型:https://en.wikipedia.org/wiki/OSI_model#Layer_architecture
