OneFile and Tail Latency

Last week we talked about OneFile, the world's first wait-free STM and on this post we're going to explain the importance of wait-free progress.
https://github.com/pramalhe/OneFile/

Lock-based concurrency mechanism (locks) have several difficulties in practice:
1) if we use more than one lock, we're subject to having deadlock issues;
2) if we use priority locks, we're subject to having priority inversion issues;
3) if we use a lock without starvation-freedom guarantees (such as a spinlock), we're subject to starvation and live-lock;
4) using locks is prone to convoying effects;
5) mutual exclusion locks don't scale for read-only operations, it takes a reader-writer lock to have some scalability for read-only operations and even then, we either execute read-only operations or one write, but never both at the same time. Until today, there is no known efficient reader-writer lock with starvation-freedom guarantees;


In concurrency, progress comes in different flavors http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html
Wait-free algorithms provide more guarantees than lock-free algorithms which in turn provide more guarantees than blocking algorithms (with one exception for blocking starvation-free).

A lock-free algorithm guarantees that at least one thread is making progress (whatever "progress" may mean). But it also implies that in the event of a failure of a thread/process, at least one of the other threads/processes will continue to execute. This is an extremely strong guarantee when it comes to failure-resilience and I'll cover it on an upcoming blog post.

Blocking algorithms don't have such a guarantee: if the thread/process holding the lock dies, then none of the other threads/processes will ever be able to do any work. There is a catch here though, if the algorithm is blocking starvation-free, it means that given enough time (execution quantum) to all the threads/processes, then they will eventually complete. This means that when it comes to completing an operation, starvation-freedom guarantees that the operation will execute in a finite amount of time, as long as the system has enough cores to run the threads/processes or the scheduler is somewhat fair, and no failure occurs. In the latency distribution, this gives a "cutoff" beyond which the operations are completed.

Lock-free algorithms don't have this cut-off. Instead, they have a "fat tail" in the latency distribution. Being lock-free implies the possibility of starvation, and in that sense (and only in that sense) starvation-free is stronger than lock-free.

Wait-free bounded progress goes one step above all this: it guarantees that given a time slice of execution (quantum) all thread make progress. This is true even in the presence of failures: if N-1 threads/process fail, the remaining thread/process will still be able to complete. If not, then the algorithm is not wait-free. Moreover, wait-freedom implies being free from starvation, which means that it also has a cutoff in the latency distribution.

In summary, wait-free (bounded) provides the strongest of all progress guarantees:
- Progress for all threads/processes;
- Progress in the presence of failures;
- Deterministic cutoff on the tail of the latency distribution;


We have implemented two variants of OneFile, one with lock-free progress and the other with wait-free progress. The implementation with wait-free progress is slightly slower in terms of throughput, because giving these strong guarantees implies executing more synchronization, however, when it comes to tail latency, the wait-free variant of OneFile is better than any other (blocking) STM by orders of magnitude (lower is better):



At the tail of the latency distribution, for the percentile 99.99% (P9999), the improvement of OneFile over the blocking STMs are huge and speak for themselves. The dark blue line is OneFile wait-free and lower times are better. Notice that this is a log-log plot with each horizontal line separating an order of magnitude, meaning that the difference to the lock-free (light blue) and blocking STMs is at least 1000x better.

Wait-freedom is a vital characteristic when working with low latency scenarios such as networking devices, high frequency trading, or control systems (autopilot cars/planes/rockets). Sure, there are other ways to deal with it such as having a tight control over the scheduler and that is what the hardcore real-time people do anyways, but with OneFile we have strong latency guarantees without having control over the scheduler, and that is on itself an important change for multi-threaded embedded systems development.


Next week we're going to talk about how OneFile allows us to create wait-free balanced trees.

OneFile - The world's first wait-free Software Transactional Memory

