Low-level design

Designing a rate limiter

A gatekeeper that decides, in under a millisecond, whether a request gets to proceed or gets turned away — protecting shared resources from being overwhelmed by any single client, on purpose or by accident.

Strategy pattern · middleware · distributed systems · concurrency

Requests arrive, the gate decides

allowed 0 allowed · 0 blocked blocked

STEP 1

Understanding & Motivation

Before designing anything, articulate *why* a system needs rate limiting. Interviewers are listening for whether you connect the mechanism to real failure modes, not just recite algorithm names.

DoS / abuse prevention

Blocks a single bad actor (or buggy retry loop) from monopolizing capacity meant for everyone else.

Resource starvation

Protects finite resources — DB connections, thread pools, third-party quotas — from being exhausted by traffic spikes.

Cost optimization

Every request often has a real dollar cost (compute, egress, downstream API calls) — limiting caps the bill.

Cascading failure mitigation

Stops overload in one service from rippling upstream and taking down every dependent service with it.

Illustrative real-world limits (rounded, publicly documented order-of-magnitude)

Service	Typical Limit	Why this shape
GitHub REST API	~5,000 req/hour (authenticated)	Long window, high ceiling — optimized for scripts & CI, not bursts.
Stripe API	~100 req/sec (live mode)	Short window — protects a payments-critical path from spikes.
Social APIs (e.g. X/Twitter)	Tiered, per 15-min window	Per-endpoint tiers so expensive reads are throttled harder than cheap ones.

STEP 2

Requirements Gathering

Split requirements into functional (what it does) and non-functional (how well it does it) — interviewers explicitly score this separation.

Functional Requirements

Allow or block a request based on a configurable threshold.
Support scoping by client ID, IP address, API token, or user tier.
Different limits per route/endpoint (e.g. cheap read vs. expensive write).
Give real-time feedback via standard response headers.
Return 429 Too Many Requests with a Retry-After hint.

Non-Functional Requirements

Low latency overhead — check should add <2ms to the request path.
Memory-efficient — ideally O(1) state per client, not O(requests).
Horizontally scalable — correct even across many stateless API instances.
High availability — the limiter must never become the outage.
Graceful degradation — decide fail-open vs. fail-closed if the store is down.

Standard response contract

Success — headers on every response

HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
X-RateLimit-Reset: 1755392400

Denied — limit exceeded

HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Remaining: 0

{"error":"rate_limit_exceeded"}

STEP 3

Design Patterns Applied

A rate limiter is a great vehicle for demonstrating pattern fluency — naming the pattern is worth less than explaining why it fits here.

Strategy Pattern

A common RateLimiter interface with interchangeable algorithm implementations (Token Bucket, Sliding Window, ...) selected per route or client tier at runtime.

Decorator / Middleware Pattern

Rate limiting wraps the request handler as a composable middleware layer — stacked with auth and logging, without the handler ever knowing it exists.

Singleton / Factory Pattern

A RateLimiterFactory builds and caches limiter instances per config; the underlying store connection (e.g. a Redis pool) is typically a process-wide singleton.

Shared State Synchronization

Once you scale horizontally, bucket/window state must live in a shared store (Redis) or be reconciled across instances — this is where most interviews pivot to distributed design.

Deep Dive: 5 Core Algorithms

Every simulator below runs a real, correct implementation of the algorithm — adjust the sliders, fire requests, and watch the accept/deny decisions in the log console.

How it works

A bucket holds up to capacity tokens. Tokens refill continuously at refill rate tokens/sec, capped at capacity. Each request spends 1 token if one is available; otherwise it's denied. Because tokens pile up while idle, a client can legitimately burst up to the full capacity at once.

space O(1)/client time O(1) bursts allowed

Try it

10.0 / 10 tokens ready

Each dot is one token. Send spends a token; if none are ready, the request is denied.

Capacity 10 Refill rate 2.0/s

Production Code

Fully working, idiomatic implementations — no placeholder logic. Each includes unit tests covering the edge cases interviewers probe for.

token_bucket.py

Concurrency, Race Conditions & Distributed Scaling

The algorithm is the easy 60% of this interview. The other 40% is proving you know it breaks under concurrent access — and how to fix that.

The Check-Then-Act Race

Two servers both read the same counter (9/10) before either writes back — both allow their request.

Server A

Server B

Pick a scenario above to run it.

Fixing it: Lua Scripts

