Skip to content

系统设计:设计一个分布式限流器(04)

Published: at 11:50:44

在网络系统中,限流器被用于控制客户端或服务端发送流量的速率。在HTTP世界中,限流器限制在指定时间内允许发送客户端请求数。 如果API请求次数超过了限流器设置的阈值,则所有超出的调用都会被阻止。 以下是一些示例:

在本章中,您需要设计一个限流器。在开始设计之前,我们先看看使用 API 限流器的好处:

第1步:了解问题并确定设计范围

速率限制可以通过不同的算法来实现,每一种算法都有其优点和缺点。 面试官和候选人之间的互动有助于阐明我们试图建立的限流器的类型。

候选人:我们要设计什么样的限流器?是客户端的限流器还是服务器端的API限流器?

面试官:好问题,我们专注于服务器端的API限流器。

候选人:限流器是否根据IP、用户ID或其他属性来限制API请求?

面试官:限流器应该足够灵活,能够支持不同的限流规则集。

候选人:该系统的规模是多少?它是为初创企业还是拥有庞大用户群的大公司建立的?

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

候选人:系统会在分布式环境下工作吗?

面试官:是的。

候选人:限流器是一个单独的服务还是应该在应用程序代码中实现?

面试官:这是一个由你决定的设计问题。

候选人:是否需要通知被限流的用户?

面试官:是的。

要求

以下是对系统要求的概述

第2步:提出高层次的设计方案并获得认同

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

限流器放在哪里

直觉上,你可以在客户端或服务器端实现限流器。

让我们使用图 4-3 中的示例来说明这种设计中的限流器是如何工作的。 假设我们的 API 允许每秒 2 个请求,而客户端在一秒内发送了3个请求到服务器。 前两个请求被路由到 API 服务器。 但是,限流器中间件会限制第三个,请求并返回 HTTP 状态代码 429。 HTTP 429 响应状态代码表示用户发送了过多的请求。

云微服务[4]已经变得非常流行,限流通常在一个叫做API网关的组件中实现。API网关是一个完全托管的服务,支持限速、SSL、认证、IP白名单、服务静态内容等。现在,我们只需要知道API网关是一个支持限流的中间件。

在设计限流器时,要问自己的一个重要问题是:限流器应该在哪里实现,在服务器端还是在网关中?这没有绝对的答案。这取决于你公司目前的技术栈、工程资源、优先级、目标等。这里有一些通用的指南:

限流算法

限流可以使用不同的算法来实现,每种算法都有其独特的优缺点。尽管本章并不关注算法,但在高层次上了解它们有助于选择正确的算法或算法组合来适应我们的使用情况。

下面是一个流行算法的列表:

令牌桶算法

令牌桶(Token bucket)算法广泛用于速率限制。 它简单易懂,常被互联网公司采用。 Amazon [5] 和 Stripe [6] 都使用这个算法来限制他们的 API 请求。

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

图 4-6 说明了令牌消耗、重新填充和速率限制逻辑的工作原理。 在此示例中,令牌桶大小为 4,重新填充速率为每 1 分钟 4 个。

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

  1. 桶大小:桶内允许的最大令牌数。
  2. 填充速率:每秒放入到桶内的令牌数量。

我们需要多少个桶?这取决于限流规则,并且会有所不同。 以下是几个例子。

优点

缺点

漏桶算法

漏桶(Leaking bucket)算法与令牌桶类似,不同之处在于请求是以固定速率处理的。它通常用先入先出(FIFO)队列来实现。

该算法的工作原理如下:

图4-7解释了该算法的工作原理:

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

Shopify,一家电子商务公司,使用泄漏桶来限制速度[7]。

优点:

缺点:

固定窗口计数器算法

固定窗口计数器(Fixed window counter)算法工作原理如下:

让我们用一个具体的例子来看看它是如何工作的。在图4-8中,时间单位是1秒,系统允许每秒钟最多有3个请求。在每个秒窗口中,如果收到的请求超过3个,额外的请求就会被放弃,如图4-8所示:

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