Ok, so we've been silent for more than a year but for a good reason: busy doing cool stuff.
I'm pleased to announce one of those cool things:
OneFile - A Wait-Free Persistent Transactional Memory
Paper here:  https://github.com/pramalhe/OneFile/blob/master/OneFile-2019.pdf
Source code here: https://github.com/pramalhe/OneFile

OneFile is the world's first STM (Software Transactional Memory) with wait-free progress.
Andreia, Pascal, Nachshon and I got together to make OneFile and what this means is that you can write a sequencial data structure (single-threaded code) and with OneFile it gets transformed into a wait-free concurrent data structure. Moreover, it comes with integrated memory reclamation, memory allocation and memory de-allocation, all with wait-free progress. And on top of that, it works on Persistent Memory (PM), sometimes called Non-Volatile Main Memory NVMM).


Let's go one step at a time.
First things first, why make a wait-free STM ?

As a developer of multi-threaded applications, whenever the need arises to have a concurrent data structure, you typically have two different solutions:
take a sequential data structure (single-threaded code) that does whatever you need to do and protect it with a lock, or take an existing fine-grained lock or lock-free data structure that someone else implemented.

If you go with the first approach, you get maximum flexibility because it's easy to modify the data structure to your own needs. The reason for this "ease-of-use" is because code protected by a lock can be reasoned about in a "sequential way", something which is very intuitive to us humans. You won't have to consider interleavings of operations or instructions or the the memory model of the language you're using or anything like that, all you need to do is add mutex.lock() at the beginning of the data structure's methods and mutex.unlock() at the end, or the equivalent semantics in your language/lock implementation.
This is possible because a researcher, many years ago, invented a "mutual exclusion lock algorithm" to deal with all of that, and some kind-soul engineer has decided to implement it in the language/library you use so that you, the developer, can now write safe and correct concurrent code without actually having to understand anything about concurrency. It's hard enough to deal with the business logic of your application and all the details that using a programming language entails.

The second approach is much more restrictive. Fine-grained locking code is very sensitive to changes and any modification to the underlying data structure's behavior is likely to cause incorrect results. This is even worse for lock-free code, where changing the order of a single line of code almost always results in an incorrect data structure. Considerations about interleavings and memory models become crucial for these, implying that such data structures are the product of hard work by experts in the field.

In essence, it's the difference between taking a HashMap (a sequential data structure) https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html modifying whatever you need and protecting it with a lock to make it concurrent, or taking a ConcurrentHashMap (a fine-grained concurrent data structure) https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html and start modifying code in it.
Modifying the code in HashMap is something that an entry-level engineer is likely to achieve correctly, but modifying the code in ConcurrentHashMap is something only expert engineers are likely to succeed in doing correctly. And when we start talking about lock-free data structures, then we enter an expert-only domain, an elite group of people who spend a lot of time thinking about concurrency... and dealing with concurrency bugs  ;)

With OneFile we have eroded this "class" separation. Now, even a novice developer is capable of implementing a lock-free data structure correctly. Not just lock-free, but wait-free even!
The reason for this is because OneFile takes a sequential data structure and provides concurrent wait-free access to it. Instead of adding mutex.lock()/unlock() at the beginning/end of each method in the data structure, the transformation requires a few more changes, but still easy enough for any developer to implement. Namely:
- Wrap each mutative method in a lambda and call to updateTx([=] { your_code_here });
- Wrap each read-only method in a lambda and call to readTx([=] { your_code_here });
- Replace calls to 'new T' with tmNew<T>();
- Replace calls to 'delete' with tmDelete();
- Wrap the members of every struct/class T in the tmtype<T> template, so as to provide concurrent access;

