限流器 (Rate Limiter) 是什么? 有哪些限流策略?

过去一周在推特上，看到许多人在讨论 Upstash 的开源限流器 (Rate Limiter) 套件(GitHub 连结)，让人可以非常轻松地做限流(连结)，因此这篇来聊聊限流器。

限流器 (Rate Limiter)是什么？

限流器 (Rate Limiter) 顾名思义，是用来限制流量的。在全端的世界中，限流器可能是用来限制来自客户端的请求，或者服务对其他服务发送请求时，也可以用限流器来限流。举例来说，可以从 IP 的角度，限制每个 IP 每天的请求数；或者以使用者为维度，来限每个使用者在某段时间的请求数量。

限流器的好处:

一来可以阻挡像是 DoS (Denial of Service) 攻击，避免伺服器过载；
二来可以降低成本，特别是如果你有用第三方 API，流量大起来帐单费也会变很可观。

限流器多半不会在客户端实作，因为请求在客户端比较容易被伪造；所以一般可能会放在伺服器端，或者是放在 API Gateway；或者像是 Upstash 的这个开源套件，是放在 Edge 上。

限流有几种策略，一般常见做法包含：

令牌桶（Token Bucket）
漏桶（Leaky Bucket）
固定窗口（Fixed Window）
滑动窗口（Sliding Window）

限流器三种策略

而 Upstash 的开源限流器，提供了令牌桶、固定窗口，以及滑动窗口三种策略，同时分析了这三种策略的优缺点。

令牌桶（Token Bucket）

首先来谈令牌桶（Token Bucket），可以想像一个装满 {maxTokens} 个令牌的水桶，它会以每隔 {interval} 时间以 {refillRate} 速率，自动补充相对应的令牌。每次请求都会从水桶中取走一个令牌，如果水桶中没有令牌，则请求会被拒绝。

这种做法的优点在于能够让突发性的请求高峰变平滑，让系统可以用稳定的速率处理请求。如果将 maxTokens 设置得比 refillRate 更高，可以允许系统在一开始承担更高的请求。而缺点则是运算成本比较高。

固定窗口 (Fixed Window)

固定窗口 (Fixed Window) 的做法是，将时间划分为固定窗口。例如，每个窗口为 10 秒。当有新的请求进入时，将使用当前时间来判断所属窗口，并增加一个计数器。如果计数器超过设定的限制，该请求就会被拒绝。

固定窗口的优点包含，在数据量和计算成本上节省、较新的请求不会因为过去的高流量突发而延迟。但也有一些缺点，例如可能会导致窗口边界处的高流量突发，以及如果许多用户试图在一个新窗口开始时，访问你的伺服器，就会引发请求堵塞。

滑动窗口 (Sliding Window)

而滑动窗口 (Sliding Window)，是建立在固定窗口的基础上，但与固定窗口不同的是，它采用了滑动的窗口机制。举例来说，我们设定每分钟 10 个请求的限流。如同固定窗口的作法，我们将时间切分为 1 分钟的区间。第一个窗口将从 00:00:00 到 00:01:00。假设当前时间为 00:01:15，并且在第一个窗口中收到了 4 个请求，在当前窗口中收到了 5 个请求。用来判断请求是否该通过的近似计算方法如下：

limit = 10

// 4 个请求来自旧的窗口，把它们放入权重，同时加上当前的窗口
rate = 4 * ((60 - 15) / 60) + 5 = 8

return rate < limit // True 代表我们会让请求通过

滑动窗口的优点在于，解决了固定窗口演算法中因窗口边界导致的问题。但同时会造成存储和运算耗费更大。并且因为这做法，假设先前窗口中的请求流是均匀的，因此虽然滑动，实际上是近似而非完全准确 (但在大多数情况下这并不会构成大问题)。