Re:Exponential Backoff and Jitter
by arghbleargh on Sunday March 15, 2015 @01:39PM
(#9207282)
> It’s worth noting that none of these approaches fundamentally change the N^2 nature of the work to be done, but do substantially reduce work at reasonable levels of contention.
I don't think that statement from the article is true if I understood correctly... the performance gains are precisely because you're reducing from N^2 to N log N.
An interesting theoretical question would be to identify the optimal backoff policy. I think FullJitter should be close to optimal, but maybe you can squeeze out a little more with something more sophisticated.
Edit: I just realized the DecorrelatedJitter (not sure why it's called that?) makes a lot of sense as a minor optimization because if you already waited a long time and still failed, that suggests there is a lot of contention, and you should wait even longer.
Re:Exponential Backoff and Jitter
by tptacek on Sunday March 15, 2015 @11:21AM
(#9206761)
Great post. There's a classic LBL paper about self-synchronization in (I think) time protocols that demonstrates the same conclusion in a more dramatic way.
Re:Exponential Backoff and Jitter
by diggs on Sunday March 15, 2015 @05:32PM
(#9208244)
What a coincidence, I found myself writing a little Go lib for exponential back off yesterday, and was wondering what the purpose of introducing jitter was and what effects it would have. I need it for interacting with the Twitter stream api and they're pretty clear that when they say exponential they mean it. But jitter looks very useful in some situations after reading this, so I added that to my lib as well...
(apologies for the long link, I keep all my one-file python libs in a single git repo for sanity. I think i've uploaded this one to pypi, where it's available under the name "backoff")
Re:Exponential Backoff and Jitter
by powertower on Sunday March 15, 2015 @04:19PM
(#9207947)
Wouldn't this be completely alleviated by placing each new connection into a queue, instead of rejecting it and telling the client to try again? Or am I reading this wrong?
Re:Exponential Backoff and Jitter
by djb_hackernews on Sunday March 15, 2015 @05:01PM
(#9208113)
The simplest way to understand OCC is to basically take any of your models and add a version attribute and whenever you update an object you also do an UPDATE ... WHERE version={obj.version}.
This is useful when you don't want writes to overwrite previous writes. If the version check doesn't hold it fails letting your client know that your assumptions about the state of the data are wrong. You then have a few options, like either redoing your computation using the new state or not doing anything at all because the current state is good.
Re:Exponential Backoff and Jitter
by TheLoneWolfling on Sunday March 15, 2015 @12:08PM
(#9206957)
The version with jitter but without exponential backoff is still doing O(n^2) work, I'm pretty sure, although with a (much) smaller constant.
Just something to keep in mind.
Also, I find the inherent time taken / work done tradeoff interesting. Something involving a limited amount of server state might work better on the work front while keeping the work done limited. (Something like "please don't try again for x ms" sent as a reply)
The ideal case is, what, 2n-1 calls (everyone sends at once, server replies to the first guy and schedules all other clients such that there is no contention) and O(n) (what is the scale factor here? 20ms?) delay? Are there any algorithms that come close to the limit?
Re:Exponential Backoff and Jitter
by oautholaf on Sunday March 15, 2015 @03:18PM
(#9207669)
I wish the experimenter had explored random distributions other than uniform. I suspect uniform distribution may be non-ideal here and other distributions may produce better results.
Re:Exponential Backoff and Jitter
by encoderer on Sunday March 15, 2015 @03:09PM
(#9207623)
I've always thought of "jitter" as just adding a dash of entropy to the system I'm building.
I suppose a textbook example is... If I'm managing a pool of long-running threads I want to periodically bounce, I could write logic to throttle respawning threads. Or I could just add a rand() to the conditional -- introduce "jitter" -- and let probability theory "throttle" for me.
I'd rather build on top of probability than statistics.
Re:Exponential Backoff and Jitter
by kabdib on Sunday March 15, 2015 @04:09PM
(#9207906)
Nice post.
Use of pure color in a graph makes me sad, though. This colorblind guy had to crack open a paint program and match up RGB values. A few dotted/dashed lines go a long way (and I suspect, for more than just colorblind folks, too).
I don't think that statement from the article is true if I understood correctly... the performance gains are precisely because you're reducing from N^2 to N log N.
An interesting theoretical question would be to identify the optimal backoff policy. I think FullJitter should be close to optimal, but maybe you can squeeze out a little more with something more sophisticated.
Edit: I just realized the DecorrelatedJitter (not sure why it's called that?) makes a lot of sense as a minor optimization because if you already waited a long time and still failed, that suggests there is a lot of contention, and you should wait even longer.
[1] http://ee.lbl.gov/papers/sync_94.pdf
Thanks for finding that.
It's here if anyone's interested it https://github.com/Diggs/go-backoff
https://github.com/ekimekim/pylibs/blob/master/libs/backoff....
(apologies for the long link, I keep all my one-file python libs in a single git repo for sanity. I think i've uploaded this one to pypi, where it's available under the name "backoff")
Thought you might be interested in my Elixir impl, though not as featureful: https://github.com/rickhull/backoff/blob/master/lib/backoff....
Example usage: https://github.com/rickhull/backoff/blob/master/examples/dem...
This is useful when you don't want writes to overwrite previous writes. If the version check doesn't hold it fails letting your client know that your assumptions about the state of the data are wrong. You then have a few options, like either redoing your computation using the new state or not doing anything at all because the current state is good.
Just something to keep in mind.
Also, I find the inherent time taken / work done tradeoff interesting. Something involving a limited amount of server state might work better on the work front while keeping the work done limited. (Something like "please don't try again for x ms" sent as a reply)
The ideal case is, what, 2n-1 calls (everyone sends at once, server replies to the first guy and schedules all other clients such that there is no contention) and O(n) (what is the scale factor here? 20ms?) delay? Are there any algorithms that come close to the limit?
I suppose a textbook example is... If I'm managing a pool of long-running threads I want to periodically bounce, I could write logic to throttle respawning threads. Or I could just add a rand() to the conditional -- introduce "jitter" -- and let probability theory "throttle" for me.
I'd rather build on top of probability than statistics.
Use of pure color in a graph makes me sad, though. This colorblind guy had to crack open a paint program and match up RGB values. A few dotted/dashed lines go a long way (and I suspect, for more than just colorblind folks, too).
(Assuming red/green. There are analogous methods for other types of color blindness, however.)