Rate Limiting Algorithms

Rate limiting caps how many requests a client can make in a period, for example 100 requests per minute per API key. It protects services from overload and abuse (scraping, brute-force logins, runaway scripts), enforces fair use between customers, and controls cost. Requests over the limit are rejected, usually with HTTP 429 Too Many Requests.

Why rate limit

Without limits, one script calling an endpoint 100,000 times a second saturates the database, response times spike for everyone, and legitimate users suffer because one bad actor took all the capacity.

• Fair use and tiers: free users get 100 requests per minute, paid users 10,000, so free traffic can't eat capacity meant for paying customers.
• Abuse prevention: credential stuffing tries thousands of passwords per second, crawlers scrape whole sites, bots create fake accounts; limits slow them to manageable levels.
• Different limits per resource: writes cost more than reads (create a post: 10/min; read posts: 1,000/min), and complex searches more than simple lookups (100/min vs 10,000/min).

Algorithms

Token bucket

Each client has a bucket holding up to B tokens, refilled at R tokens per second. A request spends one token; if the bucket is empty, it's rejected. This allows bursts up to B while enforcing an average rate of R, which matches how real clients behave. It's the most widely used algorithm.

Leaky bucket

Requests enter a queue that drains at a fixed rate; when the queue is full, new requests are dropped. Output is perfectly smooth, which suits protecting a fragile downstream, but bursts wait in the queue (added latency).

Fixed window counter

Count requests per key per fixed window (user:42:2026-10-17T10:05) and reject above the limit. Trivial with Redis INCR + EXPIRE. The flaw: a client can send the full limit at the end of one window and again at the start of the next, double the rate across the boundary.

Sliding window log and sliding window counter

• Sliding log: store a timestamp per request (a Redis sorted set) and count those in the last 60 seconds. Exact, but memory grows with the limit.
• Sliding window counter: keep counts for the current and previous fixed windows and weight the previous by how much of it still overlaps: count = current + previous × (1 − elapsed fraction). Nearly exact with two counters per key, and the common production choice alongside token buckets.

The algorithms, worked through

• Token bucket, 100 requests per minute: the bucket holds 100 tokens and gains one every 600 ms. A client can burst 100 requests at once, then must wait ~600 ms per request. Four pieces of state: capacity (max burst), refill rate (sustained throughput), current tokens and the last refill time; on each request add elapsed × rate tokens (capped), then spend one or reject. Bursts match real usage: a dashboard load fires 20 calls at once, a background job sends a batch of 50.
• Leaky bucket, 10 per second with a queue of 100: requests queue and drain at exactly 10/s, so 50 simultaneous requests take 5 seconds; when the queue is full, new requests overflow and fail. Output is smooth, which protects downstream systems that can't take spikes, such as a payment gateway that accepts only 5 transactions per second. The cost is latency: requests wait behind earlier arrivals.
• Fixed window's boundary problem: with 100 per minute resetting at 00:00:00, a client sends 100 at 00:00:59 and another 100 at 00:01:01: 200 requests in 2 seconds.
• Sliding window log: at 14:32:45 count requests from 14:31:45 to 14:32:45; one second later the window has moved one second. It needs every timestamp (100 per user for 100/min; 10,000 for 10,000/hour). Redis sorted sets fit: timestamps as scores, ZREMRANGEBYSCORE drops old entries, ZCARD counts.
• Sliding window counter: keep only this minute's and last minute's counts and weight the previous one by how much of it still overlaps the window. At 14:32:45 (45 s into the minute), with 80 requests last minute and 30 this minute: 80 × (15/60) + 30 = 50 < 100, so allow. Memory drops from O(limit) to O(1); the error is small for smooth traffic and larger for sharp bursts near a boundary.

import time

class TokenBucket:
    """Allows bursts up to `capacity`, refills at `rate` tokens per second."""

    def __init__(self, capacity: float, rate: float):
        self.capacity, self.rate = capacity, rate
        self.tokens, self.last = capacity, time.monotonic()

    def allow(self, cost: float = 1.0) -> bool:
        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

