http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue
It seems that the current queue implementation in Akka uses this algorithm. It took me some time to understand how it works, and there are a few interesting things:
First, this queue is wait-free for push() and pop() operations.
The push() function does one XCHG and one store with release barrier, and no retries are needed.
The pop() function does stores, and that's it.
It's true that this queue is single-consumer only, but you should try to come up with a MPSC queue that is wait-free (or even lock-free) to see how hard it is. Yep, it's hard, and this guy did it, so I'm definitely impressed, and so should you!
Just to give it some perspective, the typical Michael & Scott queue which is implemented in Java's ConcurrentLinkedQueue, needs at least two CAS to insert a new node... both of which may fail and will have to be retried.
The disadvantage is, that this queue is not linearizable. In fact, it's not even sequentially consistent, or weakly consistent, or even has an happens-before relation between calls of push() and pop(). It's consistency model is serializable.
As surprising as it may seem, this is enough to get the actor model properly working and passing messages from actor to actor. I'm guessing this happens because each actor needs to see the received messages in FIFO order, but it is ok to not see those messages immediately.
It's the joy of distributed systems :)
Later note:
After some comments (thanks Nitsan!) I realized that some details of this post were a bit confusing, namely, there are two variants of this MPSC queue and they have a slightly different pop().
In the implementation by Vyukov the pop()'s Progress Condition is Lock-Free and its Consistency Model is Serializable.
http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue
In the implementation in Akka, the pop()'s Progress Condition is Blocking, but its Consistency Model is Linearizable.
https://github.com/akka/akka/
The Akka implementation is Blocking because it may spin eternally if the thread inserting the node blocks/crashes/sleeps before setting the next of the previous node, but Linearizability is a much stronger consistency model than Serializability, so it's a trade-off (both implementation are correct).
Hi Pedro,
ReplyDeleteInitial version of MPSC queue for actors (that encouraged Akka team for message box with queue mentioned in your article) was alternative implementation of Scalaz actor: https://github.com/scalaz/scalaz/commit/c7c5c70c25f00e64537e4cbb07cf15a2791b1366
Hi,
ReplyDeleteThe MPSC algo by Vyukov is great, but note that the Akka implementation is not the same. In particular it has the following snippet in peekNode (called from poll()):
final Node tail = ((Node)Unsafe.instance.getObjectVolatile(this, tailOffset));
Node next = tail.next();
if (next == null && get() != tail) {
// if tail != head this is not going to change until consumer makes progress
// we can avoid reading the head and just spin on next until it shows up
do {
next = tail.next();
} while (next == null);
}
return next;
As you can see the while loop is an attempt at avoiding the linearization issue at the cost of redundant head reads and becoming lock-free instead of wait-free. Also, though this is murky waters, I believe the queue has happens before guarantees as the getAndSet implementation in Java is as good as a volatile write (StoreLoad) so 'value' fields writes are correctly visible when value is polled from the queue.
Hi Nitsan,
DeleteAssuming this is the code you're talking about:
https://github.com/akka/akka/blob/master/akka-actor/src/main/java/akka/dispatch/AbstractNodeQueue.java
this queue implementation in Akka is a variant of the Vyukov's algorithm where we're just spinning while waiting for a "partially inserted" node to be made visible.
It has the advantage that poll() (due to peekNode) is Linearizable instead of being only Serializable (I think this is what you're saying as well), but it has the disadvantage of being Blocking instead of Lock-Free.
Notice that both implementations are correct (the one in Akka and the original one by Vyukov), but they have different progress conditions and consistency model.
Just to make it clear, in the Akka implementation, the poll() is _not_ lock-free because it may spin eternally if the thread inserting the node blocks/crashes/sleeps before setting the next of the previous node.
poll() properties:
Vyukov original code Akka
Progress Condition Lock-Free Blocking
Consistency Model Serializable Linearizable
> Linearizable instead of being only Serializable (I think this is what you're saying as well)
DeleteYes.
> in the Akka implementation, the poll() is _not_ lock-free
You are right, it's indeed blocking.
I think the post should highlight the above differences between Vyukov and Akka impls to prevent confusion.
You're right, the post is confusing on that aspect, I realized that after reading your comment. I'll have to update it to add that info... although the readers can always read our comments ;)
DeleteI know from my blog that many people don't bother with reading comments, so I would add an update to the post clarifying the point and adding a pointer to the discussion. But this is a style decision, so what do I know...
Delete