Design a Rate Limiter

Adapted from: Alex Xu, System Design Interview – An Insider's Guide (2020), Chapter 4 — rewritten and condensed for teaching.

This is the first full design problem in the series, and it follows the four-step framework from Lesson 3.

A rate limiter controls how much traffic a client or service may send. For an HTTP API, that means capping the number of requests a client can make within a time period. Once the client goes over the limit, the extra calls are blocked. Some example rules:

A user may write at most 2 posts per second.
At most 10 accounts may be created per day from one IP address.
A device may claim rewards at most 5 times per week.

Why rate limit?

Prevent resource starvation from denial-of-service (DoS). Blocking excess calls protects the service from floods of traffic, whether malicious or accidental. Nearly every large public API enforces limits. When the book was written, Twitter allowed 300 tweets per 3 hours, and the Google Docs API defaulted to 300 read requests per user per 60 seconds.
Reduce cost. Fewer excess requests means fewer servers, and capacity can go to high-priority APIs. This matters most when you pay a third party per call, for example for credit checks, payments, or health-record lookups.
Prevent overload. Filtering out excess traffic from bots or misbehaving clients keeps servers healthy.

What you'll be able to do after this lesson:

Decide where a rate limiter belongs: client, server, or gateway middleware.
Implement and compare token bucket, leaking bucket, fixed window, sliding window log, and sliding window counter.
Design a distributed rate limiter on Redis and handle race conditions and synchronization.
Communicate throttling to clients with HTTP 429 and rate-limit headers.

Step 1: Understand the Problem and Establish Scope

Candidate asks	Interviewer answers
Client-side or server-side API rate limiter?	Server-side
Throttle by IP, user ID, or something else?	Flexible: support different sets of throttle rules
What scale? Startup or large company?	Must handle a large number of requests
Will it run in a distributed environment?	Yes
Separate service, or part of the application code?	Your design decision
Should throttled users be told?	Yes

Requirements

Accurately limit excessive requests.
Low latency: the limiter must not noticeably slow down HTTP responses.
Little memory use.
Distributed: one limit shared across many servers or processes.
Clear exceptions: throttled users get a clear error.
High fault tolerance: if part of the limiter fails (say, a cache server goes offline), the rest of the system keeps working.

Step 2: High-Level Design

Where should the rate limiter live?

Client side: an unreliable place to enforce limits. Malicious clients can forge requests, and you often don't control the client code.
Server side: inside the API servers.
Middleware: a separate layer in front of the API servers that throttles requests before they reach them.

flowchart LR
  C[Client] --> RL[Rate limiter middleware] --> API[API servers]

Suppose the API allows 2 requests per second and a client sends 3 in one second. The first two pass through to the API servers. The middleware rejects the third with HTTP 429 Too Many Requests.

sequenceDiagram
  participant C as Client
  participant RL as Rate limiter
  participant API as API servers
  C->>RL: request 1
  RL->>API: forward
  C->>RL: request 2
  RL->>API: forward
  C->>RL: request 3 (same second)
  RL-->>C: 429 Too Many Requests

In microservice architectures, rate limiting usually lives in an API gateway. This is typically a managed service that also handles SSL termination, authentication, IP allow-listing, serving static content, and more. For our purposes, a gateway is simply middleware that can rate limit.

Server or gateway? There is no universal answer. Some guidelines:

Consider your stack. Make sure your language and cache service can implement rate limiting efficiently on the server.
Pick the algorithm you need. Building it yourself gives full control over the algorithm. A third-party gateway may limit your choices.
Already running a gateway for auth or allow-listing? Adding rate limiting there is natural.
Building takes engineering time. If you're short on people, a commercial gateway is the better option.

Check: placement

Quiz

Where to rate limit

1 / 2

Why is the client a poor place to enforce an API rate limit?

Pick an answer to see if you are right.

Rate-Limiting Algorithms

Each algorithm makes different trade-offs between burst tolerance, accuracy, and memory:

Algorithm	Allows bursts?	Accuracy	Memory	Used by
Token bucket	Yes, up to bucket size	Good	Low	Amazon, Stripe
Leaking bucket	No, fixed outflow	Good	Low (bounded queue)	Shopify
Fixed window counter	Yes, up to 2× at window edges	Weak at edges	Very low
Sliding window log	No	Exact	High (one timestamp per request)
Sliding window counter	Smoothed	Approximate	Low	Cloudflare

