4 设计限流器

前言

在网络系统中，限流器用于控制客户端或者服务端发送的流量的速率。在HTTP的世界里，限流器限制的是客户端在一定时间内被允许发送的请求数量。如果API请求数超过了限流器设定的阈值，所有超出阈值的请求就会被拦截。下面是一些例子。

一个用户每秒只能发布不超过两篇帖子。同一个IP地址每天最多可以创建10个账号。

使用限流器的好处：

预防由拒绝服务攻击(Denial of Service，DoS)引起的资源耗尽问题。大型科技公司发布的所有API几乎都强制执行某种形式的限流操作。限流器通过有意或无意地拦截超额的请求来预防DoS攻击；降低成本。限制过量的请求意味着需要的服务器更少，把更多资源分配给优先级更高的API。尤其是使用第三方付费API的场景。比如，对于外部API，如检查信用值、请求付款、获取健康记录等，你需要按照请求次数付费；预防服务器过载：过滤机器人或用户不当操作所造成的过量请求。

第一步：理解问题并确定设计的边界

限流器可以使用不同的算法来实现，每种算法都有其优缺点。与面试官沟通可以帮助理清你应该创建何种限流器。
候选人： 我们要设计什么样的限流器？是客户端限流器还是服务器端API限流器？
面试官： 好问题。我们重点讨论服务器端API限流器。
候选人： 这个限流器是基于IP地址、用户ID还是其他属性来限制API请求速率的？
面试官： 限流器需要足够灵活来支持不同的限流觃则。
候选人： 这个系统的觃模如何？是为初创公司还是为有大量用户的大公司创建的？
面试官： 该系统必须能处理大量请求。
候选人： 这个系统是在分布式环境中运行的吗？
面试官： 是的。
候选人： 限流器需要作为一个独立服务还是应该在应用程序的代码里实现？
面试官： 这取决于你如何设计。
候选人： 我们需要通知被限流的用户吗？
面试官： 是的。

系统需求总结如下：

准确限制过量的请求。低延时。限流器不能拖慢HTTP响应时间。尽量占用较少的内存。这是一个分布式限流器，可以在多个服务器或者进程之间共享。需要处理异常。当用户的请求被拦截时， 给用户展示明确的异常信息。高容错性。如果限流器出现任何问题（比如某个缓存服务器宕机）， 不能影响整个系统。

第二步：提议高层级的设计并获得认同

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

在哪里实现限流器

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

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

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

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

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

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

评估公司现在的技术栈，比如编程语言、缓存服务等。确保你现在用的编程语言能高效地在服务器端实现流量限制。到适合业务需求的流量限制算法。如果把所有功能或模块都放在服务器端实现，你就可以自由地选择算法。如果使用第三方网关，你的算法选择就有可能受到限制。如果你已经使用了微服务架构，并且在设计中包含了API网关以实现身份验证、IP地址白名单等功能，那么你可以把限流器加在API网关上。创建自己的限流器是很花时间的。如果你没有足够的工程资源去实现限流器，使用商业版的API网关是更好的选择。

流量限制算法

流量限制可以通过不同的算法来实现，每种算法都有不同的优点和缺点。

代币桶算法(Token Bucket)。漏桶算法(Leaking Bucket)。固定窗口计数器算法(Fixed Window Counter)。滑动窗口日志算法(Sliding Window Log)。滑动窗口计数器算法(Sliding Window Counter)。

代币桶算法（令牌桶）

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

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

每个请求消耗一个代币。当一个请求到达时，我们检查桶里有没有足够的代币。下图解释了它是如何工作的。
如果有足够的代币，每次请求到达时，我们就取出一个代币，然后这个请求就可以通过。
如果没有足够的代币，这个请求将被丢弃。

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

代币桶算法有两个参数。

桶大小：桶内最多允许有多少个代币。重新注入代币的速度：每秒放进桶里的代币数量。

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

通常，不同的API端点需要使用不同的桶。比如，如果允许用户每秒发1篇帖子，每天添加150个好友，每秒点赞5篇帖子，那么每个用户就需要3个桶。如果我们需要基于IP地址来对请求限流，则每个IP地址需要一个桶。如果系统最多允许每秒发送10000个请求，那么所有请求理应共享一个全局桶。

代币桶算法有不少优点。

算法容易实现。内存的使用效率高。允许在很短时间内出现突发流量。只要还有代币，请求就可以通过。

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

漏桶算法

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

当一个请求到达时，系统先检查桶是否已满。如果没有，就将请求添加到队列中。否则，丢弃请求。定期从队列中取出请求并进行处理。

漏桶算法有如下两个参数。桶大小：它等于队列大小。队列中保存了要按固定速率处理的请求。出栈速度：它定义了每秒可以处理多少个请求，通常以秒为时间单位。Shopify是一个电商公司，它使用漏桶算法来进行流量限制。

漏桶算法的优点：

因为队列大小是有限的，所以内存的使用更高效。因为对请求是按固定速率来处理的，所以漏桶算法很适合要求出栈速度稳定的场景。

漏桶算法的缺点：

突发流量会使队列中积压大量旧的请求，如果这些请求不能被及时处理，最新的请求会被限流。该算法有两个参数，要调校好它们可能不那么容易。

固定窗口计数器算法

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

将时间轴分成固定大小的时间窗口，并给每个时间窗口分配一个计数器。每到达一个请求， 计数器的值都会加1。一旦计数器到达预先设定的阈值，新请求就会被丢弃，直到开始一个新的时间窗口。

