令牌桶与固定窗口（流量突发）

Question

我正在比较令牌桶和固定窗口速率限制算法，但对这两种算法中的流量突发有点困惑。

假设我想将流量限制为 10 个请求/分钟。

令牌桶中以每分钟10个令牌的速度添加令牌。

 Time      Requests AvailableTokens
10:00:00     0          10 (added 10 tokens)
10:00:58    10          0
10:01:00     0          10 (added 10 tokens)
10:01:01    10          0 

现在，如果我们在时间戳 10:01:01 看到，最后一分钟允许 20 个请求，超过了我们的限制。

类似地，使用固定窗口算法。窗口大小：1 分钟。

 Window    RequestCount IncomingRequests
10:00:00      10         10 req at 10:00:58
10:01:00      10         10 req at 10:01:01

类似的问题也在这里。

这两种算法都遇到这个问题吗，还是我的理解存在差距？

Answer 1

我对这些算法也有同样的困惑。

令牌桶的技巧是桶大小（b）和填充率（r）不必相等。

对于您的特定示例，您可以将存储桶大小设置为 b = 5，重新填充率 r = 1/10（每 10 秒 1 个令牌）。

在此示例中，客户端仍然能够每分钟发出 11 个请求，但这已经少于您的示例中的 20 个请求，并且它们随着时间的推移而分布。我还相信，如果您使用这些参数，您可以在根本不允许 >10 个请求/分钟的情况下实现策略。

 Time      Requests AvailableTokens
10:00:00     0          5 (we have 5 tokens initially)
10:00:10     0          5 (refill attempt failed cause Bucket is full)
10:00:20     0          5 (refill attempt failed cause Bucket is full)
10:00:30     0          5 (refill attempt failed cause Bucket is full)
10:00:40     0          5 (refill attempt failed cause Bucket is full)
10:00:50     0          5 (refill attempt failed cause Bucket is full)
10:00:58     5          0 
10:01:00     0          1 (refill 1 token)
10:01:10     0          2 (refill 1 token)
10:01:20     0          3 (refill 1 token)
10:01:30     0          4 (refill 1 token)
10:01:40     0          5 (refill 1 token)
10:01:49     5          0 
10:01:50     0          1 (refill 1 token)
10:01:56     1          0

其他选项：

• b = 10 且 r = 1/10
• b = 9 且 r = 1/10