Exponential Backoff and Jitter (2015) | Hacker News Reader

Exponential Backoff and Jitter (2015)

aws.amazon.com

63 pointstuxie_14 comments

While at WhatsApp, I learnt the importance of jitter the hard way.

One day one of our backend services became temporarily unavailable and caused millions (probably in 10s of millions at this point) of connected web clients to go into jitter-less retry loops. The retry requests were arriving in coordinated waves and their amplitude was so high that we had trouble bringing the service back up, causing further disruptions. Once we had dug ourselves out, the first thing we did was to make sure all retry loops had jitter.

I "re-invented" jitter back in 2010, when I developed an Erlang/OTP-based Pub/Sub server supporting up to 1M concurrent long polling connections per single topic.

After you published a message to that topic all 1M of them were closing a long polling HTTP request and immediately reconnecting. Which was causing a thundering herd problem [1], but I only learned this term much much later. The obvious solution was to add randomized delays to reconnects.

Of course that was probably the easiest part of scaling that system.

[1] https://en.wikipedia.org/wiki/Thundering_herd_problem

This looks like they learned from tcp_random_drop which was a method for combating syn flooding back in the day, and the principle appears consistent and applies to higher level abstractions like filesystem writes and others.

I'm interpreting that congestion may be the result of the client expectation of sending into a queue based on the maximum possible availability of a channel, whereas if you add randomness to the percieved availability of the channel across all clients, all clients will then send based on the perception/calculation of the mean availability, which is always less than the max as they all converge/revert to that mean.

(crazily, it could imply if we halved speed limits but didn't really enforce them, people would mentally reserve twice the time duration for a given trip, and therefore only choose discretionary travel based on that doubled time commitment, reducing the number of people using the roads together at a given time, while the ones on the road could travel double the percieved speed limit)

This reminds me of https://en.wikipedia.org/wiki/Thundering_herd_problem

This is history that I wish I knew in more detail, but I think TCP learned[1] it from Ethernet, and Ethernet learned[2] it from ALOHAnet[3] (in the 1970s).

[1] https://cs162.org/static/readings/jacobson-congestion.pdf [2] https://www.i-programmer.info/babbages-bag/398-ethernet.html... [3] https://www.cs.utexas.edu/users/lam/NRL/backoff.html

If you like this article you should check out the AWS Builders library https://aws.amazon.com/builders-library

It is absolutely full of really interesting topics that don't get covered frequently enough other than in footnotes or in overly simplified hand-waivey explanations. AWS has done a great job in trying to demystify some complex topics.

Digestible articles authored by L8+ amazon SWEs? Sign me up!

Oh, as I dig through it this seems to be pretty good! The bits of AWS I have to deal with daily tend to drive me up the wall but I'd be a lot happier to take that if I've a deeper understanding of the whys and wherefores.

Corridor advice: add jitter to everything. A mobile device coming online might seem random enough by itself, so why add jitter to it?

Well, those things go on and off at random but then the mobile operator fixes a huge network outage and boom, several million devices go online at once.

The article concludes: "The return on implementation complexity of using jittered backoff is huge, and it should be considered a standard approach for remote clients." But if I am reading the graphs correctly, the "None" backoff algorithm was twice as fast as the jitter algorithms but didn't get any mention in the text. What am I missing?

Its not presented in a very clear way from the charts alone -- Here the goal was to reduce/optimize the amount of unnecessary 'work' done. There is an implied cost of handling more work where contention is the root cause of extra (unnecessary) work. We're basically saying "I'd rather have a little more latency vs handle X times higher load".

One common real world situation where this comes into play are things like thundering herd scenarios. Rather than trying to cope with huge bursts of traffic, we want to spread the load out in time.

what you are missing is that there are two sets of graphs, since there are two ways of measuring performance: number of calls (scales as n^2 with no backoff) and time to completion (scales linearly with no backoff) and an unjittered backoff will improve the number of calls while making the time to completion hugely worse (exponential?) - but jittered backoff looks to drop the number of calls substantially and also scales almost linearly, while still not doing too badly on time to completion.

Discussed at the time:

Exponential Backoff and Jitter - https://news.ycombinator.com/item?id=9206090 - March 2015 (15 comments)

I feel like this is a lesson that the engineer(s) on every big scale service learns the hard way... :) I wish more libraries did this sort of thing out of the box.

Reply on news.ycombinator.com