Cheat sheet · Reliability
Rate limiting
The problem
One noisy client can slow an API down for everyone. How to cap each client fairly: windows, token buckets, 429 answers and a counter shared by all servers.
What you learn
- Fixed window, sliding window and token bucket, and where each fails
- What a good
429answer tells the client - Whom to limit: an IP, an API key or a user
- Why the counter must be shared, and what to do when it is gone
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_partner(["Partner app"])
n_bot(["Script"])
n_api["API"]
n_db[("Database")]
n_office(["Office (300 people)"])
n_lb{"Load balancer"}
n_api2["API 2"]
n_api3["API 3"]
n_redis{{"Redis"}}
n_api -->|"call"| n_db
n_partner -->|"call"| n_lb
n_office -->|"call"| n_lb
n_bot -->|"call"| n_lb
n_lb -->|"call"| n_api
n_lb -->|"call"| n_api2
n_lb -->|"call"| n_api3
n_api2 -->|"call"| n_db
n_api3 -->|"call"| n_db
n_api --x|"lost"| n_redis
n_api2 --x|"lost"| n_redis
n_api3 --x|"lost"| n_redis
classDef down fill:#fde2e2,stroke:#c62828,color:#4a0d0d,stroke-dasharray:4 3
class n_redis downMermaid: request sequence
sequenceDiagram
participant n_bot as Script
participant n_api as API
participant n_partner as Partner app
participant n_office as Office (300 people)
participant n_lb as Load balancer
participant n_redis as Redis
Note over n_bot,n_api: One script takes the whole API
n_bot->>n_api: GET /v1/products?page=8812 HTTP/1.1
n_api-->>n_bot: HTTP/1.1 200 OK
Note over n_bot,n_api: Count requests per second
n_bot->>n_api: GET /v1/products?page=8812 HTTP/1.1
n_api-->>n_bot: HTTP/1.1 429 Too Many Requests
Note over n_bot,n_api: Twice the limit at the window edge
n_bot->>n_api: limit 10 per second, fixed window, ip=198.51.100.7
Note over n_bot,n_api: A sliding window looks back
n_bot->>n_api: sliding window, ip=198.51.100.7, t=12:00:01.250
Note over n_partner,n_api: An honest burst is rejected
n_partner->>n_api: partner app opens: 25 requests in 300 ms
Note over n_partner,n_api: Token bucket: bursts allowed, average fixed
n_partner->>n_api: token bucket ip=203.0.113.24: capacity=30 refill=10/s
Note over n_office,n_api: 300 people behind one IP
n_office->>n_api: GET /v1/orders HTTP/1.1
n_api-->>n_office: HTTP/1.1 429 Too Many Requests
Note over n_office,n_api: Limit by key, not by address
n_office->>n_api: GET /v1/orders HTTP/1.1
n_api-->>n_office: HTTP/1.1 200 OK
Note over n_bot,n_lb: Three servers, three separate counters
n_bot->>n_lb: local counters, key_id=k_88, limit 10/s
Note over n_api,n_redis: One counter in Redis
n_api->>n_redis: EVALSHA 9f2c7a1e4b8d3f60a5c2e7b19d4f8a6c3e1b2d07 1 rl:k_88 30 10
n_redis-->>n_api: 1) (integer) 0
Note over n_api,n_redis: When the limiter itself fails
n_api-xn_redis: rate limiter: redis timeout after 20 msD2
direction: right
n_partner: "Partner app" {
shape: rectangle
}
n_bot: "Script" {
shape: rectangle
}
n_api: "API" {
shape: rectangle
}
n_db: "Database" {
shape: cylinder
}
n_office: "Office (300 people)" {
shape: rectangle
}
n_lb: "Load balancer" {
shape: diamond
}
n_api2: "API 2" {
shape: rectangle
}
n_api3: "API 3" {
shape: rectangle
}
n_redis: "Redis" {
shape: hexagon
style.fill: "#fde2e2"
style.stroke: "#c62828"
style.stroke-dash: 3
}
n_api -> n_db: "call"
n_partner -> n_lb: "call"
n_office -> n_lb: "call"
n_bot -> n_lb: "call"
n_lb -> n_api: "call"
n_lb -> n_api2: "call"
n_lb -> n_api3: "call"
n_api2 -> n_db: "call"
n_api3 -> n_db: "call"
n_api -> n_redis: "lost" {
target-arrowhead.shape: cross
}
n_api2 -> n_redis: "lost" {
target-arrowhead.shape: cross
}
n_api3 -> n_redis: "lost" {
target-arrowhead.shape: cross
}PlantUML: request sequence
@startuml
participant "Script" as n_bot
participant "API" as n_api
participant "Partner app" as n_partner
participant "Office (300 people)" as n_office
participant "Load balancer" as n_lb
collections "Redis" as n_redis
note over n_bot, n_api : One script takes the whole API
n_bot -> n_api : GET /v1/products?page=8812 HTTP/1.1
n_api --> n_bot : HTTP/1.1 200 OK
note over n_bot, n_api : Count requests per second
n_bot -> n_api : GET /v1/products?page=8812 HTTP/1.1
n_api --> n_bot : HTTP/1.1 429 Too Many Requests
note over n_bot, n_api : Twice the limit at the window edge
n_bot -> n_api : limit 10 per second, fixed window, ip=198.51.100.7
note over n_bot, n_api : A sliding window looks back
n_bot -> n_api : sliding window, ip=198.51.100.7, t=12:00:01.250
note over n_partner, n_api : An honest burst is rejected
n_partner -> n_api : partner app opens: 25 requests in 300 ms
note over n_partner, n_api : Token bucket: bursts allowed, average fixed
n_partner -> n_api : token bucket ip=203.0.113.24: capacity=30 refill=10/s
note over n_office, n_api : 300 people behind one IP
n_office -> n_api : GET /v1/orders HTTP/1.1
n_api --> n_office : HTTP/1.1 429 Too Many Requests
note over n_office, n_api : Limit by key, not by address
n_office -> n_api : GET /v1/orders HTTP/1.1
n_api --> n_office : HTTP/1.1 200 OK
note over n_bot, n_lb : Three servers, three separate counters
n_bot -> n_lb : local counters, key_id=k_88, limit 10/s
note over n_api, n_redis : One counter in Redis
n_api -> n_redis : EVALSHA 9f2c7a1e4b8d3f60a5c2e7b19d4f8a6c3e1b2d07 1 rl:k_88 30 10
n_redis --> n_api : 1) (integer) 0
note over n_api, n_redis : When the limiter itself fails
n_api ->x n_redis : [lost] rate limiter: redis timeout after 20 ms
@endumlPlantUML: components
@startuml
left to right direction
agent "Partner app" as n_partner
agent "Script" as n_bot
component "API" as n_api
database "Database" as n_db
agent "Office (300 people)" as n_office
node "Load balancer" as n_lb
component "API 2" as n_api2
component "API 3" as n_api3
stack "Redis" as n_redis #fde2e2;line:c62828;line.dashed
n_api --> n_db : call
n_partner --> n_lb : call
n_office --> n_lb : call
n_bot --> n_lb : call
n_lb --> n_api : call
n_lb --> n_api2 : call
n_lb --> n_api3 : call
n_api2 --> n_db : call
n_api3 --> n_db : call
n_api -[#c62828,dashed]-> n_redis : lost
n_api2 -[#c62828,dashed]-> n_redis : lost
n_api3 -[#c62828,dashed]-> n_redis : lost
@endumlRecap
A rate limit protects everyone else from one client, and it must be cheap to say no.
1) Fixed windows leak at the edges; sliding windows and token buckets do not. 2) Token buckets allow honest bursts and hold the average. 3) Answer 429 with Retry-After. 4) Limit by key or user, use IP only for anonymous calls. 5) With many servers, keep the counter in one shared place and decide how to fail without it.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Partner p95 | 2 400 ms | 87 ms |
| Honest errors | 9% | 0% |
| Over the limit | 90 x | 1.2 x |
Steps
- Problem One script takes the whole API
Someone runs a script that pages through the whole catalogue as fast as it can: 900 requests a second.
- Fix Count requests per second
The API now keeps a counter per IP for the current second.
- Problem Twice the limit at the window edge
The script learns the rhythm: 10 requests at the very end of one second, 10 more at the very start of the next.
- Fix A sliding window looks back
The sliding window counts the last second at any moment, not the calendar second.
- Problem An honest burst is rejected
When the partner app opens, it loads the home screen with 25 requests at once and then is quiet for a minute.
- Fix Token bucket: bursts allowed, average fixed
Each client gets a bucket of up to 30 tokens, refilled at 10 per second.
- Problem 300 people behind one IP
A customer's office of 300 people reaches the internet through one address.
- Fix Limit by key, not by address
Authenticated calls are now limited per API key (or per user); the IP limit stays only for anonymous endpoints like login, and it is much looser.
- Problem Three servers, three separate counters
Traffic grows and the API runs on three servers behind a load balancer.
- Fix One counter in Redis
The bucket moves to Redis, shared by all API servers.
- Case When the limiter itself fails
Redis is unavailable.
- Recap Recap
A rate limit protects everyone else from one client, and it must be cheap to say no.
Terms
- Rate limiting
- Capping how many requests one client may send per unit of time, to protect everyone else. Over the limit the answer is 429 with Retry-After, and the counter is shared by all servers.
- Token bucket
- Each client has a bucket of limited size refilled at a steady rate, and each request takes one token. Honest bursts fit, while the average rate stays fixed.