Rate Limiter

API Gateway Component

Design a rate limiting service that every API gateway node calls on each request, so that each client stays within its limits across the whole fleet, with rules that change without a deploy.

Overview

A rate limiter caps how many requests a client may send in a period of time, for example 100 requests a second per API key. It protects the service from one client's runaway script, keeps capacity fair between customers, and lets cheap and expensive endpoints carry different limits.

On one server, a counter in memory is enough. The design problem starts when the API runs on a hundred gateway nodes behind a load balancer: each node sees only part of a client's traffic, so the count has to live somewhere shared, and every request must read and update it in a few milliseconds without two nodes both spending the same last token. The algorithms themselves (fixed window, sliding window, token bucket, leaky bucket) are covered in the Rate Limiting and Token Bucket vs Leaky Bucket topics; this problem is about building the service around them.

Questions to ask first

Who is limited, and by what? — API keys, plus users, IP addresses for unauthenticated calls, and endpoints
How much traffic? — 1 million requests a second at peak across 100 gateway nodes
Must the limit be exact? — Close is fine: a few percent over for a moment is acceptable
Bursts allowed? — Yes, a short burst above the average rate
What if the limiter breaks? — Keep serving (fail open) for most endpoints; stay strict on login
How fast must rules change? — Within seconds, without a deploy

What you will be able to do

Place the limiter in the request path and say what it adds to latency.
Make check-and-spend atomic across many gateway nodes, for one limit or several at once.
Store rules, resolve which rule applies to a request, and change them in seconds.
Size and shard the counter store, and keep hot keys from overloading one shard.
Decide what happens when the counter store is down, endpoint by endpoint.

Key concepts

Token bucket
Sliding window counter
Atomic check-and-spend
Limit keys and rules
Shared counter store
Local pre-limiting
Fail open or closed
429 and Retry-After
Shadow mode

Functional requirements

Limit requests per API key, user, IP address and endpoint
Support plan tiers and per-key overrides
Allow a short burst above the average rate
Reject over-limit requests with 429 and a Retry-After value
Tell clients their quota in response headers
Change rules without restarting any node

Non-functional requirements

The check adds under 5 ms at p99 (a target we chose)
The limit holds across all gateway nodes, within a few percent
Two concurrent requests can never both spend the last token
A counter store failure never takes the API down
A rule change reaches every node within about 10 seconds (a target we chose)

Interview questions

How do you make one limit hold across a hundred gateway nodes?
Why not read the count, then write it back?
Which algorithm would you pick, and why?
What happens when the counter store is down?
How do you change limits without a deploy?
How do you apply several limits to one request?
What should the client see when it is limited?
How is this different from load shedding?