mufassall

Cheat sheet · Reliability

Rate limiting

13 min · Intermediate · mufassall.dtwin.uz/en/l/rate-limiting/

← Open the lesson

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 429 answer 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
Final scene
30%20%30%30%30%

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 down

Mermaid: 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 ms

D2

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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
Partner p952 400 ms87 ms
Honest errors9%0%
Over the limit90 x1.2 x

Steps

  1. 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.

  2. Fix Count requests per second

    The API now keeps a counter per IP for the current second.

  3. 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.

  4. Fix A sliding window looks back

    The sliding window counts the last second at any moment, not the calendar second.

  5. 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.

  6. Fix Token bucket: bursts allowed, average fixed

    Each client gets a bucket of up to 30 tokens, refilled at 10 per second.

  7. Problem 300 people behind one IP

    A customer's office of 300 people reaches the internet through one address.

  8. 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.

  9. Problem Three servers, three separate counters

    Traffic grows and the API runs on three servers behind a load balancer.

  10. Fix One counter in Redis

    The bucket moves to Redis, shared by all API servers.

  11. Case When the limiter itself fails

    Redis is unavailable.

  12. 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.