如果你之前接触过后端服务，你可能听说过速率限制（Rate Limit）这个术语。

如果没有这个关键的工具包，客户端可以在任何时间点向你的服务发起无限多的请求。这会导致突然的流量激增，从而使你的服务器负载过重。

在这篇博文中，让我们回归基础，讨论四种常用的速率限制算法。

令牌桶（Token Bucket）

在其他四种算法中，令牌桶是最容易实现的之一。

让我们看看简化后的步骤。

?想象一下有一个包含 N 个令牌的桶?如果有一个请求到达，我们从桶中取出一个令牌并处理该请求?假设没有剩余的令牌，我们将丢弃该请求而不进行处理。?在每个固定的时间间隔内，我们将桶中的令牌重新补充到 N 个。

我们可以使用一个简单的哈希映射来实现这个算法。

假设每个用户每分钟只能触发四个请求。

用户ID = 123

usersBucket[userID] = 4

当收到一个请求时，我们将usersBucket[userID]中的计数器减去1。如果令牌用完了，我们就丢弃该请求。每分钟，我们将哈希映射中的计数器重置为4。

这里有一个棘手的情况：

?12:00:59：用户触发了四个请求?12:01:00：我们将令牌重置为 4?12:01:01：用户再次触发了四个请求

在上面的情况中，用户在三秒内触发了八个请求！

为了确保流量更加平稳，令牌的补充速率应该与速率限制不同。

假设我们的速率限制是每分钟四个请求。我们可以每15秒添加一个令牌，而不是每分钟添加四个令牌。这样可以防止在重置边界处突然爆发的流量。

漏桶（Leaky Bucket）

在前面的算法中，虽然我们每15秒补充一次令牌，但用户仍然可以在第14秒触发四个请求，从而导致流量突然激增。

漏桶在确保流量更平稳分布方面非常有用。

以下是简化后的步骤：

?想象一下桶底部有一个孔的桶?当一个请求到达时，我们将请求放入桶中?在每个固定的时间间隔内，一个请求从底部“漏出”并得到处理

漏桶遵循先进先出（FIFO）的概念。我们可以使用队列来实现它。

每个到达的请求不会被丢弃，而是被入队到一个桶中。在每个固定的时间间隔内，第一个到达的请求将被出队并处理。

使用漏桶，请求可以以不同的速率到达，而服务器以恒定且可预测的速率进行处理。

正如俗话说，“没有最好的解决方案，只有权衡。” 一个恒定的速率意味着漏桶以平均速率处理请求，从而导致响应时间较慢。

固定窗口（Fixed Window）

固定窗口与令牌桶类似，两者都可能遭受突然的流量激增。

同样，让我们简化步骤。假设我们要实现每分钟四个请求的速率限制：

?时间线根据每个窗口的分钟数进行划分?每个窗口包含一个计数器为 4?当一个请求到达时，我们根据时间戳的下取整来分配请求?如果请求在 12:01:45 到达，则分配到 12:01:00 窗口?如果计数器大于 0，我们减少计数器并处理请求?否则，我们丢弃请求

当所有请求在窗口边界处同时到达时，会发生流量激增

固定窗口算法最大的缺点是：

?它有可能在窗口边界附近导致突然的流量激增?如果计数器在窗口开始时用完，所有客户端都需要等待较长的重置窗口

滑动窗口（Sliding Window）

滑动窗口算法与固定窗口算法非常相似，只是它解决了上述缺点。

假设我们要实现每分钟四个请求的速率限制：

请求 5 将被处理并添加到数组中，因为在过去 1 分钟内只有 3 个请求被处理。请求 1 将被弹出。

?使用一个数组，也就是窗口，来存储已处理的请求，以及它们的时间戳?当一个请求到达时，我们遍历数组并检查在过去一分钟内处理的请求数?如果在过去一分钟内处理的请求数少于四个，我们将请求添加到数组中并处理它?随着我们遍历数组，我们弹出在一分钟前长时间处理的请求

正如你所看到的，滑动窗口算法是确保在任何给定时间点严格遵守速率限制的理想选择。

由于我们将过去 1 分钟的所有请求存储在内存中并在每次到达请求时遍历数组，所以该算法消耗更多的内存和CPU。

结论

每种算法都具有不同的优点和限制。

因此，在决定应用程序所承受的权衡时，了解它们的工作原理变得至关重要。