Design a Rate Limiter

Token bucket, leaky bucket, sliding window logs, and Redis Lua enforcement.

8 min readSystem Design for SREProvision

Why Rate Limiting?

Rate limiting controls the number of requests a client can make in a given time period. It protects backend services from traffic spikes, prevents abuse, ensures fair resource allocation, and maintains system stability during incidents.

Rate Limiting Algorithms

Algorithm	Memory	Accuracy	Burst Handling
Token Bucket	Low	Good	Allows bursts up to bucket size
Leaky Bucket	Low	Good	Smooths bursts
Fixed Window	Low	Coarse	Edge spike problem
Sliding Window Log	High	Exact	Smooth
Sliding Window Counter	Low	Good	Smooth

Token Bucket

Token bucket is the most widely used algorithm. Tokens are added to a bucket at a fixed rate. Each request consumes a token. If the bucket is empty, the request is rejected. The bucket has a maximum size, allowing controlled bursts.

Token bucket implementation


import time

class TokenBucket:
    def __init__(self, rate: float, capacity: int):
        self.rate = rate          # Tokens per second
        self.capacity = capacity  # Maximum tokens
        self.tokens = capacity
        self.last_refill = time.time()
    
    def allow(self) -> bool:
        now = time.time()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last_refill = now
        
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

# 10 requests per second, burst of 20
limiter = TokenBucket(rate=10, capacity=20)

Token bucket allows bursts up to the bucket size while maintaining a steady rate. This is ideal for APIs where clients occasionally need burst capacity.

Sliding Window Log

Sliding window log tracks the timestamp of each request. When a new request arrives, it removes timestamps older than the window and counts remaining timestamps. This provides exact rate limiting without the edge spike problem of fixed windows.

Redis sliding window rate limiter


-- KEYS[1] = rate limit key
-- ARGV[1] = window size in milliseconds
-- ARGV[2] = max requests
-- ARGV[3] = current timestamp in milliseconds

local key = KEYS[1]
local window = tonumber(ARGV[1])
local limit = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

-- Remove entries outside the window
redis.call('ZREMRANGEBYSCORE', key, 0, now - window)

-- Count requests in current window
local count = redis.call('ZCARD', key)

if count < limit then
    -- Add current request
    redis.call('ZADD', key, now, now .. math.random())
    redis.call('PEXPIRE', key, window)
    return 1  -- Allowed
else
    return 0  -- Denied
end

This Lua script runs atomically in Redis. It maintains a sorted set of request timestamps, removes expired entries, and checks if the count is within the limit.

Distributed Rate Limiting

When running multiple rate limiter instances, they must share state. Redis is the most common shared state store. Each rate limiter instance checks Redis before allowing a request. Redis operations are fast enough (< 1ms) to not impact request latency.

Distributed rate limiting architecture


Client ──► Load Balancer ──► Rate Limiter Instance 1 ──┐
                        │                               │
                        ├──► Rate Limiter Instance 2 ──┼──► Redis
                        │                               │  (shared state)
                        └──► Rate Limiter Instance 3 ──┘

All instances check Redis for the same key:
  rate_limit:user:12345 → { count: 47, window: ... }

Redis atomic operations ensure no race conditions.

Redis provides the shared state for distributed rate limiting. Atomic operations (INCR, ZADD) prevent race conditions between instances.

Where to Place Rate Limiters

API Gateway — Centralized, handles all traffic. Best for global limits.
Service mesh — Per-service rate limits at the sidecar level.
Application level — Fine-grained limits based on business logic.
CDN edge — Rate limit before reaching origin. Fastest.

Rate limit at multiple layers

Use CDN-level rate limiting for DDoS protection, API Gateway for global limits, and service-level for fine-grained business limits. Each layer provides defense in depth.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 4 · Provision

System Design Interviews