Rate Limiting Algorithms
Rate limiting is a strategy for limiting network traffic. It sets a cap on how often someone can repeat an action within a certain timeframe – for instance, trying to log in to an account. Rate limiting can help stop certain kinds of malicious bot activity, reduce strain on web servers, and ensure fair usage.
1. Why Rate Limit?
- Prevent DoS Attacks: Stop attackers from flooding the system with requests.
- Cost Control: Prevent excessive use of resources (e.g., paid API calls).
- Fairness: Ensure all users get a fair share of resources.
2. Common Algorithms
Token Bucket
A bucket holds tokens. Tokens are added at a fixed rate. Each request consumes a token. If the bucket is empty, the request is dropped.
- Pros: Allows for bursts of traffic. Memory efficient.
- Cons: Tuning the bucket size and refill rate can be tricky.
Leaky Bucket
Requests enter a bucket (queue). They are processed (leak) at a constant rate. If the bucket is full, new requests are discarded.
- Pros: Smooths out bursts into a stable outflow.
- Cons: Bursts of traffic can fill the queue and cause recent requests to be dropped.
Fixed Window Counter
The timeline is divided into fixed windows (e.g., 1 minute). A counter tracks requests in the current window. If the counter exceeds the limit, requests are dropped until the next window starts.
- Pros: Simple to implement.
- Cons: Traffic Spike at Edges: If a user sends all requests at the end of minute 1 and the start of minute 2, they can double the allowed rate for a short period.
Sliding Window Log
Keeps a log of timestamps for every request. When a new request comes in, remove all outdated timestamps. If the log size is less than or equal to the limit, allow request.
- Pros: Very accurate.
- Cons: High memory usage (stores a timestamp for every request).
Sliding Window Counter
A hybrid approach. It approximates the number of requests in the rolling window using the weighted average of the previous window and the current window.
- Formula:
Requests = (Requests in Prev Window * Overlap %) + (Requests in Current Window) - Pros: Memory efficient and handles boundary spikes well.
3. Distributed Rate Limiting
In a distributed system with multiple servers, rate limiting becomes harder.
- Race Conditions: Two servers might read the counter at the same time, see it's below the limit, and both increment it, effectively allowing one extra request.
- Synchronization: Using a centralized store like Redis (with Lua scripts for atomicity) is a common solution.
programming/system-design-interview-basics programming/distributed-systems programming/load-balancing