How about RLU? Is RLU a generic concurrency control?

On the previous post we went over why RCU is not a generic concurrency control. This time we'll talk about RLU (it's an L, not a C):
http://alchem.usc.edu/courses-ee599/downloads/rlu-sosp15.pdf

RLU is a synchronization technique which contains inside it an efficient userspace RCU.
It supports multi-atomic updates, making them visible in one-shot to the readers, without having to make an replica of the entire data, like on RCU.

The idea of RLU is that during a write operation, each modified object is first copied into a per-thread log, then it makes the modifications to the object in the log. When all modifications have been made, it increments the global clock, thus making all modifications atomically visible to readers. I'm over-simplifying, but it's ok for this post.

RLU is certainly more generic and efficient than RCU but it does not allow for generic code to be used. In fact, RLU does write-read synchronization but it does not handle write-write synchronization and the the paper itself mentions this explicitly:
"The basic idea of RLU described above provides read-write synchronization for object accesses. It does not however ensure write-write synchronization, which must be managedby the programmer if needed (as with RCU)".


To better understand why RLU is not a generic approach to concurrency, let's consider the canonical example of two threads 1 and 2 with cross dependencies. They are attempting to execute the following operations, where x and y start both at false:
Thread 1:
  if (!x) y = true;

Thread 2:
  if (!y) x = true;
 
As I'm sure you're aware, any serializable execution of these two operations will either result in x and y being {true,false} or {false,true} but never {true,true}. One of the operations has to "happen before" the other. If T1 executes before T2 then the end result will be {false,true} and if T2 executes before T1 then the end result will be {true,false}.
If you run this code without modification on RLU, it can happen that T1 reads x and sees false while T2 reads y and sees false, then T1 acquires the lock on y while T2 acquires the lock on x and each write to their log that the variables will be true and each advance the global clock and commit. In case you're wondering, this scenario is not linearizable.






In the database world, this kind of problem is called a write skew anomaly (see section 2.4 of the MV-RLU paper for a great explanation in the context of RLU). In the context of concurrent data structures, we call these bugs!
Handling cases like this is what an STM or a Universal Construction are supposed to do because an STM/UC must handle any sequential piece code (with some exceptions).
Granted, if you're really careful how you write the code, you can use RLU as long as you avoid writing sequential code that has this kind of cross dependencies. The problem is, in practice, this is very hard to do and even when you do it, you're never really sure it's actually done correctly (did I miss some cross dependency?). If you write user-code that has one of these problems, it will be hard to find it and likely hard to fix it.

There is an easy solution for RLU and that is to use a global lock, but then it looses some of its appeal because it no longer scales for writes.
Keep in mind though that RLU scales for read-only transactions!

STMs like TinySTM or TL2 have time-based algorithms that keep a read-set of all loads done within the transaction and do validation of the read-set at commit time exactly to handle these kind of cross dependencies.
If you're wondering how frequent are cross dependencies in real code, then even an ordered linked list is prone to these kind of issues (depending on how it is implemented), which helps to show that it's very hard to get away from this problem in practice.

If you ever read a paper where they say that they used RLU to make an STM, be very very suspicious: an STM must be able to handle cross dependencies and provide linearizable (globally serializable) operations regardless of what the underlying sequential user-code. If it works only for some small subset of user programs, then it's not an STM... sure it's a very valuable tool, but it's not an STM.

What is Eventual Consistency ?

On this post we're going to talk about Eventual Consistency in the context of lock-free and wait-free data structures, with focus on the C++ memory model, although most (or all) of what we're going to cover also applies to other memory models likes the ones in D, Java , Rust, C11, <insert language here>.
If you're looking for an explanation on what Eventual Consistency is in the context of databases then this (may or) may not be what you're looking for!

Before we explain what is eventual consistency in C++, we need to explain a little of what shared memory is and a what is a memory model.
Computers do many things: arithmetic computations, decide different things based on logical expressions, sending and receiving packets, putting pixels on a screen, etc. For this post, we care about reading from main memory and writing to main memory. This means "loads" and "stores".
The whole C++ memory model is about what happens when you do loads and stores from different threads, and all the other stuff that the computer does is pretty much out of the picture.
Obviously, stores are used to store a value in a certain memory location, and loads are used to read a value from a given memory location:
    x.store(value);
    value = x.load();

