关于后端:如何设计一个速率限制器令牌桶漏桶固定窗口滑动窗口

在网络系统中，速率限制器被用来管制客户端或服务发送的流量的速率。在 HTTP 畛域，速率限制器限度了在指定周期内容许发送的客户端申请的数量。如果 API 申请的数量超过了速率限制器定义的阈值，所有超出的调用都会被阻止。以下是一些示例：

• 用户每秒钟最多只能公布 2 篇帖子。
• 你能够每天最多从同一 IP 地址创立 10 个帐户。
• 你能够每周最多从同一设施支付 5 次处分。

欢送关注我的公众号：更 AI。第一工夫理解前沿行业音讯、分享深度技术干货、获取优质学习资源

在这一章中，你被要求设计一个速率限制器。在开始设计之前，咱们首先看一下应用 API 速率限制器的益处：

• 避免由拒绝服务（DoS）攻打 [1] 引起的资源耗尽。简直所有大型科技公司公布的 API 都执行一些模式的速率限度。例如，Twitter 限度每 3 小时的推文数量为 300 条[2]。Google 文档的 API 默认限度为：对于读取申请，每个用户每 60 秒 300 个[3]。速率限制器通过阻止适量的调用来避免 DoS 攻打，无论是无意还是无心的。
• 缩小老本。限度适量的申请意味着更少的服务器和将更多的资源分配给高优先级的 API。对于应用付费第三方 API 的公司来说，速率限度极其重要。例如，你按次免费的内部 API 包含：查看信用，进行领取，获取衰弱记录等。限度调用次数是缩小老本的要害。
• 避免服务器过载。为了缩小服务器负载，速率限制器被用来过滤由机器人或用户的不当行为引起的适量申请。

第一步 – 了解问题并确定设计范畴

速率限度能够通过不同的算法来实现，每种算法都有其长处和毛病。面试官和面试者之间的交换有助于廓清咱们试图构建的速率限制器的类型。

面试者 ：咱们要设计的是哪种类型的速率限制器？是客户端速率限制器还是服务器端 API 速率限制器？
面试官：好问题。咱们关注的是服务器端的 API 速率限制器。

面试者 ：速率限制器是基于 IP、用户 ID 还是其余属性来对 API 申请进行限流的？
面试官：速率限制器应该足够灵便，能反对不同的限流规定。

面试者 ：零碎的规模如何？是为初创公司构建的，还是为领有大量用户根底的大公司构建的？
面试官：零碎必须能解决大量的申请。

面试者 ：零碎会在分布式环境下工作吗？
面试官：是的。

面试者 ：速率限制器是一个独自的服务，还是应该在利用程序代码中实现？
面试官：这是由你来决定的设计决策。

面试者 ：咱们须要告诉被限流的用户吗？
面试官：是的。

需要

以下是零碎的需要摘要：

• 精确地限度适量的申请。
• 低提早。速率限制器不应升高 HTTP 响应工夫。
• 尽可能少地应用内存。
• 分布式速率限度。速率限制器能够在多个服务器或过程之间共享。
• 异样解决。当用户的申请被限流时，向用户显示清晰的异样。
• 高容错性。如果速率限制器呈现任何问题（例如，缓存服务器离线），它不会影响整个零碎。

第二步 – 提出高层次设计并取得认可

让咱们放弃简略，应用根本的客户端和服务器模型进行通信。

应该在哪里搁置速率限制器？

直观地说，你能够在客户端或服务器端实现速率限制器。

• 客户端实现。一般来说，客户端是施行速率限度的不牢靠中央，因为歹意参与者能够轻易地伪造客户端申请。此外，咱们可能无法控制客户端的实现。
• 服务器端实现。图 4-1 显示了搁置在服务器端的速率限制器。

除了客户端和服务器端的实现，还有另一种形式。咱们不是在 API 服务器上搁置速率限制器，而是创立一个速率限度中间件，如图 4-2 所示，对你的 API 的申请进行限流。

