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 → [API Gateway + Rate Limiter] → 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.

Identifying the client#

Before you can limit anyone, you have to decide what counts as one client. Sitting at the gateway, the limiter sees only the HTTP request, so the key has to come from there:

• User ID, taken from the verified auth token. The best option whenever it exists: it maps to a real account, it cannot be forged, and it follows the user across networks and devices.
• API key, from a header like X-API-Key. The natural key for a developer API, where the limit is part of what the customer bought.
• IP address, for anonymous traffic, and a last resort. One corporate NAT or campus WiFi puts thousands of people behind a single address, so a per-IP limit tuned for one person punishes all of them. Keep IP limits loose and treat them as abuse protection, not fair-use enforcement.

Real systems apply several of these at once rather than picking one:

per user          1,000 requests / hour
per IP              100 requests / minute
per organisation 10,000 requests / minute
per endpoint     50,000 requests / second   (global, protects the backend)

A request has to satisfy every rule that matches it, so the effective limit is the most restrictive one. Alice can be at 50 of her 1,000 personal requests and still get a 429, because the office IP she shares has hit its own limit. That is correct behaviour and worth saying out loud, because it is also the top cause of "I'm being limited below my quota" support tickets.

Layering has a consequence for the counter logic: a single request now reads several counters. All of the checks have to pass before any of the increments happen, or a request rejected by one rule still burns quota against the others. Deep dive 3 covers how to keep that atomic.

Deep Dives#

1. Where the Limiter Lives#

Settle this before the algorithm. Placement decides what information the limiter can see, how much latency it adds, and how much traffic reaches your servers before anything rejects it.

Decision: at the API gateway. It is the cheapest place to say no, it adds one hop instead of two, and the information it needs is already in the request. A standalone service is the right call only if limiting logic has to be shared across services that do not share a gateway.

Worth naming the layers this does not replace. Volumetric DDoS is absorbed at the CDN or WAF before it reaches your gateway at all. Client-side limiting in your official SDKs is a courtesy that smooths traffic from well-behaved callers, never a control, because the client is the one party you cannot trust. The gateway limiter is the enforcement point; the others reduce how much work it has to do.

2. 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.

3. 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

4. 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.

5. 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.

6. Keeping the Added Latency Under 5ms#

The limiter sits in front of every request, so its latency is added to every request. A Redis op is a few hundred microseconds; the budget gets spent on everything around it.

Pool the connections. A fresh TCP connection per check means a handshake before every request, and if you are doing TLS to Redis, several round trips. At 100k RPS that is absurd. Keep a pool of persistent connections per gateway, sized from your concurrency rather than guessed, and watch for pool exhaustion (requests queueing for a connection is a latency cliff that looks exactly like Redis being slow).

One round trip, not several. Evaluating per-user, per-IP and per-endpoint limits as three separate calls costs three round trips. Put them in one Lua script, or pipeline them. This is the same constraint that pushes all the layered checks into a single script in deep dive 3.

Keep the store close. A gateway in Frankfurt calling Redis in Virginia pays 90ms, which blows the entire budget eighteen times over on network alone. Each region gets its own gateways and its own counter store. The consequence, which you should state rather than hide: limits become per-region, so a client spread across three regions can use up to three times their limit. For a fair-use limit that is acceptable. For a hard quota it is not, and you either key on something that pins a client to one region or accept eventual reconciliation.

Watch the tail, not the mean. A p50 of 0.4ms and a p99 of 40ms is a limiter that looks healthy on a dashboard and is visibly slow to 1 in 100 requests. The usual culprits are pool exhaustion, a hot shard, and a Redis node doing something expensive on the same thread. Put a hard timeout on the check (say 5ms) and treat a timeout as the fail-open path from deep dive 4: a limiter that hangs is worse than a limiter that briefly stops limiting.

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.

Reject, do not queue. The tempting alternative is to hold excess requests and release them as the limit frees up, which sounds kinder to the caller. It is not. Queued requests occupy memory and a connection on your side, the caller sees an unexplained multi-second hang and usually gives up and retries (so you now hold two), and your latency percentiles stop meaning anything because they blend served requests with parked ones. Worst of all, the queue is unbounded in exactly the scenario it exists for. Fail fast with a 429 and let the client decide when to come back. Queueing is defensible only for async batch work where nobody is waiting on the response.

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, and why not just put it in the application?

At the API gateway. An in-process limiter cannot work across a fleet: with 50 servers each seeing 1/50th of a user's traffic, a 100/min limit is really enforced at 5,000/min, and sharing state between them means adding the network call you were trying to avoid. It is also the most expensive possible place to say no, since the request has already crossed the load balancer, terminated TLS and woken an application worker. The gateway rejects at the outermost edge with one hop to the counter store. A standalone limiter service is the alternative worth naming: cleaner if many services need identical logic, but it puts two hops and a hard dependency on every request.

Q: A user says they're getting 429s when they've only used 50 of their 1,000 requests. What's happening?

Almost certainly another rule. Limits layer, and a request must satisfy all of them, so their personal quota is only one of the counters being checked. The usual culprit is a shared IP: a corporate NAT puts the whole office behind one address and the per-IP limit trips long before any individual's per-user limit does. Per-organisation and global per-endpoint limits can do the same. This is why the 429 response should say which rule was hit, and why per-IP limits are set loose and used for abuse protection rather than fair-use enforcement.

Q: Why reject over the limit instead of queueing the request until quota frees up?

Queueing sounds friendlier and behaves worse. The request holds memory and a connection on your side, the caller experiences an unexplained hang and usually retries (so now you hold two), and your latency percentiles blend served requests with parked ones and stop meaning anything. The queue is also unbounded in precisely the situation it exists for. Fail fast with a 429 and Retry-After, and let the client decide when to come back.

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 14 min: Placement and client identity Say where the limiter lives and why before you touch algorithms. Name the three options, pick the gateway, and give the killer argument against in-process: 50 servers each see 1/50th of the traffic, so the limit is enforced 50x too loosely. Then cover what you key on (user ID, API key, IP) and that limits layer with the most restrictive winning.

14 to 20 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.

20 to 38 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 and hash tags, hot keys, and the fail-open strategy with local fallback.

38 to 45 min: Latency, failure scenarios and wrap-up Connection pooling and a per-region counter store are the two latency points worth the time. Then clock skew (use Redis TIME), X-Forwarded-For spoofing, and rule-cache refresh. Summarize in one sentence: "Rate limit at the gateway with a sliding window counter in a sharded Redis cluster, atomic via Lua, failing open so the limiter never takes down the API."

Green flags

• Decides placement before algorithm, and explains why in-process can't work across a fleet
• Keys on user ID, treats IP as a loose fallback, and knows limits layer with the most restrictive winning
• 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
• Calls out X-Forwarded-For spoofing, and notices that a cross-region store blows the latency budget

Red flags

• Designs a single-server in-memory counter and stops
• Never says where in the stack the limiter runs
• 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
• Queues over-limit requests instead of rejecting them
• Confuses rate limiting with load shedding or circuit breaking (they're related but distinct)

Further Reading#