# 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]]