Lock-free в C++: когда оправдан, а когда стреляет в ногу

Команда переписала очередь задач с std::queue под мьютексом на самописную lock-free очередь на std::atomic. Ожидали рост пропускной способности под нагрузкой. Получили падение на 15% при 8 потоках, три недели отладки ABA-проблемы и утечку из-за неверного порядка освобождения узлов. Мьютекс вернули. Это типичная история: lock-free кажется быстрым по определению, но выигрывает в узком диапазоне сценариев, а цена ошибки в нём выше, чем где-либо ещё в прикладном коде.

Речь про C++ начиная с C++11, где появились std::atomic и модель памяти. Всё ниже опирается на стандартную модель памяти; конкретные гарантии сверяйте с разделом [atomics] актуального стандарта, а поведение compare_exchange — с документацией вашей реализации.

Что вообще значит lock-free

Термин часто используют как синоним «быстро и без мьютексов», но у него точное значение. Алгоритм lock-free, если при любом раскладе выполнения хотя бы один поток гарантированно продвигается вперёд за конечное число шагов. Это не то же самое, что wait-free (продвигается каждый поток) и не то же самое, что просто «без блокировок».

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

Lock-free — это не про скорость. Это про то, что зависший поток не роняет систему. Скорость — побочный эффект, который случается не всегда.

Три уровня, которые путают

• Lock-free — система в целом продвигается, отдельный поток может «пробуксовывать» в цикле CAS сколько угодно.
• Wait-free — каждый поток завершает операцию за ограниченное число шагов. Реализуется тяжело, почти всегда медленнее lock-free на реальной нагрузке.
• Obstruction-free — поток завершается, если ему не мешают. Самая слабая гарантия, на практике встречается редко.

Где atomic реально выигрывает

Есть сценарии, где lock-free даёт измеримый прирост и не тянет за собой сложность полноценной структуры данных.

1. Счётчики и флаги. std::atomic<int> для количества активных соединений, fetch_add для агрегатов. Здесь нет ни ABA, ни управления памятью — только одна ячейка.
2. SPSC-очередь (один писатель, один читатель) на кольцевом буфере. Это самый честный случай применения lock-free: логика простая, корректность доказуема, прирост реальный. Такие очереди лежат в основе аудиодвижков и обработчиков сетевых пакетов.
3. Флаги остановки, sequence-номера, once-инициализация. Одно значение, атомарная запись, читатели видят согласованную картину при правильном порядке памяти.

Общее у этих случаев: нет динамического управления временем жизни узлов. Как только появляется структура с указателями, которые кто-то освобождает, — начинается настоящая сложность.

Пример: SPSC-очередь на кольцевом буфере

Один поток кладёт, один забирает. Никакого CAS, только два атомарных индекса с аккуратным порядком памяти. Код рабочий, C++11 и новее.

#include <atomic>
#include <cstddef>
#include <vector>

template <typename T>
class SpscQueue {
public:
    explicit SpscQueue(std::size_t capacity)
        : buffer_(capacity), capacity_(capacity) {}

    // Вызывается только из потока-писателя
    bool push(const T& value) {
        const std::size_t head = head_.load(std::memory_order_relaxed);
        const std::size_t next = (head + 1) % capacity_;
        // Читаем хвост с acquire: видим все записи читателя
        if (next == tail_.load(std::memory_order_acquire)) {
            return false; // очередь заполнена
        }
        buffer_[head] = value;
        // release: читатель, увидев новый head, увидит и данные
        head_.store(next, std::memory_order_release);
        return true;
    }

    // Вызывается только из потока-читателя
    bool pop(T& out) {
        const std::size_t tail = tail_.load(std::memory_order_relaxed);
        if (tail == head_.load(std::memory_order_acquire)) {
            return false; // очередь пуста
        }
        out = buffer_[tail];
        tail_.store((tail + 1) % capacity_, std::memory_order_release);
        return true;
    }

private:
    std::vector<T> buffer_;
    std::size_t capacity_;
    std::atomic<std::size_t> head_{0}; // пишет только писатель
    std::atomic<std::size_t> tail_{0}; // пишет только читатель
};

Обратите внимание: head_ пишет только один поток, tail_ — только другой. Именно это делает конструкцию корректной без CAS. Как только писателей или читателей станет двое, эта очередь сломается, и потребуется совсем другой алгоритм.

Где lock-free стреляет в ногу

Многопользовательская очередь (MPMC), стек, хеш-таблица на atomic — это территория, где ошибаются даже авторы стандартных библиотек. Три проблемы, которые не видны на ревью и всплывают под нагрузкой.

ABA-проблема

Поток читает указатель A, засыпает. За это время A удаляют, память переиспользуют под новый узел с тем же адресом A. Поток просыпается, compare_exchange видит A, считает, что ничего не изменилось, — и рушит структуру. Классическое лечение — версионные указатели (tagged pointers) или отложенное освобождение памяти. Оба варианта усложняют код в разы.

Управление временем жизни

В lock-free нельзя просто вызвать delete на узле: другой поток может держать на него указатель прямо сейчас. Нужны hazard pointers, epoch-based reclamation или RCU-подобные схемы. Это отдельная подсистема, которую придётся написать, протестировать и сопровождать. Именно здесь чаще всего появляются utечки и use-after-free.

Ложное разделение кеш-линий

Два atomic-поля в одной кеш-линии (обычно 64 байта) заставляют ядра постоянно перекидывать линию туда-обратно. Результат — lock-free код, который медленнее мьютекса. Лечится выравниванием через alignas(64), но об этом нужно помнить заранее.

Сравнение подходов

Что и как мерить, прежде чем переписывать

Решение «нужен ли lock-free» принимается по замерам, а не по интуиции. Придуманных цифр здесь не будет — вместо них методика.

• Профиль под реальной параллельностью. Мьютекс проигрывает только при высокой контенции. Померьте долю времени в lock() при том числе потоков, что будет в проде, а не на вашей 4-ядерной машине.
• Пропускная способность, а не латентность одной операции. Lock-free часто выигрывает по throughput и проигрывает по худшему хвосту латентности из-за пробуксовки CAS. Смотрите оба, включая p99.
• Счётчики кеш-промахов. perf stat -e cache-misses,LLC-load-misses покажет false sharing быстрее, чем недели гадания.
• Санитайзеры. Гоняйте под ThreadSanitizer. Он ловит гонки, которые проявляются раз в миллион запусков, — а именно такие и роняют прод по ночам.

Что делать дальше

Порядок действий, который экономит недели: сначала мьютекс, потом замер под боевой параллельностью, и только если контенция реально высокая — сначала готовая библиотека, а свой lock-free код в последнюю очередь. Если дошли до своего — начните с SPSC, где корректность доказуема, и не трогайте MPMC без hazard pointers или epoch-reclamation.

Для погружения смотрите доклады Herb Sutter «atomic Weapons» по модели памяти C++ и материалы по hazard pointers (предложение std::hazard_pointer обсуждается для будущих стандартов — проверьте статус в актуальных документах комитета). Управление временем жизни узлов — отдельная большая тема, здесь она только обозначена.