Rate Limiting 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.

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.

त्वरित जाँच: Which algorithm allows short bursts while enforcing a long-term average rate?

• Fixed window with a tiny window
• No rate limiting
• Random dropping
• Token bucket