Redis executes a Lua script as a single atomic operation — no other client's commands can interleave between the read and the write, so the check-then-act sequence becomes safe by construction.

local count = redis.call("INCR", KEYS[1])
if count == 1 then
  redis.call("EXPIRE", KEYS[1], ARGV[1])
end
if count > tonumber(ARGV[2]) then
  return 0  -- denied, atomically
end
return 1    -- allowed, atomically

Sorted Sets for Sliding Windows

A Redis ZSET keyed by timestamp implements the Sliding Log directly on the server:

ZREMRANGEBYSCOREevict timestamps older than the window

ZADDrecord this request's timestamp

ZCARDcount requests currently in-window

EXPIRElet idle keys disappear on their own

Multi-Region Considerations

Active-Active Replication

Each region runs local Redis, replicated to others asynchronously. Fast locally, but replication lag means the true global count is briefly stale — a client can slip through slightly over the limit across regions.

Local Fallback, Approximate Counters

Each region conservatively enforces limit / N regions locally and reconciles globally when connectivity allows — trading precision for availability during partitions.

Interview Cheatsheet & Quiz

A last-mile reference before the whiteboard, plus a 5-question self-check.

Algorithm Comparison Matrix

Algorithm	Memory	CPU	Burst Handling	Concurrency Complexity	Best Used For
Token Bucket	O(1) / client	Low	Allows, up to capacity	Medium — atomic decrement	Public APIs needing burst tolerance
Leaky Bucket	O(capacity)	Low–Med	Smooths, none allowed	Medium — queue processing	Traffic shaping, protecting downstream
Fixed Window Counter	O(1) / client	Very Low	Poor — 2× edge burst	Low	Simple, coarse-grained quotas
Sliding Window Log	O(n) requests	High	Precise, no edge issue	High — sorted-set ops	Low-volume, high-accuracy endpoints
Sliding Window Counter	O(1) / client	Low	Good approximation	Medium	General-purpose production default

Common Interview Traps

What actually goes wrong at a Fixed Window boundary?

A client can send limit requests in the last millisecond of one window and limit more in the first millisecond of the next — up to 2× the intended rate lands in a near-instant window. Sliding Window Counter exists specifically to fix this.

Why not just SELECT the counter, check it, then UPDATE it?

That's a classic check-then-act race: two concurrent requests can both read the same pre-update value and both proceed to write, silently letting more requests through than the limit allows. Fix it with an atomic primitive — a Lua script, INCR, or a sorted-set operation — not a read followed by a separate write.

Is Token Bucket the same thing as Leaky Bucket?

No — despite the shared "bucket" name they have opposite intents. Token Bucket permits bursts up to capacity. Leaky Bucket eliminates bursts by forcing a constant outflow rate regardless of how requests arrive.

Where should the rate limit actually be enforced?

Layered: a coarse global limit at the gateway/edge, finer per-route limits per service, and client-side backoff as a courtesy only — never trusted, since a malicious client simply won't honor it.

What should the API actually return when a request is denied?

429 Too Many Requests with a Retry-After header and the standard X-RateLimit-* headers so well-behaved clients can back off correctly instead of hammering the endpoint again immediately.

How do you fairly limit many users hiding behind one IP (NAT / corporate proxy)?

Key by the most specific identity available — authenticated user ID or API token — and fall back to IP only for anonymous traffic. Combining a coarse per-IP ceiling with a finer per-user limit is a common compromise.

Self-Assessment Quiz

0 / 5 answered

Pick one answer per question, then submit for your score.

Designing a rate limiter

Understanding & Motivation

DoS / abuse prevention

Resource starvation

Cost optimization

Cascading failure mitigation

Requirements Gathering

Functional Requirements

Non-Functional Requirements

Design Patterns Applied

Strategy Pattern

Decorator / Middleware Pattern

Singleton / Factory Pattern

Shared State Synchronization

Deep Dive: 5 Core Algorithms

How it works

Try it

How it works

Try it

How it works

Try it

How it works

Try it

How it works

Try it

Architecture & UML Diagrams

UML Class Diagram

End-to-End Sequence Diagram

Distributed Architecture

Production Code

Concurrency, Race Conditions & Distributed Scaling

The Check-Then-Act Race

Fixing it: Lua Scripts

Sorted Sets for Sliding Windows

Multi-Region Considerations

Interview Cheatsheet & Quiz

Algorithm Comparison Matrix

Common Interview Traps

Self-Assessment Quiz