Design a Rate Limiter

Implement a distributed rate limiting service that can be used across multiple services to prevent abuse and ensure fair resource usage.

Functional Requirements

• Limit requests per user/IP/API key within a time window
• Support different rate limiting algorithms (fixed window, sliding window, token bucket)
• Return appropriate headers (X-RateLimit-Remaining, Retry-After)
• Support different limits for different API endpoints
• Allow rate limit overrides for premium users

Non-Functional Requirements

• Extremely low latency (< 1ms overhead)
• Distributed across multiple data centers
• Accurate counting (no significant over or under limiting)
• Fault tolerant (fail-open vs fail-closed decisions)

Questions to Consider

• Which rate limiting algorithm would you choose and why?
• How will you synchronize counters across servers?
• How will you handle race conditions in a distributed setting?