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!

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.

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.

Dawn of the Universal Constructs

Historical Introduction

Some time ago I saw this nice presentation by Andrei Alexandrescu about Generic Locking.
https://www.youtube.com/watch?v=ozOgzlxIsdg
He starts the talk by giving an introduction to how the "Concurrency Problem" has been attacked.

And what is the "Concurrency Problem" you might ask?
Well, remember this little issue about Moore's Law (on CPU clock speed) having stopped back in 2004 and that nowadays to get more performance you need to use multiple cores, which means using some form of concurrency? Yeah, that's the "Concurrency Problem"!
Sure, if you can write your application or algorithms in a map-reduce form, then you can parallelize it, but not all algorithms are inherently parallel to profit from this approach, and those are the ones we need to worry about.

As Andrei says in his presentation, in the beginning there were mutual exclusion locks, and those were pretty much the only way to deal with concurrency.
Then came reader-writer locks, lock-free and wait-free data structures, CSP, Actor Models, Software Transactional Memory, Hardware Transactional Memory and many others.
For a while, lock-free and wait-free data structures seemed to be the thing, but the fact that there wasn't a memory model to program them in, and that it was very hard to verify their correctness, and very hard to do efficient lock-free memory reclamation (wait-free is even harder), it caused people to try the other approaches. Nowadays, there is no clear winner, and maybe there never will be. Actor models have been gaining a lot of followers, with the whole Rx/Reactive movement based on it... I'm not sure they all realize that at the base of the actor model is the message-passing queue between the actors which is itself based on a lock-free queue.

Anyways, fast-forwarding to 2017, one of the upcoming CppCon talks which will definitly be worth watching, is the one by Paul McKennney, Maged Michael and Michael Wong:
https://cppcon2017.sched.com/event/Bgtm/the-landscape-of-parallel-programming-models-is-it-still-hard-or-just-ok-part-1-of-2?iframe=no&w=100%&sidebar=no&bg=no
As they mention in the abstract, there was a time when writing a simple loop seemed as perilous then as writing a lock-free data structure seems now.
I don't know what their talk will be about, but I do agree that most of the dangers in concurrent programming can be avoided by using better programming tools, and on that note, I would dare go so far as to say that we're entering "The Dawn of the Universal Constructs"!

What is a Universal Construct

Universal Constructs aren't a new thing. The first Wait-Free Universal Construct (WFUC) was invented by Maurice Herlihy back in 1993:
http://www.cs.utexas.edu/~lorenzo/corsi/cs380d/papers/p745-herlihy.pdf
WFUCs are a construction that encapsulate an object (or data structure) which was written for single-threaded usage, and provide a way to call its methods with wait-free progress.
It's kind of like wrapping all the methods in an object with a call to lock()/unlock() of a mutual exclusion lock, except that a lock is blocking while WFUC are, well, wait-free!



In summary, a Wait-Free Universal Construct lets you write your favorite data structure as if it was "single-threaded code" and then wraps its methods to provide wait-free progress.
If you saw Andrei's presentation at the beginning of the post, you'll know that he has a cool way (in C++) of automatically exporting the methods of an object/data-structure wrapped with a read-lock or a write-lock depending on whether the methods are mutative or read-only. The same kind of approach can be done with WFUCs, which means that they are truly generic.

How come I never heard of this before?

Well, you kind of have heard about this (if you read this blog).
Left-Right for example, is a Universal Construct that provides wait-free progress for readers and blocking (starvation-free) progress for writers:
http://concurrencyfreaks.blogspot.nl/2013/12/left-right-concurrency-control.html
It's fast, it reclaims memory, it's "universal", but it's not completely wait-free, i.e. it's not wait-free for mutations.

There are truly WFUCs in the literature and we've even added (wait-free) memory reclamation to a few of them. The most famous being P-Sim by Panagiota Fatourou and Nikolaos Kallimanis:
http://thalis.cs.uoi.gr/tech_reports/publications/TR2011-01.pdf

But even the best of them still works on the COW principle, in the sense that it requires a full copy of the data structure for every mutation.
Yes, that's right, if we have a map with 1M keys/values, and we want to insert a new key (or remove an existing one), we have to make a full copy of the 1M nodes of the data structure.

Waaaaiiiit wwwhhhaaat? Did you just say that this thingy has to copy 1 million nodes every time I want to insert a new key/value in my hashmap?

Yes, I'm afraid that's how it works. It's not as bad as it looks if the data structure is small, but as soon as you start going to anything bigger than a few thousand nodes in the data structure, throughput is going to go down the drain. And cache locality is a big issue with COW.

What's on the horizon

I happen to have insider knowledge that it is possible to make a wait-free universal construct that is fast enough to be used in production, because it doesn't have to copy the entire data structure (except on very rare occasions). This new way of doing WFUCs is fast enough to be used in real-life applications, in fact, it's capable of beating hand-written lock-free and wait-free data structures.
Yes, it's that good. We call it CX and the paper is almost ready.
... did I say it does wait-free memory reclamation as well?  ;)

As soon as other researchers see what CX is capable of, I'm sure they will have their own ideas and improve upon it, thus bringing about a new age of production-capable WFUCs.

Going back to the Concurrency Problem, how does this change the way we program multi-threaded applications?

Based on my experience as a developer, software engineers rarely use an off-the-shelf data structure as is. We always add a little twist to it.
I don't know whether this happens due to us having big egos and wanting to give our little personal touch to everything we do (I'm generalizing here), or if it's simply because we're tinkerers and we like to see what's under the hood and tweak it to our own desire. the truth is, if we could use it as is then there wouldn't be a need to write all the software people write, there would be just one search engine, just one banking software, just one customer management software, etc.

Whatever the reason may be, the consequence is, that we always make changes to the data structures, and the problem with that, is that lock-free and wait-free data structures will fall apart if they're touched. They have sequences of instructions that have to be done in a particular way, they have optimizations for relaxed memory orderings and subtle details, and memory reclamation, etc, etc. The temptation to touch and tinker a lock-free data structure is just too much, and we end up getting burned and then we say that "lock-free data structures suck", which is not true.
The algorithms behind these data structures are very subtle, and our human nature is to tinker with it, which is incompatible.

This is where Wait-Free Universal Constructs come in.
With an efficient WFUC, any software engineer without any knowledge of lock-free data structures (or atomics or the memory model) can just take a "single-threaded data structure", modify it to satisfy its needs (or ego) and then wrap it with WFUC and BOOOOM, out comes a fast and scalable implementation of its customized data structure, with wait-free progress.
Even more, another software engineer working on the code can later fix bugs or add new features to the data structure without breaking its correct functionality. Try doing that with a lock-free data structure, it's hard enough to get it right the first time, to add new functionality later is just too nuts.
As a software engineer, what more could I ask for?

No wonder that WFUCs are seen by researchers as the Holy Grail of concurrency, it's because they make it so easy to solve the Concurrency Problem in production.
Yes, I'm a fan boy of Universal Constructs, but the hype is called for and needed. This stuff doesn't solve all the concurrency problems, but it solves a a lot of them, enough to become a standard way of dealing with multi-threaded code, or at least for writing multi-threaded data structures.

Whatever happens, Universal Constructs are here to stay as one of the easiest tools to use when writing multi-threaded applications, and we all know that when it comes to multi-threaded programs, any help we can get is not enough  ;)