Быстрые MPMC-очереди с bounded waiting

Иногда хочется получить очередь для нескольких производителей и потребителей, которая не захлёбывается в CAS-циклах, не создаёт лишнего шума в кэше и при этом ведёт себя предсказуемо. Именно такую схему я и хотел сделать — но важно сразу сказать: она не wait-free, хотя и остаётся быстрой и с bounded waiting.

Идея дизайна

Очередь опирается на систему ожидания по билетам: у производителей и потребителей есть свои диспетчеры, а рядом расположен набор из N ячеек кольцевого буфера. У каждой ячейки есть состояние, которое показывает, чья сейчас очередь.

СТРУКТУРА MPMC-ОЧЕРЕДИ
══════════════════════

  ПРОИЗВОДИТЕЛИ            ПОТРЕБИТЕЛИ
  ───────────────          ────────────
      ▼                         ▼
  ┌─────┐                   ┌─────┐
  │ T1  │                   │ T1  │
  │ T2  │                   │ T2  │
  │ T3  │                   │ T3  │
  │ ... │                   │ ... │
  └─────┘                   └─────┘
      │                         │
      ▼                         ▼
  ┌─────┬─────┬─────┬─────┐
  │  0  │  1  │  2  │ ... │  N ячеек
  ├─────┼─────┼─────┼─────┤
  │[D0] │[D1] │[D2] │     │  данные
  ├─────┼─────┼─────┼─────┤
  │ S0  │ S1  │ S2  │     │  состояние
  └─────┴─────┴─────┴─────┘
        ▲
        │
   индикатор показывает
   текущую очередь

Поток: взять билет ▶ дождаться своей очереди ▶ выполнить работу ▶ переключить состояние

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

Эта схема гарантирует, что для любой ячейки соблюдаются важные свойства:

• ячейка изначально пуста;
• первой к ней подходит операция производителя;
• два одинаковых типа операций подряд не вызываются.

За счёт этого производитель не пытается записать в занятую ячейку, а потребитель не пытается читать из пустой.

ПОТОК ОПЕРАЦИИ
═══════════════

  билет ▶ ожидание ▶ доступ к ячейке ▶ запись/чтение ▶ переключение

  ┌───────┐   ┌────────┐   ┌──────────┐   ┌────────────┐   ┌──────────┐
  │ ticket│ ▶ │ wait   │ ▶ │ target   │ ▶ │ data access │ ▶ │ toggle   │
  └───────┘   └────────┘   └──────────┘   └────────────┘   └──────────┘

Как это работает на практике

В реализации используются два счётчика AtomicUsize: один для производителей, другой для потребителей. Дополнительно есть два кольцевых буфера: один хранит данные, второй — состояние владения каждой ячейкой.

Тип билета кодируется в AtomicTicket: младшие 63 бита хранят номер билета или резервации, а старший бит определяет тип операции — производитель или потребитель.

Для постановки элемента в очередь производитель:

• увеличивает счётчик производителей с помощью fetch_add и получает номер резервации;
• ждёт, пока состояние нужной ячейки не совпадёт с этим номером и не укажет на очередь производителя;
• записывает значение в соответствующую ячейку данных;
• переключает бит состояния, передавая очередь потребителю.

Для извлечения элемента потребитель:

• увеличивает счётчик потребителей с помощью fetch_add и получает номер резервации;
• ждёт, пока состояние нужной ячейки не совпадёт с этим номером и не укажет на очередь потребителя;
• читает значение из кольцевого буфера;
• обновляет состояние ячейки, сдвигая номер на N и возвращая очередь производителю.

Преимущества

Без CAS-циклов и с меньшей конкуренцией за кэш. Ожидание строится на простом чтении состояния ячейки, поэтому нет постоянной борьбы в стиле compare-and-swap. При подходящей модели кэш-когерентности это снижает лишний обмен данными между ядрами.

Ограниченное ожидание. Если не считать остановки или отказа потоков, любая операция завершается за конечное время. Это означает отсутствие голодания: и производители, и потребители в итоге получат свою очередь.

На практике время ожидания зависит от положения потока в очереди и от числа активных потоков противоположного типа. Например, при N = 64 можно быстро поставить первые 64 элемента, а затем дальнейшие операции производителей будут ждать, пока потребители освободят место.

Выводы

В результате получается bounded-waiting MPMC-очередь без привычных CAS-циклов, с понятной логикой и меньшим количеством кэш-перестановок. Это не wait-free структура, но для многих реальных задач такой компромисс вполне практичен.

Если нужна строгая wait-free гарантия, придётся идти в более сложную архитектуру. Если же важны простота рассуждения, предсказуемость и хорошая производительность, этот подход выглядит очень достойно.

Ссылки

• Girls just wanna have fast MPMC queues with bounded waiting — оригинальная статья о конструкции очереди и её свойствах.