Lock-free: структуры без замков

Прошлый урок собрал замки: спинлок, futex, condvar. Но даже самый быстрый замок в момент конкуренции усыпляет поток, а пока один поток держит замок, остальные стоят. Сегодня уберём замок совсем. compare_exchange из урока про атомики понесёт не флаг, а целые структуры данных: соберём кольцевой буфер, по которому два потока обмениваются без единой блокировки, и свой Arc, у которого даже подсчёт ссылок обходится без замка. И честно разберём обратную сторону: где lock-free действительно выигрывает, а где это дорогая ловушка, в которую лезть не надо.

Идея

Lock-free это не «быстрее замка», а другое свойство: гарантия прогресса. У замка есть беда. Если поток захватил замок и его вытеснил планировщик (или, хуже, он упал), все ждущие стоят, пока он не вернётся. Lock-free-алгоритм этого не допускает: в любой момент хотя бы один поток продвигается, потому что блокировать друг друга нечем, замка просто нет. Строится всё на compare_exchange в цикле, том самом «прочитай, посчитай новое, попробуй записать, при неудаче повтори».

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

SPSC кольцевой буфер

Кольцевой буфер фиксированного размера: производитель пишет в позицию head, потребитель читает из tail, индексы ходят по кругу. Магия SPSC в том, что head двигает только производитель, а tail только потребитель. Драться за общий индекс некому, и весь lock-free сводится к одной паре release-acquire на каждой передаче.

pub fn try_push(&self, value: T) -> Result<(), T> {
    let head = self.head.load(Ordering::Relaxed);   // свой индекс читаем расслабленно
    let next = (head + 1) % self.slots;
    if next == self.tail.load(Ordering::Acquire) {   // чужой индекс через Acquire
        return Err(value); // буфер полон
    }
    // SAFETY: слот head пуст, и мы единственный писатель
    unsafe { *self.buffer[head].get() = Some(value); }
    self.head.store(next, Ordering::Release);        // публикуем: запись слота видна до сдвига
    Ok(())
}

Прочитай порядки памяти глазами прошлого урока про атомики. Свой индекс head производитель читает Relaxed: кроме него туда никто не пишет, синхронизировать нечего. Чужой tail он читает Acquire, чтобы увидеть, что потребитель уже освободил место. А сдвиг head он публикует Release, и это ключ: release гарантирует, что запись в слот произойдёт до того, как потребитель увидит сдвинутый индекс. Поэтому потребитель, увидевший новый head через свой Acquire, гарантированно увидит и положенное значение, а не мусор. Без этой пары был бы ровно тот баг с опережающей публикацией, что мы разбирали на флаге READY. Потребитель устроен зеркально, и весь буфер ты соберёшь в задаче ниже.

Свой Arc: подсчёт ссылок без замка

Второй пример ближе к дому. Arc из урока про потоки это тоже lock-free: его атомарный счётчик ссылок двигается без всякой блокировки. Соберём упрощённую версию и заодно увидим тонкость с порядками памяти, которую легко пропустить.

use std::ops::Deref;
use std::ptr::NonNull;
use std::sync::atomic::{fence, AtomicUsize, Ordering};

struct Inner<T> {
    count: AtomicUsize,
    value: T,
}

pub struct MyArc<T> {
    ptr: NonNull<Inner<T>>,
}

unsafe impl<T: Send + Sync> Send for MyArc<T> {}
unsafe impl<T: Send + Sync> Sync for MyArc<T> {}

impl<T> MyArc<T> {
    pub fn new(value: T) -> Self {
        let boxed = Box::new(Inner { count: AtomicUsize::new(1), value });
        Self { ptr: NonNull::from(Box::leak(boxed)) }
    }

    fn inner(&self) -> &Inner<T> {
        // SAFETY: пока жив хоть один MyArc, Inner не освобождён
        unsafe { self.ptr.as_ref() }
    }
}

impl<T> Clone for MyArc<T> {
    fn clone(&self) -> Self {
        // Просто считаем владельцев, с данными это не связано: Relaxed достаточно.
        self.inner().count.fetch_add(1, Ordering::Relaxed);
        Self { ptr: self.ptr }
    }
}

impl<T> Deref for MyArc<T> {
    type Target = T;
    fn deref(&self) -> &T {
        &self.inner().value
    }
}

impl<T> Drop for MyArc<T> {
    fn drop(&mut self) {
        // Release: всё, что мы делали с данными, должно случиться ДО возможного освобождения.
        if self.inner().count.fetch_sub(1, Ordering::Release) == 1 {
            // Мы последний. Дождёмся, пока чужие Release-уменьшения станут видны, и только потом free.
            fence(Ordering::Acquire);
            // SAFETY: счётчик дошёл до нуля, других владельцев нет
            unsafe { drop(Box::from_raw(self.ptr.as_ptr())); }
        }
    }
}

