Token Bucket vs Bursty Rate Limiter

This post is created under the impression that there is a wrong opinion on fixed window rate limiting approach.

As author of rate-limiter-flexible Node.js package I got some experience using different rate limiter approaches in different environments.

Extended version of this post with description of Token Bucket and Fixed Window rate limiting approach was originally posted on Medium. So if you want more details, read extended vesion.

Fixed Window rate limiter is slightly better than Token Bucket. Here is why.

Roman Voloboev ・ Apr 9, 2020 ・ 5 min read

Medium

TL;DR: Fixed Window rate limiter with traffic burst allowance can easily replace Token Bucket and even bring performance boost.

Main difference

Token Bucket allows traffic burst by nature. If tokens are not taken during some period of time, token bucket is refilled partly or completely. More tokens in a bucket, higher traffic burst allowed.

Bursty Rate Limiter like from rate-limiter-flexible package actually consists of two Fixed Window limiters: one for constant rate like 2 requests per second and another for traffic burst allowance like 3 requests per 5 seconds.

Visual traffic comparison

There are two examples on Chart 1 and Chart 2 below. Order and amount of requests are the same for both. Square without background color represents not touched token/point. Green square defines consumed token and allowed action. Red square — rejected action.

Chart 1: Token Bucket with capacity 5 and fill rate 2 tokens per second.

Chart 2: BurstyRateLimiter with 2 points per second and burst allowance 3 requests per 5 seconds.

You could notice, allowed requests’ shape is not the same, but quite similar. Both allowed traffic bursts.
You could also notice, that BurstyRateLimiter allowed 5 actions in time window 5–6, but Token Bucket allowed 2 only. Token Bucket didn’t have enough tokens by that time. But it could have, if there are no requests for time window 4–5.

Benchmarks

Two Node.js packages are benchmarked: hyacinth’s TokenBucket and rate-limiter-flexible’s BurstyRateLimiter.

The aim of this benchmark is comparison of two algorithms not providing absolute truth on every of them. Results may be different on different environments.

Chart 3: 1000 requests per second from 1000 concurrent clients during 30 seconds.

Chart 4: 2000 requests per second from 1000 concurrent clients during 30 seconds.

Note, Bursty Rate Limiter from rate-limiter-flexible applies inmemoryBlockOnConsumed option. It stores blocked users in process memory until their time window’s end. It speeds up processing requests. This is not only performance boost, but also good protection against massive DDoS attacks, if your application doesn’t have one yet.

Bursty Rate Limiter can be slower, since it requires to make 2 requests to a store in particular conditions. It all depends on amount of unique users, project and environment. But it is still fast enough.

Conclusion

Bursty Rate Limiter’s advantages:

• It is more flexible in terms of central store. Fixed rate limiter implementation is relatively similar on different stores. Packages like rate-limiter-flexible or express-rate-limit provide ability to choose from several stores. It simplifies changes in your application.
• It sets exact amount of traffic burst allowance. No surprises.
• It is easier to cache known time window end to avoid extra requests to store. Not really big advantage for all applications, but still could be useful for some.

Bursty Rate Limiter’s disadvantages:

• It can be slower on high traffic like 5000 requests per second and more, as it makes 2 requests to a store sometimes. Especially, if in-memory block technique is not applied.

You can test it yourself and compare using this gist.

Thanks for reading!