Design a Rate Limiter: System Design Interview 2026

A rate limiter looks like a small counter, but it sits in the request path and makes an admission decision under concurrency, partial failure, and hostile input. A bad design either overloads the protected service or rejects legitimate traffic. A strong interview answer therefore starts with what resource is protected, whose usage is counted, and what error is acceptable before choosing Redis or an algorithm.

This walkthrough assumes the 6-step system design framework and applies it at senior depth. It is Part 2 of a system design series.

Table of Contents

1. The Problem
2. Step 1 - Clarify Requirements
3. Step 2 - Estimate Scale
4. Step 3 - API and Data Model
5. Step 4 - High-Level Design
6. Step 5 - Algorithms and Atomic State
7. Step 6 - Failure, Hot Keys, and Multiple Regions
8. Reference Architecture
9. Common Interview Mistakes
10. Quick Reference
11. Sources
12. Frequently Asked Questions
13. Related Articles

The Problem

Design an admission-control service that decides whether a request may consume a protected resource. Typical goals are abuse prevention, fair sharing between tenants, API-plan enforcement, and overload protection.

Rate limiting is only one control:

• a rate limit bounds work admitted per time unit;
• a concurrency limit bounds work currently in flight;
• a quota bounds cumulative use over a longer period;
• load shedding rejects work when the service is unhealthy, even if a caller still has quota.

A production gateway often combines them. One cheap request and one expensive report export should not necessarily cost one identical token.

Step 1 - Clarify Requirements

Ask these questions before drawing boxes:

• What is limited: requests, bytes, compute units, writes, or concurrent jobs?
• Who owns the allowance: tenant, API key, authenticated user, device, IP prefix, endpoint, or a combination?
• May clients burst? If so, by how much and for how long?
• Is enforcement global, regional, or deliberately approximate?
• Which rules fail open, fail closed, or enter a conservative degraded mode?
• Do rejected requests consume quota? How are retries and idempotent replays treated?
• How quickly must a rule change or emergency block propagate?

Functional requirements

• Evaluate several versioned rules, such as tenant-wide, endpoint-specific, and weighted-cost limits.
• Return an allow/reject decision, remaining allowance where meaningful, and retry guidance.
• Support plan changes and emergency policies without restarting the gateway fleet.
• Keep a defensible audit trail for security-sensitive or billable decisions.

Identity and trust boundary

Prefer an authenticated tenant, API key, or user subject. Use source IP only as a fallback signal: many legitimate users can share NAT, IPv6 clients can rotate addresses, and attackers can distribute traffic. Accept Forwarded or X-Forwarded-For only after a trusted proxy has stripped client-supplied copies and appended its own value. Never place raw secrets or unnecessary personal data in Redis keys; use stable internal IDs or keyed hashes.

Non-functional requirements

• Latency: reserve an explicit budget and measure it on the selected topology; there is no universal sub-millisecond guarantee.
• Availability: the limiter must have a bounded answer when configuration or state storage is slow or unavailable.
• Accuracy: name the permitted false-rejection and over-admission bounds per rule.
• Cardinality: malicious clients must not be able to create unbounded keys and exhaust memory.
• Isolation: one hot tenant or shard must not stall decisions for everyone else.

Step 2 - Estimate Scale

Use scenario numbers, not product claims. Suppose the platform receives 1,000,000 requests per second at peak, evaluates two rules per request, and batches none of them. The decision tier then sees roughly 2 million rule evaluations per second. A local rejection cache or multi-rule function can reduce network calls, while additional dimensions can increase state mutations.

Benchmark the exact Redis version, command or function, payload, pipelining policy, replication mode, cluster layout, and hot-key distribution. A generic “one Redis node does N operations per second” figure is not a capacity plan.

If 10 million rule subjects each hold 100 bytes of logical state, the payload alone is about 1 GB. Real memory is higher because keys, hash tables, allocator fragmentation, expiration metadata, replicas, and failover headroom all cost space. Also estimate the number of subjects active within the TTL window, not only registered accounts.

Size the network and latency budget too. One atomic operation may still cross an availability-zone boundary, queue behind a slow script, or time out during failover. Capacity tests should include skewed keys and failure, not only uniform steady traffic.

Step 3 - API and Data Model

The internal decision contract can be explicit about degraded behavior:

check(subject, rules, requestCost, requestContext)
  -> { decision, matchedRule, remaining, retryAfterSeconds,
       policyVersion, mode }
 
