Design a tiered API rate limiter

WHAT THIS TESTS The interviewer wants algorithm knowledge plus the distributed-systems reality that counters must be shared. A rate limiter is easy on one box and subtle across a fleet, where naive per-node counting silently multiplies the effective limit.

A GOOD ANSWER COVERS Pick an algorithm to fit the goal. Token bucket allows controlled bursts and refills at a steady rate; sliding-window log or counter gives smoother, more accurate enforcement without the boundary spikes of a fixed window. Key the limit by API key, and on each request look up the partner's tier to get its quota, free gets a low limit, premium a higher one, stored as config so tiers change without code. Track state, the token count or request counter, in a low-latency shared store such as Redis, so every gateway node sees the same count; use atomic operations or a Lua script to increment-and-check without races. Make the decision early, at the API gateway or edge, before requests hit backends. When throttled, return HTTP 429 with Retry-After and X-RateLimit headers so well-behaved clients back off. Consider a small local cache with periodic sync to cut Redis round-trips at extreme scale, accepting slight imprecision.

COMMON WRONG ANSWERS Per-instance in-memory counters, letting a partner exceed the limit by hitting different nodes. Non-atomic read-then-write that races under concurrency. Hard-coding tier quotas. Enforcing deep in the backend after work is already done.

LIKELY FOLLOW-UPS Token bucket versus sliding window, when to use each? How do you make the counter update atomic in Redis? How do you trade accuracy for fewer round-trips at scale?

ONE CONCRETE EXAMPLE A premium partner's key allows 1000 requests per minute. Each gateway node, on every call, runs an atomic Redis script that decrements that key's token bucket; when tokens hit zero the node returns 429 with Retry-After. Because the bucket lives in Redis, ten gateway nodes enforce one shared limit. Upgrading the partner to a higher tier is a config change to their quota, no deploy.