The whiteboard for this problem is in
excalidraw/2. Design Rate Limiting.excalidraw. This file is the full write up
of that board.
1. Problem Statement
Services break down under sudden load. A rate limiter is the piece that keeps that from happening. It counts how many requests a caller has made in a period, lets them through while they are under the limit, and rejects them with HTTP 429 once they cross it.
We have to design a limiter that:
- Limits the number of requests in a given period.
- Lets developers configure the threshold at a granular level, per user, per IP, per API token, per endpoint.
- Does not add meaningful overhead to the request it is protecting.
2. Requirements
2.1 Functional Requirements
| Requirement | Detail |
|---|---|
| Count requests per key | The key can be a user id, an IP, or an API token |
| Enforce a threshold | For example 100 requests per minute |
| Configurable rules | Different limits per endpoint, per plan tier, per client |
| Correct response | Allow, or reject with 429 and a Retry-After header |
| Tell the caller where they stand | Return remaining quota and reset time in headers |
| Rules can change without a deploy | Config is fetched, not hardcoded |
2.2 Non Functional Requirements
- Low overhead. The limiter check must add single digit milliseconds. It runs on every single request, so anything slower is worse than the problem.
- Accurate enough. It must not block legitimate callers. Being slightly generous at a boundary is acceptable, wrongly rejecting a paying customer is not.
- Highly available. If the limiter is down, the protected service must still work. The limiter must never be the reason the site is down.
- Horizontally scalable. It has to work with many API servers in many regions, not one process.
- Atomic counting. Two concurrent requests for the same key must not both read the same count and both be allowed.
2.3 Out of Scope
Bot detection, WAF rules, DDoS scrubbing at the network layer, billing based on usage.
3. Where Does It Fit
This is the first design decision, and it matters more than the algorithm.
3.1 At the Proxy or Gateway
The request never reaches the service when it is rejected. That saves service CPU, database queries and downstream network calls. This is the production standard, and it is what nginx, an API gateway or Cloudflare give you.
3.2 Inside the Service
Here the request does hit the service and the limiter runs as middleware. Use this only when there is no gateway in front, or when internal service to service traffic needs protection that a public gateway never sees.
Pick either one, but know what you gave up. The gateway saves work, the in service version sees business context the gateway does not have.
4. Dissecting the Limiter
The limiter has to track how many requests happened in the current period. That means it needs storage, and the access pattern tells us which kind.
- Every incoming request writes, it increments a counter.
- Every incoming request reads, it compares the counter to the limit.
- Counters have to expire when the period ends.
So: a key value store with per key expiry, in memory speed, and atomic increments. That is Redis.
key: ratelimit:user:1729:minute:2026-08-19T10:31
value: 47
TTL: 60 secondsResetting the counter is the same thing as expiring the key, so we never write a cleanup job. Redis also persists periodically, which is enough here because losing a few counters on restart only means a few callers get a fresh window.
4.1 Key Design and Size
| Key type | Key size | Value size | Total per entry |
|---|---|---|---|
user_id | 4 B | 4 B | 8 B |
ip (IPv6) | 16 B | 4 B | 20 B |
token | 16 B | 4 B | 20 B |
Taking the largest case at 100 million active keys:
20 B x 100M = 2,000 MB = 2 GBTwo gigabytes is nothing for a Redis cluster. Data is not the concern here, compute is. We shard for request throughput, not for storage.
5. Deployment Shapes
5.1 Limiter as Its Own Service
Clean boundary, Redis internals hidden behind an API. The cost is two extra network hops on the hot path of every request. Nothing is wrong with this shape, just be aware of the tradeoff.
5.2 Limiter as a Library
All the business logic lives in a library that the service imports, and the service talks to Redis directly. This saves two network hops, which is exactly what the low overhead requirement asked for. The cost is that Redis endpoints and key layout are now known to every caller, and a library upgrade means redeploying every service.
For a limiter, saving two hops per request usually wins, so we go with the library shape.
6. Algorithms
6.1 Token Bucket
A bucket holds tokens up to a capacity and refills at a fixed rate. Each request takes one token. No token means reject.
- Allows bursts up to the bucket size, then settles to the refill rate.
- Two numbers per key: token count and last refill time.
- This is what most real systems use.
6.2 Leaky Bucket
Requests enter a queue and are processed at a constant rate. A full bucket drops requests.
- Output rate is perfectly constant, which smooths traffic.
- No bursts allowed at all, so valid requests get dropped during a spike.
- One line: it enforces a constant processing rate by queuing and dropping the overflow.
6.3 Fixed Window Counter
Count requests per discrete window, such as per calendar minute, and reset at the boundary.
- Simplest to build, one integer per key, cheapest memory.
- Boundary burst problem: 100 requests at 10:00:59 and 100 more at 10:01:00 means 200 requests inside one second while both windows individually look legal.
- One line: it counts requests in discrete intervals but has boundary burst issues.
6.4 Sliding Window
Track requests over a moving time range instead of a fixed one.
- Sliding log: store a timestamp per request in a Redis sorted set, drop entries older than the window, count what is left. Exact, but memory grows with request count.
- Sliding counter: keep the current and previous fixed window counts and weight the previous one by how much of it still overlaps. Nearly as accurate for a fraction of the memory.
- One line: it limits based on a continuously moving time range, which gives the most accurate control.
6.5 Comparison
| Algorithm | Burst handling | Accuracy | Complexity | Memory per key |
|---|---|---|---|---|
| Token bucket | Good, bounded burst | High | Medium | Two numbers |
| Leaky bucket | None | Medium | Medium | Queue state |
| Fixed window | Poor | Low | Low | One integer |
| Sliding log | Good | Exact | High | One entry per request |
| Sliding counter | Good | High | Medium | Two integers |
What to say in an interview: "I would prefer sliding window for accuracy, but in most real systems token bucket is used because it balances burst handling and simplicity."
6.6 Atomic Increment
The check and the increment must be one atomic step. Two requests must not both read 99 and both be allowed through a limit of 100. In Redis:
MULTI
INCR ratelimit:user:1729:2026-08-19T10:31
EXPIRE ratelimit:user:1729:2026-08-19T10:31 60 NX
EXECFor anything more involved, a small Lua script runs the whole read, decide and write on the Redis server in one shot. That is how token bucket refill is implemented correctly under concurrency.
7. Scaling
Because the service talks to Redis directly, scaling the limiter is the same thing as scaling Redis.
| Question | Answer | Why |
|---|---|---|
| Scale vertically? | Yes | A bigger Redis box handles far more operations per second, and it is the cheapest first move |
| Add read replicas? | No | The traffic is not read heavy, every request writes. Replicas do not help writes |
| Shard the database? | Yes | Access is purely key based, so the keyspace splits cleanly |
Every key is independent, so hash(user_id) % N picks a shard and the same
caller always lands on the same shard. No cross shard reads, no coordination.
Consistent hashing is the better choice if shards get added or removed while
running, because plain modulo remaps almost every key when N changes.
7.1 Startup and Runtime Flow
- The service starts, the limiter library initializes.
- The library fetches configuration from a central config service: shard endpoints, limits per endpoint, limits per plan tier.
- It opens connections to all Redis shards.
- A request arrives. The library pulls
user_idfrom the token. - It computes the shard from the hash of the key.
- It runs the atomic increment with expiry against that shard.
- Under the limit, the request proceeds. Over the limit, it returns 429.
The rejection path:
8. Configuration Model
Rules should not live in code. A small relational table read by the config service is enough, since it is tiny and rarely written.
rate_limit_rules
| Column | Type | Notes |
|---|---|---|
id | uuid | Primary key |
scope | enum | USER, IP, TOKEN, GLOBAL |
endpoint_pattern | text | For example POST /payments, or * |
plan_tier | text | free, pro, enterprise, null for all |
limit_count | integer | Requests allowed |
window_seconds | integer | Period length |
algorithm | enum | TOKEN_BUCKET, FIXED_WINDOW, SLIDING_COUNTER |
burst_capacity | integer | Token bucket only |
enabled | boolean | Kill switch per rule |
updated_at | timestamptz |
Relationship wise this is deliberately flat. There are no joins on the hot path, because the hot path never reads this table. The library loads all rules at startup and refreshes them on a timer, so a rule change reaches every service within one refresh interval and needs no deploy.
Most specific rule wins: an exact endpoint plus tier match beats an endpoint match, which beats the wildcard default.
9. Response Contract
| Header | Example | Meaning |
|---|---|---|
X-RateLimit-Limit | 100 | Allowance for this window |
X-RateLimit-Remaining | 53 | Requests left |
X-RateLimit-Reset | 1755600000 | Epoch second when the window resets |
Retry-After | 12 | Seconds to wait, sent on 429 only |
Returning these turns a mystery failure into something a client can back off from correctly.
10. Failure Handling
| Failure | Effect | Handling |
|---|---|---|
| Redis shard unreachable | Cannot count for keys on that shard | Fail open, allow the request and log it. The limiter must never take the service down |
| Redis latency spike | Every request slows | Hard timeout of a few milliseconds on the limiter call, treat a timeout as allow |
| All of Redis down | No limiting at all | Fall back to a per process in memory counter. Less accurate, still some protection |
| Config service down | Rules cannot refresh | Keep serving the last known good config from memory |
| Clock skew between servers | Window boundaries disagree | Use Redis server time, not application time |
| Hot key, one huge caller | One shard saturates | Add a per key local counter in front, or split that key across sub keys and sum |
Fail open is the decision worth defending out loud. A limiter that fails closed turns its own outage into a full site outage, which is a much worse failure than briefly letting extra traffic through.
11. Tradeoffs
| Decision | Chosen | Alternative | Reason |
|---|---|---|---|
| Placement | Gateway or proxy | Inside the service | Rejected requests never cost service CPU |
| Shape | Library plus direct Redis | Standalone limiter service | Saves two network hops on every request |
| Store | Redis | Relational database | Needs atomic increments, expiry and in memory speed |
| Algorithm | Token bucket by default | Sliding log | Bounded bursts with tiny state |
| Scaling | Vertical then shard | Read replicas | The load is writes, replicas do not help |
| Sharding key | Hash of limit key | Range partitioning | Even spread, no hot ranges |
| On failure | Fail open | Fail closed | The limiter must not become the outage |
12. Interview Talking Points
- Answer "where does it fit" before "which algorithm". Placement is what actually saves capacity.
- Say the numbers: 20 bytes times 100 million keys is 2 GB, so compute is the constraint and not storage. That sentence justifies sharding for throughput.
- Explain why read replicas are the wrong answer here. Every request is a write.
- Insist on atomicity, and name Lua or MULTI as the mechanism.
- State the fail open decision and why. Interviewers look for it.
- Mention the fixed window boundary burst with the 10:00:59 example, it shows you understand the algorithm rather than reciting it.