Is Left-Right a generic concurrency control?

Spoiler alert, yes, Left-Right is a generic concurrency control!

We mentioned Left-Right many times before, but here it goes again.
Left-Right is a technique where two replicas of your data are kept up to date. Mutative operations execute in one replica while the other replica can be read by in-flight readers and then the role of the replicas toggles for the write to apply the same operation on the opposite replica while the new readers go on the freshly modified replica.

Through the careful usage of atomics and RCU, this can be done in such a way as to have wait-free progress for the readers and that's what Left-Right is about.
There is only one writer at a time (we can use a global lock) but it can use flat combining to aggregate requests from multiple writers and thus have data locality without causing too much contention on the writer lock. This data locality allows for a "flat" throughput of the write operations, and in the case of Persistent Memory (Romulus) is can even have high positive scaling due to saving writes to PM.

If you want to see more details on Left-Right you check out this ppt: https://github.com/CppCon/CppCon2015/tree/master/Presentations/How%20to%20make%20your%20data%20structures%20wait-free%20for%20reads
or see my cppcon video on this topic:
https://youtu.be/FtaD0maxwec?t=1738


Because Left-Right is a generic concurrency control, it can be used to make a Universal Construction
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/left-right-2014.pdf
or an STM
https://dl.acm.org/citation.cfm?id=3210392
both approaches imply blocking yet starvation-free writes, and wait-free population oblivious reads.
Read-only operations can execute in parallel with the write operation because they're accessing opposite replicas.

