Design a Rate Limiter

Problem Statement#

"Design a rate limiter. It should cap how many requests a client can make to an API within a time window."

That's it. One sentence. The rest is yours to figure out.

Requirements Gathering#

This is where the interview actually begins. A strong candidate doesn't start drawing boxes. They ask questions. Not to stall, but because the answers fundamentally change the design.

Here's how a good requirements conversation looks:

Candidate: "Do we limit per-user, per-IP, or both? That decides what we key the counters on."

Interviewer: "Primarily per authenticated user. Fall back to IP for unauthenticated endpoints."

Candidate: "Is this for external API clients, or internal service-to-service traffic? It changes how strict we need to be."

Interviewer: "External API clients. Think a public API with free and paid tiers."

Candidate: "What scale? Peak requests per second through the limiter?"

Interviewer: "100,000 requests per second across the fleet."

Candidate: "Do we need strict per-second limits, or do we allow short bursts? A user uploading 5 files at once is different from sustained abuse."

Interviewer: "Mostly steady limits, but some endpoints should tolerate bursts. Design for both."

Candidate: "When the counter store is unreachable, do we fail open and let requests through, or fail closed and block them?"

Interviewer: "Fail open. The limiter must never take down the API."

Candidate: "Do different endpoints and tiers have different limits, and can they change without a redeploy?"

Interviewer: "Yes. Rules are per endpoint and per tier, and they must be editable live."

Candidate: "Out of scope: DDoS protection, billing-based quotas, geographic limits?"

Interviewer: "Correct, out of scope. DDoS is a CDN/WAF concern. Just application-layer rate limiting."

Functional and Non-Functional Requirements#

Functional Requirements#

1. Limit requests a client (by user ID or IP) can make to an endpoint within a time window
2. Return HTTP 429 Too Many Requests with a Retry-After header when the limit is exceeded
3. Return rate-limit headers on every response: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset
4. Support different limits per endpoint and per client tier (free, pro, enterprise)
5. Rules are configurable live, without a service restart
6. Support both steady limits and burst-tolerant endpoints

Non-Functional Requirements#

Out of scope: DDoS/volumetric protection (CDN/WAF layer), billing-based quotas, geographic rate limiting

Capacity Estimates#

Work through the math. Don't just state the numbers.

Per-request budget:
  Under 5ms p99 total; the counter check must fit in ~1-2ms
  At 100k RPS, one store op per request = 100k store ops/sec

Single Redis instance:
  ~100k ops/sec ceiling → you are AT the limit with one node
  Must shard the counter store from day one

Memory per counter (sliding window = 2 integers + key):
  ~50 bytes × 100M active clients = ~5 GB
  With Redis overhead (~2x): ~10 GB → trivially fits a small cluster

Config lookups:
  Rules cached in-process, refreshed every 60s → ~0 hot-path DB load

The number that should make you pause: one store op per request at 100k RPS puts a single Redis instance at its ceiling immediately. That's why the counter store is sharded and why atomicity has to be cheap.

High-Level Design#

One flow drives everything: a request arrives, and the limiter decides allow or reject before application logic runs. Keep it on the hot path but out of the way.

Client → Load Balancer → [Rate Limiter Middleware] → API Server → Database
                                   ↓ ↑
                          Counter Store (Redis Cluster)
                                   ↑
                          Rules Cache (in-process, 60s TTL) ← Rules DB

Check path: The rate-limiter middleware reads the rule for (endpoint, tier) from an in-process cache, runs a single atomic check-and-increment against the sharded counter store, and either forwards the request or returns 429 with Retry-After.

Config path: Rules live in Postgres. Each middleware instance caches them in memory with a 60-second TTL, so edits propagate within a minute with zero hot-path database load.

The key insight: the limiter is a stateless middleware in front of a shared atomic counter. All the correctness lives in making the check-and-increment atomic on a single shard. Everything else is plumbing.

Deep Dives#

1. Algorithm Selection#

This is the first thing the interviewer wants to hear you reason through. Four algorithms are standard, each trading accuracy against memory and burst tolerance.

rate = prev_count × (1 - elapsed_fraction) + curr_count

Decision: Sliding window counter as the default for its memory efficiency and accuracy. Token bucket for the specific endpoints the interviewer flagged as burst-tolerant.

2. The Distributed Counter: Race Conditions and Atomicity#

This is where the interview is won or lost. A single-server counter is a hash map, trivial. The real problem is that dozens of gateway instances read and increment the same counter concurrently.

Naive approach (wrong): read counter → check limit → increment → write back.

Server A reads 99   Server B reads 99
Server A: 99 < 100 → allow, write 100
Server B: 99 < 100 → allow, write 100

Both allowed. The client got 101 requests through a limit of 100. This is a classic read-modify-write race, and at 100k RPS it happens constantly.

Correct approach: make check-and-increment a single atomic operation. A Lua script runs atomically on a single Redis shard, so no other command interleaves. Here's the fixed-window version, shown first because it's the simplest illustration of atomicity. The sliding-window variant we actually ship is in the senior deep dive below and in the Code section:

