Rate limiting algorithms explained: Token Bucket vs Sliding Window vs Fixed Window

Rate limiting algorithms dictate how an API behaves under heavy load. The three main algorithms are Fixed Window, Token Bucket, and Sliding Window. Fixed Window is the simplest, counting requests in a set time window. When the limit is reached, further requests are blocked until the window resets. This can cause boundary spikes, where a client sends requests right before and after the window boundary, exceeding the limit within a short period.

Token Bucket allows bursts by giving each client a bucket of tokens that refill at a constant rate. Each request costs one token, so if the bucket is empty, the request is denied. This lets clients send short bursts above the average rate. Sliding Window is similar to Fixed Window but the window slides continuously over the last N seconds, counting requests within this sliding window.

This eliminates boundary spikes and provides smooth rate limiting. GCRA (Generic Cell Rate Algorithm) is used in telecom networks, tracking the theoretical arrival time of the next allowed request for very smooth and memory-efficient rate limiting. Leaky Bucket is another approach where requests enter a bucket that leaks at a constant rate, producing a constant output rate regardless of input spikes.

In summary, Fixed Window is simple but prone to boundary spikes, while Token Bucket is usually the better default for bursty traffic with natural bursts allowed. Sliding Window offers smooth behavior without boundary spikes. GCRA provides the smoothest rate limiting for high-throughput APIs. Leaky Bucket is useful for background jobs or APIs needing a constant processing rate. The choice depends on the specific traffic pattern and rate limiting requirements.