The blog post gatekeeps the definition of "queue" to require a global processing order, (not just merely global dequeue order following the FIFO principle) when the vast majority of real life queues have no such constraint whatsoever.
If you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will be the first to be assigned to a counter. If there is one counter, the second person has to wait for the first person. If there are two counters, then the second person can go to the second counter. If the second counter works faster than the first counter, then the third person will go to the second counter.
According to the blog post this violates a global processing order constraint (created by who?). The people at the second counter appear to be coming from the future from the perspective of a global processing order constraint.
This is a very strange way to look at queues, because the primary purpose of a queue is to temporarily buffer data when there is insufficient capacity to process incoming requests. Calling something broken because it fulfills its purpose is a very negative way to approach life.
As other comments note there are plenty of problems restricting queues to ordered execution. For most use cases that simply does not matter. What matters are related features like avoidance of starvation or execution bias. And those are perfectly possible to do with multiple consumers/producers.
Title feels a bit too click-baity. The article first says multi-consumer queues break global ordering (but preserves per-consumer ordering), and then proposes a data structure that completely abandons any ordering, without explaining why that’s ok. It’d be good to at least acknowledge that queues have their uses.
Also if this is really about bags, why not open with that?
Ignoring all the other problems with this article that have been pointed out around definitions, it also claims that lockless is slow anyway. Without giving literally any data.
Good news: it's not slow
Let's take rust, which has an oddly thriving ecosystem of lockless mpsc/mpmc/etc queues, and lots of benchmarks of them in lots of configurations.
The fastest ones easily do at least 30 million elements/second in most configurations. The "slowest" around 5-10.
So the fastest is doing 33ns per element and the slowest is 100ns.
Which is probably why the article offers no data. It's not actually slow. It's actually really fast when done well.
The article basically says that when you have multiple suppliers or consumers, the "order" of the queue loses meaning. It turns into an "unordered" pool of data. Therefore focus should be shifted from maintain a "queue of data" to a "bag of data".
"They come in four variants: {single,multi}-producer {single,multi}-consumer."
The article makes it sound a bit as if they were all created equal, while I think only MPSC is really used widely. The others are all kind if niche, because usually we have better solutions for the problems they are suitable for.
I did do an actual lock-free MPMC ring buffer implementation as an exercise. I used that to make blocking bounded queues using various synchronization mechanisms, mutex/condvars and eventcounts among others. The eventcount version runs about 8x faster than the mutex version.
> Acausality within consumers is the only upheld invariant: a consumer will not see any elements prior to the last element it has seen.
This is simply not true. A standard multi-consumer queue is ordered on the consumer side so long as consumers synchronize with each other. This could be as simple as one consumer setting a global flag after receiving message A and another consumer observing that flag before receiving message B. A lockless bag will not have this property.
Similarly, any of these queues have the nice property that, even if no one synchronizes anything, they’re fair: even under heavy load such that the queue never comes close to emptying, every push attempt will be fairly serviced by a pop without any other synchronization needed.
Attempting to relax either of these could be problematic, especially as a drop-in replacement of the data structure. I suspect that quite a lot of software that uses queues pushes special tokens to indicate changes of global state, and safety and correctness may be violated by reordering. For example, an MPMC system could have a producer push a special “I’m done” token when it’s all done, and the consumers could collectively count the “I’m done” tokens and assume (correctly on a standard MPMC queue) that no more messages will be in the queue once one “I’m done” per producer have been globally seen. If those tokens come out a bag too early, then a different synchronization mechanism would be needed.
The author has a point, but the global ordering of an MPMC queue is not entirely pointless. Assuming the queue marks the messages with the order, the ordering might be used at a later stage in the pipeline to reorder the processed messages and recover the total order.
Also there are implications for fairness. A queue implemented as a stack might means that messages pushed during a spike might never be processed or experience very high latency.
Finally it is actually possible to implement a decent lock free MPSC queue in top of a node-based stack: the consumer would pop all elements on one operation, then reverse the list. This N cost is amortized over N pops so it is actually not bad.
Imagine standing in line at the supermarket, or municipality, or anywhere where you stand in line.
The front of the line is near service desk 1. When it’s your turn, you have to walk to service desk 10. As you’re walking to it, service desk 1 frees up, and the person who was behind you in line walks to service desk 1. They arrive in seconds, while you’re still halfway to being served, a few meters away.
Op is pointing out that (programming) queues without locking lack a certain purity which is also lacking in real life queues.
I think the key advantage they are describing for their bag is that it allows you to claim a element then operate on that element independently. This avoids head-of-line blocking caused by things like random context switching mid-processing.
However, that can be implemented with a MPMC queue with no exotic operations with precise O(1) behavior with no size bounds. For a bag with two N-bit bit-vectors, just have two N-bit queues of indexs. Dequeue on acquire (giving you a unused index) and enqueue on release (releasing your now used index). If anybody finishes processing quickly, they release back to the queue for new processing which means there is no head-of-line blocking. Only by having all N actively processing do you wait.
I guess you also still have the tiny window on enqueue between reserving the slot and actually writing out the index where you could tear due to a perfectly sub-optimal context switch.
Possible compromise between space and time efficiency: use bytes instead of bits to mark reserved/committed slots. This wastes 7/8 of space but you can now use ordinary byte-width loads/stores instead of CAS (these are guaranteed to be atomic on both x86 and ARM). You still have false sharing of course, but it's diluted somewhat and you avoid atomic RMW overhead. The other problem of course is that you now have 8x more memory to scan for free slots, so not sure whether it's a good tradeoff; only benchmarking will tell.
13 comments
[ 4.0 ms ] story [ 26.5 ms ] threadIf you go to the the city hall and they have multiple counters, you pull a ticket with your number. There is a global order of dequeue operations. The first person to pull a ticket will be the first to be assigned to a counter. If there is one counter, the second person has to wait for the first person. If there are two counters, then the second person can go to the second counter. If the second counter works faster than the first counter, then the third person will go to the second counter.
According to the blog post this violates a global processing order constraint (created by who?). The people at the second counter appear to be coming from the future from the perspective of a global processing order constraint.
This is a very strange way to look at queues, because the primary purpose of a queue is to temporarily buffer data when there is insufficient capacity to process incoming requests. Calling something broken because it fulfills its purpose is a very negative way to approach life.
> Lockless queues are slow
That particular implementation of a lockless queue may be slow, but that is not globally true for lockless queues. There are variants, for example BBQ, https://www.usenix.org/conference/atc22/presentation/wang-ji..., that have great performance.
Also if this is really about bags, why not open with that?
Good news: it's not slow
Let's take rust, which has an oddly thriving ecosystem of lockless mpsc/mpmc/etc queues, and lots of benchmarks of them in lots of configurations.
The fastest ones easily do at least 30 million elements/second in most configurations. The "slowest" around 5-10.
So the fastest is doing 33ns per element and the slowest is 100ns.
Which is probably why the article offers no data. It's not actually slow. It's actually really fast when done well.
The article basically says that when you have multiple suppliers or consumers, the "order" of the queue loses meaning. It turns into an "unordered" pool of data. Therefore focus should be shifted from maintain a "queue of data" to a "bag of data".
The article makes it sound a bit as if they were all created equal, while I think only MPSC is really used widely. The others are all kind if niche, because usually we have better solutions for the problems they are suitable for.
This is simply not true. A standard multi-consumer queue is ordered on the consumer side so long as consumers synchronize with each other. This could be as simple as one consumer setting a global flag after receiving message A and another consumer observing that flag before receiving message B. A lockless bag will not have this property.
Similarly, any of these queues have the nice property that, even if no one synchronizes anything, they’re fair: even under heavy load such that the queue never comes close to emptying, every push attempt will be fairly serviced by a pop without any other synchronization needed.
Attempting to relax either of these could be problematic, especially as a drop-in replacement of the data structure. I suspect that quite a lot of software that uses queues pushes special tokens to indicate changes of global state, and safety and correctness may be violated by reordering. For example, an MPMC system could have a producer push a special “I’m done” token when it’s all done, and the consumers could collectively count the “I’m done” tokens and assume (correctly on a standard MPMC queue) that no more messages will be in the queue once one “I’m done” per producer have been globally seen. If those tokens come out a bag too early, then a different synchronization mechanism would be needed.
Also there are implications for fairness. A queue implemented as a stack might means that messages pushed during a spike might never be processed or experience very high latency.
Finally it is actually possible to implement a decent lock free MPSC queue in top of a node-based stack: the consumer would pop all elements on one operation, then reverse the list. This N cost is amortized over N pops so it is actually not bad.
The front of the line is near service desk 1. When it’s your turn, you have to walk to service desk 10. As you’re walking to it, service desk 1 frees up, and the person who was behind you in line walks to service desk 1. They arrive in seconds, while you’re still halfway to being served, a few meters away.
Op is pointing out that (programming) queues without locking lack a certain purity which is also lacking in real life queues.
However, that can be implemented with a MPMC queue with no exotic operations with precise O(1) behavior with no size bounds. For a bag with two N-bit bit-vectors, just have two N-bit queues of indexs. Dequeue on acquire (giving you a unused index) and enqueue on release (releasing your now used index). If anybody finishes processing quickly, they release back to the queue for new processing which means there is no head-of-line blocking. Only by having all N actively processing do you wait.
I guess you also still have the tiny window on enqueue between reserving the slot and actually writing out the index where you could tear due to a perfectly sub-optimal context switch.