Тут три разных порядка, и каждый осмыслен. clone прибавляет счётчик Relaxed: это чистый подсчёт, как счётчик из задачи прошлого урока, с данными не связан. А вот drop сложнее. Уменьшение идёт Release, потому что перед освобождением надо опубликовать всё, что этот поток делал с данными: вдруг именно он окажется не последним, и его работу должен увидеть тот, кто освободит память. А когда счётчик дошёл до нуля, последний поток ставит барьер fence(Acquire). Зачем: release-уменьшения от всех прежних владельцев должны стать видны до того, как мы запустим деструктор и освободим память, иначе деструктор может работать с данными, которые другой поток ещё дописывал. Барьер тут отделён от конкретной операции и наводит порядок «вообще», что и нужно: синхронизироваться надо со всеми, а не с одним.

Проблема ABA

Пойдём дальше SPSC, к структурам с указателями (стек, очередь на связанных узлах), и сразу упрёмся в фирменную ловушку lock-free. compare_exchange проверяет «значение всё ещё то, что я прочитал?». Но «то же значение» не значит «ничего не менялось». Это проблема ABA: ты прочитал указатель A, отвлёкся, другой поток снял A, что-то сделал и вернул на вершину адрес A снова (например, переиспользовав освобождённый узел). Твой compare_exchange видит A, решает «всё на месте» и проходит, хотя структура под ним уже другая. Значение совпало, а смысл нет.

С ABA борются по-разному: тегированные указатели (к адресу клеят счётчик версии, и тогда A с версией 1 и A с версией 2 различимы), либо запрет на переиспользование памяти, пока кто-то может на неё смотреть. И это подводит к самой тяжёлой части lock-free.

Кто и когда освободит память

В структуре с замком всё просто: снял узел под замком, тут же освободил. В lock-free так нельзя. Ты снял узел через CAS, но другой поток мог прочитать указатель на него миллисекунду назад и вот-вот в него заглянет. Освободишь сейчас, получишь use-after-free. Это центральная проблема lock-free на указателях: безопасная рекламация памяти, то есть как понять, что узел больше никому не виден.

Готовых решений два. Рекламация по эпохам (crossbeam-epoch): снятые узлы не освобождают сразу, а откладывают, и чистят, только когда все потоки покинули эпоху, в которой узел ещё мог быть виден. Второе это hazard pointers: каждый поток публикует, на какие узлы он сейчас смотрит, и освобождать их нельзя. Оба механизма нетривиальны, и писать их руками почти всегда ошибка.

Когда lock-free выигрывает, а когда вредит

Здесь нужна честность, потому что lock-free звучит как «всегда лучше», а это не так. Выигрывает он в считанных местах: жёсткий реалтайм, где недопустимо, чтобы вытесненный под замком поток заморозил остальных; отсутствие инверсии приоритетов; иногда очень горячие очереди между фиксированными ролями (как раз SPSC).

А вот где вредит. Lock-free MPMC-структура почти всегда сложнее и нередко медленнее хорошего Mutex: атомарные CAS-циклы под высокой конкуренцией перевыполняются по многу раз, гоняя строки кэша между ядрами, и суммарно проигрывают одному короткому захвату замка. Плюс рекламация памяти добавляет накладные расходы. Правило практика: не пиши lock-free MPMC руками. Для SPSC и счётчиков (как наш Arc) ручной код оправдан, для остального бери проверенные структуры из крейта crossbeam (его очереди и стеки уже решили и ABA, и рекламацию) и всегда меряй, а не верь, что без замка автоматически быстрее.

Практика

Собери SPSC кольцевой буфер целиком: два атомарных индекса, release-acquire на каждой передаче, ноль замков. Тесты прогонят его из двух потоков и проверят, что порядок сохранён и ничего не потеряно.

Что унести из урока

Lock-free это гарантия прогресса, а не ярлык «быстро»: замка нет, поэтому вытесненный поток не морозит остальных. В простом случае это почти бесплатно: SPSC-буфер это два индекса и пара release-acquire, где release публикует запись слота раньше сдвига индекса. Свой Arc показывает всю палитру порядков разом: Relaxed на подсчёте клонов, Release на уменьшении при drop, и fence(Acquire) у последнего владельца перед освобождением. Дальше начинается тяжёлое: на указателях вылезает ABA, и появляется главная проблема, безопасная рекламация памяти, которую решают эпохи и hazard pointers. Поэтому MPMC без замка руками не пишут, берут crossbeam и меряют, а ручной lock-free оставляют для SPSC и счётчиков.

Дальше последний урок блока: спустимся ещё ниже атомиков, к самому железу. Разберём, почему атомарные операции стоят дорого, что такое строка кэша и false sharing, и чем модель памяти x86 отличается от ARM. Тогда замкнётся всё: от Send и Sync до барьеров процессора.

Домашка