Comment by nly
2 days ago
The MPSC/MPMC structure in Aeron is wait-free with respect to producers - one producer cannot block another
There are simple node based algorithms that achieves a similar guarantee:
https://web.archive.org/web/20240928080729/https://www.1024c...
There is also a MPMC algorithm on this site very similar to the article
https://web.archive.org/web/20220524214823/https://www.1024c...
Nice to see Vyukov's MPMC queue mentioned. It's pretty neat. I have used a C implementation[1] of this in a small personal project.
[1]: https://github.com/dorjoy03/dsync/blob/master/src/mpmc_queue...
Both Vyukov queues are fast and useful in practice, but neither is even obstruction-free, let alone lock-free or wait-free.
What's important is you know the trade-offs you are making.
You can't have a bounded queue that is always non-blocking because slow consumers can block producers.
You can't have a global FIFO order + multiple producers without slow producers blocking consumers.
You can't have a global FIFO order + have have non-atomic reserve and commit without a interrupted/de-scheduled producer thread being able to block the consumer
If you want atomic commit then you lose separate reserve which means either unbounded memory or atomic fixed-size data with sentinel values, ABA problems etc.
There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
> There are trade-offs everywhere, and it's best to pick the data structure that fits your needs just like any other problem.
That part I think is most crucial. Neither "Lock-free" nor "Wait-free" are vague terms for how awesome a thing is, they're specific properties which are expensive to provide, if you need such a property it was indispensable, if you don't need it then you can likely do better without it.
4 replies →