Jittery Back Off to Speed Up

In systems where there are multiple participants who need to interact with a shared resource some sort of concurrency protection is usually appropriate. The obvious technique is to use locking (and fun words like “mutex”) but this adds a constant performance hit as every participant needs to spend time interacting with the lock regardless of the number of other participants. It turns out this is actually a Big Problem that garners original research, but there are techniques that can yield great effect without a PhD. Years ago [Marc] posted a great walkthrough of one such method, exponential backoff with jitter, to Amazon’s AWS blog which is a great introduction to one such solution.

The blog post was written specifically to deal systems using a specific technique called optimistic concurrency control (OCC) but that doesn’t mean the advice isn’t generally applicable. OCC refers to a method where each writer checks for a write collision only after performing the write (but before committing it), which works well in scenarios where writes are relatively uncommon. [Marc] observed that even in systems where this is a safe assumption things bog down significantly when there are too many writers clamoring for attention all at once.

The traditional solution to such a problem is for each writer to pause for an exponentially increasing amount of time before trying again, but as writers come back in big groups the same problem can recur. He provides a discussion of simple modifications to that strategy which result in significantly reduced wait times for writers.

Problems like this are not especially relevant for single Arduino sensor networks, but even small groups of systems can have concurrency trouble and it’s nice to see such an accessible write up with solutions which are viable even for simple systems. Bonus points to [Marc] for posting source to his test tool online. It doesn’t require anything outside of your computer to run (no AWS required) so if you have any brainwaves about speeding up multi-writer environments it might make a nice test environment! Maybe don’t mention the blog post in your PhD applications though.

6 thoughts on “Jittery Back Off to Speed Up

  1. Thanks for this one. (Randomised) exponential backoff is staple in network land in the context of a shared medium (think Ethernet or WiFi), but it’s nice to see it presented like this.

    I just don’t get this one: “Maybe don’t mention the blog post in your PhD applications though”. Huh? Why not?

        1. Yeah, I’m just jaded having seen so many new ‘discoveries’ that we all knew (and had documented) for years, but the webjockeys couldn’t be bothered learning from history. Maybe it’s just a generational thing – after all, thin clients were a “brand new innovation” 20 years ago…

    1. This sort of falls into the category of things that we’ve all known and used and maybe had an intuitive understanding of but few of us have stopped to really think about in detail let alone coding up a simulation. Seeing it all described in detail and simulated make it less fuzzy.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.