What is rate limiting and what algorithms are used to implement it?

Short answer

Rate limiting caps how many requests a client can make in a window to protect services from abuse, fair-share resources, and control costs. Common algorithms: token bucket (allows bursts up to a cap while refilling steadily), leaky bucket (smooths traffic to a fixed rate), fixed window (simple counter per block, but allows boundary bursts), and sliding window log or counter (accurate but more memory). Pick based on whether you need to allow bursts and how much boundary accuracy matters.

Detailed explanation

Rate limiting sits at the edge — API gateway, load balancer, or middleware — and decides whether to allow, delay, or reject a request. Token bucket: a bucket holds tokens; each request consumes one; tokens refill at a steady rate up to a max. Allows bursts up to the bucket size while enforcing a long-term average — good for APIs that permit occasional spikes. Leaky bucket: requests enter a queue and leave at a fixed rate — smooths bursty traffic into a constant flow, useful for downstream systems that cannot handle spikes. Fixed window: count requests per fixed interval (e.g., per minute). Simple and memory-efficient but a client can send 2x the limit by bursting at the window boundary. Sliding window: tracks timestamps of recent requests (log) or uses weighted overlapping windows (counter) — accurate, no boundary burst, but uses more memory. State must be shared across servers for a distributed system — typically stored in Redis with atomic INCR + EXPIRE, or a dedicated rate-limit service. Return 429 Too Many Requests with a Retry-After header. Apply per-user, per-IP, per-API-key, or per-tenant depending on the fairness model.

Common mistakes

• Only naming one algorithm without comparing trade-offs.
• Forgetting that distributed rate limiting needs shared state (Redis).
• Not mentioning the 429 status and Retry-After header.