Timeouts, retries, backoff and jitter

Every real system calls other servers. One day one of them is slow or down. The interviewer asks: "The price server stops answering. What happens to your system?"

A weak answer says "we retry". A strong answer says how long a call may wait and how many times it tries. It says how long to wait between tries, and which calls it never repeats. It also knows that trying again can make a small problem much bigger.

At SDE-1 level you should know that a call needs a time limit and that a retry must be limited. At SDE-2 level you should work out the waiting times and the extra load. At SDE-3 level you should also find where retries multiply across the parts of a system.

Think about phoning a friend who does not answer. You give up after a few rings. That is a time limit. You try again after a short wait. If there is still no answer, you wait longer before the next call. And if ten friends all phone the same shop at 5:00:00, the line is busy. It is better if each calls at a slightly different random time.

A dependency is another server that your code calls to do its job. Four ideas help you to deal with a dependency that fails.

Timeouts

A timeout is the longest time a call may wait for an answer. After that time, the caller stops waiting and treats the call as failed. Without a timeout, a call to a stuck server can wait forever.

This matters because waiting is not free. While a request waits, it holds a worker: one slot of your server that handles one request at a time. The number of requests in progress is found like this:

• requests in progress = requests per second x seconds each one takes

A server has a fixed number of workers. If a slow dependency makes every request take longer, all workers fill up. Then the server cannot answer any request, even one that does not need that dependency.

To choose a timeout, look at how fast the dependency normally is. The p99 is the time that 99 of every 100 calls beat (lesson 4). A timeout at the p99 makes 1 normal call in 100 fail by mistake. A timeout above it makes fewer mistakes. This is our own advice, not a standard. A timeout that is too short fails calls that would have worked. One that is too long keeps workers busy.

Timeouts add up along a chain of calls. Suppose the phone waits at most 2 seconds for your API server. Then all the calls that the API server makes must finish inside those 2 seconds in total.

Some libraries wait forever unless you set a limit. Set one limit for opening the connection and one for waiting for the answer.

Retries

A retry is a second try of a call that failed. Many failures are short: a lost message, a server that is restarting. A retry often works.

Not every failure should be retried. Use these rules:

1. Retry a timeout, a broken connection, or a 503 status. 503 Service Unavailable means the server is too busy or down for now.
2. Do not retry most 4xx statuses, such as 400 or 404. The same request will fail again (lesson 9). Two 4xx statuses are different: 408 Request Timeout and 429 Too Many Requests. They mean "try again after a wait", so retry them after a wait.
3. Retry only a call that is safe to repeat. GET, PUT and DELETE are idempotent (lesson 9). A POST that creates something is not.
4. Remember that a timeout is not a failure report. It means "no answer". The server may have done the work and the answer was lost.
5. Limit the number of tries, for example 3 in total.

Retries help only when failures are independent. If a call fails 5% of the time, by chance, three tries all fail with chance 0.05 x 0.05 x 0.05 = 0.000125. That is 99.9875% success. But if the dependency is down, every try fails.

Backoff

Backoff means waiting between tries, and waiting longer each time. Exponential backoff doubles the wait each time. Pick a base wait and a cap, the longest wait you allow:

• wait before retry number n = min(cap, base x 2 to the power of n)
• n is 0 for the first retry, 1 for the second, and so on

With base 100 ms and cap 2,000 ms the waits are 100, 200, 400, 800 and 1,600 ms. The next would be 3,200 ms, so the cap makes it 2,000 ms. A failing server gets time to recover.

Jitter

Backoff alone has a problem. Suppose 1,000 clients fail at the same moment. They all wait 100 ms and all retry together. Then they all wait 200 ms and retry together. The load comes in waves.

Jitter is a random part added to the wait. With full jitter, you pick the wait at random between 0 and the backoff value: random(0, min(cap, base x 2 to the power of n)). The retries spread out in time.

import random, time

def call_with_retries(call, max_tries=3, base=0.1, cap=2.0):
    for attempt in range(max_tries):
        try:
            return call(timeout=0.3)
        except (TimeoutError, ConnectionError):
            if attempt == max_tries - 1:
                raise
            ceiling = min(cap, base * 2 ** attempt)
            time.sleep(random.uniform(0, ceiling))

Retry storms

A retry storm is a failure that grows because callers retry. It has two causes.

1. Layers multiply. A layer is one part that calls the next one. Suppose the phone app, the API server and the order server each retry 3 times. Every call then has up to 1 + 3 = 4 tries. One user action can become 4 x 4 x 4 = 64 calls at the last server.
2. It makes itself worse. The extra calls slow the dependency more, so more calls time out, so there are more retries.