在图4-9中,系统允许每分钟最多有5个请求,可用的配额在整点分钟时重置。如图所示,在2:00:00和2:01:00之间有5个请求,在2:01:00和2:02:00之间又有五个请求。 在2:00:30和2:01:30之间的1分钟窗口,有10个请求通过了。这是允许请求数量的两倍。 优点:

缺点:

滑动窗口日志算法

如前所述,固定窗口计数(Sliding window log)算法有一个主要问题:它允许更多的请求在窗口的边缘通过。滑动窗口日志算法解决了这个问题。 它的工作原理如下:

我们用图4-10所示的一个例子来解释该算法。

在这个例子中,限流器允许每分钟2个请求。通常情况下,Linux的时间戳会存储在日志中。然而,在我们的例子中,为了提高可读性,使用了人类可读的时间表示法。

优点:

缺点:

滑动窗口计数器算法

滑动窗口计数器(Sliding window counter)算法是一种混合方法,结合了固定窗口计数器和滑动窗口日志。 该算法可以通过两种不同的方法来实现。我们将在本节中解释一种实现方法,并在本节末尾提供另一种实现方法的参考。

图4-11说明了这种算法的工作原理:

假设限流器允许每分钟最多有7个请求,在上一分钟有5个请求,当前一分钟有3个请求。对于在当前分钟内到达30%位置的新请求,滚动窗口中的请求数用以下公式计算:

由于限流器每分钟最多允许7个请求,当前的请求可以通过。然而,再收到一个请求后,就会达到限制。

由于篇幅所限,我们在此不讨论其他的实现。有兴趣的读者可以参考参考资料[9]。这种算法并不完美。它有优点也有缺点。

优点:

缺点:

高层次的架构

限流算法的基本思想很简单。在高层次上,我们需要一个计数器来跟踪来自同一用户、IP地址等的多少个请求。如果计数器大于限制值,则请求被禁止。

我们应该在哪里存储计数器?由于磁盘访问速度慢,使用数据库并不是一个好主意。选择内存缓存是因为它速度快并且支持基于时间的过期策略。 例如,Redis[11]是实现速率限制的一个流行选择。它是一个内存中的存储,提供两个命令:INCREXPIRE

图4-12显示了速率限制的高层结构,其工作原理如下:

第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次。规则一般写在配置文件中并保存在磁盘上。

超过速率限制

如果一个请求被限制了速率,API会向客户端返回一个HTTP响应代码429(请求太多)。根据不同的使用情况,我们可能会将速率受限的请求排队等候以后处理。 例如,如果一些订单由于系统过载而受到速率限制,我们可以保留这些订单以便以后处理。

限流器请求头

一个客户如何知道它是否被节流?客户端如何知道在被节流之前允许的剩余请求的数量?答案就在HTTP响应头中。限流器向客户端返回以下 HTTP 标头:

当用户发送过多请求时,将向客户端返回 429 too many requests 错误和 X-Ratelimit-Retry-After 标头。

详细设计

图 4-13 给出了系统的详细设计。

分布式环境下的限流器

构建一个在单个服务器环境下运行的限流器并不困难。然而,将系统扩展到支持多个服务器和并发线程是另一回事。这里有两个挑战:

竞争条件

如前所述,限流器在高层的工作原理如下

- 从Redis读取计数器的值
- 检查 ( 计数器 + 1 ) 是否超过阈值
- 如果不是,则将 Redis 中的计数器值加 1

如图4-14所示,在高度并发的环境中会发生竞争条件。

假设 Redis 中的计数器值为 3。如果两个请求在其中一个请求写回值之前同时读取计数器值,则每个请求都会将计数器加 1 并在不检查另一个线程的情况下将其写回。 两个请求(线程)都认为它们具有正确的计数器值 4。但是,正确的计数器值应该是 5

