A rate limiter serves as a reverse proxy (if it serves for multiple services), or servers as a middleware of a server

For

• Reducing Cost (e.g. an API uses third party APIs)
• Preventing Resource Starvation (e.g. from DoS)
• Security (e.g. user password retry)

Algorithm Comparison

✅ In common code example (When the bucket is not full.) | ❌ | ❌ | ❌ | | Avoid Over-Accepting | ✅ | ✅ | ❌ | ✅ | ✅  (Cloudflare: It is approximate) | | Avoid Over-Rejecting | ✅ | ✅ | ❌ | ❌ | ❌ | | Time Complexity (per request, Redis implementation) | O(1) | O(1) | O(1) | O(log n + m)

(n number of timestamps, m the number of outdated timestamps) | O(1)

(n ≤ 3) | | Memory Usage (data)

(int64/float64 → 8 bytes, timestamp → 8 bytes) | ✅ ~8 bytes x 2 = 16 bytes | ✅ ~8 bytes x 2 = 16 bytes | ✅ ~8 bytes x 2 = 16 bytes | ❌ ~8 bytes x N requests | ✅ ~8 bytes x 2 = 16 bytes |

Token Bucket

• Each request consume one token (a quota of permission) from the bucket.
• Bucket Size: A bucket holds tokens. It determines how much burst can be served instantly. It could aligns with limited RPS.
• Refill Rate: A refiller, a rate puts tokens into the bucket. (e.g. 2 tokens per ****second.) It usually aligns with sustained RPS. It controls the system won’t have constant bursts.

Burst Request

Example

• Token Bucket: BucketSize = 4, RefillRate = 2 tokens/sec
• Fixed Window Counter: Rate = 2 requests/sec

Token Bucket can set sudden burst request to 4 requests, allowing for setting system’s both limit RPS and stable RPS, but Fixed Window Counter only provides fixed rate for system’s stable RPS.

Avoid Over-Rejecting ✅

If requests arrive at: T = 0.1s, T = 0.2s, T = 0.9s, T = 1.1s

If Token Bucket: BucketSize = 2, RefillRate = 2 tokens/sec

It gives fine-grained refill based on elapsed time from last request.