Also, from the memory model's point of view, all loads are indistinguishable, and so are all stores. CPU vendors have peculiarities, like some stores may re-order but others not (think stores on the same cache line), but the memory model doesn't really care about that, so for this post, we won't care either.

Ok, so this was really important. If you're not convinced that everything is about loads and stores then you better go and read the memory model of your favorite language and then come back.
Let me say it once more: It's all about loads and stores.


Combinatorically, if we have two different operations (loads and stores) we can define ordering constraints based on four cases:
1. A load may not reorder with a subsequent load;
2. A store may not reorder with a subsequent store;
3. A load may not reorder with a subsequent store;
4. A store may not reorder with a subsequent load;

When none of the four constraints above are set, and if we want to share data among threads or processes (remember, our context is lock-free and wait-free data structures) then in C++ this is called memory_order_relaxed. In this memory ordering any loads can reorder with any stores. Whatever the order of the code you wrote, the compiler may decide to reorder the loads and stores in whatever way it thinks is the best.
This has reduced synchronization and gives a lot of leeway to the compiler, thus resulting in high performance code. The downside is that most lock-free and wait-free algorithms were designed with a specific order in mind, and when this order is not respected, the algorithm no longer works.

To enforce constraint 1, the first load has to be done with a memory_order_acquire or memory_order_seq_cst. In the C++ memory model, loads with memory_order_acquire can not be reordered with any subsequent load or store. Most of today's CPUs enforce this constraint by default already, which means that it needs no synchronization as well.

To enforce constraint 2, the second store has to be done with a memory_order_release or memory_order_seq_cst. In the C++ memory model, stores with a memory_order_release can not be reordered with any previous load or store. CPUs with Total-Store-Order (TSO) like x86, enforce this constraint by default already, which means it needs no explicit synchronization. In practice the CPU internally has synchronization to achieve this strong ordering, but that's out of scope.

To enforce constraint 3, the first load has to be done with memory_order_acquire or memory_order_seq_cst. x86 CPUs provide this guarantee without explicit synchronization (barriers/fences).

To enforce constraint 4, both the load and the store have to be memory_order_seq_cst. No practical CPU provides this by default (such a CPU would be too slow) and to have such a constraint requires costly synchronization, typically a full fence or at least a store-load fence.
Explaining why this requires such high synchronization would require an entire (large) post about this topic, so let's just accept it as it is.

To sum it up, if we want all four constraints, we have to use sequentially consistent memory ordering, while if we want only the first three constraints, then the acquire-release memory ordering is enough.
Notice that stores and loads are done at the word level, 64 bits let's say. Therefore, when we talk about sequential consistency we are talking about it at the word level. Any object bigger than one word and this guarantee disappears because it will take multiple stores (or multiple loads) to modify (or read) such an object.


So what about eventual consistency?
Roughly speaking, eventual consistency guarantees if no new updates (stores) are made to a data item (word), then eventually all accesses (loads) to that item (word) will return the last updated value.
In other words, if we stop doing stores in a certain variable, eventually, when we go and read it from another thread, we will see the last store that was made. Pop quiz: which memory ordering is the weakest that gives this guarantee?
Answer: It's memory_order_relaxed (memory_order_acq_rel and memory_order_seq_cst also provide this guarantee but at a greater cost).
You see, something I didn't say about memory_order_relaxed is that the end result must look like the code you wrote, which means that eventually it will have to keep whatever was the last store you wrote in your code. This is highly non-obvious from reading the specs, but that's how it works, otherwise it would let the compiler produce incorrect programs, even in single-threaded code.


Ok, so now that we know that in C++ memory_order_relaxed provides eventual consistency (at the word level), what can we do with that?
Well, the answer to that depends on how useful you think that eventual consistency is.
The term eventual consistency is meant as a consistency property of an item, or object in C++ parlance. If the object is the size of a word (64 bits or less) then just make it atomic<> and all stores and loads to/from it must be changed to use memory_order_relaxed.
If the object is larger than a word then things start to get more complicated because then we could have concurrent stores touching different words of the object and it would leave it in an inconsistent state. Example below:
struct myobject {
    atomic<uint64_t> a {0};  // Consistency for this object implies that a is equal to b
    atomic<uint64_t> b {0};
}

myobject obj;

Thread 1:
    obj.a.store(1, memory_order_relaxed);
    obj.b.store(1, memory_order_relaxed);
   
Thread 2:
    obj.a.store(2, memory_order_relaxed);  // May occur before a.store() in thread 1
    obj.b.store(2, memory_order_relaxed);  // May occur after b.store() in thread 1
   
