System Design: Rate Limiter (1M Requests/sec, Sub-ms Decision Latency)
1. The Problem in One Page
Think of a public API with 10,000 customer companies. We'll call each company a tenant. Each tenant has many users. Each user calls many endpoints.
Now one tenant releases a bug, and their app starts to retry every failed call immediately, again and again, with no wait in between.
In a few seconds that one tenant is using most of your servers, and the other 9,999 tenants see timeouts for something they didn't do.
A rate limiter stops this by counting requests per caller and saying no as soon as a caller goes over their share.
The answer it gives to a caller who is over the limit is the HTTP status 429 Too Many Requests.
That sounds simple, and counting is the simple part, but three other things make it hard.
It sits in front of every request.
Whatever time the limiter takes is added to every API call you serve, so a 10 ms check makes your whole API 10 ms slower.
So the check has to be fast, and in this design we're aiming for a median under one millisecond.
The count has to be shared.
Say you have 40 gateway servers and a user is allowed 100 requests a minute.
With a count in each server, the user can send 100 requests to each one, and that's 4,000 requests with no server seeing a problem.
So the count has to live in one shared place, but a shared place means a network call and every network call costs time.
Most of this design, from the script to the leases to the fallback, is about that one conflict between sharing and speed.
It must not become the outage.
A limiter whose counter store is down can fail in two ways, by letting everything through or by blocking everything.
Blocking everything means your whole API is down for the single reason that a counter store is down. Nobody would accept that.
But letting everything through means the tenant with the bug is overloading you again, so we need something in between, and section 10 explains it.
The numbers we design for:
- 1M decisions per second at peak
- 10,000 tenants
- 100M live counter keys (tenant, user and endpoint combinations)
- 40 gateway pods, each handling about 25,000 requests a second
- Median decision under 1 ms
These are design inputs for this post. They aren't measurements from a real company.
Mistakes this design avoids:
- Counting in each server's memory only. The user gets 40 times the limit.
- Counting in a SQL database. One row update per request means a million row locks a second.
- One network call per level. Four levels would mean four round trips. One script can check all of them.
- Blocking all traffic when the counter store is down. A helper system shouldn't be able to stop the main one.
- Trusting each server's clock. Two servers that disagree by two seconds are in different windows.
- One Valkey node. A node runs commands one at a time on a single thread, so it has a hard speed limit, and if it dies every counter is gone.
- Sending a new rule to every server at the same time. A wrong limit is the fastest way to block your own customers.
2. Requirements
2.1 Functional Requirements
| ID | Requirement | Priority |
|---|---|---|
| FR-01 | Decide allow or deny for each incoming request | P0 |
| FR-02 | Limits per tenant (for example 10,000 a minute) | P0 |
| FR-03 | Limits per user (for example 100 a minute) | P0 |
| FR-04 | Limits per endpoint (for example 50 a minute on search) | P0 |
| FR-05 | A global limit across all tenants | P0 |
| FR-06 | Tell the client the limit, what is left, and when to retry | P0 |
| FR-07 | Change rules without restarting anything | P0 |
| FR-08 | Limits per IP for callers who aren't logged in | P1 |
| FR-09 | Burst allowance (token bucket) | P1 |
| FR-10 | Requests with different costs (a bulk call costs more than a read) | P1 |
| FR-11 | Shadow mode, where a rule only logs what it would have denied | P1 |
| FR-12 | Overrides and a bypass list | P1 |
| FR-13 | Analytics: who is limited, by which rule, how close each tenant is | P1 |
| FR-14 | A webhook when a tenant passes 80% of a limit | P2 |
2.2 Non-Functional Requirements
| ID | Requirement | Target |
|---|---|---|
| NFR-01 | Decision latency, median | under 1 ms |
| NFR-02 | Decision latency, p99 | under 2 ms |
| NFR-03 | Hard timeout on the counter call | 3 ms, then decide locally |
| NFR-04 | Throughput | 1M decisions a second |
| NFR-05 | Availability of the decision | The gateway always gets an answer |
| NFR-06 | Accuracy when healthy | within 5% of the limit for normal traffic. Worst case in section 5.3. |
| NFR-07 | Accuracy when Valkey is down | has a known maximum, see section 10 |
| NFR-08 | Rule change reaches all pods | under 5 seconds by push, 30 seconds worst case |
| NFR-09 | Counter durability | Not needed for short windows |
| NFR-10 | Wrong denials | fewer than 1 in 10,000 denials (section 15.5) |
| NFR-11 | Decisions made with a real shared count, not from a pod's fallback memory | 99.9% over a month |
A note on p99. "p99" means 99 out of 100 calls are faster than this number.
The title says sub-millisecond, and the median is. The p99 target is 2 ms, and I prefer to say so here than to promise a number the design can't keep.
The reason is short. Our counters sit in three zones for safety, and a call to another zone is slower. Section 8.2 has the detail.
2.3 Out of Scope
- Stopping a large DDoS. That's the job of the CDN or the edge network. Our limiter sees traffic only after it reaches the gateway.
- Billing. A monthly quota that turns into money needs a durable ledger. We'll show where it connects, and stop there.
- Bot detection. Deciding that a caller is a bot is a different system. The limiter only counts.
3. Where the Limiter Sits
🔒 Premium section
4. Architecture
🔒 Premium section
5. The Algorithms, All Eight
🔒 Premium section
6. The Counter Path
🔒 Premium section
7. Capacity
🔒 Premium section
8. How Should Valkey Be Set Up?
🔒 Premium section
9. The Rule Engine
🔒 Premium section
10. What Happens When Each Part Goes Down
🔒 Premium section
11. Bottlenecks and How to Fix Them
🔒 Premium section
12. Regions and Scaling
🔒 Premium section
13. Analytics
🔒 Premium section
14. Operations
🔒 Premium section
15. Cost, Migration and Ownership
🔒 Premium section
16. The Trade-off Ledger
🔒 Premium section
17. Questions You'll Get Asked
🔒 Premium section
Appendix: The GCRA Script
🔒 Premium section
Explore the Technologies
🔒 Premium section
