Design a Distributed Rate Limiter

You're designing a rate limiter for an API platform. Clients (e.g., mobile apps, third-party services) call your API and each has a quota: e.g., 1,000 requests per minute, or 10,000 per day. Requests that exceed the quota are rejected with HTTP 429. The limiter must be fast (<10ms overhead), accurate, and handle network partitions gracefully.

Scale assumptions:

• 10 million active API clients
• 5% of clients make requests in any given minute (500K concurrent)
• Each concurrent client averages 10 requests/minute → 5M requests/minute total
• Peak factor: 3× average during business hours
• Quota types: per-minute and per-day limits (both enforced)
• Accuracy requirement: false negatives (<1%), false positives acceptable
• Latency SLA: <10ms per rate-limit check

Derived numbers:

• Average QPS: 5M/60 sec ≈ 83K req/sec
• Peak QPS: 250K req/sec
• State to track: 500K concurrent clients × ~200 bytes (quota buckets) = ~100GB in-memory