Design a Rate Limiter: Distributed Implementation

The gap between “use Redis” and a working system

“Just put the counter in Redis” is where most candidates stop, and it’s where the interviewer starts asking harder questions. Centralizing state in Redis solves the multi-server consistency problem in principle, but a naive implementation reintroduces race conditions at the exact moment you need correctness most: under high concurrent load, which is precisely when a rate limiter matters.

This article is the implementation-depth follow-up: how to make the Redis operations atomic, what breaks across regions, and where client-side enforcement still has a legitimate role.

The race condition in the naive version

A tempting first implementation:

count = GET key
if count < limit:
    INCR key
    allow request
else:
    reject request

Between the GET and the INCR, two concurrent requests can both read a count of, say, 99 (with a limit of 100), both decide they’re under the limit, and both proceed — and now the counter is at 101 with two requests admitted that should have had one of them rejected. Under low traffic this race window rarely gets hit. Under the exact bursty, high-concurrency traffic a rate limiter exists to handle, it gets hit constantly, and the limiter silently over-admits.

Fix: atomic operations via Lua scripting

Redis executes Lua scripts atomically — no other command can interleave partway through. This closes the race entirely by making “check and increment” a single indivisible operation from Redis’s point of view.

A token bucket implemented as a Lua script, conceptually:

-- KEYS[1] = bucket key, ARGV[1] = capacity, ARGV[2] = refill_rate, ARGV[3] = now
local bucket = redis.call('HMGET', KEYS[1], 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or tonumber(ARGV[1])
local last_refill = tonumber(bucket[2]) or tonumber(ARGV[3])
local elapsed = ARGV[3] - last_refill
local refill = elapsed * tonumber(ARGV[2])
tokens = math.min(tonumber(ARGV[1]), tokens + refill)

if tokens >= 1 then
  tokens = tokens - 1
  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last_refill', ARGV[3])
  return 1  -- allowed
else
  redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last_refill', ARGV[3])
  return 0  -- rejected
end

Run via EVALSHA for efficiency (cache the compiled script server-side instead of resending the source every call). The entire read-compute-write sequence happens inside Redis’s single-threaded execution model — no other client can observe or mutate the bucket state mid-script. This is the concrete answer to “how do you avoid the race condition,” and naming Lua/EVALSHA specifically (not just “use a transaction”) is what distinguishes a candidate who’s implemented this from one who’s only read about it.

An alternative worth mentioning: Redis MULTI/EXEC transactions with WATCH for optimistic locking. This works but requires a retry loop on conflict (the transaction aborts if the watched key changed), whereas the Lua script approach never needs retries because nothing can interleave in the first place. For a rate limiter specifically, Lua is the cleaner and more common production choice.

What happens under Redis failure

Once the design depends on Redis for correctness, “what if Redis is unavailable” is a guaranteed follow-up. Three postures, each a legitimate answer if justified:

• Fail open: if Redis is unreachable, allow the request. Prioritizes availability; risk is unmetered traffic during an outage, acceptable for internal or non-critical limits.
• Fail closed: if Redis is unreachable, reject the request. Prioritizes strict enforcement; risk is a Redis outage becoming a full service outage for legitimate users too.
• Degrade to local in-memory limiting: each app server falls back to a local, per-instance approximate limiter (e.g., local token bucket) during the outage, accepting that the effective limit becomes “limit × number of app servers” temporarily rather than a hard global cap.

Most production systems fail open for read-heavy public APIs (availability matters more) and fail closed for sensitive actions like payment or login attempts (correctness matters more). Stating this distinction — that the right failure posture depends on what’s being protected — is a stronger answer than picking one universally.

Multi-region consistency

A global product with regional deployments faces the real distributed-systems version of this problem: a user hitting your US region and your EU region (via anycast routing, failover, or just a mobile client roaming) shouldn’t be able to get 2x their limit by splitting requests across regions.

Three approaches, in increasing order of consistency and cost:

For rate limiting specifically, eventual consistency is almost always the right tradeoff. The cost of a user briefly exceeding their limit by some small margin during replication lag is low; the cost of adding a cross-region synchronous round-trip to every single request (multiplying tail latency for every request, not just the rare over-limit case) is high and paid by everyone, always. The correct interview answer here is explicitly naming that asymmetry: “I’d rather occasionally over-admit slightly than pay cross-region latency on every request” — this is a real production tradeoff, not a cop-out.

A practical middle ground worth naming: keep independent regional counters (fast, local), but periodically (every few seconds) sync aggregate counts asynchronously and apply a slightly reduced per-region limit (e.g., 60% of the global limit per region instead of 100%) so no single region can exhaust the entire global budget alone even under partition.

Client-side vs. server-side: why both still matter

Server-side enforcement (everything above) is the source of truth and the only thing that actually stops abuse — a malicious client can always ignore client-side logic. But client-side rate limiting still earns its place for a different reason: cooperative efficiency, not security.

• A well-behaved mobile app that tracks “I have 3 of my 5 allowed requests left this minute” can avoid sending requests it already knows will be rejected, saving battery, data, and a wasted round trip.
• Response headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset — the informal but widely adopted convention) let clients self-regulate without the server doing any extra work beyond echoing its own internal counter state back.
• Exponential backoff on the client, triggered by 429 responses, reduces retry storms that would otherwise make an already-throttled situation worse.

The framing that lands well in an interview: server-side enforcement is about correctness and abuse prevention; client-side awareness is about efficiency and good citizenship. Neither replaces the other, and a mature API exposes rate-limit headers specifically so well-behaved clients can build the client-side half themselves.

Putting the full distributed picture together

Client (tracks X-RateLimit-* headers, backs off on 429)
   |
Regional Load Balancer
   |
App Servers --EVALSHA(token_bucket.lua)--> Regional Redis (source of truth for the region)
                                                |
                                    async aggregate sync (seconds-level lag)
                                                |
                                     Cross-region coordination (soft global cap)

This is the answer that satisfies the “make it distributed, make it correct, make it resilient” arc of the question: atomic Lua scripts close the race condition within a region, an explicit failure posture (fail-open/closed/degrade) handles Redis outages, and accepted eventual consistency handles multi-region without paying synchronous cross-region latency on every request.

Further reading

The 0-to-1 SWE Interview Playbook (Amazon: https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20) includes the full implementation-level walkthroughs — Lua scripts, failure postures, and consistency tradeoffs — for rate limiters and several other high-frequency system design questions, written for candidates who want to go one level deeper than the standard whiteboard answer.