local key    = KEYS[1]
local limit  = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local current = redis.call('INCR', key)
if current == 1 then
  redis.call('EXPIRE', key, window)
end
if current > limit then
  return 0   -- reject (note: the request still incremented the counter)
end
return 1     -- allow

INCR returns the post-increment value, so the check and the increment can never be split by another request. MULTI/EXEC is not a substitute here: it queues commands but you still can't branch on an intermediate value inside the transaction without WATCH, and WATCH-based retries reintroduce the race under contention.

(This fixed-window script keeps counting rejected requests, which is harmless within a window but is one more reason to prefer the sliding-window counter, whose script only increments when a request is admitted.)

local now      = tonumber(ARGV[1])
local window   = tonumber(ARGV[2])
local limit    = tonumber(ARGV[3])
local curr_key = KEYS[1]  -- counter for current window
local prev_key = KEYS[2]  -- counter for previous window
local elapsed  = (now % window) / window
local prev     = tonumber(redis.call('GET', prev_key) or '0')
local curr     = tonumber(redis.call('GET', curr_key) or '0')
local rate     = prev * (1 - elapsed) + curr
if rate >= limit then return 0 end
redis.call('INCR', curr_key)
redis.call('EXPIRE', curr_key, window * 2)
return 1

3. Handling Store Failure: Fail Open vs Fail Closed#

The limiter is on the critical path of every request. Redis going down must not take the API down with it.

Fail open (recommended here): if the counter check times out or errors, allow the request and log the failure. Brief Redis downtime means some excess requests slip through, which is acceptable for a public API where availability beats strict enforcement. This is what the interviewer asked for.

Fail closed: if the store is unavailable, reject everything. Protects the backend absolutely but causes a user-visible outage. Only right for strict compliance or financial systems where over-serving is worse than downtime.

Local fallback (the nuance that impresses): each instance keeps a small in-memory counter. If Redis is unreachable, fall back to local counting. It loses global coordination (each of N gateways enforces the limit independently, so effective limits inflate up to N×) but it degrades gracefully instead of failing fully open. State the trade-off out loud; there's no free lunch.

4. Rate-Limit Rules and Live Configuration#

Rules live in Postgres and are cached in-process on every gateway with a 60-second TTL, so an edit propagates within a minute with no redeploy and no hot-path DB read.

rules:
  endpoint      VARCHAR   -- "POST /api/v1/messages"
  client_tier   VARCHAR   -- "free" | "pro" | "enterprise"
  limit         INTEGER   -- requests per window
  window_secs   INTEGER   -- window duration
  algorithm     VARCHAR   -- "sliding_window" | "token_bucket"

At request time the middleware resolves (endpoint, tier) to a rule from the local cache and runs the matching algorithm's Lua script. Rule misses (no rule configured) default to a permissive global limit rather than blocking; a missing config should never look like an attack.

Data Model#

-- Rules (Postgres, source of truth, cached in-process)
rate_limit_rules (
  id            BIGSERIAL PRIMARY KEY,
  endpoint      TEXT        NOT NULL,
  client_tier   VARCHAR(32) NOT NULL DEFAULT 'free',
  limit_count   INTEGER     NOT NULL,
  window_secs   INTEGER     NOT NULL,
  algorithm     VARCHAR(32) NOT NULL DEFAULT 'sliding_window',
  created_at    TIMESTAMPTZ DEFAULT NOW()
)
-- Unique index: (endpoint, client_tier), the rule lookup key

-- Counter Store (Redis Cluster, sharded by key hash)
-- Sliding window counter:
--   user:{id}:{endpoint}:curr   → INTEGER, TTL = 2 × window
--   user:{id}:{endpoint}:prev   → INTEGER, TTL = 2 × window
-- Token bucket:
--   user:{id}:{endpoint}:tokens → FLOAT (remaining)
--   user:{id}:{endpoint}:ts     → last refill timestamp
-- IP fallback (unauthenticated endpoints):
--   ip:{ip_hash}:{endpoint}:curr → INTEGER

The counter keys are ephemeral: everything is TTL'd to at most twice the window, so memory is self-cleaning and no background purge is needed.

API Design#

The rate limiter is middleware, not a standalone API. It annotates every response and returns 429 when limits are exceeded.

Any endpoint
─────────────────────────────────────────────
Response headers on allowed requests:
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 43
  X-RateLimit-Reset: 1717776000

Response 429 when exceeded:
  HTTP/1.1 429 Too Many Requests
  Retry-After: 47
  X-RateLimit-Limit: 100
  X-RateLimit-Remaining: 0
  X-RateLimit-Reset: 1717776000
  Content-Type: application/json

  {
    "error": "rate_limit_exceeded",
    "message": "Too many requests. Try again in 47 seconds.",
    "retry_after": 47
  }

