Rate Limiting Algorithms
Rate limiting is crucial in system design. Without it, servers can get hammered by DDoS attacks, brute force attempts, or even just poorly behaved clients retrying too often. The idea is to control how many requests can hit a service in a given time window so things stay fair and stable.
When it comes to actually implementing rate limiting, the choice of algorithm matters a lot. Different algorithms trade off between simplicity, precision, memory, and how well they handle bursts. Here are the most common ones:
Fixed Window Counter
How it works: For each window of time (say, one second), you keep a counter in memory or Redis. Every request increments the counter. If the counter exceeds the limit, requests are rejected. At the end of the window, the counter resets back to zero.
Pros: Very simple to implement and cheap.
Cons: If requests come at the end of one window and the start of the next, you can get almost double the allowed requests.
Use case: Works fine for simple APIs where strict accuracy is not critical, like free-tier limits.
Sliding Window Log
How it works: Instead of a counter, you store the timestamp of each request in a log (array, list, or Redis sorted set). When a new request arrives, you remove old timestamps that are outside the window and count the remaining ones. If the count exceeds the limit, reject the request.
Pros: Very precise and prevents burst exploits.
Cons: Uses more memory and can get slower at high scale because you are storing timestamps.
Use case: High-value APIs where accuracy is more important than performance, such as financial transactions.
Sliding Window Counter
How it works: Split the time window into smaller buckets (like seconds inside a minute). For a given request, sum the current bucket plus a weighted share of the previous bucket to estimate the rate. This smooths out the sharp edges of fixed windows without storing every timestamp.
Get AK’s stories in your inbox
Join Medium for free to get updates from this writer.
Pros: Uses less memory than a full log and is smoother than fixed windows.
Cons: It is still an approximation, but usually good enough in practice.
Use case: Popular choice for web APIs at scale because it balances precision and efficiency.
Leaky Bucket
How it works: Imagine a queue where requests are added. They leak out at a fixed rate (like water dripping). If the queue is full when a request arrives, that request is dropped. This keeps the output rate steady, regardless of how bursty the input is.
Pros: Ensures a smooth and predictable outflow of requests.
Cons: Bursts are not handled well because the queue fills up quickly.
Use case: Good for workloads that need steady processing, like payment systems or video streaming.
Token Bucket
How it works: A bucket is filled with tokens at a steady rate. Each incoming request consumes a token. If tokens are available, requests are allowed instantly. If the bucket runs dry, requests are rejected until tokens refill. This lets you handle short bursts but still enforce an overall rate.
Pros: Flexible and handles bursts gracefully.
Cons: Slightly more complex to implement than leaky bucket.
Use case: Perfect for APIs where occasional bursts are acceptable, like API gateways (GitHub API uses this).
Most real-world systems stick to one of these five. Sometimes you combine rate limiting with concurrency limits, quotas per user or IP, or even adaptive throttling. But for the majority of use cases, picking the right algorithm from this list is enough.