decision = ALLOW | REJECT
mode     = AUTHORITATIVE | LOCAL_DEGRADED | LEASED

A canonical state key needs the policy epoch as well as the subject:

rl:{tenantHash}:rule:{ruleId}:v:{policyVersion}:subject:{subjectHash}

Versioning prevents a new limit from accidentally inheriting incompatible old state. TTLs retire old epochs, while a cardinality guard stops arbitrary subject strings from producing unlimited keys. In Redis Cluster, hash tags such as {tenantHash} keep all keys needed by one atomic function in the same slot.

HTTP response semantics

RFC 6585 defines 429 Too Many Requests and says a response may include Retry-After; it intentionally does not define how the server identifies a user or counts requests.

HTTP/1.1 429 Too Many Requests
Retry-After: 23
Content-Type: application/problem+json

As of September 2026, RateLimit and RateLimit-Policy are defined by an active IETF Internet-Draft, not a published RFC. If an API adopts that draft, pin a version and document the contract; deployed X-RateLimit-* fields remain implementation-specific. Do not promise remaining quota on every response unless the product actually needs the extra disclosure and computation.

State by algorithm

Step 4 - High-Level Design

Use a control plane for policies and a data plane for decisions. Gateways cache signed, versioned policy snapshots; the hot path must not call a configuration database.

flowchart TD
    Admin[Policy admin] --> CP[Rate-limit control plane]
    CP -->|signed versioned snapshot| Edge[Edge and API gateways]
    Client([Client]) --> Edge
    Edge --> ID[Authenticate and normalize identity]
    ID --> RL{Evaluate applicable rules}
    RL -->|atomic state update| Store[(Partitioned decision store)]
    RL -->|allow| Service[Backend service]
    RL -->|reject| Deny[429 and retry guidance]
    Service --> Guard[Service-level concurrency or cost guard]
    RL -. timeout .-> Local[Bounded degraded policy]

Figure 1. Policies flow through a versioned control plane; identities and atomic decisions stay in the data plane. A service-level guard protects capacity the edge cannot model.

The edge is the cheapest place to reject obvious abuse, but it is not the only useful placement. A downstream service knows whether work is expensive, which resource is saturated, and how much concurrency it can safely accept. Layered controls also cover internal callers that bypass the public gateway.

The shared store is authoritative only while an authoritative mode succeeds. During an outage, a local or leased decision must be labeled as degraded so operators can measure its error rather than pretending two sources of truth agree.

Step 5 - Algorithms and Atomic State

Fixed window

A fixed window is cheap, but adjacent windows are independent. If the limit is L, a client can spend L at the end of one window and another L at the start of the next.

flowchart LR
    A["Window A<br/>L requests near the end"] --> B["Window B<br/>L requests near the start"]
    B --> C["Almost 2L requests<br/>in a very short interval"]

Figure 2. A fixed-window boundary permits almost twice the nominal window allowance in an arbitrarily short interval.

The increment and first expiry must be one atomic operation. A bare INCR followed by EXPIRE is a race: a process can fail between commands and leave an immortal key; resetting expiry on every hit can also change the window semantics. Redis Open Source 8.8 added INCREX, which combines increment, conditional expiry, and an optional upper bound. On older versions, use a short Redis Function or Lua script.

Sliding log and sliding counter

A sliding log removes expired timestamps, counts the remaining entries, and inserts the accepted request atomically. It is precise only relative to its timestamp resolution, clock source, and tie handling, and its memory and operation cost grow with traffic.

A two-bucket sliding counter estimates the rolling total:

estimated = currentCount + previousCount * overlapFraction

It uses O(1) state, but it is an approximation. Quantify its maximum error for the bucket width and traffic pattern instead of claiming it eliminates every boundary effect.

Token bucket

A token bucket refills at rate R up to capacity C; a request consumes its weighted cost. Capacity is an explicit burst allowance, while refill controls the sustained rate. Refill is computed lazily, so no timer scans idle buckets.

flowchart LR
    Clock[Elapsed trusted time] --> Refill[Refill up to capacity C]
    Request[Request cost k] --> Check{tokens at least k?}
    Refill --> Check
    Check -->|yes| Consume[Subtract k and allow]
    Check -->|no| Reject[Reject and compute retry]

Figure 3. Token-bucket capacity expresses allowed burst size; refill rate expresses long-run throughput.

The full transition must be atomic. The following interview-level Lua example fixes the common initialization and time-regression bugs. Production code should use integer fixed-point token units, validate every argument, and derive nowMs inside trusted infrastructure rather than from the end client.

