我在比较令牌桶和固定窗口速率限制算法,但在这两种算法中都与流量突发有点混淆。
假设我想将流量限制为 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
这里也有类似的问题
两种算法是否都存在这个问题,还是我的理解存在差距?
我对那些算法也有同样的困惑。
令牌桶的技巧是桶大小(b)和填充率(r)不必相等。
对于您的特定示例,您可以将 Bucket 大小设置为 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
其他选项:
不同之处在于令牌重新填充到桶中的方式。
如果我们要以固定的时间间隔准确地重新装满整个桶,那么它将类似于固定窗口。
然而,在令牌桶的情况下,可以修改令牌重新填充的逻辑以能够控制突发。 让我们考虑以下示例
最大容量 - 10 InitialTokens - 10 充值率 - 每分钟 10 个代币。
Taking your example
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 个代币/分钟可以传播到类似 每 12 秒 2 个令牌。 这样我们现在有
Time Requests AvailableTokens
10:00:00 0 10 (initial 10 tokens)
10:00:58 10 0
10:01:00 0 2
10:01:01 10 0 (rejected)
10:01:12 0 4 (2 tokens added)
10:01:24 0 6 (2 tokens added)
10:01:36 0 8 (2 tokens added)
10:01:48 0 10(2 tokens added)
bucket4j 将此实现称为贪心填充。 bucket4j-笔芯 但它也会注意避免在两个不同窗口的末尾和开始时出现 10 + 10 个请求。