面试场景题系列：设计限流器

首先看看使用API限流器的好处。

•预防由拒绝服务攻击(Denial of Service，DoS)引起的资源耗尽问题。大型科技公司发布的所有API几乎都强制执行某种形式的限流操作。例如，推特限制每个用户每3小时最多发300条推文。谷歌文档API的默认限制是每个用户每60秒最多发出300个读请求。限流器通过有意或者无意地拦截超额的请求来预防DoS攻击。

•降低成本。限制过量的请求意味着需要的服务器更少，并且可以把更多的资源分配给优先级更高的API。限流器对于使用付费的第三方API的公司来说极为重要。比如，对于外部API，如检查信用值、请求付款、获取健康记录等，你需要按照请求次数付费。限制这些请求的数量对于降低成本很重要。

•预防服务器过载。为了降低服务器负载，可以使用限流器来过滤机器人或者用户不当操作所造成的过量请求。

1.限流器场景需求设定：

•能准确限制过量的请求。

•低延时，限流器不能拖慢HTTP响应时间。

•尽量占用较少的内存。

•这是一个分布式限流器，可以在多个服务器或者进程之间共享。

•需要处理异常。当用户的请求被拦截时，给用户展示明确的异常信息。

•高容错性。如果限流器出现任何问题（比如某个缓存服务器宕机），不能影响整个系统。

2.顶层设计

我们从简单的情形入手，采用基本的客户—服务器通信模式。

2.1在哪里实现限流器

直观地说，既可以在客户端也可以在服务器端实现限流器。

•在客户端实现。一般而言，客户端不是一个强制实行限流的可靠位置，因为客户端请求很容易被恶意伪造。此外，我们也可能无法控制客户端的实现。

•在服务器端实现。图-1展示了一个服务器端的限流器。

图-1

除了在客户端和服务器端实现，还有一种方案。我们可以创建一个中间件作为限流器，用它来限制对API的请求，而不是把限流器放在API服务器上，如图-2所示。

图-2

我们用图-3作为例子来讲解限流器在我们的设计中是怎样工作的。假设我们的API服务器允许客户端每秒发送两次请求，而客户端在1秒之内向服务器发送了3个请求，那么头两个请求被转发到API服务器上，限流器中间件会拦截第3个请求并返回HTTP状态码429，表示用户发送的请求太多。

图-3

云微服务已经非常流行，限流器通常在一个叫作API网关的组件中实现。API网关是一个完全托管的服务，支持流量限制、SSL终止、身份验证、IP地址白名单、静态内容服务等功能。现在，我们只需要知道API网关是一个支持流量限制的中间件即可。

在设计限流器的时候，我们要问自己一个很重要的问题：这个限流器应该在哪里实现？是在服务器端还是在网关中实现？这个问题没有唯一的答案，而是取决于你公司现在的技术栈、工程资源、优先级、目标等因素。以下是一些一般性的指导原则。

•评估公司现在的技术栈，比如编程语言、缓存服务等。确保你现在用的编程语言能高效地在服务器端实现流量限制。

•找到适合业务需求的流量限制算法。如果把所有功能或模块都放在服务器端实现，你就可以自由地选择算法。如果使用第三方网关，你的算法选择就有可能受到限制。

•如果你已经使用了微服务架构，并且在设计中包含了API网关以实现身份验证、IP地址白名单等功能，那么你可以把限流器加在API网关上。

•创建自己的限流器是很花时间的。如果你没有足够的工程资源去实现限流器，使用商业版的API网关是更好的选择。

2.2 流量限制算法

流量限制可以通过不同的算法来实现，每种算法都有不同的优点和缺点。本文虽然并不重点讨论算法，但是大概了解一下它们有助于为我们的场景选择最适合的算法或者算法组合。下面是流行算法的列表。

•代币桶算法(Token Bucket)。

•漏桶算法(Leaking Bucket)。

•固定窗口计数器算法(Fixed Window Counter)。

•滑动窗口日志算法(Sliding Window Log)。

