CX - Wait-Free Universal Construction

After many years, we've decided to make public the source code for the CX Universal Construction and explain what it is. Source code can be obtained here: https://github.com/pramalhe/CX
and paper here: https://arxiv.org/abs/1911.01676

CX is the first wait-free Universal Construction that can actually be used in practice.
It can take lambdas for its operations, it has integrated (wait-free) memory reclamation, it was extensively tested and it doesn't leak.
CX allows you to take a sequential data structure or object (single-threaded code) and make a wait-free concurrent implementation of the same object by simply encapsulating the methods in calls to updateTx() or readTx(). The resulting data structures have linearizable operations.

Transforming a sequential data structure with CX is not trivial, but it is simple enough that a developer fresh out of college can do it. There are a few rules specific to wait-free UCs that need to be followed (no I/O, no exceptions, no side effects, deterministic code only) but these are easy enough to adhere to.

Unlike handmade wait-free and lock-free data structures, you can have any kind of type in your container (there are limitations on the return values though). All lock-free data structures I've seen so far were meant for integers only, or something equal or smaller than 64bits. Moreover, with CX it's easy to modify the data structure later and add more functionality.

Unlike STMs, CX does not need to have interposing and therefore, we can use CX to wrap data structures in libraries to which we don't have access to the source code. For example, you can use CX to wrap STL containers (we have!). Here is an example on how to make a wait-free std::set
https://github.com/pramalhe/CX/blob/master/examples/WFStdSet.hpp
or even easier, just create the instance and do the operations on the fly:
https://github.com/pramalhe/CX/blob/master/examples/example1.cpp

All you need is a copy constructor for the underlying data structure you want to protect. As long as your sequential data structure has a copy constructor (or something logically equivalent) and deterministic operations, you should be able to convert it to a wait-free data structure.

We've used CX to make the world's first wait-free balanced binary tree, with integrated wait-free memory reclamation, capable of supporting multiple types. How did we do that? Well, we wrapped a std::set in CX and BOOM, out comes the world's first wait-free balanced BST  :)


Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX.
Sure, it has its limitations, but it opens new venues for research and is evidence of some contrarian concepts:
- wait-freedom can be generic and fast (at least for read-mostly workloads);
- wait-free memory reclamation can be lightweight;
- wait-freedom can be achieved with locks;


Now for the bad news: just because it's wait-free, doesn't mean it scales.
CX serializes all mutative operations which means it's flat at best if the workload consists of only mutations on the sequential object.
It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object. If the object is a data structure with 1000 nodes, then it doesn't make a dent, but if we're talking about a container with multiple millions of keys and tens of threads writing to it, then it's going to chew up with DRAM pretty fast.
This high memory usage means CX likely won't be your favorite concurrency approach when deploying in production.

The good news is that it scales really well for read-only operations. This means that as long as your workload is read-mostly, it will be able to scale.
Synchronization for read-only operations in CX is very low, typically a few acquire-loads and a single seq-cst fence instruction and beyond that it's just regular loads.
Yes, that's right, the user-code you place in the lambdas is being executed without having to do any load acquires or heavy synchronization fences, just like when you execute code inside a lock!
This is what makes CX be very fast for read-mostly workloads.


In fact, it's so fast that when we submitted the paper to conferences, a few reviewers complained that it was too good to be true and it couldn't possibly be correct. That's how fast it is  ;)
Hand-made lock-free data structures can take months (or years) of work by expert researchers to complete, therefore it's normal be greeted with disbelief when we show them a technique capable of transforming generic sequential code into wait-free safe code. Something a young developer can do in minutes. If on top of that we say that it has wait-free memory reclamation and on top of it we show plots where it beats multiple handmade data structures in read-mostly scenarios, then they go ballistic and think it's all a bunch of BS.
It's understandable, we all have our biases. Mine is to think that it's a good idea to trade off large amounts of memory for a generic construct that scales in read-mostly workloads.What's yours?

Hey, nobody's perfect!

The difference between a Universal Construct and a Software Transactional Memory

In this post we're going to talk about Universal Constructs (UC), Software Transactional Memory (STM), the different between the two of them, and why it's not possible to have a UC for persistent memory.

