Which rate-limiting algorithm, and where do you enforce it?
“You need to limit an API to 100 requests per minute per client. Compare fixed window, sliding window and token bucket, pick one, and explain how it works across 20 gateway instances.”
What this tests
- The boundary problem of fixed windows
- Token bucket burst semantics vs sliding-window smoothness
- Distributed counters in Redis with atomic operations
- Client-facing behaviour: 429, Retry-After, headers
Answers by level
Read the beginner answer first and notice what is missing.
Fixed window (counter per minute) is cheap but lets 200 requests through in two seconds around the boundary (100 at 0:59, 100 at 1:00). Sliding window log stores each request timestamp and counts those in the last 60 s — exact, but O(requests) memory per client. Sliding window counter blends the previous and current window weighted by overlap — approximate, O(1) memory, no boundary spike. Token bucket refills at 100/min to a capacity of 100 and each request takes a token — allows a burst up to capacity, then a steady rate, which is usually what clients want.
I would pick token bucket (or sliding window counter if bursts must be flattened) and enforce at the gateway, keyed by client id. Across 20 instances the counter lives in Redis: a small Lua script does get-refill-decrement atomically in one round trip, with a TTL so idle clients expire. Reject with 429 plus Retry-After and X-RateLimit-Remaining so well-behaved clients back off — see Rate Limiting.
Green flags · Red flags
- Explains the fixed-window boundary spike with numbers
- Token bucket burst semantics stated precisely
- Atomic Redis operation (Lua / INCR + TTL), not read-then-write
- Decides fail-open vs fail-closed when Redis is unavailable
- 429 with Retry-After and remaining-quota headers
- "Keep the counter in memory and use sticky sessions." (breaks on scale-out and restarts)
- Divides the quota by instance count
- Read counter, check, then write — with no atomicity
- Returns 500 or 403 instead of 429