Start practising

SYSTEM DESIGN · CONCEPTS · DISTRIBUTED SYSTEMS · EPISODE 30

Rate Limiting Algorithms

Why APIs limit requests, where the limiter sits, and the four algorithms interviewers expect: fixed window, sliding window log, sliding window counter and token bucket (plus leaky bucket), with their trade-offs, a Redis implementation for many servers, and the 429 response with Retry-After.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
1 / 12

Press play to hear the narration, or step through at your own pace. Every picture here is the same one used in the YouTube video.

Notes

Why

Why limit? To protect capacity from one noisy or buggy client. To stop abuse, like password guessing and scraping. To control cost when every call costs you money. And for fairness, like a free plan getting sixty requests a minute and a paid plan six hundred.

Why limit
  • protect capacity from one
  • noisy or buggy client
  • stop abuse: password guessing,
  • scraping, spam sign-ups
  • control cost (paid APIs, LLMs)
  • fairness: plans and quotas
  • (free: 60/min, pro: 600/min)

Where

Put the limiter at the edge, in the API gateway or Nginx, so rejected requests cost almost nothing. Count per key: user id, API key, IP address, or user plus endpoint. Over the limit? Return 429 Too Many Requests with a Retry-After header saying when to come back.

Where it lives
  • at the edge: API gateway,
  • load balancer, Nginx
  • (reject before doing work)
  • key: user id, API key, IP,
  • or user + endpoint
  • response: 429 Too Many Requests
  • Retry-After: 30

Fixed window

Algorithm one: fixed window. One counter per user per minute. Each request increments it; over a hundred, reject. Very simple, one number per user. The flaw: a client can send a hundred at twelve oh five fifty-nine and another hundred at twelve oh six, two hundred requests in two seconds.

1. Fixed window
limit 100 per minute
key = user:42:12:05
INCR → if > 100, reject

simple, one counter

flaw: 100 at 12:05:59
+ 100 at 12:06:00
= 200 in two seconds

Sliding log

Two: sliding window log. Store the timestamp of every request. On each new request, drop the ones older than a minute and count the rest. It's exact, with no edge burst. But it stores one entry per request, which is a lot of memory for a busy API.

2. Sliding window log
keep a timestamp per request
(sorted set)

on each request:
  drop entries older than 60 s
  count < 100 ? allow : reject

exact, no edge burst
memory: one entry per request

Sliding counter

Three: sliding window counter, the practical middle. Keep this minute's and last minute's counts. Fifteen seconds into the minute, estimate the last sixty seconds as this minute's count plus three quarters of last minute's. Thirty plus sixty is ninety: allowed. Nearly exact, and only two numbers per user.

3. Sliding window counter
two fixed counters:
previous minute: 80
current minute:  30
15 s into the current minute

estimate = 30 + 80 × 45/60
         = 90  → allow

close to exact, 2 numbers

Token bucket

Four: token bucket, the most common in real systems. Each user has a bucket of up to ten tokens that refills at one per second. Each request takes a token; empty bucket, rejected. It allows short bursts up to the bucket size while enforcing a steady average. You only store the token count and the last refill time.

4. Token bucket
bucket holds up to 10 tokens
refills 1 token per second

request takes 1 token
empty bucket → reject

allows short bursts (10)
with a steady average (1/s)

store: tokens + last refill time

Leaky bucket

A cousin, the leaky bucket, puts requests in a queue that drains at a fixed rate. The output is perfectly smooth; bursts wait or are dropped. It's ideal in front of something with a hard capacity, like a payment provider or an SMS gateway that allows exactly fifty calls a second.

Leaky bucket
  • requests enter a queue that
  • drains at a fixed rate
  • output is perfectly smooth
  • bursts wait or are dropped
  • good for protecting a
  • downstream with a hard
  • capacity (payment provider,
  • SMS gateway)

Distributed

You'll have many gateway servers, but one limit per user, so counters live in a shared store like Redis. Increment and expire in one atomic step, usually a small Lua script, to avoid races. Decide what happens if Redis is down: most APIs fail open and allow traffic, but login and payments fail closed.

Across many servers
10 gateways, one limit per user
→ counters in Redis

INCR user:42:min
EXPIRE 60 (Lua script =
atomic check-and-update)

Redis down? fail open
(allow) for most APIs,
fail closed for login

Decision

Which one? Public API quotas: token bucket or sliding window counter. Login and one-time-password abuse: a sliding window keyed by both IP and account. Protecting a downstream with a fixed capacity: leaky bucket. And when you just need something now, a fixed window is fine.

Which one?
  • public API quotas:
  • token bucket or
  • sliding window counter
  • login / OTP abuse:
  • sliding window, per IP + user
  • protect a fixed-capacity
  • downstream: leaky bucket
  • quick and good enough:
  • fixed window

Say it like this

'Design a rate limiter' is a classic question. Cover where it runs, what it's keyed on, the algorithm and why, token bucket for burst plus average, where the state lives, Redis with atomic scripts, what the client gets back, 429 with Retry-After, and what happens when the limiter's store fails.

In the interview
  • "Design a rate limiter"
  • where: gateway at the edge
  • key: user / API key / IP
  • algorithm: token bucket
  • (burst + average)
  • state: Redis, atomic Lua
  • response: 429 + Retry-After
  • failure: fail open vs closed

Interview questions

Why do APIs need rate limiting?

To protect shared capacity from noisy or buggy clients, prevent abuse such as credential stuffing and scraping, control the cost of expensive operations, and enforce per-plan quotas fairly.

What is the problem with a fixed window counter?

Requests can cluster at the boundary of two windows, so a client can send up to twice the limit within a short interval, for example 100 at the end of one minute and 100 at the start of the next.

How does a sliding window counter work?

It keeps counts for the current and previous fixed windows and estimates the last full window as current count plus previous count weighted by the fraction of the previous window still in range, giving near-exact limits with two numbers.

How does a token bucket work?

Each key has a bucket with a maximum number of tokens that refills at a fixed rate. Each request consumes a token and is rejected if the bucket is empty, allowing bursts up to the bucket size while enforcing the refill rate on average.

Token bucket vs leaky bucket?

A token bucket allows bursts and limits the average rate of accepted requests. A leaky bucket queues requests and emits them at a constant rate, smoothing output, which suits protecting a downstream with fixed capacity.

How do you rate limit across many servers?

Keep counters or buckets in a shared low-latency store such as Redis and update them atomically, for example with INCR plus EXPIRE in a Lua script, so all gateway instances enforce the same limit.

What should the API return when a client is limited?

HTTP 429 Too Many Requests with a Retry-After header, and often headers showing the limit, remaining requests and reset time so well-behaved clients can back off.

Should a rate limiter fail open or closed if its store is down?

Usually fail open for general API traffic to avoid an outage caused by the limiter, but fail closed for security-sensitive endpoints such as login, OTP and payments.