Rate Limiting Algorithms

Token bucket, leaky bucket, sliding window counter, fixed window -- tradeoffs, boundary bursts, and Redis-based distributed rate limiting patterns.

Overview

Overview Rate limiting controls how frequently a client can perform an action within a time window. It protects API servers from abuse, ensures fair resource sharing among tenants, and prevents single clients from exhausting server capacity.

Four fundamental algorithms: Fixed window counter divides time into discrete buckets and counts requests -- simple but allows boundary bursts. Sliding window log tracks every request timestamp -- accurate but memory-intensive. Sliding window counter approximates the sliding window by interpolating between two adjacent fixed window counts -- efficient and nearly accurate. Token bucket maintains a bucket that refills at a fixed rate; each request consumes a token, allowing bursts up to the bucket size. Leaky bucket queues requests and drains at a fixed rate regardless of burst -- smoothing traffic for rate-sensitive downstreams.

In distributed systems, rate limiting must be distributed. Local-only state on each API gateway instance enforces N times the limit when traffic is load-balanced across N instances. Redis atomic operations (INCR+EXPIRE for fixed window, Lua scripts for token bucket) provide shared state with sub-millisecond lookup latency.

Key concepts

Token Bucket: A bucket with capacity N tokens refills at a fixed rate (e.g., 100 tokens/sec). Each request consumes a token. If empty, reject. The bucket accumulates up to N tokens during idle periods, allowing short bursts. Token bucket is the most common algorithm because it accommodates legitimate bursty traffic while enforcing a long-term average rate. AWS API Gateway uses token bucket (burst capacity + steady-state RPS limits).
Sliding Window Counter: Approximates a sliding window using two fixed window counters. Estimate for the last 60 seconds: prev_count * (1 - elapsed_fraction) + current_count. Small error (< 1% at low rates) but uses only two Redis keys instead of a full timestamp log. Used by Cloudflare for distributed rate limiting because it is memory-efficient and maps to two INCR+EXPIRE operations.
Redis Lua for Atomic Rate Limiting: Redis Lua scripts execute atomically (Redis is single-threaded). A token bucket in Redis stores (token_count, last_refill_timestamp) in a hash. The Lua script computes tokens to add since last refill, caps at bucket size, decrements if > 0, and stores the updated state. Without atomicity, two concurrent requests both reading count=99 could both be allowed, exceeding the limit. Lua eliminates this race condition.

When to use it

Protecting an API endpoint from being hammered by misbehaving clients or bots.
Implementing usage-based billing tiers (100 req/min free, 10,000 req/min paid).
Designing a rate limiter in a system design interview -- classic question.
Configuring Envoy local rate limiting or global rate limit service in Kubernetes.

Interview questions

Design a distributed rate limiter allowing 100 requests per minute per user across 10 API gateway instances.

Rate Limiting Algorithms

Overview

Key concepts

When to use it

Interview questions

More Networking topics