Buffering MPSC queue

[Joseph Perez]

Swap-buffer-queue : https://github.com/wyfo/swap-buffer-queue

I've designed a "bufering" MPSC queue : elements are enqueued one by one, but dequeued all at once.

The main use case it was designed for is IO buffering (especially writing). In this regard, the algormithm can be specialized to act as a shared bytes slice, allowing concurrent writings of variable size ; it can also be used as a shared `iovec` for vectored writing.

As written in its name, it works with 2 buffers, which are atomically swapped at dequeue operation. Each buffer has 2 counters, one for "reserving" a slice of the buffer, and the other for acknowledging the slice writing – this pattern is quite common, but the innovative part is that counter increment can be variable, thanks to the all-at-once dequeuing.

The algorithm has an intermediate state, when dequeue operation must wait for all "reserved" slice to be written ; the waiting happens after the buffer swap, so enqueuing can still be done on the second buffer. After a small spin loop, if the queue is still in intermediate state, dequeuing must be retried. That means that the algorithm is not purely  lock-free, because if an enqueuing thread die suddenly, dequeuing will be blocked indefinitely  – it can be recovered though, but buffer's data would be lost.

Actually, buffer doesn't return the buffer but a "RAII-guarded" reference to the buffer ; the reference must be released before the next dequeuing operation. It's thus MPSC.

A nice feature allowed by buffer swapping is that previously dequeued buffer can be resized before the next swap, so this queue can be made unbounded (there is an example in the documentation).

This queue algorithm is currently used in a database driver prototype, for connection multiplexing, and seems to work fine, even in high contention.

As I don't have a lot of experience in concurrent algorithms, any feedback would be appreciated. More importantly, I would like to ask if this in reality a well-knwon algorithm that I've just reinvented while ignoring it.

Thank you,

Joseph Perez

[Joseph Perez]

Erratum: The "reservation" counter is in fact shared for both buffers, and it also stores the index of the buffer currently used for enqueuing. Buffer swap is done with a CAS on this counter.