Design a rate limiter

Problem: Design a Rate Limiter

Design a rate limiting service to protect an API from abuse and to provide fair usage.

Requirements

• The API gateway (or edge service) must enforce limits such as:
  • Per-user (or per API key) requests per time window (e.g., 100 req/min).
  • Per-IP limits (optional).
  • Potentially per-endpoint or per-tenant limits.
• Should support common policies:
  • Fixed window (acceptable if you discuss edge effects), sliding window, token bucket, or leaky bucket.
• Must work in a distributed environment (multiple stateless API servers).
• Low latency overhead (rate limiting should be fast).

Clarifications to address

• What happens when over limit (HTTP 429, headers like Retry-After )?
• How do you handle bursts?
• What are the consistency needs (strict vs near-accurate)?
• How do you avoid a single point of failure?

Deliverables

Explain:

1. The chosen algorithm(s) and why.
2. The high-level architecture and data stores.
3. Key data model, read/write flow.
4. Scaling, fault tolerance, and edge cases.