You are viewing...

Interesting Things in Software (9/17/2016)

Updated on September 05, 2017 at the 01th hour
Posted under:

DISCLAIMER: All views are considered my own and you should not draw any conclusions on associates.

Left-Right Algorithm for Concurrent Reading and Writing

Here's an interesting, practical and more memory efficient way alternative to the Read Copy Update (RCU) Algo. These algos assume far more reads than writes. Instead of copying the data structure for writing (essentially creating a new version), you maintain two copies of your data structures where both sides are eventually consistent. Strictly, writers will modify the opposite (say left) side of what the current readers are reading (right) and then point new readers to the modified side (left) while waiting for old readers to finish up before modifying the other side (right). When another write comes in, the same process occurs starting with the right side.

Simple concurrent algorithm too and there is no reason to use heavy synchronization mechanisms here. A counter (Array of counters is better because contention is bad) for each side and an index for where the reads are going. It is pretty novel for me.

Links
  1. Video: https://www.youtube.com/watch?v=FtaD0maxwec&index=73&list=PLHTh1InhhwT75gykhs7pqcR_uSiG601oh
  2. CF: http://concurrencyfreaks.blogspot.com/2013/12/left-right-concurrency-control.html

 
You just read "Interesting Things in Software (9/17/2016)". Please share if you liked it!
You can read more recent posts here.