Token bucket

The token bucket is simple, well understood, and widely used (Amazon and Stripe throttle APIs with it).

A bucket holds up to a fixed number of tokens (its capacity).
A refiller adds tokens at a fixed rate. When the bucket is full, extra tokens overflow and are lost.
Each request takes one token. If a token is available, the request goes through. If not, it is dropped.

flowchart LR
  R["Refiller<br/>+2 tokens/s"] --> B[("Bucket<br/>capacity 4")]
  REQ[Request] --> CHK{Token available?}
  B -.-> CHK
  CHK -- "yes: take 1" --> API[Forward to API]
  CHK -- no --> DROP[Drop / 429]

Parameters: bucket size (maximum tokens) and refill rate (tokens per second).

How many buckets? That depends on the rules:

One bucket per endpoint per user is common. If a user may make 1 post per second, add 150 friends per day, and like 5 posts per second, each user needs 3 buckets.
To throttle by IP, each IP address gets its own bucket.
For a global cap such as 10,000 requests per second, use one bucket shared by all requests.

Pros	Cons
Easy to implement	Two parameters (size, rate) that can be hard to tune
Memory efficient (a count and a timestamp per bucket)
Allows short bursts as long as tokens remain

Practice: implement a token bucket

Instead of running a separate refiller process, compute the refill lazily on each request: tokens = min(capacity, tokens + elapsed × refill_rate). The bucket starts full at time 0.

Input: line 1 is capacity refill_rate, and line 2 is the request timestamps in seconds, in non-decreasing order. The wrapper prints allow or reject for each request.

The second test is the key one. After 10 idle seconds the bucket holds only 4 tokens, not 20, because refill stops at capacity. That cap is what keeps bursts bounded.

Leaking bucket

Like the token bucket, except requests leave at a fixed rate. It is usually built on a FIFO queue:

When a request arrives, it joins the queue if the queue isn't full. Otherwise it is dropped.
At regular intervals, requests are pulled off the queue and processed.

flowchart LR
  REQ[Requests] --> FULL{Queue full?}
  FULL -- yes --> DROP[Drop]
  FULL -- no --> Q[["FIFO queue<br/>(bucket size)"]]
  Q -- "fixed outflow rate" --> P[Process]

Parameters: bucket size (queue length) and outflow rate (requests processed per second). Shopify uses leaky buckets for its API.

Pros	Cons
Memory efficient (bounded queue)	A burst fills the queue with old requests. If those aren't processed in time, newer requests get limited
Steady outflow, good when downstream needs a stable rate	Two parameters that are hard to tune

Fixed window counter

Split the timeline into fixed-size windows, each with its own counter.
Each request increments its window's counter.
Once the counter hits the threshold, new requests are dropped until the next window starts.

With 1-second windows and a limit of 3, any fourth or later request within the same second is dropped.

The edge problem. Say the limit is 5 requests per minute, resetting on the minute. Five requests arrive between 2:00:30 and 2:01:00, and five more between 2:01:00 and 2:01:30. Each fixed window sees only 5, so all 10 go through. Yet the rolling minute from 2:00:30 to 2:01:30 contains 10 requests, twice the limit.

Pros	Cons
Memory efficient	Bursts at window edges can let through up to 2× the quota
Easy to understand
Resetting on a fixed boundary suits some use cases, such as "per calendar day"

Sliding window log

The sliding window log fixes the edge problem by remembering every request's timestamp, often in a Redis sorted set:

When a request arrives, remove timestamps that fall outside the current rolling window.
Add the new request's timestamp to the log.
If the log size is within the limit, accept the request. Otherwise reject it, but its timestamp stays in the log.

Example, with a limit of 2 requests per minute:

Arrival	Log after the update	Size	Result
1:00:01	1:00:01	1	Allowed
1:00:30	1:00:01, 1:00:30	2	Allowed
1:00:50	1:00:01, 1:00:30, 1:00:50	3	Rejected (timestamp kept)
1:01:40	1:00:50, 1:01:40 (1:00:01 and 1:00:30 are older than 1:00:40, so they are removed)	2	Allowed