Thread 3:
    while (true) {
        if (obj.a.load() == obj.b.load()) break; // This may loop forever
    }   
   
In the above example, we defined the object to be consistent when having a and b members equal. The stores with Thread 1 may interleave with the stores in Thread 2, causing the object to be left in a inconsistent state permanently, with a=1 and b=2, which is not eventually consistent because the stores on the object have stopped but thread 3 will be in an infinite loop waiting for the object to be consistent.


Even without going into the topic of whether or when is eventual consistency useful, we still have to care about a subtle but extremely important detail in the definition of eventual consistency: it refers to an object.
Let me say this again because it's important: Eventual Consistency requires you to define the item (or object) on where this consistency is being applied.
This means that what you define to be the object affects the consistency.
Saying that you provide eventual consistency in your application is completely irrelevant unless you define at which granularity level you're providing such a guarantee.
If you're providing eventual consistency at the word level, then it's easy to implement, just make all accesses memory_order_relaxed;
If it's eventual consistent at the C++ object level, then each object must itself be atomic<>, which means that the underlying implementation is using a mutual exclusion lock to protect it, thus denying any benefit from doing eventual consistency. You might has well say you're providing strong consistency because you are in fact providing linearizability (at the object level);

In the context of data structures, if we say that a data structure is eventually consistent, it still needs to be atomic itself and all its nodes/whatever constitutes it. This means that the data structure itself needs to be consistent, or atomic. This is extremely hard to achieve without going into a fully linearizable (or at least sequentially consistent) algorithm, so perhaps this is not very useful in practice.

