设计限流器

在网络系统中，限流器用于控制客户端或者服务端发送的流量的速率。

例如：

• 个用户每秒只能发布不超过两篇帖子。
• 同一个 IP 地址每天最多可 以创 建 10 个账号。
• 在同一个设备上每周可以兑奖不超过 5 次。

加限流器好处：

• 预防由拒绝服务攻击引起的资源耗尽问题
• 降低成本
• 预防服务器过载

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

先理清楚应该创建何种限流器

系统需求总结如下：

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

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

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

在哪里实现限流器

既可以在客户端也可以在服务器端实现限流器。

• 放客户端
• 放服务器
• 创建一个中间件作为限流器，用它来限制对API的请求，而不是把限流器放在API服务器上

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

流量限制算法

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

代币桶算法

代币桶是一个有预定义容量的容器。代币按照预定的速率被放入桶中。 一旦桶被装满，就不再往里面添加代币 。

代币桶算法有两个参数：

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

漏桶算法

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

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

漏桶算法有两个参数：

• 桶大小：它等千队列大小。队列中保存了要按固定速率处理的请求。
• 出栈速度：它定义 了 每秒可以处理多少个请求，通常以秒为时间单位。

固定窗口计数器算法

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

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

滑动窗口日志算法

固定窗口计数器算法有一个重大问题：在时间窗口的边界上，它允许更多的请求通过。滑动窗口日志算法解决了这个问题。它

就像一个固定时间范围，在数轴上移动。无论怎么移动范围内的请求数都不超过上限。

滑动窗口计数器算法

滑动窗口计数器算法是组合了固定窗口计数器算法和滑动窗口日志算法的方法。

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

当前窗口的请求数＋之前窗口的请求数 x 滑动窗口和之前窗口的重合率

可以算出滑动窗口所允许的请求数量为 6.5 个 (3+ 5x 0.7=6.5 ) ，对这个数字可以向上或者向下取整。。

在我们的例子中，将它向下取整为6。

因为限流器每分钟最多允许通过 7 个请求 ，所以现在的 请求可以通过 。

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

高层级架构

应该在哪里存储计数器？存在内存上，用Redis。

Redis 提供了命令。INCR和EXPIRE。

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

三 设计继续深入

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

流量限制规则

规则一般都写在配置文件中并保存在硬盘上。

超过流量的限制

请求被限流，API会给客户端返回HTTP响应码 429 请求过多。

也有可能会把超过阈值的请求放入队列，之后再处理。

限流器返回的 HTTP 头：

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

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

详细设计

下面图展示了系统的详细设计：

分布式系统中的限流器

单服务器环境创建一个限流器并不难，要将限流器系统扩展，支持多个服务器和并发线程

竞争问题：

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

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

同步问题：

同步是分布式系统中需要考虑的另一个重要因素 。为了支持百万量级的用户 ，一个限流器有可能不足以处理所有的流量。当使用多个限流器时，限流器之间就必须同步 。

通常使用中心化的数据存储，多个限流器使用同一个Redis。

性能优化

1. 设置多数据中心，离数据中心越远，响应延时越高，多数云服务提供商在全球设置了很多边缘服务器 。
2. 通过最终一致模型来同步数据

监控

在设置好限流器之后，收集数据来检查限流器是否有效是很重要的。确保，流量限制算法有效， 确保流量限制规则有效。