CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 6 of 7 · 4 min read

Telling the caller, and being a good caller

Status 429, headers that explain the limit, and how clients back off.

Telling the caller, and being a good caller

Think of a shop assistant saying "we are busy, come back in ten minutes". That is far more helpful than ignoring the customer or closing the door without a word.

When the limiter blocks a request, the server answers with HTTP status 429, "too many requests". The book also lists headers that explain the situation.

Header Meaning
X-Ratelimit-Limit How many calls are allowed per window
X-Ratelimit-Remaining How many calls are left in the window
X-Ratelimit-Retry-After How many seconds to wait before trying again

An example reply:

HTTP/1.1 429 Too Many Requests
X-Ratelimit-Limit: 100
X-Ratelimit-Remaining: 0
X-Ratelimit-Retry-After: 17

Depending on the use, a blocked request can also be dropped or put on a queue to be processed later. The book suggests that orders refused because of overload might be kept for later.

The rules should be flexible. The book shows a rule file from Lyft's open-source limiter: a rule can say that a user may send at most 5 marketing messages a day, or that a client may try to log in at most 5 times in a minute. Rules live in configuration files, so they can be changed without new code.

Good callers avoid being limited. The book lists habits:

  • Use a client cache so that the same data is not requested again and again.
  • Know the limit and do not send too many requests in a short time.
  • Catch errors and recover.
  • Add enough waiting time to retry logic.

A worked example of retry timing. A client gets 429 and retries after waiting 1, 2, 4, 8 and 16 seconds, doubling each time. This is called exponential backoff.

  • Total wait after five failures: 1 + 2 + 4 + 8 + 16 = 31 seconds.
  • If 10,000 clients all fail at the same instant and all wait exactly 1 second, they all retry together and are all refused again. Adding jitter, a random amount, to each wait spreads the retries. A random wait between 0 and 2 seconds spreads 10,000 retries to about 5,000 per second (10,000 ÷ 2), instead of 10,000 in the same instant.

The server's Retry-After value, when given, should take priority over the client's own guess.

Monitoring closes the loop, as the book says. Check that the algorithm and the rules work. If the rules are too strict, many valid requests are refused and the rules should be relaxed. If the limiter fails when traffic jumps suddenly, such as in a flash sale, the algorithm may need to change to one that allows bursts, for example the token bucket.

Interview angle

Answer in your head first, then open it.

Which algorithm do you pick?

Token bucket when short bursts are fine and memory is limited. Sliding window counter for a smooth limit with small memory. Leaky bucket when the downstream needs an even flow. Name the weakness of the one chosen.

Where does it run?

At the gateway or a middleware in front of the services, so all services share one rule set. Counters live in a shared in-memory store.

What happens with several servers?

A central store, atomic increments, and a choice between fail open and fail closed.

What does the caller see?

Status 429 with headers for the limit, the remaining calls and the time to wait.

Check yourself:

  • Which header tells a client how long to wait?
  • Why add jitter to a backoff?

Words you will meet

Word Plain meaning
Rate limiter Controls how many requests may pass in a period
Throttling Slowing down or refusing requests above the limit
Middleware Software between the caller and the application that handles each request
Token bucket Tokens refill at a steady rate, each request takes one
Leaky bucket A fixed-size queue drained at a fixed rate
FIFO First in, first out
Fixed window counter One counter per equal time window
Sliding window log A list of request times in the last window
Sliding window counter An estimate from the current and previous window counts
Burst Many requests in a short moment
Race condition A bug that depends on the timing of overlapping actions
Atomic Done completely in one step, nothing can interrupt
Fail open, fail closed Let everything through, or refuse everything, when the limiter fails
Exponential backoff Doubling the wait after each failure
Jitter A random amount added to waits
429 The status code for too many requests