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.

Source link

Leave a Reply

Your email address will not be published. Required fields are marked *