让咱们用图 4-3 中的一个例子来阐明这种设计中的速率限度是如何工作的。假如咱们的 API 每秒容许 2 个申请，客户端在一秒钟外向服务器发送 3 个申请。前两个申请被路由到 API 服务器。然而，速率限度中间件限流第三个申请并返回 HTTP 状态码 429。HTTP 429 响应状态码示意用户发送的申请过多。

云微服务 [4] 曾经变得广受欢迎，速率限度通常在一个被称为 API 网关的组件内实现。API 网关是一个全面治理的服务，反对速率限度、SSL 终止、身份验证、IP 白名单、服务动态内容等。目前，咱们只须要晓得 API 网关是一个反对速率限度的中间件。

在设计速率限制器时，咱们须要问本人一个重要的问题：速率限制器应该在服务器端实现还是在网关中实现？这个问题没有相对的答案。它取决于你公司现有的技术栈、工程资源、优先事项、指标等。以下是一些一般性的指南：

• 评估你以后的技术栈，如编程语言、缓存服务等。确保你以后的编程语言足够高效，能在服务器端实现速率限度。
• 确定合乎你业务需要的速率限度算法。当你在服务器端实现所有性能时，你能够齐全控制算法。然而，如果你应用第三方网关，你的抉择可能会受限。
• 如果你曾经应用了微服务架构，并在设计中蕴含了 API 网关来进行身份验证、IP 白名单等操作，你能够在 API 网关中增加速率限制器。
• 自建你本人的速率限度服务须要工夫。如果你没有足够的工程资源来实现速率限制器，商业 API 网关是一个更好的抉择。

速率限度的算法

能够应用不同的算法实现速率限度，每种算法都有其独特的长处和毛病。尽管这一章并不专一于算法，然而高层次的了解有助于咱们抉择适宜咱们用例的正确算法或算法组合。上面是一些常见的算法：

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

令牌桶算法

令牌桶算法被宽泛用于速率限度。它简略、易于了解，并且被互联网公司宽泛应用。亚马逊 [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]。

长处：

• 鉴于队列大小无限，内存效率高。
• 申请按固定速率解决，因而实用于须要稳固出流速率的用例。

毛病：

• 流量暴发将使队列充斥旧的申请，如果它们没有及时处理，最近的申请将受到速率限度。
• 算法中有两个参数。可能不容易正确地调整它们。

固定窗口计数器算法

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

• 该算法将工夫线划分为固定大小的工夫窗口，并为每个窗口调配一个计数器。
• 每个申请将计数器减少一。
• 一旦计数器达到预约义的阈值，新的申请将被抛弃，直到新的工夫窗口开始。

让咱们用一个具体的例子来看看它是如何工作的。在图 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]的试验，400 million 申请中只有 0.003% 的申请被谬误地容许或限速。

高级架构

速率限度算法的根本思维很简略。在高级别上，咱们须要一个计数器来跟踪同一用户、IP 地址等发送的申请数量。如果计数器的数值大于限度，那么申请就会被回绝。

那咱们应该在哪里存储计数器呢？因为磁盘拜访速度慢，应用数据库不是一个好主见。因而抉择了内存缓存，因为它疾速并反对基于工夫的过期策略。例如，Redis [11]是实现速率限度的一个风行选项。它是一个内存存储，提供了两个命令：INCR 和 EXPIRE。

• INCR：它将存储的计数器减少 1。
• EXPIRE：它为计数器设置一个超时。如果超时到期，计数器会主动删除。

图 4 -12 显示了速率限度的高级架构，其工作流程如下：

• 客户端向速率限度中间件发送申请。
• 速率限度中间件从 Redis 中相应的存储桶获取计数器，并查看限度是否曾经达到。
• 如果达到了限度，申请将被回绝。
• 如果没有达到限度，申请将被发送到 API 服务器。同时，零碎会减少计数器并将其保留回 Redis。

第 3 步 – 深刻设计

图 4 -12 中的高级设计并没有答复以下问题：

