Rate Limiter

What it is

A rate limiter caps how many requests a client (user id, IP, API key) can make in a window to protect services and ensure fair usage. Algorithms differ in burst behavior and memory costs.

Algorithms

Token bucket

• Tokens refill at rate refillPerSecond up to capacity.
• Allows smooth bursts up to bucket size; common for APIs that tolerate short spikes.

Leaky bucket

• Requests enter a queue leaking at fixed rate; smoothes output to steady rate; can queue or drop when full.

Sliding window log

• Store timestamps of each request in a window; precise count; memory-heavy for high QPS (optimize with sliding window counter hybrids).

  Token bucket:   [tokens + refill] --allow--> forward request
  Leaky bucket:   queue --drip fixed rate--> steady downstream

Distributed approaches

• Central Redis (or similar): INCR with TTL, Lua scripts for atomicity, or Redis Cell-style modules.
• Sticky routing: limit per gateway instance—inconsistent across nodes unless synchronized.
• Approximate counting (e.g. Gossip, probabilistic) for global scale—trade accuracy for cost.

Synchronization cost affects latency-throughput; local + async sync is a common compromise.

When to use

• Public APIs, login endpoints, expensive operations.
• Multi-tenant fairness and DDoS mitigation at application layer (with network-layer defenses).

Alternatives

• Admission control at load balancer (see load-balancer); coarser granularity.
• Back-pressure via queues instead of hard reject—different UX.

Failure modes

• Clock skew across nodes skews windows—use server time authority or tolerate fuzz.
• Redis down: fail-open (risky) vs fail-closed (availability hit)—document policy.
• Hot keys for global counters—shard limit keys or use local token buckets with small error.

Interview talking points

• State limit dimensions: per user, per IP, per endpoint, global vs regional.
• Choose algorithm by burst tolerance (token bucket) vs strict smoothness (leaky bucket).
• Estimate allowed QPS with back-of-envelope given fleet size.

Related fundamentals

• Back-of-the-envelope estimation
• Latency and throughput