•滑动窗口计数器算法(Sliding Window Counter)。

代币桶算法

代币桶算法被广泛用于限制流量。它很简单、容易理解，并被互联网公司广泛使用。亚马逊[插图]和Stripe都使用此算法来对它们的API请求限流。代币桶算法的工作原理如下：

•代币桶是一个有预定义容量的容器。代币按照预定的速率被放入桶中。一旦桶被装满，就不再往里面添加代币。如图-4所示，代币桶的容量是4个代币。重新注入装置每秒将两个代币放入桶中。如果桶满了，多出来的代币就会溢出。

图-4

•每个请求消耗一个代币。当一个请求到达时，我们检查桶里有没有足够的代币。图-5解释了它是如何工作的。

◆ 如果有足够的代币，每次请求到达时，我们就取出一个代币，然后这个请求就可以通过。

◆ 如果没有足够的代币，这个请求将被丢弃。

图-5

图-6描述了代币消耗、重新注入和流量限制的工作原理。在这个例子中，代币桶的容量是4个代币，重新注入代币的速度是每分钟4个。

图-6

代币桶算法有两个参数。

•桶大小：桶内最多允许有多少个代币。

•重新注入代币的速度：每秒放进桶里的代币数量。

我们需要多少个桶呢？说不准，这取决于流量限制规则。下面是一些例子。

•通常，不同的API端点需要使用不同的桶。比如，如果允许用户每秒发1篇帖子，每天添加150个好友，每秒点赞5篇帖子，那么每个用户就需要3个桶。

•如果我们需要基于IP地址来对请求限流，则每个IP地址需要一个桶。

•如果系统最多允许每秒发送10000个请求，那么所有请求理应共享一个全局桶。

代币桶算法有不少优点。

•算法容易实现。

•内存的使用效率高。

•允许在很短时间内出现突发流量。只要还有代币，请求就可以通过。

代币桶算法也有缺点。尽管该算法只需要两个参数，但是要把这两个参数调校好，可能很具有挑战性。

漏桶算法

漏桶算法跟代币桶算法很相似，只不过它对请求是按照固定速率处理的。漏桶算法通常采用先进先出(First-In-First-Out，FIFO)队列来实现。该算法的工作原理如下所述。

•当一个请求到达时，系统先检查桶是否已满。如果没有，就将请求添加到队列中。

•否则，丢弃请求。•定期从队列中取出请求并进行处理。

图-7解释了该算法是如何工作的。

图-7

漏桶算法有如下两个参数。

•桶大小：它等于队列大小。队列中保存了要按固定速率处理的请求。

•出栈速度：它定义了每秒可以处理多少个请求，通常以秒为时间单位。Shopify是一个电商公司，它使用漏桶算法来进行流量限制。

漏桶算法的优点：

•因为队列大小是有限的，所以内存的使用更高效。

•因为对请求是按固定速率来处理的，所以漏桶算法很适合要求出栈速度稳定的场景。

漏桶算法的缺点：

•突发流量会使队列中积压大量旧的请求，如果这些请求不能被及时处理，最新的请求会被限流。

•该算法有两个参数，要调校好它们可能不那么容易。

固定窗口计数器算法

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

•将时间轴分成固定大小的时间窗口，并给每个时间窗口分配一个计数器。

•每到达一个请求，计数器的值都会加1。

•一旦计数器到达预先设定的阈值，新请求就会被丢弃，直到开始一个新的时间窗口。

我们用一个具体的例子来看看它到底是怎么工作的。在图-8中，时间单位是秒，系统允许每秒最多通过3个请求。在每个1秒的时间窗口中，如果收到超过3个请求，超出的请求会如图4-8所示的那样被丢弃。

图-8

---

