CODEWITHSUNDEEP
algorithmthrottlingrate-limiting
Vip
Vip

Reputation: 1616

Token bucket vs Fixed window (Traffic Burst)

I was comparing Token bucket and Fixed window rate limiting algorithm, But a bit confused with traffic bursts in both algorithm.

Let's say i want to limit traffic to 10 requests/minute.

In Token bucket, tokens are added at the rate of 10 tokens per minute.

 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

Now if we see at timestamp 10:01:01, in last minute 20 requests were allowed, more than our limit.

Similarly, With Fixed window algorithms. Window size: 1 minute.

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

Similar problem is here as well.

Does both the algorithms suffer from this problem, or is there a gap in my understanding?

Upvotes: 14

Views: 7564

Answers (3)

Damian J
Damian J

Reputation: 51

Seems that I don’t have reputation enough to reply to comments. But token bucket and fixed window are equivalent. For the people that say that you can adjust the bucket size and the refresh rate, well, why can’t you can adjust the window size and the quota?

If you have a bucket of 2 with a refresh rate of 12 seconds, you can also have a window size of 12 seconds with a quota of 2.

The only difference is that one counts from 0 up to a limit and the other from a limit down to 0 haha

Upvotes: 2

Nayanava
Nayanava

Reputation: 129

The difference lies in the way tokens are refilled in the bucket.

If we were to refill the entire bucket exactly at fixed intervals, then it would be analogous to a Fixed Window.

However in case of a Token Bucket, the logic of the refilling of tokens can be modified to be able to control the burst. Let's consider the following example

MaximumCapacity - 10 InitialTokens - 10 refill rate - 10 tokens per minute.

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

This behaviour is analogous to Fixed Window, however we can split the token addition into granular intervals of refill time. In our case 10 tokens/minute could be spread to something like 2 tokens every 12 seconds. In that way we now have

 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 calls this implementation greedy-refill. bucket4j-refill But it will also take care of avoiding 10 + 10 requests at the end and start of two different windows.

Upvotes: 6

Mikhail Romanov
Mikhail Romanov

Reputation: 1612

I had the same confusion about those algorithms.

The trick with the Token Bucket is that Bucket size(b) and Refill rate(r) don't have to be equal.

For your particular example, you could set Bucket size to be b = 5 and refill rate r = 1/10 (1 token per 10 seconds).

With this example, the client is still able to make 11 requests per minute, but that's already less than 20 as in your example, and they are spread over time. And I also believe if you play with the parameters you can achieve a strategy when >10 requests/min is not allowed at all.

 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

Other options:

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

Upvotes: 22

Related Questions