这个算法的一个主要问题是，如果在时间窗口的边界上出现流量的爆发，则有可能会导致通过的请求数超出阈值。（感觉也不算缺点哈）

我们来看下面这个例子。如下图所示，系统每分钟最多只允许通过5个请求，并且可用配额（阈值）在整分钟时会重置。在2:00:00和2:01:00之间有5个请求，在2:01:00和2:02:00之间又有5个请求。对于2:00:30至2:01:30这1分钟的时间窗口，有10个请求通过，而这是允许通过的请求数量的两倍。

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

内存的使用效率高；容易理解；在每个单位时间窗口结束时重置请求数阈值， 这种设计适用于某些特定场景。

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

滑动窗口日志算法

滑动窗口日志算法用于解决固定窗口计数算法在时间窗口的边界上运行更多的请求通过的问题。
它的工作原理如下所述：

算法记录每个请求的时间戳。 时间戳数据通常保存在缓存中，比如Redis中的有序集合 。当新请求到达时，移除所有过时的时间戳。 过时时间戳是指那些早于当前时间窗口起始时间的时间戳。将新请求的时间戳添加到日志中。如果日志的条数等于或者少于允许的请求数， 则请求通过，否则请求被拒绝。

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

滑动窗口计数器算法

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

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

另一种实现方法：滑动窗口是在计数器限流的固定窗口的基础上，把固定窗口划分为多个小窗口，这些小窗口构成一个环，每个小窗口分别计数，而这些小窗口计数的总和不能超过总的限制，从而保证限流。

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

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

滑动窗口计数器算法的缺点是，它只对不那么严格的回溯窗口起作用。该算法只是对真实流量速率进行了近似估计，因为它假设前一个窗口中的请求是均匀分布的。尽管如此，这个问题可能并没有看起来那么严重。

高层级架构

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

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

INCR：把存储的计数器值加1。EXPIRE： 为计数器设置一个超时时间。如果超时时间到期， 计数器会被自动删除。

它按如下方式工作。

客户端将请求发送给限流器中间件。限流器中间件在Redis对应的桶中获取计数器并检查其值是否达到了阈值。如果达到阈值，请求将被拒绝。如果没有，请求将被发送给API服务器。同时，系统增加计数器的值并把它保存到Redis中。

第三步：设计继续深入

高层级设计并没有回答下面的问题：

流量限制规则是如何创建的？这些规则存储在哪里？如何处理被限流的请求？

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

流量限制规则

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

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

超过流量的限制

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

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

X-Ratelimit-Remaining：在当前时间窗口内剩余的允许通过的请求数量。X-Ratelimiit-Limit：客户端在每个时间窗口内可以发送多少个请求。X-Ratelimit-Retry-After：在被限流之后，需要等待多少秒才能继续发送请求而不被拦截。

当用户发送的请求过多时，限流器将向客户端返回HTTP响应码429（表示请求太多）和X- Ratelimit-Retry-After响应头。

详细设计

流量限制规则存储在硬盘上，工作进程(Worker)经常从硬盘中获取规则并将其存储到缓存中。当客户端想服务器发送请求时，请求会首先被发给限流器中间件。限流器中间件从缓存中加载规则。它从Redis缓存中获取计数器和上一次请求的时间戳。基于响应，限流器中间件做出以下决定：
如果请求没有被限流，就将其转发给API服务器。如果请求被限流， 限流器会向客户端返回429响应码（请求太多）来报错。同时， 请求要么被丢弃，要么被转发到队列中。

分布式系统中的限流器

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

竞争条件。同步问题。

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

从Redis中读取计数器的值。检查计数器值加1后是否超过了阈值。如果没有，就把计数器的值在Redis中加1。

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

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

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

Lua脚本的优势：
原子性：:Lua脚本在Redis中是原子性执行的，这意味着脚本中的所有操作要么全部成功，要么全部失败，不会出现中间状态，有效避免了竞争条件。
性能：:通过在Redis服务器端执行脚本，可以减少网络往返时间，提高整体性能。

Redis有序集合的优势：
并发控制：:利用有序集合的特性，可以按照时间戳或唯一ID等排序的元素来控制访问顺序，实现一种公平的并发访问机制。
减少阻塞：:相比于传统的锁机制，有序集合可以更灵活地处理并发，减少不必要的阻塞，例如在处理分布式锁时，可以通过有序集合按顺序释放锁。

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

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

性能优化

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

对限流器而言，设置多数据中心是至关重要的，因为离数据中心越远， 响应延时越高。大多数云服务提供商在全球设置了很多边缘服务器。通过最终一致模型来同步数据。

监控

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

流量限制算法有效。流量限制规则有效。

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

第四步：总结

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

代币桶算法。漏桶算法。固定窗口计数器算法。滑动窗口日志算法。滑动窗口计数器算法。

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

硬流量限制与软流量限制。硬流量限制是指请求数量不能超过阈值。 软流量限制是指请求数量可以在短时间内超过阈值。在不同层级做流量限制。在本文中，我们只讨论了在应用层（HTTP层，第7层）做流量限制。流量限制也可以用在其他层。例如，你可以使用Iptables（IP层，第3层）并根据IP地址来限流。避免被限流。用以下最佳实践来设计你的客户端：
使用客户端缓存，避免频繁地调用API。理解流量限制，不要在短时间内发送太多请求。添加代码以捕获异常或错误，使客户端可以优雅地从异常中恢复。添加代码以捕获异常或错误，使客户端可以优雅地从异常中恢复。

后记

恭喜你已经看到这里了。 给自己一些鼓励。干得不错！

参考

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