• 速率限度规定是如何创立的？规定存储在哪里？
• 如何解决被限速的申请？

在本节中，咱们将首先答复对于速率限度规定的问题，而后探讨解决被限速申请的策略。最初，咱们将探讨分布式环境中的速率限度、具体设计、性能优化和监控。

速率限度规定

Lyft 开源了他们的速率限度组件[12]。咱们将深刻这个组件并查看一些速率限度规定的例子：

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 次。规定通常写在配置文件中并保留在磁盘上。

超过速率限度

如果一个申请受到了速率限度，APIs 会向客户端返回 HTTP 响应码 429（申请过多）。依据应用场景，咱们可能会将受到速率限度的申请退出队列以便稍后解决。例如，如果一些订单因为零碎过载而受到速率限度，咱们可能会保留这些订单以便稍后解决。

速率限制器头

客户端如何晓得它是否正在被限流？客户端如何晓得在被限流之前容许的残余申请数量？答案在 HTTP 响应头中。速率限制器向客户端返回以下 HTTP 头：

X-Ratelimit-Remaining：在窗口内容许的残余申请数量。

X-Ratelimit-Limit：批示客户端每个工夫窗口能够进行多少次调用。

X-Ratelimit-Retry-After：在不被限流的状况下，期待多少秒后能够再次发送申请。

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

具体设计

图 4 -13 展现了零碎的具体设计。

• 规定存储在磁盘上。工作过程频繁地从磁盘中提取规定并将它们存储在缓存中。
• 当客户端向服务器发送申请时，申请首先发送到速率限度中间件。

• 速率限度中间件从缓存中加载规定。它从 Redis 缓存中获取计数器和上一个申请的工夫戳。依据响应，速率限制器决定：

  • 如果申请没有被限速，它会被转发到 API 服务器。
  • 如果申请被限速，速率限制器返回 429 过多的申请谬误给客户端。同时，申请被抛弃或转发到队列中。

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

在单服务器环境中构建一个工作失常的速率限制器并不艰难。然而，将零碎扩大以反对多个服务器和并发线程是另一个挑战。有两个挑战：

• 竞态条件
• 同步问题

竞态条件

如前所述，速率限制器在高级别上依照以下形式工作：

• 从 Redis 读取 计数器 的值。
• 查看 ( 计数器 + 1)是否超过阈值。
• 如果没有，就在 Redis 中将计数器的值减少 1。

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

假如 Redis 中的 计数器 值为 3。如果在任何一个申请写回值之前，两个申请同时读取 计数器 值，每个申请都会将 计数器 减少 1，而后在不查看其余线程的状况下写回。两个申请（线程）都认为他们领有正确的 计数器 值 4。然而，正确的 计数器 值应该是 5。

锁是解决竞态条件的最显著的解决方案。然而，锁会显著升高零碎的速度。通常用两种策略来解决这个问题：Lua 脚本 [13] 和 Redis 中的有序集数据结构[8]。对这些策略感兴趣的读者，能够参考相应的参考资料 8。

同步问题

在分布式环境中，同步是另一个须要思考的重要因素。为了反对数百万用户，一个速率限制器服务器可能无奈解决这样的流量。当应用多个速率限制器服务器时，须要进行同步。例如，在图 4 -15 的左侧，客户端 1 向速率限制器 1 发送申请，客户端 2 向速率限制器 2 发送申请。

因为 Web 层是无状态的，客户端能够向不同的速率限制器发送申请，如图 4 -15 的右侧所示。如果没有产生同步，速率限制器 1 就不蕴含对于客户端 2 的任何数据。因而，速率限制器无奈失常工作。

一个可能的解决方案是应用粘性会话，容许客户端将流量发送到同一速率限制器。这个解决方案不倡议应用，因为它既不可扩大也不灵便。更好的办法是应用像 Redis 这样的集中式数据存储。设计如图 4 -16 所示。

性能优化

性能优化是零碎设计面试中的常见话题。咱们将探讨两个须要改良的畛域。