When a user decides to utilize the Left-Right UC, all it has to do is place the user-code in a lambda and pass it to the Left-Right UC.
The code in the lambda has some minor restrictions, shared in common with all other generic approaches that give wait-freedom for reads:
- No side effects in the lambda: can't modify global variables or thread-locals;
- Deterministic code: no access to random number generator devices or random functions, unless it's a pseudo-random generator and the seed is passed to the lambda;
- No I/O; no writing to files, no sending/receiving of network packets, no hw registers being written... actually all of this can be done but then you have to use an STM version (like Romulus) which needs load and store interposing
- No exceptions: any exceptions must be catch inside the lambda (user-code). For the read-only operations it can be made such that this is not a problem (implementation detail) but for the mutative operations this is an algorithmic constraint;
Operations in Left-Right are irrevocable (they don't abort-retry) which is a nice feature for most user code.

The bad news: it uses twice as much memory. Like all good things, there are trade-offs and the wait-freedom for readers has a cost, the memory usage.

Remember the issue about cross-dependencies (write skews) from the previous post ? Left-Right doesn't have such an issue because the synchronization is implicitly a global lock. Yes, yes, it serializes mutative operations, but remember, read-only operations are wait-free and go in parallel with the mutations. As long as your workload is read-dominated, Left-Right is a good trade-off.

Another nice feature is that memory reclamation works just like inside a lock: you just call malloc/free/new/delete and it works. No need to use epoch-based reclamation explicitly (it's already implicit in the usage of the userspace RCU inside Left-Right).


On the next post we're going to talk about a fully wait-free Universal Construction.

Left-Right and C-RW-WP with Flat Combining

Flat Combining is a cool technique that allows multiple threads to help each other.
http://dl.acm.org/citation.cfm?id=1810540
It was designed to be used with mutual exclusion locks but it has been used with other things,
such as Hardware Transactional Memory (see "Transactional Lock Elision Meets Combining" in PODC 2017).
We have used it to improve the throughput of C-RW-WP and Left-Right.

C-RW-WP can be seen here:
http://dl.acm.org/citation.cfm?id=2442532
and Left-Right here:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/left-right-2014.pdf

Here is how it works for C-RW-WP:
- Writers publish their operation (a std::function) using a publishing mechanism, in our case it's just an array of atomic pointers to std::function. Each std::function typically stores a lambda on which we captured whatever parameters are needed to make things simpler;
- A writer spins until it gets the exclusive lock or until its entry in the publishing array goes to nullptr, thus meaning that some other writer has completed its operation and has placed the result in the corresponding entry on the array of results;
- If the writer gets the exclusive lock, then it is his responsibility to execute the other thread's operations that are in the publishing array, save the results in the results array, and set the pointer in the publishing array back to nullptr;
- Readers don't need to publish its operation in the publishing array, unless the lock is already in exclusive mode. In that case, they publish the operation and wait for the lock to be released, or for the entry in the publishing array to become nullptr;

Example code can be seen here:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp


There are a couple of minor tricks:
1st, the writer holding the lock will execute each operation at a time
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp#L121
and only then will it set the entry to nullptr with a store release
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp#L122
this way, another thread is guaranteed to see the result there if it sees its own entry at nullptr
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp#L102

2nd, the writers don't have a starvation-free cohort lock, it's a simple spin-lock, but because the Flat Combining technique is starvation-free, the writers end up being starvation-free (among themselves), a very good property to have without having to make a more complex or strick-fairness lock, such as a ticket lock.
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp#L100

3rd, the readers attempt to get the lock in shared mode first, and only if it is not available (a writer is already there) then they publish their operations
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/locks/CRWWPFlatCombining.hpp#L100
A reader's operation is not mutative (by definition) but the result needs to be known, so it's up to the writer (who doesn't care if the operation is mutative or not) to apply the operation and place the result in the results array.
The consequence of this is that in low contention, C-RW-WP works as usual (which is blazingly fast), but when there is more contention and some threads are writers, then it goes on the "flat combining path" which is starvation-free.

This means that the end result is a technique that is fully starvation-free, i.e. readers don't starve writers, writers don't starve readers, readers don't starve other readers, and writers don't starve other writers.
I don't know about you, but I think it's pretty cool to take something that has a large propensity for starvation like C-RW-WP (writers starve readers and writers will starve other writers if the cohort is a spinlock), apply Flat Combining to it, and get something that is fully starvation-free, and on top of that has lower tail latency and higher throughput on most workloads  :-O


So how about applying Flat Combining to Left-Right ?
This was so obvious that even back in 2012 Andreia was speaking of doing this (before we even read the Flat combining paper) but it was too simplistic and we wanted full wait-freedom so she dropped it. But now, here it comes again  :)
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp

Adding Flat Combining to Left-Right is a bit trickier than adding Flat Combining to C-RW-WP, but not by much.

The first difference is that readers are wait-free in Left-Right, so there is no point for them to add their operations to the publishing array. Flat Combining is great but it provides at best starvation-free progress, while Left-Right provides wait-freedom for readers.
In Left-Right neither readers starve writers nor writers starve readers, so there isn't much of an advantage in progress of adding FC to Left-Right likes there was for C-RW-WP, but there is still the advantage of using a spin lock as the writersMutex and still providing starvation-freedom amongst writers, so we did that
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp#L124

The second difference is that we don't want the writer currently holding the writersMutex lock, to apply operations from other writers in one of the instances but not the other, because it would leave the instances in an inconsistent state. To solve this, we first copy the entire publishing array (it's just pointers) to a local (stack-allocated) array:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp#L135
and only then do we start applying the mutations from the local array
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp#L143
After the toggle, we apply the same mutations on the opposite instances
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp#L153
and only then do we set the corresponding entries in the publishing array to nullptr
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/leftright/LeftRightFlatCombining.hpp#L156


Just for fun, here are some plots.
Unfortunately I don't have the same plots with/without Flat Combining, but with FC is generally better:



For mutative only workloads (100% writes) using a global lock is better than Left-Right because on Left-Right we have to apply the same mutation twice (once on each instance). As soon as the number of readers increases, Left-Right takes the upper hand (regardless of using Flat Combining or not) and start to be better.

This kind of benchmark uses "mixed-ratio" threads and without over-subscription, so we don't really see the effects of starvation-freedom or wait-freedom, but it's good to know that Left-Right can be combined with Flat Combining and still come out ahead  :)