令牌桶与固定窗口(交通突发)

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