锁是解决竞争条件最明显的解决方案。 但是,锁会显着降低系统速度。 通常使用两种策略来解决这个问题: Lua 脚本 [13] 和 Redis [8] 中的 sorted sets 数据结构。 对这些策略感兴趣的读者可以参考相应的参考资料[8] [13]。

同步问题

同步是分布式环境中要考虑的另一个重要因素。 要支持数百万用户,一个限流器服务器可能不足以处理流量。 当使用多个限流器服务器时,需要同步。 例如,在图 4-15 的左侧,客户端 1 将请求发送到限流器 1,客户端 2 将请求发送到限流器 2。 由于 Web 层是无状态的,客户端可以将请求发送到不同的限流器,如图所示,在图 4-15 的右侧。 如果没有发生同步,限流器 1 不包含有关客户端 2 的任何数据。因此,限流器无法正常工作。

一种可能的解决方案是使用粘性会话,允许客户端将流量发送到相同的限流器。 这个解决方案是不可取的,因为它既不可扩展也不灵活。 更好的方法是使用像 Redis 这样的集中式数据存储。

设计如图 4-16 所示:

性能优化

性能优化是系统设计面试中的一个常见话题。我们将涉及两个方面的改进。

首先,多数据中心的设置对限流器至关重要,因为对于远离数据中心的用户来说,延迟很高。大多数云服务提供商在世界各地建立了许多边缘服务器位置。 例如,截至2020年5月20日,Cloudflare有194个地理上分布的边缘服务器[14]。流量被自动路由到最近的边缘服务器,以减少延时。

第二,用最终的一致性模型来同步数据。如果你不清楚最终的一致性模型,请参考 “第6章:设计一个键值存储 “中的 “一致性 “部分。

监控

限流器到位后,最重要的是要收集分析数据以检查限流器是否有效。

首先,我们要确保:

例如,如果速率限制规则过于严格,则会丢弃许多有效请求。 在这种情况下,我们想稍微放宽规则。 在另一个示例中,我们注意到当流量突然增加时(如抢购),我们的限流器变得无效。 在这种场景下,我们可能会更换算法来支持突发流量。 令牌桶很适合这种场景。

第4步:总结

在这一章中,我们讨论了速率限制的不同算法和它们的优点和缺点。

讨论的算法包括:

然后,我们讨论了系统架构、分布式环境中的限流器、性能优化和监控。 与任何系统设计面试问题类似,如果时间允许,您可以提及其他谈话要点:

恭喜你走到了这一步!现在给自己一个鼓励,干得漂亮!

参考资料

[1] Rate-limiting strategies and techniques: https://cloud.google.com/solutions/rate-limiting-strategies-techniques

[2] Twitter rate limits: https://developer.twitter.com/en/docs/basics/rate-limits

[3] Google docs usage limits: https://developers.google.com/docs/api/limits

[4] IBM microservices: https://www.ibm.com/cloud/learn/microservices

[5] Throttle API requests for better throughput:

https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html

[6] Stripe rate limiters: https://stripe.com/blog/rate-limiters

[7] Shopify REST Admin API rate limits: https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits

[8] Better Rate Limiting With Redis Sorted Sets:https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/

[9] System Design — Rate limiter and Data modelling:https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling-9304b0d18250

[10] How we built rate limiting capable of scaling to millions of domains:https://blog.cloudflare.com/counting-things-a-lot-of-different-things/

[11] Redis website: https://redis.io/

[12] Lyft rate limiting: https://github.com/lyft/ratelimit

[13] Scaling your API with rate limiters:https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter

[14] What is edge computing: https://www.cloudflare.com/learning/serverless/glossary/what-is-edge-computing/

[15] Rate Limit Requests with Iptables: https://blog.programster.org/rate-limit-requests-with-iptables

[16] OSI model: https://en.wikipedia.org/wiki/OSI_model#Layer_architecture