Let us take a real-world example. You are trying to place home delivery order via phone. Jane Doe, the restaurant steward is busy answering another call. You get a busy tone. Every time you call her she gets a waiting-tone on her line which distracts her only to make her conversation longer.
Your call to Jane Doe only makes your wait longer. Now you need to back off and call again after sometime.
There are two ways to decide what is the right sometime
- Keep calling her every 2s - Linear backoff
- Have a variable backoff time - first retry is after 2s, second retry is after another gap of 4s, third retry is after 8s and Nth retry is after 2 ^N - Exponential backoff
Various strategies
Let us now take a look at what is the merits of each of the backoff strategy
Linear backoff
Simple to implement, keep calling Jane Doe every 10 seconds.
Jane Doe needs 60s to complete her conversation and your 6th retry will succeed
Exponential backoff
There is a downside to the liner backoff, Say Jane Doe is talking to her boy friend and when you call her every 10s the waiting-tone disturbs her conversation and she starts her talk all over again. You will never be able to reach Jane Doe as she wants uninterrupted 60s to finish her conversation.
You call her after 2s, 4s, 8s, 16s, 32s, 64s, 128s, 256s, 512s. In simple terms you call with 2^n time gap. Did you notice something? Every retry gives you a better probability to allow Jane Doe to finish her conversation uninterrupted so that your call will go through little later
Exponential backoff at higher order causes looonngg wait time. Just look at the table below for the 25th retry. With exponential backoff it is going to happen after an year!
Exponential with Backoff max
To avoid the above said problem we should limit the backoff with some maximum limit. Let us say we set a max of 256s, our back off will be exponential until the 8th then become linear
Backoff Limit
What ever be the strategy, we need to have a backoff limit that is the time when you stop calling Jane Doe. Stay hungry, cook yourself or call John Doe
Comparison of various strategies
Notice how much time is elapsed from the first try in comparison with various strategies
- Linear - 4 minutes
- Exponential - An Year
- Exponential with backoff max (of 256s max) - 76 mins
| Retry | Linear | Exponential | Exponential with backoff max | |
|---|---|---|---|---|
| 1 | 1st | 10 | 2 | 2 |
| 2 | 2nd | 20 | 4 | 4 |
| 3 | 3rd | 30 | 8 | 8 |
| 4 | 4th | 40 | 16 | 16 |
| 5 | 5th | 50 | 32 | 32 |
| 6 | 6th | 60 | 64 | 64 |
| 24 | 24th | 240 | 16777216 | 4352 |
| 25 | 25th | 250 | 33554432 | 4608 |
Backoff In software
In the software world the Jane Doe is a service which might have limits in handling the requests. Understand the constraints of your dependent service and wisely choose linear backoff or exponential back off.
It is also common that the Jane Doe service is down and when it come up there is a surge of requests and Jane Doe can only handle so much and rest of the request is rejected. Having backoff helps Jane to breath
Backpressure
Taking a leaf from the fluid dynamics book, having backpressure for such requests solve ther problem gracefully.
Coming back to Jane Doe. You make a call, Jane sees your number flash in her phone. Then she messages you asking you to call him after 5mins and you happily call at that time to place your request.
Ther adds a little bit of overhead in the server but saves self from constant bombardment of requests and not starving the client more than needed
Orthogonal solution, details worth separate write ups for their own
Other Orthogonal solutions to solve ther problem
Scale horizontally
Think of cloning Jane Doe with cloned phone line
Buffering
Have mechanism where your call will be on hold for a while without disturbing Jane Doe
Callback
How about Jane Doe call you back when she sees she missed your call
Top comments (0)