Compare a singly-linked-list set data structure (wait-free) here https://github.com/pramalhe/OneFile/blob/master/datastructures/linkedlists/OFWFLinkedListSet.hpp
with a hand-made Maged-Harris singly-linked list set (lock-free) here https://github.com/pramalhe/OneFile/blob/master/datastructures/linkedlists/MagedHarrisLinkedListSetHP.hpp
Notice the difference?
Which one would you feel comfortable modifying or adapting to your application?
And the hand-made set is not even wait-free, if you want a hand-made wait-free set then good luck implementing this one (it's the only one I know of)
http://www.cs.technion.ac.il/~erez/Papers/wfll.pdf  ... ohhh and did I mention that out of all the hand-made wait-free data structures in existence, there is only one published with wait-free memory reclamation? https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/crturnqueue-2016.pdf
Data structures in OneFile have integrated wait-free memory reclamation  :)

OneFile has its limitations tough.
Mutative operations are serialized, i.e. only one is executed at time, although disjoint read-only operations can execute concurrently most of the time.
It needs a machine with a double-word compare-and-swap (DCAS) which all current x86 support, but doesn't exist on ARM or PowerPC.
Because of the use of DCAS, all data types have to be broken down to 64bit words. This means that having things like arrays of bits is hard to do (takes up too much memory). Most data structures are all about operations on pointers (to nodes or other data types) so it's mostly ok, but it may make it difficult to use in some data structures.
Despite these limitations, when you take into consideration that the alternative is to make your own hand-made wait-free data structure, the choice becomes obvious.


Next week we'll discuss the importance of having data structures with wait-free progress. In the meantime you can check out the first 20 minutes of this video to understand the importance of wait-freedom for latency  https://www.youtube.com/watch?v=FtaD0maxwec

Why do we need to flush persistent memory?

In the followup of the previous post, here is a presentation by an Intel guy where he explains to some detail exactly why we need to flush stores to NVM. He answers this exact question at the 5min mark:

https://www.youtube.com/watch?v=FcKwqdZU5dk&t=5m

... and Andy Rudoff said the same at 9m30s of this presentation:

https://www.youtube.com/watch?v=rG8h8NPnHbc&t=9m30s

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.

Can't protect a pointer without a store-load fence

This post is about memory reclamation algorithms in shared memory concurrency. That's things like Hazard Pointers, Drop the Anchor, epoch-based reclamation (User-space RCUs) and of course, Hazard Eras. There's an insight about memory reclamation, I had a long time ago, that I want to share. This insight probably isn't new, but it was to me when I thought about it  ;)


Let's start from the beginning:

Many years ago, Leslie Lamport made a short paper where he showed that to have mutual exclusion on shared memory system, you need at least one store-load fence. Not sure this is the right reference but it's close enough to this topic:
https://www.microsoft.com/en-us/research/publication/make-multiprocessor-computer-correctly-executes-multiprocess-programs/
In other words, for two threads to have mutually exclusive access to a certain data, this data must be protected with an algorithm (a lock) and to implement this algorithm you will need at least one store and one load, whose visibility must not be re-ordered to the other thread.
It's probably easier to think about this in the context of Peterson's algorithm, or Dekker's, or one of our 10 algorithms which do the same kind of thing:
https://en.wikipedia.org/wiki/Dekker%27s_algorithm
https://en.wikipedia.org/wiki/Peterson%27s_algorithm
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/cr2t-2016.pdf

If you get in the context of these algorithms, you can think about the store as being a way of signaling the intent to acquire the lock, and the load as a check that the other thread doesn't already have the lock. If the effects or visibility of these two operations could be changed (by the compiler or CPU or cache-coherence system) then the algorithm would no longer be correct.
Placing a store-load fence between the store and the load prevents re-ordering from happening, making the algorithm correct, at the cost of adding synchronization.

Another analogy, is to think about a store as a mechanism to send a message to a certain centralized location, and the load as a mechanism to read the message at that centralized location. This is easier for us humans to reason about.
In the end it's all physics, transmitting information takes time, and it involves waiting which by definition is blocking or at least involves some kind of synchronization, in this case, the store-load fence.

