[HN Gopher] Exponential Backoff and Jitter (2015)
___________________________________________________________________
Exponential Backoff and Jitter (2015)
Author : tuxie_
Score : 53 points
Date : 2021-06-14 07:14 UTC (1 days ago)
(HTM) web link (aws.amazon.com)
(TXT) w3m dump (aws.amazon.com)
| dang wrote:
| Discussed at the time:
|
| _Exponential Backoff and Jitter_ -
| https://news.ycombinator.com/item?id=9206090 - March 2015 (15
| comments)
| hderms wrote:
| 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.
| fizwhiz wrote:
| Digestible articles authored by L8+ amazon SWEs? Sign me up!
| RobertKerans wrote:
| 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.
| cpeterso wrote:
| 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?
| gwittel wrote:
| 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.
| jconley wrote:
| 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.
| motohagiography wrote:
| 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)
| an1sotropy wrote:
| 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
| fizwhiz wrote:
| This reminds me of
| https://en.wikipedia.org/wiki/Thundering_herd_problem
| praptak wrote:
| 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.
| psadri wrote:
| 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.
| nivertech wrote:
| 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
| [deleted]
___________________________________________________________________
(page generated 2021-06-15 23:01 UTC)