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

2023-09-08 08:33 由磁石空杯发表于 #软件设计

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网关是更好的选择。

参考资料

软件测试精品书籍文档下载持续更新 https://github.com/china-testing/python-testing-examples 请点赞，谢谢！
本文涉及的python测试开发库谢谢点赞！ https://github.com/china-testing/python_cn_resouce
python精品书籍下载 https://github.com/china-testing/python_cn_resouce/blob/main/python_good_books.md
Linux精品书籍下载 https://www.cnblogs.com/testing-/p/17438558.html
https://docs.platformio.org/en/latest
限制速率的策略和技术：https://cloud.google.com/solutions/rate-limiting-strategies-techniques
Twitter 使用率限制：https://developer.twitter.com/en/docs/basics/rate-limits
谷歌文档使用限制：https://developers.google.com/docs/api/limits
IBM 微服务：https://www.ibm.com/cloud/learn/microservices
节流 API 请求以提高吞吐量：https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html
Stripe 速率限制器：https://stripe.com/blog/rate-limiters
Shopify REST 管理 API 速率限制：https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits
利用 Redis 排序集更好地限制速率：https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
系统设计--速率限制器和数据建模：https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250
我们如何建立能够扩展到数百万域的速率限制：https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
Redis 网站：https://redis.io/
Lyft 速率限制：https://github.com/lyft/ratelimit
利用速率限制器扩展 API：https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter
什么是边缘计算：https://www.cloudflare.com/learning/serverless/glossary/what-is-edge-computing/
使用 Iptables 对请求进行速率限制：https://blog.programster.org/rate-limit-requests-with-iptables
OSI 模型：https://en.wikipedia.org/wiki/OSI_model#Layer_architecture

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。
了解限制，不要在短时间内发送过多请求。
包含捕获异常或错误的代码，以便客户端可以从容地从异常中恢复。
为重试逻辑添加足够的后退时间。