-- KEYS[1] = one bucket key
-- ARGV = capacity, refillPerMs, requestCost, nowMs, ttlMs
local capacity    = tonumber(ARGV[1])
local refillPerMs = tonumber(ARGV[2])
local requestCost = tonumber(ARGV[3])
local nowMs       = tonumber(ARGV[4])
local ttlMs       = tonumber(ARGV[5])
 
local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local lastMs = tonumber(state[2]) or nowMs
local safeNow = math.max(lastMs, nowMs)
local elapsed = safeNow - lastMs
 
tokens = math.min(capacity, tokens + elapsed * refillPerMs)
local allowed = tokens >= requestCost
if allowed then
  tokens = tokens - requestCost
end
 
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', safeNow)
redis.call('PEXPIRE', KEYS[1], ttlMs)
return {allowed and 1 or 0, math.floor(tokens)}

Redis executes a script atomically and blocks other server activity while it runs, so keep it bounded and fast; “single-threaded” is not the correctness contract. Redis Functions have been a first-class, server-managed alternative since Redis 7, while EVAL remains useful for explaining the atomic transition. All declared keys used by one clustered operation must be colocated in one hash slot.

Leaky bucket

A meter-style leaky bucket tracks a bounded water level in O(1) state. A queue-style implementation smooths output at a fixed drain rate but needs a finite queue, a maximum wait, cancellation, and an overflow policy. Calling it O(1) while storing every queued request hides the real memory and latency cost.

Step 6 - Failure, Hot Keys, and Multiple Regions

Storage timeout or outage

Choose behavior per rule:

• fail open for a low-risk feature where availability dominates;
• fail closed for authentication defense, scarce capacity, or a security boundary;
• degraded mode using a conservative local budget or a still-valid lease.

Do not divide a global limit by the observed node count and call it safe. Autoscaling, uneven load balancing, process restarts, and duplicated local state can all change the admitted total. If local fallback is necessary, allocate bounded per-instance or per-cell authority, expire it, fence stale epochs, and include its worst-case error in the capacity model.

Use short timeouts, a bulkhead, and a circuit breaker so a slow limiter store cannot consume all gateway threads or connections. “Store unavailable” must never silently mean “unlimited” unless that rule explicitly fails open.

Hot keys and cardinality attacks

A single abusive subject can overload its shard even while most requests are rejected. A short negative cache can reject a known-over-limit subject locally, but scope it to the exact rule version and reset horizon; otherwise it creates false rejections after a policy change.

Splitting one logical counter into subcounters distributes writes but introduces an aggregation or over-admission trade-off. It is not a free fix. Prefer isolation, per-subject admission before the shared store, batching where semantics allow it, and a key-creation budget for unauthenticated identities.

Replication and failover

Atomicity on one primary does not imply durable global accuracy. If asynchronous replication loses recent accepted increments during failover, the promoted replica can over-admit. Bound the error from measured replication lag, lost acknowledgements, and outstanding local decisions; choose stronger acknowledgement or replication settings where that cost is justified. Test failover with hot keys rather than describing staleness as merely “slight.”

Multiple regions

A strict global decision requires either synchronous coordination or preallocated authority. The usual low-latency design leases part of the global budget to each region:

flowchart TD
    CP[Global quota allocator] -->|fenced lease: epoch, amount, expiry| EU[EU regional limiter]
    CP -->|fenced lease: epoch, amount, expiry| US[US regional limiter]
    CP -->|fenced lease: epoch, amount, expiry| AP[APAC regional limiter]
    EU -->|usage and demand| CP
    US -->|usage and demand| CP
    AP -->|usage and demand| CP

Figure 4. Regional limiters spend explicitly leased authority locally; a control plane replenishes and rebalances capacity without a cross-region call on every request.

Allocate leases from expected demand plus headroom, keep a reserve for bursts, reclaim only after expiry or confirmed handoff, and reject stale lease epochs. The worst-case overshoot is tied to outstanding leases, in-flight decisions, and local burst allowances. Asynchronous counter gossip alone provides no useful bound unless the design defines those budgets.

Observability and operations

Measure at least:

• allowed, rejected, and degraded decisions by rule, tenant tier, region, and policy version;
• decision latency, store latency, timeouts, script/function duration, and cluster slot skew;
• fallback duration, outstanding regional leases, estimated over-admission, and false-rejection samples;
• active-key cardinality, key-creation rate, memory per rule, and hot-key concentration;
• configuration propagation lag and decisions made on stale policy epochs.