Pros	Cons
Very accurate: no rolling window ever exceeds the limit	Memory heavy. It stores a timestamp per request, including rejected ones

Practice: fixed window vs. sliding log

Implement both algorithms and run them on the same request stream. Use these definitions:

fixed_window(limit, window, timestamps): the window index is t // window. Allow the request if that window's count is below limit, then increment the count.
sliding_log(limit, window, timestamps): drop logged timestamps x where x <= t - window, append t, and allow the request if the log length is <= limit. Rejected timestamps stay in the log, as in the book's version.

Input: line 1 is limit window, and line 2 is the timestamps in seconds. The wrapper prints the fixed-window results, then the sliding-log results.

The third test shows the cost of keeping rejected timestamps. At t = 1.0 and t = 1.1 the fixed window has reset, but the log still holds the rejected request from t = 0.6, so the client stays blocked. A variant that logs only accepted requests avoids this and uses less memory.

Sliding window counter

A hybrid of the fixed window counter and the sliding log. It keeps just two counters, for the current and previous fixed windows, and estimates the rolling count:

rolling count ≈ requests in current window + requests in previous window × (fraction of the rolling window that overlaps the previous window)

Example: the limit is 7 requests per minute. The previous minute had 5 requests and the current minute has 3. A new request arrives 30% of the way into the current minute, so the rolling window still overlaps 70% of the previous minute:

3 + 5 × 0.7 = 6.5, rounded down to 6.

Six is below 7, so the request goes through. After it, one more request would reach the limit. (Whether to round up or down is a policy choice.)

Pros	Cons
Smooths spikes, because the estimate blends in the previous window's average rate	Approximate: assumes requests were spread evenly across the previous window
Memory efficient (two counters)	Not suitable when the look-back window must be strict

In practice the approximation holds up well. In Cloudflare's measurements across 400 million requests, only 0.003% were wrongly allowed or limited.

Practice: sliding window counter

Implement sliding_counter(limit, prev_count, curr_count, position_pct). position_pct is how far into the current window the request arrives, as an integer from 0 to 100. Return a tuple (estimate, allowed):

estimate is the rolling count before this request, rounded down. Use integer arithmetic to avoid floating-point surprises: (curr_count * 100 + prev_count * (100 - position_pct)) // 100.
allowed is True if estimate + 1 <= limit.

Input is one line: limit prev_count curr_count position_pct.

Check: algorithms

Quiz

Choosing an algorithm

1 / 4

A flash-sale API must let customers send short bursts of requests while still capping their average rate. Which algorithm fits best?

Pick an answer to see if you are right.

High-Level Architecture

Every algorithm boils down to a counter per key (user, IP, endpoint…). If the counter is over the limit, the request is refused.

Where should the counters live? Not in a database, because disk access is too slow for something checked on every request. An in-memory cache is fast and supports time-based expiry. Redis is the popular choice, and two commands do most of the work:

INCR: increment a counter by 1.
EXPIRE: set a timeout on the counter, after which Redis deletes it automatically.

flowchart LR
  C[Client] --> RL[Rate limiter middleware]
  RL <-- "read / INCR counter" --> R[(Redis)]
  RL -- "under limit" --> API[API servers]
  RL -- "over limit" --> X[429 to client]

The client sends a request to the rate-limiting middleware.
The middleware fetches the counter for the matching bucket from Redis and checks it against the limit.
If the limit is reached, the request is rejected.
Otherwise the request is forwarded to the API servers, and the counter is incremented in Redis.

A minimal fixed-window limiter in Redis, as pseudocode:

key = f"rl:{user_id}:{now // 60}"   # one counter per user per minute
count = redis.incr(key)             # atomic; creates the key at 1 if missing
if count == 1:
    redis.expire(key, 60)           # clean up after the window
if count > LIMIT:
    return http_429()
forward_to_api()

Step 3: Design Deep Dive

The high-level design leaves two questions open: how are rules defined and stored, and what happens to throttled requests? After those, we look at distributed concerns, performance, and monitoring.

Rate-limiting rules

Lyft's open-source rate limiter expresses rules as YAML configuration. Five marketing messages per day:

domain: messaging
descriptors:
  - key: message_type
    value: marketing
    rate_limit:
      unit: day
      requests_per_unit: 5