这个算法的一个主要问题是，如果在时间窗口的边界上出现流量的爆发，则有可能会导致通过的请求数超出阈值。我们来看下面这个例子。如图-9所示，系统每分钟最多只允许通过5个请求，并且可用配额（阈值）在整分钟时会重置。在2:00:00和2:01:00之间有5个请求，在2:01:00和2:02:00之间又有5个请求。对于2:00:30至2:01:30这1分钟的时间窗口，有10个请求通过，而这是允许通过的请求数量的两倍。

图-9

固定窗口计数器算法的优点：

•内存的使用效率高。

•容易理解。

•在每个单位时间窗口结束时重置请求数阈值，这种设计适用于某些特定场景。

固定窗口计数器算法的缺点是，如果在时间窗口的边界上流量激增，会导致通过的请求数超过设定的阈值。

滑动窗口日志算法

前面讨论过，固定窗口计数器算法有一个重大问题：在时间窗口的边界上，它允许更多的请求通过。滑动窗口日志算法解决了这个问题。它的工作原理如下所述。

•算法记录每个请求的时间戳。时间戳数据通常保存在缓存中，比如Redis中的有序集合。

•当新请求到达时，移除所有过时的时间戳。过时时间戳是指那些早于当前时间窗口起始时间的时间戳。

•将新请求的时间戳添加到日志中。

•如果日志的条数等于或者少于允许的请求数，则请求通过，否则请求被拒绝。我们用一个例子来解释这个算法，如图-10所示。

图-10

在这个例子中，限流器每分钟允许2个请求通过。通常Linux时间戳会被存储在日志中。但是为了使可读性更高，我们在这里使用了人类可读的时间表示。•当一个新请求在1:00:01到达时，日志是空的。因此，该请求被允许通过。

•当一个新请求在1:00:30到达时，1:00:30这个时间戳被添加到日志中。添加后，日志条数变为2，没有超过允许通过的请求数量。因此这个请求也被允许通过。

•当一个新请求在1:00:50到达时，时间戳被插入日志。在插入后，日志条数变为3，大于允许通过的最大请求数。因此该请求被拒绝，但是它的时间戳留在了日志中。

