# Rate Limiting Algorithms — Rate Limiting, Circuit Breakers & Resilience Patterns

Source: https://www.skillbyai.com/en/resilience-patterns/r-algorithms

> Compare fixed window, sliding window and token bucket algorithms.

## Counting requests over time

**Fixed window** counts requests per calendar window (per minute, resetting at :00). It is simple and cheap, but allows bursts at boundaries: 100 requests at 12:00:59 and 100 more at 12:01:00 means 200 in two seconds. **Sliding window log** stores a timestamp per request and counts those in the last 60 seconds: exact, but memory grows with traffic. **Sliding window counter** approximates the sliding window by weighting the previous window's count by how much of it still overlaps: cheap and accurate enough for most APIs. **Token bucket** holds up to *capacity* tokens that refill at a steady *rate*; each request takes a token, so clients can **burst** up to the capacity and then are held to the average rate; it is the most common choice for APIs. **Leaky bucket** processes requests at a constant rate from a queue, smoothing bursts into steady output, which suits protecting a fixed-capacity downstream system.

## Token bucket

Allows bursts up to capacity while enforcing an average rate.

```python
import time

class TokenBucket:
    def __init__(self, rate_per_sec, capacity):
        self.rate, self.capacity = rate_per_sec, capacity
        self.tokens, self.last = capacity, time.monotonic()

    def allow(self, cost=1):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

# 10 requests/second on average, bursts of up to 50
bucket = TokenBucket(rate_per_sec=10, capacity=50)

# sliding window counter estimate:
# estimated = current_count + previous_count * (1 - elapsed_in_current / window)
```

## Tokens at a ride

A token bucket is like an amusement-park ride that hands out tokens at a fixed rate: if you saved a few, you can ride several times in a row, but once your tokens are spent you wait for new ones.

**Quiz:** Which algorithm allows short bursts while enforcing a long-term average rate?

- [ ] Fixed window with a tiny window
- [ ] No rate limiting
- [ ] Random dropping
- [x] Token bucket

*Answer:* Token bucket. Token buckets accumulate tokens up to a capacity, permitting bursts within an average rate.