At most five login attempts per minute:

domain: auth
descriptors:
  - key: auth_type
    value: login
    rate_limit:
      unit: minute
      requests_per_unit: 5

Rules usually live in configuration files on disk.

Exceeding the limit

A throttled request gets HTTP 429 Too Many Requests. Depending on the use case, the request may also be queued for later. For example, orders limited during an overload can be kept and processed afterward instead of being thrown away.

Rate-limiter headers

How does a client know it's being throttled, or how many requests it has left? The limiter tells it through response headers:

Header	Meaning
`X-Ratelimit-Remaining`	Requests still allowed in the current window
`X-Ratelimit-Limit`	Requests allowed per window
`X-Ratelimit-Retry-After`	Seconds to wait before a request will succeed

A throttled response carries 429 together with X-Ratelimit-Retry-After. (The IETF standard header is plain Retry-After, and many APIs send both.)

Detailed design

flowchart LR
  RULES[(Rules on disk)] --> WK[Workers] --> RC[(Rules cache)]
  C[Client] --> RL[Rate limiter middleware]
  RC --> RL
  RL <-- "counters + last-request timestamps" --> R[(Redis)]
  RL -- "allowed" --> API[API servers]
  RL -- "429 Too Many Requests" --> C
  RL -- "rate limited (optional)" --> MQ[[Message queue]]

Rules are stored on disk. Workers pull them regularly into a cache so the middleware never reads from disk on the request path.
A client request hits the rate limiter middleware first.
The middleware loads the rules from the cache, and fetches counters and last-request timestamps from Redis. Then:
- Not limited: forward to the API servers.
- Limited: return 429 to the client, and either drop the request or enqueue it for later processing.

Check: architecture and rules

Quiz

Counters, rules, and responses

1 / 2

Why store rate-limit counters in Redis rather than in the primary SQL database?

Pick an answer to see if you are right.

Rate Limiting in a Distributed Environment

A limiter on one server is easy. Many servers and concurrent threads bring two new problems.

Race conditions

The naive flow is: read the counter from Redis, check whether counter + 1 exceeds the limit, and if not, write back counter + 1. Under concurrency, that read-then-write is not atomic:

sequenceDiagram
  participant A as Request 1
  participant R as Redis (counter = 3)
  participant B as Request 2
  A->>R: read counter → 3
  B->>R: read counter → 3
  A->>R: write 4
  B->>R: write 4
  Note over R: counter = 4, but two increments happened, so it should be 5

Locks would fix this but slow the system down considerably. The common solutions:

Lua scripts: Redis runs a script atomically, so the check and the increment happen as one step.
Redis sorted sets: for sliding-log limiters, add the timestamp, trim old ones, and count in one atomic MULTI transaction.

The INCR-first pseudocode above also avoids the race: INCR is atomic and returns the new value, so there is no separate read to go stale.

Synchronization

At large scale you run several rate-limiter servers. Because the web tier is stateless, a client's requests can land on different limiters. If each limiter keeps its own counters, limiter 1 knows nothing about client 2's requests on limiter 2, and the limits leak.

flowchart LR
  subgraph Bad["Local counters: limits leak"]
    C1[Client 1] --> L1[Limiter 1]
    C2[Client 2] --> L1
    C2 --> L2[Limiter 2]
  end
  subgraph Good["Centralized counters"]
    C3[Client 1] --> L3[Limiter 1] --> R[(Redis)]
    C4[Client 2] --> L4[Limiter 2] --> R
  end

Sticky sessions (always route a client to the same limiter) would work but are neither scalable nor flexible. This is the same argument as Lesson 1's stateless web tier. The better answer is a centralized data store such as Redis that every limiter shares.

Performance optimization

Multi-data-center or edge deployment. Users far from the limiter see high latency. Providers run many edge locations (Cloudflare had 194 in May 2020) and route traffic to the nearest one.
Eventual consistency. Synchronize counters between locations with an eventual consistency model. A briefly stale count is acceptable for rate limiting. Strong consistency on every request would cost too much latency.

Monitoring

After launch, collect analytics to confirm that both the algorithm and the rules are working:

Rules too strict: many legitimate requests are dropped, so relax them.
Algorithm can't handle bursts: for example, the limiter breaks down during a flash sale. Switch to one that tolerates bursts, such as a token bucket.

Check: distributed concerns

Quiz

Race conditions and synchronization

1 / 3

Two limiter threads both read counter = 9 (limit 10) and both write 10. What happened, and what is a standard fix?

Pick an answer to see if you are right.

Step 4: Wrap Up

We covered five algorithms (token bucket, leaking bucket, fixed window, sliding window log, sliding window counter), the architecture, distributed challenges, performance, and monitoring. If time allows, more talking points:

Hard vs. soft limits. A hard limit never lets requests exceed the threshold. A soft limit lets them exceed it briefly.
Rate limiting at other layers. This lesson limited at the application layer (HTTP, OSI layer 7). You can also limit by IP at the network layer (layer 3), for example with iptables. For reference, the OSI model's seven layers are: 1 Physical, 2 Data link, 3 Network, 4 Transport, 5 Session, 6 Presentation, 7 Application.
Designing clients that avoid being limited:
- Cache responses on the client to avoid repeated calls.
- Know the limits and don't send many requests in a short span.
- Catch errors and exceptions so the client recovers gracefully.
- Add enough backoff to retry logic, such as exponential backoff with jitter.

Key Takeaways

Enforce limits on the server side or in a gateway, never only on the client.
Token bucket allows bursts. Leaking bucket gives a steady outflow. Fixed window is simple but leaks up to 2× at window edges. Sliding log is exact but memory-hungry. Sliding counter is a cheap, accurate-enough approximation.
Keep counters in Redis, not a database, and make check-and-increment atomic.
Share counters across limiter instances through a central store instead of sticky sessions.
Tell clients clearly: 429 plus rate-limit headers.

Previous lesson: A Framework for System Design Interviews.

Next lesson: Design Consistent Hashing — why hash % N breaks when servers change, the hash ring, virtual nodes, and finding affected keys.

Reference Materials

Rate-limiting strategies and techniques — Google Cloud
Twitter rate limits
Google Docs API usage limits
IBM: Microservices
Throttle API requests for better throughput — Amazon API Gateway
Stripe: Scaling your API with rate limiters
Shopify REST Admin API rate limits
Better Rate Limiting With Redis Sorted Sets — ClassDojo Engineering
System Design — Rate limiter and Data modelling
How we built rate limiting capable of scaling to millions of domains — Cloudflare
Redis
Lyft rate limiting service
Scaling your API with rate limiters (request rate limiter, Lua script)
What is edge computing? — Cloudflare
Rate Limit Requests with Iptables
OSI model: layer architecture — Wikipedia

Step 1: Understand the Problem and Establish Scope​

Requirements​

Step 2: High-Level Design​

Where should the rate limiter live?​

Check: placement​

Rate-Limiting Algorithms​

Token bucket​

Practice: implement a token bucket​

Leaking bucket​

Fixed window counter​

Sliding window log​

Practice: fixed window vs. sliding log​

Sliding window counter​

Practice: sliding window counter​

Check: algorithms​

High-Level Architecture​

Step 3: Design Deep Dive​

Rate-limiting rules​

Exceeding the limit​

Rate-limiter headers​

Detailed design​

Check: architecture and rules​

Rate Limiting in a Distributed Environment​

Race conditions​

Synchronization​

Performance optimization​

Monitoring​

Check: distributed concerns​

Step 4: Wrap Up​

Key Takeaways​

Reference Materials​

Step 1: Understand the Problem and Establish Scope

Requirements

Step 2: High-Level Design

Where should the rate limiter live?

Check: placement

Rate-Limiting Algorithms

Token bucket

Practice: implement a token bucket

Leaking bucket

Fixed window counter

Sliding window log

Practice: fixed window vs. sliding log

Sliding window counter

Practice: sliding window counter

Check: algorithms

High-Level Architecture

Step 3: Design Deep Dive

Rate-limiting rules

Exceeding the limit

Rate-limiter headers

Detailed design

Check: architecture and rules

Rate Limiting in a Distributed Environment

Race conditions

Synchronization

Performance optimization

Monitoring

Check: distributed concerns

Step 4: Wrap Up

Key Takeaways

Reference Materials