•当一个新请求在1:01:40到达时，所有在[1:00:40，1:01:40）范围内的请求都在最近的时间窗口中，所有早于1:00:40发送的请求都已过时。两个过时的时间戳1:00:01和1:00:30从日志中被删除。删除后，日志的条数变成2；因此，这个请求被允许通过。

滑动窗口日志算法的优点是，其实现的流量限制非常准确，在任何滑动的时间窗口中，请求的数量都不会超过阈值。但是其消耗的内存过多，因为即使一个请求已被拒绝，它的时间戳依然被保存在内存中。

滑动窗口计数器算法

滑动窗口计数器算法是组合了固定窗口计数器算法和滑动窗口日志算法的方法。这个算法有两种不同的实现方法，这里会解释其中的一种。图-11展示了这个算法是怎么工作的。

假设限流器每分钟最多允许通过7个请求，然后前一分钟有5个请求，当前分钟有3个请求。当一个新请求出现在当前分钟的30%的位置时，滑动窗口所允许的请求数量通过下面的公式来计算：

当前窗口的请求数+之前窗口的请求数×滑动窗口和之前窗口的重合率

用这个公式，我们可以算出滑动窗口所允许的请求数量为6.5个(3+5×0.7=6.5)。基于不同的用户场景，对这个数字可以向上或者向下取整。在我们的例子中，将它向下取整为6。

图-11

因为限流器每分钟最多允许通过7个请求，所以现在的请求可以通过。但是，再多接收一个请求就会超过阈值。受篇幅所限，我们不讨论另一种实现方式，感兴趣的读者可以阅读Medium网站上的文章“System Design—Rate limiter and Data Modelling”。滑动窗口计数器算法也不是完美的。它也有优点和缺点。

滑动窗口计数器算法优点：

•它平滑了流量中的波动，因为当前时间窗口内请求的速率是基于前一个时间窗口内请求的平均速率计算出来的。

•对内存的使用很高效。滑动窗口计数器算法的缺点是，它只对不那么严格的回溯窗口起作用。该算法只是对真实流量速率进行了近似估计，因为它假设前一个窗口中的请求是均匀分布的。尽管如此，这个问题可能并没有看起来那么严重。根据Cloudflare的实验，在4亿个请求中，只有0.003%的请求被错误地允许通过或被限流。

2.3 高层级架构

流量限制算法的基本理念是简单的。从高层级来看，我们需要一个计数器来记录有多少请求是由同一个用户、同一个IP地址等发来的。如果计数器的值超出设定的阈值，请求就不允许通过。

那么，我们应该在哪里存储计数器呢？使用数据库并不是一个好主意，因为硬盘的访问速度很慢。内存上的缓存速度快且支持基于时间的过期策略，因此可以选它。比如，Redis就是一个很受欢迎的选项。Redis是一个内存存储系统，它提供了两个命令：INCR和EXPIRE。

•INCR：把存储的计数器值加1。

•EXPIRE：为计数器设置一个超时时间。如果超时时间到期，计数器会被自动删除。

图-12展示了限流器的高层级架构，它按如下方式工作。

•客户端将请求发送给限流器中间件。

•限流器中间件在Redis对应的桶中获取计数器并检查其值是否达到了阈值。

◆ 如果达到阈值，请求将被拒绝。

◆ 如果没有，请求将被发送给API服务器。同时，系统增加计数器的值并把它保存到Redis中。

图-12

3.深入设计

图-12所示的高层级设计并没有回答下面的问题：

•流量限制规则是如何创建的？这些规则存储在哪里？

•如何处理被限流的请求？

在本节中，我们先回答关于流量限制规则的问题，然后讨论处理被限流请求的策略，最后讨论如何在分布式系统中进行流量限制。我们会给出一个详细的设计并探讨性能优化和监控方面的问题。

3.1 流量限制规则

Lyft开源了它的流量限制组件。我们来看两个使用这个组件编写的流量限制规则的例子。在下面的例子中，系统设置了每天最多允许有5条营销消息。

下面是另一个例子。这个规则是在1分钟之内客户端登录不允许超过5次。这些规则一般都写在配置文件中并保存在硬盘上。

3.2 超过流量的限制

如果一个请求被限流，API会给客户端返回HTTP响应码429（请求过多）。根据应用场景，我们有可能会把超过阈值的请求放入队列，之后再处理。比如，一些订单请求因为系统过载被限流了，我们可以保存这些订单以便稍后处理。

限流器返回的HTTP头

客户端如何知道请求有没有被限流呢？客户端如何在请求被拦截之前知道允许通过的请求数还剩多少？答案藏在HTTP头里。限流器会返回下面的HTTP头给客户端。

•X-Ratelimit-Remaining：在当前时间窗口内剩余的允许通过的请求数量。

•X-Ratelimit-Limit：客户端在每个时间窗口内可以发送多少个请求。

•X-Ratelimit-Retry-After：在被限流之后，需要等待多少秒才能继续发送请求而不被拦截。当用户发送的请求过多时，限流器将向客户端返回HTTP响应码429（表示请求太多）和X-Ratelimit-Retry-After响应头。

3.3 详细设计

图-13

•流量限制规则存储在硬盘上。工作进程(Worker)经常从硬盘中获取规则并将其存储到缓存中。

•当客户端向服务器发送请求时，请求会首先被发给限流器中间件。

•限流器中间件从缓存中加载规则。它从Redis缓存中获取计数器和上一次请求的时间戳。基于响应，限流器中间件做出以下决定：

◆ 如果请求没有被限流，就将其转发给API服务器。

◆ 如果请求被限流，限流器会向客户端返回429响应码（请求太多）来报错。同时，请求要么被丢弃，要么被转发到队列中。

3.4 分布式系统中的限流器

在单服务器环境中创建一个限流器并不难。但是，要将限流器系统扩展，以支持多个服务器和并发线程，那就是另一回事了。其中存在两个挑战：

•竞争条件(Race Condition)。

•同步问题。

竞争条件

如前所述，限流器大体上是按如下方式工作的：

•从Redis中读取计数器的值。

•检查计数器值加1后是否超过了阈值。

•如果没有，就把计数器的值在Redis中加1。

竞争条件可能会发生在一个高并发的环境中，如图-14所示。

图-14

假设在Redis中计数器的值是3。如果两个请求同时读计数器的值，它们中的任何一个在将值写回Redis之前，都会把计数器的值加1，而不检查其他线程的情况。这样，两个请求（线程）都认为它们拥有正确的计数器值——4，但是正确的计数器值应该是5。

锁是竞争条件最直观的解决方案，但是它会显著地拖慢系统。通常我们使用以下两种策略用来解决这个问题：Lua脚本和Redis的有序集合数据结构。

同步问题

同步是分布式系统中需要考虑的另一个重要因素。为了支持百万量级的用户，一个限流器有可能不足以处理所有的流量。当使用多个限流器时，限流器之间就必须同步。举个例子，如图-15所示，在左图中，客户端1向限流器1发送请求，客户端2向限流器2发送请求。但因为网络层是无状态的，所以客户端也可以把请求发给别的限流器，如图-15的右图所示。如果没有同步，则限流器1将不包含任何关于客户端2的数据，因此限流器1就无法正常工作。

图-15

一个可行的解决方案是使用黏性会话(Sticky Session)，允许客户端将请求发往同一个限流器。但是，这个解决方案既不可扩展也不灵活，因此不建议使用。更好的方法是使用中心化的数据存储，比如Redis。该设计如图-16所示。

图-16

3.5 性能优化

性能优化是系统设计面试中常见的主题。我们会针对两个方面来做优化。

第一，对限流器而言，设置多数据中心是至关重要的，因为离数据中心越远，响应延时越高。大多数云服务提供商在全球设置了很多边缘服务器。比如，截至2020年5月20日，Cloudflare有194个在地理上广泛分布的边缘服务器。流量会被自动转发到最近的边缘服务器以降低延时（如图-17所示）。

图-17

3.6 监控

在设置好限流器之后，收集数据来检查限流器是否有效是很重要的。我们主要想确保：

•流量限制算法有效。

•流量限制规则有效。

举个例子，如果流量限制规则太严格，就会导致很多有效请求被丢弃。在这种情况下，我们希望稍微放宽限制。另一个例子是，我们发现，在限时促销这种流量激增的场景下，限流器变得无效了。因此，可能需要换一种流量限制算法来应对突发的流量。这时候，代币桶就是一个合适的替代算法。

4.总结

在本文中，我们讨论了不同的流量限制算法及其优缺点。这些算法包括：

•代币桶算法。

•漏桶算法。

•固定窗口计数器算法。

•滑动窗口日志算法。

•滑动窗口计数器算法。

然后，我们讨论了系统架构、分布式系统中的限流器、性能优化和监控。同任何其他系统设计面试题类似，如果有时间，你还可以谈一谈下面的话题。

•硬流量限制与软流量限制。硬流量限制是指请求数量不能超过阈值。软流量限制是指请求数量可以在短时间内超过阈值。

•在不同层级做流量限制。在本文中，我们只讨论了在应用层（HTTP层，第7层）做流量限制。流量限制也可以用在其他层。例如，你可以使用Iptables[插图]（IP层，第3层）并根据IP地址来限流。注意：开放系统互联模型（Open Systems Interconnection，OSI模型）有7层[插图]，其中，第1层为物理层，第2层为数据链路层，第3层为网络层，第4层为传输层，第5层为会话层，第6层为表示层，第7层为应用层。

•避免被限流。用以下最佳实践来设计你的客户端：

◆ 使用客户端缓存，避免频繁地调用API。

◆ 理解流量限制，不要在短时间内发送太多请求。

◆ 添加代码以捕获异常或错误，使客户端可以优雅地从异常中恢复。

◆ 在重试逻辑中添加足够的退避时间。