Ways to stop a storm:

• Retry at one layer only.
• Use a retry budget: allow retries only up to a small share of normal requests.
• Wait for the time in a Retry-After header when the server sends one. This header tells the caller how long to wait, as a number of seconds or as a date.
• Give the whole action a deadline. A deadline is the time by which the answer must be ready. Pass the time left to each next call, and do not retry after the deadline.
• Always use jitter.

A shop app has a sale. The product page calls the price server with GET /price/7. A GET is safe to repeat.

Assumptions (made up to teach with, not real traffic):

• The API server has 200 workers and gets 100 requests per second. Each calls the price server once.
• The price server normally answers in 50 ms. Its p99 is 120 ms.
• The price server can handle 2,000 calls per second. 500 user actions per second reach it, from all API servers together.

Step 1: no timeout. Normally, requests in progress = 100 x 0.05 = 5. Now the price server hangs. Every request that arrives stays stuck. After 200 / 100 = 2 seconds, all 200 workers are stuck (a little less, because 5 are already busy). This answers the predict box. Every page now fails, including pages that do not need prices.

Step 2: add a timeout. We choose 300 ms, which is 2.5 times the p99 of 120 ms. Fewer than 1 normal call in 100 will time out by mistake.

• During the outage a request waits 0.3 seconds. In progress = 100 x 0.3 = 30 workers. That is 30 / 200 = 15%.
• With a 1-second timeout it would be 100 x 1 = 100 workers, which is 50%.

Step 3: add retries. Up to 3 tries, each with a 300 ms timeout, and full jitter with base 100 ms. The longest total time is 300 + 100 + 300 + 200 + 300 = 1,200 ms. The waits are at most 100 ms and 200 ms. In progress during the outage is at most 100 x 1.2 = 120 workers, or 60%. The caller of the API server must wait more than 1,200 ms. If it gives up at 500 ms, the API server works for an answer nobody reads.

Step 4: the backoff schedule. With more tries, base 100 ms and cap 2,000 ms, the waits are 100, 200, 400, 800, 1,600 and 2,000 ms. The total is 5,100 ms.

Step 5: why jitter. 1,000 clients fail together. Without jitter, 1,000 retries arrive at the same moment after 100 ms. With full jitter, the 1,000 retries spread over 0 to 100 ms: 1,000 / 100 = 10 in each millisecond. The next round spreads over 0 to 200 ms: 5 per ms. The one after that, over 0 to 400 ms: 2.5 per ms. The first-round peak is 100 times lower: 10 in a millisecond, not 1,000.

Step 6: the storm. The chain is: phone app -> API server -> order server -> price server. Each of the three callers retries 3 times. The price server normally gets 500 calls per second: 500 / 2,000 = 25% of its limit. If it fails completely:

• All three layers retry: 500 x 64 = 32,000 calls per second. That is 32,000 / 2,000 = 16 times its limit.
• Only the order server retries: 500 x 4 = 2,000 per second. That is 100% of the limit.
• Only the order server retries, with a budget of 10% extra: 500 x 1.1 = 550 per second, or 27.5%.

Only the last case leaves room to recover: 72.5% of the capacity is free.

• A timeout solves workers stuck on a dead dependency. It costs false failures when it is too short. I would set it above the p99, and lower it if workers fill up.
• Retries solve short failures. They cost extra load and extra waiting time for the user. I would retry at one layer only, with a small limit.
• Jitter solves waves of retries. It costs a slightly longer average wait, because some clients wait the full value. I would always use it for many clients.
• A retry budget solves a storm. It costs some calls that could have been saved by a retry. I would set it from the share of failures I expect on a normal day.

"A timeout means the request failed, so a retry is always safe." A timeout means no answer. The work may be done. A retried POST that creates an order can create two. Retry only calls that are safe to repeat.

"More retries mean a more reliable system." Only while failures are short and independent. With 4 tries at 3 layers, one action became 64 calls, and the price server was at 1,600% of its limit.

"Exponential backoff is enough." Without jitter, clients that failed together retry together at 100, 300 and 700 ms. Backoff changes the gaps. Jitter makes the clients stop moving in step.

1. Name the four ideas of this lesson and say in one line what each one does. Which status codes would you not retry?
2. Base wait 200 ms, cap 3,000 ms. What are the waits before retries 1 to 5 (without jitter), and what is their total?
3. A system has 4 layers. Each layer retries a failed call 2 times. The bottom server normally gets 300 calls per second and fails completely. How many calls per second does it get, and what do you change?