Waaaiiiittt what?!?! It's not possible to have a Universal Construct for non-volatile memory?!? Why not?

The reason is at end of the post, first, like on all voyages, we start at the beginning.
Back in 1991, Maurice Herlihy (yes, it's the guy that wrote "The Art of Multiprocessor Programming" with Nir Shavit) decided he was tired of locks and blocking progress, and tired of dealing with errors in lock-free data structures, and he proposed a thing he called a "Universal Wait-Free Construct".
https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf
You can see an implementation in Java of this UC in chapter 6 of his book.
A UC is a construct (an object) that wraps a sequential implementation of an underlying object (or data structure) and provides safe concurrent access to the underlying object. In the case of a universal wait-free construct, it provides wait-free access to the underlying object.

In other words, you can write a data structure as if it was single-threaded, and then, instead of slapping a lock on top of it (which is blocking), you slap a wait-free UC (which is wait-free) and booom! You get a wait-free data structure.
In hand-made lock-free and wait-free data structures, if you so much as modify a single line of code in them, they're likely going to break apart completely. On the other hand, when using a UC you don't have that problem, as long as the sequential implementation is still correct from a single-threaded point of view. It's as if we're decoupling the concurrency part from the actual object, while providing wait-free progress.


Hummm, so how come I've never heard of this "Universal Construct" thingy?!?

Well, the main reason is that completely wait-free UCs have been until now, extremely slow.
There are partially wait-free UCs, like Left-Right, which provides blocking (starvation-free) progress for writers and wait-free progress for readers. Left-Right is simple and pretty fast, but anything that provides wait-free progress for both readers and writers, is bound to be slow.
The reason behind this slow performance is related to the Copy-On-Write (COW) pattern behind almost all wait-free UCs. Wait-free UCs typically make an entire copy of the underlying object for every mutation. If the object is small, this will be fast, but if the "object" is a data structure with one million nodes, then its going to be super slow.
This means, that UCs are great for theoretical research, but not so great for making non-blocking data structures.
If you want to know more about this topic, then take a look at P-Sim which is probably the best know wait-free UC:
https://dl.acm.org/citation.cfm?id=2664096
or to our own UC named COWMutationQ which is simpler and has a similar performance:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/cowmq-2015.pdf

UCs have a few peculiarities.
First, they can protect a single object, or if you prefer, they have a single root pointer from which all inner objects must be accessible. UCs allow for transactions to be made as long as the objects in that transaction are accessible from the same root pointer, and they must not be accessible from any other root pointer (in case you have other UC instances).
In other words, objects inside the UC have a 1-to-1 connection to the UC (as if it was a lock) and the wait-free UC provides wait-free progress with linearizable consistent for any operation being applied to the underlying object(s).
Second, for multiple objects to be protected by the same UC (as is the case of nodes in a data structure), there has to be a well defined way of copying those objects, what is called in C++ terminology a copy constructor. Without a copy-constructor, or something equivalent, you can't have data structures inside the UC. This pretty much leaves out low-level languages like C from having any practical usage for UCs, ohhh well.
Third, there is no annotation of the sequential implementation.
Let me repeat this one because it's going to be really important later in this post: The user does NOT have to annotate the sequential implementation of the underlying object that is put on the UC. None, Zero, Nada!
The whole point of the "Universal" part of UC is that it can be applied universally to any underlying object, without having to modify it in any way whatsoever.


And what does this have to do with STMs?

It turns out that Maurice is actually a pretty smart guy (should not be a surprise to anyone) and he figured out that if you relax some of these constraints you might be able to improve the performance.
So, only two years later, in 1993, him and JEB Moss coined the term "Transactional Memory" to describe a construct that can do pretty much the same as a UC but without the first and second constraint I mentioned on the paragraph above.
Granted, they originally though TMs were going to be deployed in hardware (HTM) and it's true that it eventually happened, but they also though it was going to be wait-free, and it's currently worse than blocking. For example, Intel's HTM doesn't guarantee any kind of progress.

In 1997, Nir Shavit and D. Touitou showed the first Software Transactional Memory (blocking). From then until now, many, many STMs have been created, but very few with lock-free progress, and I doubt any has been made with wait-free progress. Even if they do exist, they are likely to be just as slow as P-Sim and COWMutationQ.

I'm pretty sure Maurice has been a bit disappointed by this turnout of events. He must have been expecting someone to come up with a lock-free or wait-free STM that had some nice performance. In fact, I asked him about this on a conference once, and he said that "If someone could come up with a lock-free STM, then it would be something that's actually very useful". I could tell his eyes were sparkling as he said that  :)

The main disadvantage of STMs is that they require some kind of annotation of the underlying object(s). In other words, you can't just write a sequential implementation of a data structure, slap an STM on top of it and get concurrent access for free. Nope, you need to annotate or even modify (depending on the STM) some code of the sequential implementation.
Granted, the annotations are typically small, such as changing data types or calls to allocator or deallocator, but still, some work needs to be done by the user. The process is not automatic and it's not "universal".

Just to summarize:
- STMs can have multiple root pointers. UCs can have only one root pointer;
- STMs allow transactions between any object (allocated in the TM). Each UC can execute transactions only within the objects it protects;
- STMs don't need copy constructors. UCs need copy constructors or equivalent methods;
- STMs require annotation of the underlying object. UCs require no annotation or change to the sequential implementation;

Just to consolidate the idea: If it needs annotation, it's not a Universal Construct!


What about that stuff you said about not having UCs for persistent memory ?

Now we get to the insightful part.
Any code that modifies data in Non-Volatile Memory (NVM) must (currently) flush the cache lines after the modification. On x86 this is done with a CLFLUSH or CLFLUSHOPT or CLWB instructions.
The only way to do the flushing automatically is to have some kind of annotation, typically in the type of the variables modified. Yes, the compiler can hide that from me, but I still have to have a way of telling the compiler which data is volatile and which data is non-volatile, and that is typically done through type annotation. The compiler can't guess what data is meant to be persisted and what data is meant to be volatile, there is just no way for it to figure that one out because that is related to application logic, and by definition, only the user knows that. The only way around this is to have _everything_ be non-volatile, but that requires hardware which doesn't currently exist, and may not be an interesting programming model anyways.
This means, that the whole concept of "Universal Construct" kind of fades away when it comes to NVM, because the main point of having a UC, is not doing any change to the underlying code, but the only way to have a sequential (non persistent) implementation of an object be persistent, is to annotate it.
Of course, if they ever make an architecture where writing to NVM doesn't need to be flushed, then ok, it should be possible for someone to make a UC with persistence, but that's very unlikely to happen (the no-need-for-flushing-cpu-architecture).

In practice all of this is fine because we still have STMs, and STMs are particularly suited for working in NVM because they were designed to provide transactions. Having NVM is just an added bonus that can make the transactions persistent, which is great because it gives ACID.

Up until recently, STMs only had ACI, there was no Durability, but now with NVM, STMs can provide full ACID support, just like databases... and that is a game-changer.

Ultimately, whether you call it a UC or an STM depends on the interface that is being given to the user. If it needs annotation, it's not a UC. But then again, having to annotate a data structure is typically not too hard, therefore, it's fine to do it if you get some extra performance in return for that extra work.

An update: Actually, there is a way to make a universal construct for NVM, it's just a matter of flushing the entire memory region on each operation. So I guess I was wrong, yes, it is possible to have universal constructs for persistence, it's just that their performance will go down the drain if we have to flush the entire NVM region on every single transaction. Moral of the story, if you're into to persistence, better stick to STMs.

Why is memory reclamation so important?

As it so happens, object lifetime tracking (or Memory Reclamation as I prefer to call it) is the current most difficult open problem in shared memory concurrency.
If you want to design or implement a lock-free or wait-free data structure, the hardest part isn't designing/implementing the data structure itself. The hardest task is to add memory reclamation to this data structure, without reducing the progress or throughput of the data structure you designed/implemented.

Huhhhh wait, are you saying that implementing a lock-free data structure is easy when compared to memory reclamation? Wwwhhaaaat?!?
No, I'm only saying that memory reclamation is even harder  :)
Let me try to explain why, and there are four reasons behind it:

Reason number 1, progress

So let's say you designed/implemented/found-on-github a non-blocking data structure to serve your needs, but this data structure comes without memory reclamation, and unless you're on a language with a Garbage Collector, you now come face to face with the problem of adding memory reclamation to it.
Think of it this way, what is the purpose of going through all the trouble of doing lock-free/wait-free stuff if then you end up having to slap a blocking mechanism on top of it?
Obviously, it would be kind of fruitless to put a blocking memory reclamation on top of a non-blocking data structure because the end result would be blocking.
This implies that whatever memory reclamation you're going to use on your favorite data structure, needs to have at least the same progress guarantees as the data structure. If not, then all that work that went into designing/implementing a lock-free data structure, just goes down the drain, and you might as well go back to using a global lock, which has low overhead and provides safe memory reclamation (just grab the lock before calling delete/free on nodes of the data structure).

Btw, even if you have a GC, no known GC is lock-free (much less wait-free), so you don't really have non-blocking guarantees of progress. Just take a look at the previous post with Erez Petrank's presentation.

Reason number 2, throughput

When we use a non-blocking data structure, whether lock-free or wait-free, one of the goals is to achieve more performance. By performance I mean either more throughput, or lower tail latency, or both.
Typically, as developers, what we want from these data structures is to have higher throughput as the number of threads working on the data structure increases, and maybe we also care that the tail latency stays low. If we didn't care about one or both of these things, then we could just protect whatever single-threaded data structure we needed to use, with one global lock and be done with it, but as everyone knows, this doesn't scale.

Progress is not enough, if the lock-free data structure you're using is fast, then you need a memory reclamation technique that is at least as fast as it, so as to not become the bottleneck.
What is the purpose of having a super-duper fast lock-free data structure if then you slap on top of it a lock-free-but-horribly-slow memory reclamation technique which drags down performance? Well ok, you may still have the progress guarantee, which will give you low tail latency for wait-free data structures with wait-free memory reclamation, but really... if it's slow, will you use it?

Reason number 3, simplicity

When we apply a memory reclamation on top of a pre-existing non-blocking data structure, we want it to be as simple as possible. The simpler it is, the less likely it we will be that we make mistakes. Unfortunately, most memory reclamation techniques are hard to deploy on pre-existing data structures.
I've previously wrote an entire post explaining just how hard it can be for Hazard Pointers and how much easier it is for URCUs:
http://concurrencyfreaks.blogspot.com/2016/08/hazard-pointers-vs-rcu.html

The jist of it is, that it requires expert knowledge about the data structure where the memory reclamation is being applied, so expert that most data structure designers/researchers don't bother to add memory reclamation to their data structures. They claim it's "an implementation detail", but I know better, it's because it's really hard. Don't take it the wrong way, it's not that they aren't smart enough, it's just that this kind of work is not valued in academia, therefore, there is no incentive for them to waste precious space in their articles explaining how to make a data structure that is actually deployable in a production setting.  Not to mention spending brain power thinking about it (it's true, it always gives me a headache).
And if you're convinced that things like Hazard Pointers can be tricky to use, well then, it can be even more complex, for techniques like Drop The Anchor.

Reason number 4, resilience

Another reason to go with lock-free/wait-free data structures is because they are resilient to failures. On a shared memory system with multiples processes accessing the same data structure, even if one of the processes dies, the others will be able to progress in their work. This is the true gem of lock-free data structures: progress in the presence of failure.
Blocking data structures (typically) do not have this property (there are exceptions though).
If we add a blocking memory reclamation (like URCU) to a lock-free/wait-free data structure, we are loosing this resilience because one dead process will prevent further memory reclamation and eventually bring down the whole system.
There goes the resilience advantage out the window.

The three families of memory reclamation

Manual memory reclamation comes in one of three flavors: Atomic reference counting, quiescent-based, pointer-based.
All memory reclamation techniques belong to (at least) one of these families. Many memory reclamation algorithms exist but we'll focus only on the ones that can be implemented using the C++ memory model and atomics.

Atomic Reference Counting is just what the name says, it's a "reference counting" technique but with atomics. The details are a bit more tricky than your usual reference counting (aka smart pointers), but it's still graspable for most. They can be implemented in a wait-free way (in x86) but they have two main drawbacks: they're slow and they aren't universal.
They're slow because whenever we have to traverse a list of nodes we need to atomically increment a counter in one node and decrement a counter in another... even though we're just reading.
They're not universal because of several reasons, most of them described in section 9.1 of Paul McKenney's excellent book
https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook-e1.pdf

Quiescent-based is where Epoch-Based-Reclamation (EBR) and all Userspace RCUs belong. The fastest memory reclamation is here (for readers). These methods tend to have very little synchronization, are easy to deploy in nearly all algorithms (i.e. data structures) and they're easy to understand.
When everything goes well, these are the fastest way of doing memory reclamation.
The downside is that they're blocking for memory reclamation. This isn't a simple limitation of the current algorithms that someone will one day be able to crack. Nope, it's something intrinsic to this approach. Reclamation with EBR or URCU is, and always will be, inherently blocking.

Pointer-based is where Hazard Pointers, Pass The Buck, Drop The Anchor and Hazard Eras belong. Pointer-based, well, they're not too hard to implement, but they can be extremely tricky to deploy. Their main problem is they're slow (though faster than atomic reference counting).
They can be completely wait-free, for readers and reclaimers. In case you didn't notice, this makes them the only family that can be used generically and capable of providing lock-free/wait-free progress.
Hazard Eras are the fastest of these, approaching (and in some scenarios surpassing) the best URCUs, but they do it at a cost in memory usage. It's the typical trade-off memory vs CPU.

You may notice that most (ok, almost all) academic papers on non-blocking data structures don't mention memory reclamation anywhere, or just briefly mention it in one sentence. This is because they would need many pages to detail all the intricacies of adapting such algorithm to have safe memory reclamation. Their typical approach is to say "That's not my problem, I'm just designing the algorithm. Memory Reclamation is an implementation detail."
... an "implementation detail", yeah, right.

Going back to our four reasons why memory reclamation is a hard problem (progress, performance, simplicity, resilience), if we look at the three families and compare some of the techniques of each family we see their advantages/disadavantages.


In the end there is no one solution fits all and it's highly unlikely that there ever will be. As always in engineering (software or not) some solutions are better in some scenarios and others in different scenarios. Though I have to say that Hazard Eras works well for scenarios with traversal of linked lists.

Wrapping up

The point I'm trying to make is the following: The fact that the memory reclamation technique needs to have the same progress (or better) as the data structure where you're using it, means that for fully lock-free or wait-free data structures the only true solution is to use pointer-based memory reclamation. Moreover, if we want the data structure to be fast, we need the memory reclamation needs to be just as fast (on top of having the same progress).

Let me be super clear on this. As of this writing, and likely for all eternity, the biggest bottleneck on deploying a lock-free or wait-free data structure is the memory reclamation technique.
If you think about it, a memory reclamation technique that is wait-free, must itself be composed of one or several data structures, likely to have wait-free progress, so we're stuck in a catch-22 where we want to make wait-free data structures faster, but we need to use (other) wait-free data structures to protect those wait-free data structures.

To end on a positive note, yes it's sad we likely can't make memory reclamation any faster than URCU or Hazard Eras, but we can certainly make it easier to use, and that's one of the things Andreia and I are working on. More on this in a future post  ;)

Userspace RCU in GlusterD

Here is a great example of how RCU can be used in a project to improve scalability and throughput, namely in GlusterD:

Atin Mukherjee talks about several interesting details on how to use RCU.
My only quirk is on slide 8 "Different Locking Primitives", RCU is not a locking primitive in the sense that it doesn't provide mutual exclusion by itself, but it's hard to explain exactly what it does, so it's ok to put it on the same slide.


He even talks about a bug in their code where they did something like:
    rcu_read_lock();
    // do some stuff
    synchronize_rcu();   // This will deadlock
    rcu_read_unlock();
This happens because we can't call synchronize_rcu() from within a block of code protected with rcu_read_lock().

It's interesting that they went with the Bullet-Proof RCU variant, which just shows that most software engineers are willing to sacrifice a small amount of performance if it gives them more flexibility and ease-of-use (myself included).

A good resource for programming with atomics

One common question the I've heard is: Where can I find a good resource for learning how to use C++ atomics?

There is a good resource, it's this page: http://en.cppreference.com/w/cpp/atomic/memory_order
and if you don't like reading, you can watch the Atomic Weapons presentation by Herb Sutter
http://concurrencyfreaks.blogspot.com/2013/02/the-new-memory-model-in-c11-and-c11.html

But that's not the answer most people expect.

This happens for two reasons:

First, because the memory order page is "too technical". It needs more examples, particularly of how the different memory orders interact with each other. For example, from reading that page alone, it can be very hard to understand what happens when you have a store with a memory_order_release followed by a load with a memory_order_acquire  (I talk about this in my interview with Channel9), and if you throw consume into the mix it gets even trickier.

However, the information is (almost) all there, it's just a matter of knowing how to read it, which I agree, can sometimes be a daunting task.

Second, and this is the big one, expectations!

When someone asks about more information on atomics, what they really want to know is more information on concurrent/lock-free/wait-free data structures and algorithms. And the reason why they want a lock-free/wait-free data structure is because they want it to be fast/scalable/low-latency in a multi-threaded application.

This has the further implication that once they have an implementation of the concurrent data structure, they won't be happy about it because it will be "slow", because it is using memory_order_seq_cst, so they'll want to know how to implement the same data structure using one of the other (faster) memory orders.

Obviously, before implementing or understanding a lock-free/wait-free data structure, we need to have a good understanding of atomics. But what they really want to know is how to implement a lock-free data structure, and this, unfortunately is extremely tricky and requires a very long time.

For those of you that studied CS (I didn't, but I attended some classes), remember those classes about (single-threaded) data structures? How many semesters did you study data structures?

Well, if they had lock-free/wait-free data structures in CS classes at college, it should take a lot longer, because concurrent data structures have not only the dificulties of single-threaded data structures, but many more subtle details, which require some time to grasp.

If I had an euro for every time I found a bug in a concurrent data structure that was designed by someone who thought it was a good idea to design its own data structure, I wouldn't be a High Net Worth Individual , but I would have enough for a weekend escapade at some semi-tropical place  :)

Para-quoting Fedor Pikus: designing concurrent data structures is hard... the only thing harder, is to design correct concurrent data structures.

So yes, people want to understand how to make their own data structures, but it's such a hard task. It requires a lot of testing, a lot of careful reviewing, perhaps even some praying to pagan deities and a few animal sacrifices... and in the end, you may not be sure that it's correct, or when the next developer comes and (innocently) modifies a line to "add a feature" or "fix a bug", the result will be an incorrect algorithm.

Personally, I think that the near future will bring tools that are capable of doing static analysis on the concurrent code, to show if it breaks mutual exclusivity or some invariant that you define. We're not there yet though, and for the moment, if we want to "prove" that a certain algorithm is correct, we must do so in the form of a paper, with some "mathematicaleze" language. Even then, the "proof" itself might be wrong, and all is for naught.

If you want to learn about atomics and the memory model, my recommendation is the following:

Go to the web page at the beginning of this post and read it carefully, then, find a concurrent data structure that you actually need, or you find interesting for some particular reason. If this data structure is not already implemented in C++ atomics, try to do so yourself, using only memory_order_seq_cst.

Once that is working, write as many stress test scenarios as you can think of, until you are as confident as possible about the correctness (you'll never be 100%). Try to get another pair of eyes to review your code.

Then, and only then, try to think very very very carefully about which of the atomics can be changed to memory_order_acquire and memory_order_release. Repeat the stress tests, if possible, on different architectures, the more "relaxed", the better.

Then, think about whether it's possible to change some of those atomics to memory_order_consume or even memory_order_relaxed, and again, repeat the tests and code reviews and any other rituals (pagan or not) that you may think will help.

You'll have questions while doing this, at that time, you can go and re-read the cppreference page on memory order again, or even the C++ draft. You can also take a look at some of our examples (at your own risk) where we do optimizations, but keep in mind that these are specific to the algorithm. 

http://concurrencyfreaks.blogspot.com/2015/06/lamports-one-bit-solution-in-c11.html

http://concurrencyfreaks.blogspot.com/2015/06/an-example-of-atomicthreadfence.html

You'll need to first understand the algorithm you're trying to implement and its invariants, and only then you can think about how to relax some atomics to get better performance.

That's all the advice I've got, I know it's not much, but it's better than nothin'

Linked Lists with wait-free reads in C++ (LRLinkedList and LRLinkedListSingle)

Today Andreia gave birth to a healthy baby boy. To celebrate this happy event, we are releasing the C++14 code for not one, but two concurrent linked lists, both Wait-Free Population Oblivious (WFPO) for read-only operations.

The first one, named LROrderedLinkedList (LROLL), is just a linked-list-set wrapped in the Left-Right pattern.
The second one, named LROrderedLinkedListSingle (LROLLS), is sightly more complex, but it is faster for modifications (insertions and removals).
These two data structures are interesting as examples of using and implementing the Left-Right pattern in a scalable way in C++14, and they are also the only linked-list sets that are WFPO for read-only operations. In fact, these two are the only linked list sets that are wait-free for read-only operations in C++, AFAIK.

Yes, I know about Harris linked list set which is lock-free for all operations (lookups, insertions, and removals), and I know about its variant with wait-free lookups (wait-free bounded by the number of keys in the set), but there is a detail about the variant with wait-free lookups that it implicitly requires a system with a Garbage Collector. On a system without an automatic GC (like C11 or C++1x) we can't use Harris's linked list by itself without adding some kind of memory management, i.e. Hazard Pointers.
There are two problems with using Hazard Pointers (HP) in Harris list:
First, HPs are not very fast, because they require at least one store with release barrier for each node of the list that is traversed, even though the lookup function is expected to be a read-only operation.
Second, the HP technique is lock-free and not wait-free, which means that using it in the lookup function reduces the progress condition of the lookups from wait-free bounded to lock-free.
In practice, all this means that in C11/C++1x there is no linked list set that is wait-free AFAIK (if you happen to know one, please add the link to it on the comments section).
If you have no idea what Harris linked list is, or what are Hazard Pointers, then here are the links to them:
http://timharris.uk/papers/2001-disc.pdf
http://concurrencyfreaks.com/2014/03/harriss-linked-list.html
http://researchweb.watson.ibm.com/people/m/michael/ieeetpds-2004.pdf

This is where LROLL enters. LROLL is composed of the Left-Right pattern associated with two linked list sets. The basic idea is that read-only operations are going on one of the lists, while a single modifying thread is inserting/removing a node on the other list, and afterwards redirects new lookups to the recently modified list and waits for unfinished lookups before applying the same modification on the opposite list.



Notice that there is only one instance of each key but there are two nodes for each key, and that LROLL does its own memory management without needing an extra memory management.
The big disadvantage is that the Left-Right pattern has a global lock that serializes modifications in the list (insertions/removals). This means that both insertions and removals are blocking, which by itself is not too bad, but the problem is that it's not scalable due to the serialization of the modifying operations. Moreover, two lookups are needed, and the modification has to be applied on two lists, which doubles the pain.
However, there are three big advantages:
First, the WFPO progress condition on the lookups means that the number of synchronized atomic operations is constant (depends on the readIndicator used, but typically just two or three stores with release). This provides excellent performance for lookups and very low latency guarantees.
Second, both HPs and Harris linked list are patented. HPs are patented by IBM, and Harris list by Sun/Oracle. The Left-Right pattern is free for use  :)
https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US20040107227.pdf
https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US7117502.pdf
Third, and this is non-obvious, there are no other linked list implementations that provide linearizability for read-only iterators, with the exception of using a mutex or reader-writer lock to protect a linked list, but that approach is blocking for all operations. Both Harris linked list and Michael & Scott linked list provide only weak consistency for iterators of the list, but the LROLL and LROLLS provides linearizability for read-only iterators (this property is sometimes called snapshot consistency).


Just how important is to have linearizabile read-only iterators? Well, it depends on your application, so let me give an example.
Suppose you have a banking application that uses a linked list set of bank accounts. If we use a LROLL, adding a new bank account or removing a closed account are both blocking procedures. Doing a transfer from one account to another is also a blocking operation. Checking the current amount in an account is WFPO (and linearizable).
How about determining the whole amount of cash available in all the accounts, i.e. all the money in the bank? Well, that is also a WFPO operation and linearizable, because it is a read-only iteration that goes over all the accounts. Notice that while this operations is ongoing, any modifying operation will have to wait for this to finish (and for any other read-only operations). Harris and Michael & Scott lock-free lists don't allow for this kind of operation, or they do allow, but not in a linearizable way, which in practice means that the result of a function that goes over all the accounts and sums them all will most likely be very different from the actual amount in the bank because you can count ongoing transfered amounts twice (or multiple times), or never count them. For example, suppose there are only two accounts and while one thread is summing the values from each, there is another thread that is doing a transfer from the first to second, by removing from the first 1M $ and then adding 1M $ to the second... if at the same time the other thread reads the amount after the 1M $ has been withrawed and then reads the value on the second account before it is credited, then it will see 1M $ less than the actual amount of money in the bank.
The above situation can not happen with LROLL


LROLLS extends the idea of LROLL a bit further. Instead of having two instances of the linked list, it has a single physical linked list but two logical lists as shown below:



Each node has two "next" members, one of the logical left list (nextL) and another for the logical right list (nextR):
<template T> class Node {
    T *key;
    Node *nextL;
    Node *nextR;
};

The first benefit of this approach is saving one pointer to the key, thus saving some memory, but the main advantage is the fact that an insertion or removal in the middle of the list does not have to start over and do a second lookup to find the node to insert after (or the node to be removed) because it is the same physical node. In LROLLS it's just a matter or linking/unlinking the new node on the same physical node for both nextL and nextR.

In LROLLS, an insertion has to do one lookup to find the node previous to the one before the insertion point of the new node (let's say it's nextL), and then insert the new node there, wait for the left-right toggle, and then insert on the same node but do it on the opposite list (let's say nextR). In LROLL, this last step requires a lookup from the beginning of the list, but on LROLLS we already know where the node is, so no lookup is needed, which means we don't waste time doing a second lookup. For small lists this isn't much of an advantage because most of the time is coming from the overhead of the synchronization needed by the Left-Right pattern, but for large lists, this can make a difference in performance that is nearly 2x faster for LROLLS than for LROLL.

For example, in LROLLS the removal of the key Y from the set would work like this:
1. The Writer starts from the head of the logical list opposite to the one the Readers are using and unlinks the corresponding next field.


2. The Writer re-directs new Readers to the currently modified logical list, waits for older Readers to finish on the other logical list, and then unlinks the other next field.


3. The node with the key Y can now be deleted/free’ed




All these examples use a linked-list-set, but the idea applies to any other data structure (except for LROLLS which is more specific to link-list based data structures), i.e. you can use the same kind of ideas to create concurrent versions of other single-threaded data structures.

As always, source code is available on github:
LinkedListSet.h - A single-thread only linked list set. The Left-Right pattern uses two instances of this class to create a set with WFPO read-only operations
LROrderedLinkedList.h - LROLL: two LinkedListSet instances protected with the Left-Right pattern using a DCLC readIndicator
LROrderedLinkedListSingle.h - LROLLS: Less memory usage than LROLL and 2x faster insertions and removals
RWLockLinkedListDCLC.h - Uses a DCLCRWLock (based on C-RW-WP) to provide concurrent (blocking) access to a LinkedListSet
RWLockLinkedListPT.h - Uses a pthread_rwlock_t to provide concurrent (blocking) access to a LinkedListSet
RWLockLinkedListSM.h - Uses a std::shared_time_mutex to provide concurrent (blocking) access to a LinkedListSet


PS: Ohhhhh I almost forgot, if you're on C99 or C++99 (no memory model) then you can use the Double Instance Locking instead of the Left-Right in LROLL and LROLLS and obtain lock-free progress condition for read-only operations.