Sample high-cardinality logs and protect subject identifiers. Alert on behavior changes, not just raw 429 volume: a plan rollout can look like an attack, and a store outage can make rejections disappear if a rule fails open.

Reference Architecture

The reusable pattern is:

Versioned policy plus trusted identity, evaluated through one bounded atomic state transition, with explicitly limited authority during failure and regional partitioning.

This pattern also applies to concurrency guards, spend budgets, provider quotas, and admission control. The crucial design artifact is not “Redis”; it is the written bound on what can be admitted when components disagree or disappear.

Common Interview Mistakes

• Choosing an algorithm before defining identity, burst policy, and protected capacity.
• Treating client-controlled IP headers as authenticated identity.
• Claiming INCR plus a later EXPIRE is one atomic fixed-window operation.
• Showing a token-bucket script with mismatched arguments, untrusted time, or clock regression.
• Calling a sliding counter exact or a queued leaky bucket O(1) without qualification.
• Using globalLimit / nodeCount during an outage without accounting for autoscaling and skew.
• Claiming asynchronous multi-region replication has a bound without allocating budgets.
• Ignoring key-cardinality attacks, policy epochs, failover loss, and limiter self-overload.
• Presenting draft or vendor-specific rate-limit headers as an established HTTP standard.

Quick Reference

Sources

• RFC 6585, Section 4: 429 Too Many Requests - status-code and optional Retry-After semantics.
• IETF HTTPAPI: RateLimit header fields for HTTP - current Internet-Draft status and evolving RateLimit field definitions.
• Redis INCREX command - atomic increment, conditional expiry, and bounds added in Redis Open Source 8.8.
• Redis scripting with Lua - atomic execution and server-blocking behavior.
• Redis Functions - server-managed programmable functions available since Redis 7.
• Redis Lua API - declared-key and cluster-slot constraints.

Frequently Asked Questions

What is the difference between token bucket and sliding window rate limiting?

A token bucket deliberately allows bursts up to its capacity while enforcing a long-run refill rate. A sliding window measures usage over a rolling interval: a timestamp log can be precise at its chosen time resolution, while a two-counter version is cheaper but approximate. Choose from burst policy, accuracy, and state cost rather than treating either algorithm as universally best.

Where should a rate limiter sit in the architecture?

Put coarse abuse protection at the edge, then add service- or resource-specific admission controls near the capacity they protect. The edge can reject cheaply, but it may not know request cost or downstream concurrency. Build keys from authenticated tenant or user identity and trust client IP headers only from proxies you control.

How do you make rate limiter counters atomic across many servers?

Make check, refill or expiry, consume, and state update one server-side operation. Redis 8.8 added INCREX for an atomic fixed-window increment with conditional expiry and an upper bound; token buckets and rolling counters still need a Redis Function or Lua script. In Redis Cluster, every key touched by one operation must map to the same hash slot.

Should a rate limiter fail open or fail closed?

Decide per rule and protected resource. Fail-open favors availability, fail-closed protects scarce or security-sensitive capacity, and a degraded mode can use conservative local or leased budgets. A blind global-limit-divided-by-node-count fallback is unsafe under autoscaling, restarts, and uneven routing, so define and measure the maximum over-admission or false rejection.

Why does a fixed window counter allow bursts at the window boundary?

Adjacent fixed windows are independent. A client can spend the full limit at the end of one window and again at the start of the next, so almost 2L requests can arrive in an arbitrarily short interval around the boundary. Token buckets or rolling-window algorithms express burst behavior more directly.

Can you enforce a global rate limit across multiple regions?

Strict global enforcement requires coordination or preallocated authority. A practical design leases fenced regional budgets from a control plane and enforces each lease locally; unused budget can later be reclaimed or rebalanced. Overshoot is bounded by explicitly outstanding leases and local burst allowances, not by a generic region-count formula.

Related Articles

• System Design Interview Problems: A Senior's Roadmap - the full series index and pattern library.
• System Design Interview Guide: The 6-Step Framework - the method this walkthrough applies.
• Design a URL Shortener - Part 1; another hot-path system built around shared state.
• Design a Notification Service - Part 3; rate limiting reused for provider pacing.
• Redis Interview Questions - atomic operations, scripting, clustering, and persistence.

This is Part 2 of the core track in a 16-part system design series. Next: Design a Notification Service.