def sliding_window_counter(prev_count: int, curr_count: int, seconds_into_minute: float, limit: int) -> bool:
    """Approximate a 60 s sliding window from two fixed-minute counters."""
    weight = (60 - seconds_into_minute) / 60          # share of the previous minute still in the window
    return prev_count * weight + curr_count < limit

bucket = TokenBucket(capacity=100, rate=100 / 60)       # 100 per minute: one token every 600 ms
print(sum(bucket.allow() for _ in range(150)))          # 100: the burst is capped at capacity
print(sliding_window_counter(80, 30, 45, 100))          # True: 80*0.25 + 30 = 50 < 100

-- Sliding window log in Redis (Lua runs atomically): KEYS[1]=key, ARGV = now_ms, window_ms, limit, request_id
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, ARGV[1] - ARGV[2])   -- drop entries older than the window
if redis.call('ZCARD', KEYS[1]) < tonumber(ARGV[3]) then
  redis.call('ZADD', KEYS[1], ARGV[1], ARGV[4])
  redis.call('PEXPIRE', KEYS[1], ARGV[2])
  return 1                                                       -- allowed
end
return 0                                                         -- rejected

Distributed rate limiting

With many API servers, limits must be shared, or each server allows the full limit. The usual design keeps counters in Redis, updated atomically with a Lua script or INCR, sharded by key. Considerations:

• Atomicity: read-check-update must be one operation (Lua script), or concurrent requests slip through.
• Latency: a Redis call per request adds ~1 ms; for very high volume, keep local token buckets per server with a share of the limit, synced periodically, accepting slight inaccuracy.
• Failure mode: decide whether to fail open (allow traffic if Redis is down; usual for APIs) or fail closed (block; for security-critical limits like login attempts).
• Where to enforce: at the API gateway or edge for coarse limits (per IP, per key), deeper in services for expensive operations.

Centralized counter vs local counting

Per-server limits leak: two servers each allowing 100/min let a client spread across both send 200. A central Redis counter fixes it, with INCR atomic so there are no races:

def is_allowed(user_id, limit):
    key = f"rate_limit:{user_id}:{current_minute()}"
    count = redis.incr(key)                 # atomic increment, returns the new value
    if count == 1:
        redis.expire(key, 60)               # first request in this window sets the TTL
    return count <= limit
# A fixed window: pair it with the sliding-window counter above to avoid boundary bursts.

Redis is now a dependency on every request (run Redis Cluster or replicas, and decide whether to fail open or closed if it's down), and each check costs a network round trip. The alternative is local counting with periodic sync: each server counts locally and pushes its count to Redis every second (server 1 adds 23, server 2 adds 19, global = 42), allowing a request while local + global < limit. Redis calls drop from one per request to one per second per server, at the cost of overshoot during the sync interval (two servers could each allow 60 before syncing: 120 against a limit of 100).

Choosing an algorithm

In an interview: start from the resource you're protecting and give different endpoints different limits; pick the algorithm (token bucket for a Twitter-like API, where someone writes 5 tweets in a minute then nothing for an hour); for distribution, use Redis with atomic operations and mention the latency trade-off and local-sync alternative; and cover the user experience: 429 with `Retry-After`, logging violations to spot abuse, and higher limits for authenticated users than anonymous traffic.

What to limit by

• API key or user ID for fair use and plan tiers (free: 60/min, paid: 1,000/min).
• IP address for unauthenticated endpoints, with care for shared IPs (offices, mobile carriers).
• Endpoint cost: a search or report export can cost 100× a simple read; weight requests or use separate limits.
• Global limits to protect a dependency (only 500 calls/s to a payment provider), regardless of who's calling.

Telling clients

Return 429 with a Retry-After header, and expose remaining budget with headers like RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset. Well-behaved clients then back off instead of hammering. See timeouts and retries.