What is it?
- Rate Limiting
- The act of limiting the number of requests sent to or from a system. Limit the number of operation for some amount of time. (3 requests in 1 minute)
- This is often used to prevent DoS — Denial of Service attacks or DDoS
- Rate limiting can be enforced at IP-address level, user-account level or even region level
- Example: Google Translate API quote for the selected plan, LeetCode code running limit.
- DoS attack
- Short for "denial-of-service attack"
- An attack in which a malicious user tries to bring down a system
- DDoS attack
- Short for "distributed denial-of-servcie attack"
- A type of DoS attack in which the traffic flooding the target system comes from many different sources
How to implement?
We can use Redis — to store user number of request, or when the last request was made, and even different query. And depending on these decide if we can redirect request further or return 429 Too many requests.
Algorithms
Algorithm | Burst Allowed? | Memory Usage | Complexity |
Token Bucket | Yes | Low | Low |
Leaky Bucket | No | Low | Low |
Fixed Window | No | Very Low | Very Low |
Sliding Log | Yes | High | High |
Sliding Counter | No (Smooth) | Low | Medium |
- Token Bucket: A bucket holds tokens added at a fixed rate; requests take a token to pass. It effectively allows for traffic bursts.
- Leaky Bucket: Requests enter a bucket and "leak" out at a constant, steady rate. It is ideal for smoothing out spikes into a regular flow.
- Fixed Window: Counts requests within set time blocks (e.g., 1 minute). It is simple to implement but can allow double the limit at window boundaries.
- Sliding Window Log: Stores timestamps for every request and checks the last X seconds. It is perfectly accurate but very memory-intensive.
- Sliding Window Counter: Uses a weighted average of the current and previous window counts. It offers a smooth rate limit with low memory overhead.