Note: the rate key is derived server-side from the auth token, never from a client-supplied header. And X-Forwarded-For is spoofable: the client controls the left-most entries, so trusting them lets a client rotate the header to reset their own counter. To get a trustworthy client IP, start from the right and strip the hops your own infrastructure appended, then take the first entry you don't control; configure the number of trusted proxies explicitly rather than trusting the whole header. Prefer authenticated user ID as the primary key and fall back to this vetted IP only on unauthenticated endpoints.

Failure Scenarios and Edge Cases#

Code#

Distributed Check-and-Increment (Sliding Window Counter)#

public class RateLimiter {
    private final RedisCluster redis;
    private final RuleCache ruleCache;

    // Loaded once; runs atomically on a single shard.
    private static final String LUA = """
        local now, window, limit = tonumber(ARGV[1]), tonumber(ARGV[2]), tonumber(ARGV[3])
        local elapsed = (now % window) / window
        local prev = tonumber(redis.call('GET', KEYS[2]) or '0')
        local curr = tonumber(redis.call('GET', KEYS[1]) or '0')
        if prev * (1 - elapsed) + curr >= limit then return 0 end
        redis.call('INCR', KEYS[1])
        redis.call('EXPIRE', KEYS[1], window * 2)
        return 1
        """;

    public Decision check(String userId, String endpoint) {
        Rule rule = ruleCache.get(endpoint, tierOf(userId));  // in-process, 60s TTL
        long now = Instant.now().getEpochSecond();
        long bucket = now / rule.windowSecs();

        // Hash tag {userId} keeps both keys on the same shard.
        String curr = "rl:{" + userId + "}:" + endpoint + ":" + bucket;
        String prev = "rl:{" + userId + "}:" + endpoint + ":" + (bucket - 1);

        try {
            long allowed = redis.eval(LUA, List.of(curr, prev),
                List.of(now, rule.windowSecs(), rule.limit()));
            return allowed == 1 ? Decision.allow(rule) : Decision.reject(rule);
        } catch (RedisException e) {
            log.warn("rate limiter store unavailable, failing open", e);
            return Decision.failOpen();   // availability > strict enforcement
        }
    }

}

Trade-off Summary#

Follow-up Questions#

Basic

Q: Why not just use a fixed window counter? It's the simplest.

Boundary burst. A client can send a full window's worth of requests in the last second of one window and another full window's worth in the first second of the next, doubling the intended rate across a two-second span. The sliding window counter smooths this with a weighted blend of the current and previous buckets.

Q: What does "atomic" actually buy you here?

It eliminates the read-modify-write race. Without atomicity, two gateways both read "99", both decide the request is under the limit of 100, and both allow it. A Lua script does the read, the decision, and the increment as one indivisible step on a single shard, so no two requests can both see the same pre-increment value.

Q: Where in the stack does the limiter live?

At the API gateway, in front of application logic: the earliest point where you can cheaply reject abuse before it consumes real resources. It can also appear deeper (per-service, per-DB-connection-pool), but the gateway is the primary line.

Q: Fail open or fail closed, how do you decide?

It's a business call, not a technical one. Fail open for a public API where availability beats strict enforcement. Fail closed only when over-serving is worse than downtime, like payments or compliance-bound endpoints. Say which and why; the interviewer wants the reasoning, not a default.

Minute-by-Minute Interview Playbook#

0 to 5 min: Requirements Ask the questions above. The rate key (user vs IP), the fail-open decision, and burst tolerance directly shape the design. Confirm out-of-scope (DDoS is a different layer). Write FR/NFR on the board.

5 to 8 min: Capacity estimates Do the throughput math out loud. The "one store op per request at 100k RPS = a single Redis node at its ceiling" number is what justifies sharding and cheap atomicity. Skip it and your choices look arbitrary.

8 to 15 min: Algorithm selection Walk all four algorithms; this shows breadth. Explain fixed-window boundary burst, sliding-window-log memory cost, then commit to sliding window counter and say why. Note token bucket for burst endpoints.

15 to 35 min: Distributed design This is the highest-value section. Draw the race condition explicitly: two servers both reading "99". Then solve it with a Redis Lua script and explain why MULTI/EXEC isn't enough. Cover sharding, hot keys, and the fail-open strategy with local fallback.

35 to 45 min: Failure scenarios and wrap-up Cover clock skew (use Redis TIME), X-Forwarded-For spoofing, and rule-cache refresh. Summarize in one sentence: "Sliding window counter in a sharded Redis cluster, atomic via Lua, failing open so the limiter never takes down the API."

Green flags

• Walks all four algorithms and articulates the trade-offs before committing
• Immediately identifies the read-modify-write race in the naive distributed design
• Knows Lua scripts are atomic on a shard and MULTI/EXEC+WATCH is not equivalent
• Frames fail-open vs fail-closed as a business decision
• Keys on user ID and calls out X-Forwarded-For spoofing

Red flags

• Designs a single-server in-memory counter and stops
• Can't explain what "atomic" means in this context
• Reaches for "just use a database" for the counter without addressing write throughput
• Uses fixed windows without acknowledging boundary burst
• Confuses rate limiting with load shedding or circuit breaking (they're related but distinct)

Further Reading#