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

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。

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

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

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

热门相关:神秘总裁小小妻   豪门情变,渣总裁滚远点!   异能特工:军火皇后   我成了暴戾帝君的小娇包   网游三国之城市攻略