However, if we have multiple data structure instances, even if each of them is linearizable, doing operations or two or more of these data structures is not trivial to make them appear atomic (unless we're protecting everything with a global lock, or using a transactional memory). In such case, we can simply say that we're providing eventual consistency at the data structure level, and it would be correct to say so, because in each data structure instance we provide atomicity (linearizable consistency) but across data structure instances we only guarantee that eventually the modifications will be seen over all the instances.

If you take anything away from this post it should be this:
Eventual Consistency only makes sense when we define what is the "object" where this consistency is being applied.

Cliff Click - A JVM Does That ???

There are a few people that are really knowleadgeable about Java, and Cliff Click is certainly one of them. One of his latest talks was at Devoxx and it's named "A JVM Does That???". Youtube link below.

This talk is so rich with content that it's hard to explain what it is about, so I'm just going to mention my favorite parts, but please watch it all if you haven't done so yet.

The explanation on the endless loop of GC cycles when have a cache (data structure) near the limit is just divine:
https://www.youtube.com/watch?v=-vizTDSz8NU&t=24m40s

Or how about the illusion that locks are fast (and fair)
https://www.youtube.com/watch?v=-vizTDSz8NU&t=12m55s
hence the importance of starvation-free locks that I mentioned in my CppCon talk, and the reason behind Andreia and I spending some of our time coming up with new starvation-free lock algorithms like Tidex:
http://dl.acm.org/citation.cfm?id=2851171
http://concurrencyfreaks.com/2014/12/tidex-mutex.html

The part about thread priorities is a nice demonstration of why lock-free and wait-free algorithms are so important (you don't need to care about thread priorities with lock-free and wait-free):
https://www.youtube.com/watch?v=-vizTDSz8NU&t=28m10s

But my favorite is the fact that System.currentTimeMillis() has happens-before guarantees across cores on the HotSpot JVM, because this guarantee allowed us to make a blazing fast queue (which we will show in a future post):
https://www.youtube.com/watch?v=-vizTDSz8NU&t=14m22s

Learning is fun with Cliff Click!

DoubleLink - A Low-Overhead Lock-Free Queue

On this post we're going to talk about a new lock-free queue that Andreia and I invented.
It's called DoubleLink Queue and it's a memory-unbounded Multi-Producer-Multi-Consumer linearizable lock-free queue.
Example code is in C++ with Hazard Pointers but we have a Java version as well, both available on github:
C++
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/queues/CRDoubleLinkQueue.hpp
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/queues/HazardPointersDL.hpp

Java
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/Java/com/concurrencyfreaks/queues/CRDoubleLinkQueue.java

Before we start, a short intro

There are many, many, memory unbounded linearizable MPMC lock-free (and a few wait-free as well). However, they are all based on the enqueueing and dequeueing mechanism designed by Maged Michael and Michael Scott, or at least all of the interesting lock-free memory-unbounded MPMC queues are based on it.
The only exception to this that I know of, is SimQueue by Panagiota Fatourou and Nikolaos Kallimanis (more on this later).
This is just to show that although there are many ways to make queues, there is only one simple way to do it, i.e. there is one easy way to do enqueueing and dequeueing in a singly-linked list using CAS operations.
... well, actually this isn't true, because the queue we're going to talk about today has a different way of doing it  ;)

Motivation

Why another lock-free queue?
Well, because we can, but mostly, because we were trying to answer the question:
Is it possible to insert a node in a linked list using less than 2 CAS ?
You see, the Michael-Scott queue (MS from now on) needs at least 2 CAS operations to insert a new node/item: one CAS to link the node to the last node's "next", and another CAS to advance the tail. For the dequeue, a single CAS is needed which advances the head, however, it needs two seq-cst stores when using hazard pointers, one to protect the current head node and another to protect the next node, because it's the next node that contains the pointer to the item we're trying to dequeue.
Summing up in a nice table, this is what the MS queue does, as well as all other queues based on the same mechanism:

2 links or !2 links, that is the question

The first difference between DoubleLink and MS queue is that DoubleLink is based on a doubly-linked list, while MS is based on a singly linked list. And, as strange as it may seem, its this tiny difference that allows it to do an insertion with a single CAS operation.
In MS, a new node is linked to the list in two steps:

1. CAS on the last node's next;
2. CAS to advance the tail;

On DoubleLink this work differently. First, we create a new node whose "prev" pointer is pointing to the current last node on the list. Then we do a CAS on the tail to swing the pointer to this new node, and finally we link the previous last node to the current last node. The steps are:

1. Create a new node linking its prev to the current last node;
2. CAS to advance the tail;
3. Link the previous last node to the current last node;

For those of you paying attention, you may be wondering "How can doing something in three steps be any simpler or faster than doing it in two steps?", and you're right in thinking that. The simplicity part is arguable, but the trick here is that steps 1 and 3 of DoubleLink queue have no synchronization, i.e. they are done with relaxed stores, while on the MS queue both steps 1 and 2 have a CAS which is a heavy synchronization instruction.

Code for enqueue()

Let's take a look at the enqueue() code in C++:

As can be seen in line 7, the store on the new node's prev is just a regular store because there are no races on prev: once the node is visible to other threads (with the CAS on the tail) the prev member will never change again, a concept sometimes referred to as "immutable after visible".
Then, in line 9 we make sure that the previous node is linked to the current last node, this time it's an atomic store in the next member, but it's a relaxed store.
Afterwards, in line 10 we advance the tail with a CAS, the only synchronized operation, and we link the previous node to the current last node using a release (or relaxed) store (line 11).

This kind of approach of setting the pointer "back" first and then advancing the tail is not new, and was first shown by Treiber, which used it to make the world's first (and simplest) lock-free data structure, namely, a lock-free stack: https://en.wikipedia.org/wiki/Treiber_Stack
The innovation in DoubleLink is that we can use this same trick in a doubly-linked list, and then have the enqueuers do a store race on lprev.next to make sure it is linked to the last node in the list before advancing the tail to the new last node. This race is safe according to the memory model because it is done on an atomic variable.
Personally, I find this approach super simple and very intuitive, but I'm biased  ;)

What about SimQueue?

Remember when I said earlier on this post that pretty much all other queues in this category (memory-unbounded, lock-free, linearizable, MPMC) use the MS algorithm underneath, except SimQueue? Well, a bit of history of discovery is in order here:
Andreia and I have had the idea for DoubleLink and its implementation for some time now, and we had a working implementation before we read the paper on the SimQueue, and long before we understood the algorithm used in the SimQueue. As it so happens, the enqueue method in SimQueue uses a trick that is not too far from this one, except ours is way more simple.
In SimQueue, the EnqState object has a link to the old tail, the beginning of the list, and the new tail. The first two are called link_a and link_b in the original paper if I'm not mistaken... anyways, they have multiple threads (dequeuers as well) do the link between the nodes link_a and link_b, which is pretty much the same idea we have for having all the enqueuers (and only the enqueuers) race on lprev->next to set it to the current tail using a relaxed store. One more reason to go back to the post on SimQueue and read it carefully, it's just one of its many hidden gems: http://concurrencyfreaks.com/2016/12/sim-queue-in-java-part-12.html
Their idea is way more complex than what we show in DoubleLink because they need it to be wait-free and we were just aiming for lock-free, but I just want to make it clear that we didn't copy their idea because we didn't even know about it, and it's not the same thing because ours is simpler, and simplicity is elegance. It's far easier to make something more complex with extra functionality than it is to make something simpler with the same or better functionality  ;)

