Concurrency and Consistency. Non-blocking, lock-free and async. Пост №9. Wait-free структура данных в проде

Как и обещал, примеры кода с семантикой wait-free, сегодня поговорим про то что нашло применение в реальности.

🔵 SPSC (Single Producer - Single Consumer) Queue over Ring Buffer

Предложил алгоритм Leslie Lamport в статье Proving the Correctness of Multiprocess Programs.

Идея проста до безобразия - если свести проблему к состоянию когда у структуры данных 2 участника, по одному на чтение и запись то бесконечные циклы и CAS не нужны совсем. Только 2 атомика и битовая арифметика.

type SPSCQueue struct {
  buf  []int
  mask uint64

  // tail — индекс следующей записи, пишет только производитель.
  // head — индекс следующего чтения, пишет только потребитель.
  // Оба монотонно растут, реальный слот — индекс по модулю ёмкости.
  tail atomic.Uint64
  head atomic.Uint64
}

// NewSPSCQueue создаёт очередь ёмкостью capacity, которая должна быть
// степенью двойки (чтобы взятие по модулю свелось к побитовому &).
func NewSPSCQueue(capacity uint64) *SPSCQueue {
  if capacity == 0 || capacity&(capacity-1) != 0 {
    panic("capacity must be a power of two")
  }
  return &SPSCQueue{buf: make([]int, capacity), mask: capacity - 1}
}

// Push вызывается ТОЛЬКО производителем. Возвращает false, если очередь
// полна (ждать нельзя - это нарушило бы wait-free).
func (q *SPSCQueue) Push(val int) bool {
  tail := q.tail.Load()

  // Потребитель только увеличивает head, поэтому прочитанное значение
  // может лишь "устареть в нашу пользу": если места нет по этой оценке,
  // его точно не было и на момент проверки.
  if tail-q.head.Load() == uint64(len(q.buf)) {
    return false
  }

  q.buf[tail&q.mask] = val

  // Store публикует запись в слот: потребитель увидит новый tail только
  // после того, как значение уже лежит в буфере (release-семантика).
  q.tail.Store(tail + 1)
  return true
}

// Pop вызывается ТОЛЬКО потребителем. Возвращает false, если очередь пуста.
func (q *SPSCQueue) Pop() (int, bool) {
  head := q.head.Load()

  if head == q.tail.Load() {
    return 0, false
  }

  val := q.buf[head&q.mask]
  q.head.Store(head + 1)
  return val, true
}

Сниппет чтобы пощупать код

Где встречается SPSC
- Работа с аудио
- Сетевое программирование
- Трейдинг / финансы

Выводы
SPSC это алгоритм из категории просто и со вкусом. Всего 50 строк а применений нашлось большое множество. Практически на любом устройстве / программе хоть как то взаимодействующей с ОС или железом найдется место этому алгоритму. По причине того что взаимодействовать на стыке двух независимых систем (ядро-процесс, железо - драйвер) безопаснее всего без блокирующих примитивов (иначе привет дедлоки).

Пишите в комментариях встречали ли нечто подобное и какая задача была)