Rate Limiting
Rate limiting controls how often a user or system can perform an action, such as calling an API. When the limit is exceeded, an API usually returns 429 Too Many Requests.
1. Fixed Window
What it is: A counter for a separate, fixed time block.
How it works: Count requests during the block. Reject requests after the limit is reached. Start a fresh counter for the next block.
Example: Allow 5 requests in each clock minute. After 5 requests, wait until the next minute.
Weakness: 5 requests just before the minute changes and 5 just after it can produce 10 requests almost together.
2. Sliding Window Log
What it is: An exact count of requests in a moving time interval.
How it works: Store accepted-request timestamps. Remove timestamps older than the interval. Allow a request only if the remaining count is below the limit.
Example: Allow 5 requests in the last 60 seconds. A request at 12:00:10 stops counting at 12:01:10, freeing one slot.
Tradeoff: Accurate, but stores individual timestamps and needs cleanup. It can still allow all 5 requests together.
3. Sliding Window Counter
What it is: An approximate sliding window using two counters.
How it works: Add the current-window count to a weighted portion of the previous-window count. As time passes, the previous window contributes less.
Estimate = current count + previous count × overlap fraction
Example: Halfway through a minute, with 8 requests in the previous minute and 2 in the current minute: 2 + 8 × 0.5 = 6 estimated requests.
Tradeoff: Uses less memory than a log, but the count is approximate.
4. Token Bucket
What it is: A bucket of permission tokens that refill over time.
How it works: Each request spends a token. Allow it if enough tokens exist; otherwise reject it. Unused tokens accumulate up to the bucket's capacity.
Example: Capacity 5, refill 1 token/second. You can send 5 requests immediately from a full bucket. After using them, wait 1 second for another token.
Key idea: Capacity controls the burst; refill rate controls sustained usage. This does not enforce an exact rolling-window count.
5. Leaky Bucket
What it is: In the queue-based version, a bucket of waiting work that drains at a controlled pace.
How it works: Put incoming requests in a bounded queue. Release them at a steady rate. Reject new arrivals when the queue is full.
Example: Five email jobs arrive together. Release one per second instead of sending all five immediately.
Tradeoff: Smooths outgoing work, but queued work must wait. A queue needs a scheduler to enforce the rate.
Note: A leaky-bucket meter can instead accept or reject requests without storing an actual queue.
Remember the Difference
| Algorithm | Main idea |
|---|---|
| Fixed window | Count within separate time blocks |
| Sliding window log | Count exact recent timestamps |
| Sliding window counter | Estimate recent activity with weighted counters |
| Token bucket | Save permission and allow bursts |
| Queue-based leaky bucket | Queue work and release it steadily |
Important: Rate limits control how often work starts. Concurrency limits control how much work runs at once. Multiple servers need shared, atomic limit checks to enforce one combined allowance.