As an aside, there are no explicit store-load fences on the C11/C++ memory model, therefore we must use a seq-cst store followed by a seq-cst load, or a relaxed store and relaxed load but with an atomic_thread_fence(memory_order_seq_cst) in the middle.


Waaaaiiit, you said you were going to talk about memory reclamation, but you're talking about mutual exclusion?!? You tricked us!!!

Not exactly, you see, the two-thread mutual exclusion problem and the memory reclamation problem have a lot in common.
A lock algorithm allows two threads to access an object, one a time. Each thread has the guarantee that when it is accessing the object, the other thread is not accessing the object.
A memory reclamation algorithm allows two threads (the reader and the reclaimer) to access an object, with the reclaimer having the guarantee that at a certain point in time the reader will never access the object again.
Notice the difference?

For mutual exclusion a thread needs to know if the other thread is not currently accessing the object, while for memory reclamation, a thread (the reclaimer) needs to know if the other thread (the reader) is not currently accessing the object nor will it ever try to access it again.

In summary, memory reclamation can be seen as mutual exclusion with a stronger requirement.
Which means, that if to do mutual exclusion we need a store-load fence, then we also need (at least) a store-load fence for doing memory reclamation.
To be more precise, a reader needs one store-load fence to signal its intent to protect an object to the reclaimer.

Now, I never proved this formally, this is just a sequence of logical deductions. So let me substantiate this bold statement with some examples.

Start by looking at figure 3 of our Hazard Eras paper:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/hazarderas-2017.pdf



Looking at the left side, to protect a pointer in Hazard Eras we do a seq-cst store of this pointer on a shared array, and then we check that the pointer is still valid. There is an implicit store-load fence placed in by the compiler when we use seq-cst atomic store followed by a load.
In Hazard Pointers, at least one store-load fence is needed for every object needing protection.

Looking at the right side, to protect a pointer with URCU or Epoch-based reclamation, we do a seq-cst store of an epoch and then load whatever pointer we want to use. Again here there is an implicit store-load fence so that the store of the epoch will not be re-ordered with any of the loads of the object that will be used in the read-side critical section.
In Epoch-based reclamation, a single store-load fence is needed to protect all objects, now and until the read-side critical section ends.

Looking at the middle code, to protect a pointer with Hazard Eras, we do a seq-cst store of an era, load whatever pointers we need, and then check that the era has not changed. Again here, there is an implicit store-load fence between the store of the era and the subsequent loads. In fact, there is also a constraint that the load of the pointer(s) and the following load of the era can not be re-ordered, but that's another story.


Do you see the "pattern" now?
All three classes of algorithms require one store-load fence.
The difference between the three is that:
- Hazard Pointers does one fence to protect one object;
- Epoch-based does one fence to protect all objects (until the end of the read-side critical section);
- Hazard Eras does one fence to protect all currently live objects;
and of course, Epoch-based reclamation is blocking, while Hazard Pointers and Hazard Eras are lock-free.


Having said this, there are some apparent exceptions to this, but I would argue that the synchronization of the store-load fence is always there, it just might be hidden from sight.
For example, we can use hardware transactional memory to do memory reclamation, and no explicit store-load fence is needed... because the hardware does the corresponding synchronization internally.
http://www.cs.technion.ac.il/~erez/Papers/teleportation.pdf
It's also possible to use optimistic memory reclamation, but then we're relaxing the premises of the memory reclamation problem I stated above and that may not always be possible.
http://www.cs.technion.ac.il/~erez/Papers/oa-spaa-15.pdf
There are also other approaches that make use of services provided by the Operating System, just like there are mutual exclusion locks that are OS provided. Ultimately, they will need synchronization or a store-load fence, maybe it's the kernel that's doing it instead of the user code explicitly, but the synchronization is there somewhere, hidden behind all the OS/Kernel layers.

The final insight is the following: If it does correct and safe memory reclamation in a shared memory concurrency system, it needs at least one store-load fence, or an equivalent form of synchronization!