Code for dequeue()

The dequeue method is pretty much the same as MS queue, so nothing new to see here. The only difference is that we have a doubly-linked list instead of a singly linked list:

There is one last trick in DoubleLink, and it's related to memory reclamation

Unless you're in Java or something with a Garbage Collector, you need some memory reclamation technique if you want to use MS or DoubleLink, or any other memory-unbounded lock-free queue.
DoubleLink is a lock-free queue and as such, it needs a lock-free (or wait-free) memory reclamation technique. This eliminates things like Epoch-based reclamation, RCU and Userspace RCU, and pretty much leaves pointer-based techniques like Hazard Pointers. Yes, there are other lock-free (pointer-bsaed) memory reclamation techniques, but they are usually more complex to deploy and we're aiming for simplicity, so lets stick to HP for now.
As we saw on the beginning of the post, the dequeue() in MS needs two sequentially consistent stores for the Hazard Pointers, but it would be nice if we could do it using just one... and indeed it is possible, but not for MS.
The trick is that we can make a variant of HP where the retire() scans not just for the current node that is attempting to delete but also for threads using the prev and next objects of the node.

In our variant of HP, we scan the other thread's hazard pointers for a match of the node we want to delete and we scan also for the next and prev of the node we want to delete.
If another thread is using the previous node and attempting a dequeue() operation, it may dereference the next node (line 4 of dequeue()), which is the node we're trying to delete, and therefore, we can not delete it yet. If another thread is using the next node and attempting an enqueue() operation, it may dereference the previous node (line 9 of enqueue()), which is the node we're trying to delete, and therefore, we can not delete it yet.

Each thread is looking for usages of the pointers in the next and prev of the nodes in its own retired list, and does not dereference the next or prev of the nodes in the list/array of hazardous pointers. Such behavior would be incorrect and lead to a crash.

This simple trick of scanning for occurrences of node.prev to protect lnext in dequeue(), and scanning for node.next to protect the lprev pointer in enqueue(), reduces one seq-cst store in each method. Unfortunately there is no gain in applying this HP variant to the MS queue because its enqueue() already requires one seq-cst store (only the tail node needs to be protected), and for the dequeue() the next node can not be protected because there is no way of knowing what is the previous node.

The whole logic of going through this trouble is because a seq-cst store is typically a heavyweight synchronization operation, for example, on x86 it implies one MFENCE instruction, and therefore, any reduction in the amount of seq-cst stores will reflect itself in a throughput gain.

Comparison

The comparison table of MS and DoubleLink is shown below and as you can see, DoubleLink does less synchronized operations for both enqueueing and dequeueing:




Unfortunately, this reduction in synchronized instructions doesn't reflect itself in large throughput gains because most throughput when uncontended is related to cache locality, and when highly contented is related to the contention... it's all about the cache.
Anyways, here are some comparison plots between MS and DoubleLink:






The throughput gains go up to 30% but not much more than this. Still, a good improvement having into consideration that we didn't make the code more complex.
The main drawback when compared to MS queue is that each node in DoubleLink needs two pointers: the prev and the next, while on MS needs just the next, which means DoubleLink uses more memory for a non-empty queue. This isn't important in the land of plenty of RAM like servers nowadays, but in mobile and IoT land it can be a bit annoying... nobody's perfect.


30% may not seem like a lot, but when you take into consideration that now you can go to any of the other lock-free or wait-free queue and replace the MS algorithm with DoubleLink to get an extra throughput gain, then it becomes interesting.
In the end, we set out to see if it was possible to make a lock-free memory unbounded queue using a single synchronized instruction for the insertion and a single synchronized instruction to protect the node, and it is! I would say this is pretty hard to beat, but I know for a fact Andreia has a queue that beats this, and on top of it is wait-free, so yes, we can do better (with other limitations though).... a topic for a future post.
In the meantime, we hope you enjoy the DoubleLink algorithm and use it to make even better queues!

You can get a short academic paper on the DoubleLink Queue here:
https://github.com/pramalhe/ConcurrencyFreaks/blob/master/papers/doublelink-2016.pdf