首先，多数据中心的设置对于速率限制器十分要害，因为对于远离数据中心的用户来说，提早很高。大多数云服务提供商在寰球各地建设许多边缘服务器地位。例如，截至 2020 年 5 月 20 日，Cloudflare 在天文上散布有 194 个边缘服务器[14]。流量会主动路由到最近的边缘服务器，以缩小提早。

其次，用最终一致性模型同步数据。如果你对最终一致性模型不分明，请参考“第 6 章：设计键值存储”中的“一致性”局部。

监控

在搁置速率限制器后，收集剖析数据以查看速率限制器是否无效是十分重要的。次要的是，咱们想要确保：

• 速率限度算法是无效的。
• 速率限度规定是无效的。

例如，如果速率限度规定过于严格，许多无效的申请将被抛弃。在这种状况下，咱们可能心愿略微放宽规定。在另一个例子中，咱们留神到当流量忽然减少，如闪购流动时，咱们的速率限制器变得有效。在这种状况下，咱们可能会更换算法以反对突发流量。在这里，令牌桶是一个很好的抉择。

步骤 4 – 总结

在这一章中，咱们探讨了不同的速率限度算法及其长处 / 毛病。咱们探讨的算法包含：

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

而后，咱们探讨了零碎架构，分布式环境中的速率限制器，性能优化和监控。相似于任何零碎设计面试问题，如果工夫容许，你能够提到其余的探讨点：

• 硬速率限度 vs 软速率限度。

  • 硬限度：申请次数不能超过阈值。
  • 软限度：申请在短时间内能够超过阈值。
• 在不同层级的速率限度。在这一章中，咱们只探讨了利用层级（HTTP：第 7 层）的速率限度。在其余层也能够利用速率限度。例如，你能够应用 Iptables[15]（IP：第 3 层）通过 IP 地址进行速率限度。留神：开放系统互联模型（OSI 模型）有 7 层[16]：第 1 层：物理层，第 2 层：数据链路层，第 3 层：网络层，第 4 层：传输层，第 5 层：会话层，第 6 层：表示层，第 7 层：应用层。

• 防止被限速。用最佳实际设计你的客户端：

  • 应用客户端缓存以防止频繁地调用 API。
  • 了解限度，并且不在短时间内发送过多的申请。
  • 蕴含捕捉异样或谬误的代码，以便你的客户端能够从异样中优雅地复原。
  • 在重试逻辑中增加足够的退却工夫。

恭喜你走到这一步！当初给本人一个赞。做得好！

欢送关注我的公众号：更 AI。第一工夫理解前沿行业音讯、分享深度技术干货、获取优质学习资源

参考资料

[1] 速率限度策略和技术：https://cloud.google.com/solutions/rate-limiting-strategies-t…

[2] Twitter 速率限度：https://developer.twitter.com/en/docs/basics/rate-limits

[3] Google 文档应用限度：https://developers.google.com/docs/api/limits

[4] IBM 微服务：https://www.ibm.com/cloud/learn/microservices

[5] 节流 API 申请以取得更好的吞吐量：

https://docs.aws.amazon.com/apigateway/latest/developerguide/…

[6] Stripe 速率限制器：https://stripe.com/blog/rate-limiters

[7] Shopify REST Admin API 速率限度：https://help.shopify.com/en/api/reference/rest-admin-api-rate…

[8] 应用 Redis 排序汇合实现更好的速率限度：
https://engineering.classdojo.com/blog/2015/02/06/rolling-rat…

[9] 零碎设计 — 速率限制器和数据建模：
https://medium.com/@saisandeepmopuri/system-design-rate-limit…
9304b0d18250

[10] 咱们如何建设能扩大到数百万域名的速率限制器：
https://blog.cloudflare.com/counting-things-a-lot-of-differen…

[11] Redis 网站：https://redis.io/

[12] Lyft 速率限度：https://github.com/lyft/ratelimit

[13] 应用速率限制器扩大你的 API：
https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter

[14] 什么是边缘计算：https://www.cloudflare.com/learning/serverless/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