Concurrency and Consistency. Non-blocking, lock-free and async. Пост №10. Продвинутые wait-free очереди

В прошлом посте я рассказал про один из самых популярных и полезных вариантов очередей с семантикой wait-free. Он такой не потому что использует какие то продвинутые алгоритмы, а именно из-за гарантий отсутствия нескольких читателей и писателей. Сегодня расскажу какие еще варианты существуют но уже со стороны академии и науки.

MPMC (Multiple Producers / Multiple Consumers) Queue by Kogan and Petrank

В 2011 уважаемые товарищи Alex Kogan, Erez Petrank написали статью "Wait-free queues with multiple enqueuers and dequeuers", в ней на основе очереди Майкла-Скотта реализовали свою собственную очередь с семантикой wait-free. Чтобы достичь той самой семантики они внедрили логику приоритетов в которой быстрые участники помогают медленным. Реализовали очередь на Java, с оговорками что алгоритм из статьи будет работать с листа только на языках с GC.

Достичь Wait-Freedom авторам статьи помог не раз упомянутый мной в постах Leslie Lamport и его алгоритм пекарни (A New Solution of Dijkstra's Concurrent Programming Problem)

По перформансу - однозначно победить очередь Майкла-Скотта не удалось, но есть сценарии в которых очередь действительно показывает себя лучше. Так появился первый в мире корректный алгоритм MPMC Queue, который может быть полезен в production.

MPMC Turn Queue by Ramalhete and Correia

В 2016м году другие товарищи сели писать свою очередь, как они сами пишут "по причине того что все остальное либо очень сложное, либо очень простое, привязано к языку или GC".

Так на свет появилась статья A Wait-Free Queue with Wait-Free Memory Reclamation. Ребята придумали свой протокол консенсуса, придумали подход для работы с памятью, чтобы очередь была пригодна не только для языков с GC. Как итог - самая популярная реализация очереди неограниченного размера в данный момент.

wCQ: A Fast Wait-Free Queue with Bounded Memory Usage

В 2022м Ruslan Nikolaev и Binoy Ravindran. публикуют статью в которой предлагают вариант очереди на основе кольцевого буфера фиксированного размера (как тот что мы рассматривали в прошлой заметке). Благодаря такому дизайну работы с памятью нет вообще + ребята спроектировали механику fast / slow path.

По итогу у них получилось приблизиться по перформансу к своему же детищу - lock-free SCQ (A Scalable, Portable, and Memory-Efficient Lock-Free FIFO Queue). Что на самом деле большой успех для wait-free алгоритма.

Выводы
Этой заметкой мне хотелось показать, что Concurrency исследования это то что развивается прямо сейчас и все еще нет стандартов, чтобы можно было бы просто взять и поменять и станет резко хорошо. Все таки публикации очень свежие, а области в которых они могут полезны ограничены и очень сложны. Поэтому и в публичных источниках информацию найти сложно.

При этом попытки все таки есть:
- Parsec: Fast, Scalable, and Secure Design with Wait-Free Parallelism by Ruslan Nikolaev
- Scalable and Fault-Tolerant Storage and File System Services with Non-Blocking Synchronization for Private Clouds by Mincheol Sung, Ruslan Nikolaev, Binoy Ravindran