Lock-free очередь в C++: разбор инцидента с потерей данных

Сервис агрегации метрик держал стабильные 40 000 сообщений в секунду на восьми ядрах, пока раз в несколько часов не терял по одному-два элемента из очереди между потоком-продюсером и потоком-консьюмером. Логи молчали, счётчики сходились по количеству enqueue, но consumer иногда получал мусорный указатель и один раз упал с SIGSEGV в free(). Очередь была самописная, lock-free, на односвязном списке с std::atomic и compare_exchange. Ниже — что именно сломалось, почему это не ловилось локально и как выглядел рабочий фикс.

Речь про C++17, GCC 12, x86-64. На x86 модель памяти сильная, и часть ошибок с memory_order там маскируется — это отдельно важно, потому что тот же код на ARM падал бы чаще и заметнее.

Что было в коде

Упрощённая версия очереди Майкла-Скотта на два потока (single producer, single consumer). Push добавлял узел в хвост, pop снимал с головы:

// C++17, GCC 12. Упрощённый SPSC-фрагмент с ошибкой
struct Node {
    int value;
    std::atomic<Node*> next{nullptr};
};

std::atomic<Node*> head;  // consumer читает отсюда
std::atomic<Node*> tail;  // producer пишет сюда

void push(int v) {
    Node* node = new Node{v};
    Node* prev = tail.load(std::memory_order_relaxed);
    prev->next.store(node, std::memory_order_relaxed);  // проблема здесь
    tail.store(node, std::memory_order_relaxed);
}

bool pop(int& out) {
    Node* first = head.load(std::memory_order_relaxed);
    Node* next = first->next.load(std::memory_order_relaxed);
    if (next == nullptr) return false;
    out = next->value;
    head.store(next, std::memory_order_relaxed);
    delete first;  // и здесь
    return true;
}

Тесты на одном ядре под ThreadSanitizer молчали: TSan видит гонку только тогда, когда потоки реально пересекаются во времени на конкретном прогоне. При SPSC на слабой нагрузке они почти не пересекались.

Первая ошибка: relaxed вместо release/acquire

Продюсер делал prev->next.store(node, relaxed), а потом публиковал хвост. Консьюмер читал next и сразу лез в next->value. С relaxed нет гарантии, что запись поля value в новом узле станет видна консьюмеру до того, как он увидит указатель на этот узел. Консьюмер мог прочитать актуальный указатель и устаревшее (или ещё неинициализированное) содержимое.

На x86 запись-запись не переупорядочивается, поэтому именно эта часть на проде почти не стреляла. Но компилятор с relaxed имеет право переставить инструкции сам — и на -O2 иногда это делал. Отсюда редкость: раз в несколько часов совпадали и нагрузка, и разложение инструкций.

Вторая ошибка: use-after-free на границе pop

Настоящий SIGSEGV в free() давал не порядок памяти, а освобождение узла, который логика делала «фиктивной головой». В классической очереди Майкла-Скотта head указывает на dummy-узел, а реальные данные лежат в next. Здесь delete first удалял узел, на который в этот момент ещё могла ссылаться другая часть кода при переинициализации пустой очереди. Классический жизненный цикл памяти в lock-free — самая частая причина падений, и решается он не atomic'ами, а схемой реклейма.

Lock-free — это не про то, чтобы убрать мьютексы. Это про то, чтобы вручную взять на себя две вещи, которые мьютекс делал за вас: порядок видимости записей и безопасное освобождение памяти. Забыли про вторую — получите segfault, а не выигрыш в latency.

Как это воспроизвели

Локально на восьмиядерном Ryzen под нагрузкой 40 000 msg/s баг не ловился часами. Что помогло:

• Запуск под ThreadSanitizer с реальной параллельностью — не один поток, а продюсер и консьюмер на разных физических ядрах, прогон 10-15 минут. TSan показал гонку данных на prev->next и на поле value.
• Сборка под AArch64 в эмуляторе — на слабой модели памяти порча value воспроизводилась в разы чаще, потому что ARM переупорядочивает записи, которые x86 сохраняет.
• AddressSanitizer поймал use-after-free в pop с трейсом до delete first.

Вывод по методике: lock-free нельзя тестировать на той же архитектуре и той же нагрузке, что в проде, и считать это проверкой. TSan обязателен, а прогон под слабой моделью памяти — единственный способ отделить «корректный код» от «кода, который случайно работает на x86».

Что было в фиксе

Порядок видимости чинится расстановкой memory_order. Продюсер публикует узел через release, консьюмер читает через acquire — это создаёт отношение happens-before между записью содержимого узла и его чтением:

void push(int v) {
    Node* node = new Node{v};
    Node* prev = tail.load(std::memory_order_relaxed);
    // release: все записи до этой строки станут видны тому,
    // кто прочитает next через acquire
    prev->next.store(node, std::memory_order_release);
    tail.store(node, std::memory_order_release);
}

bool pop(int& out) {
    Node* first = head.load(std::memory_order_relaxed);
    // acquire: после этого чтения видно всё, что producer
    // записал до соответствующего release
    Node* next = first->next.load(std::memory_order_acquire);
    if (next == nullptr) return false;
    out = next->value;  // теперь value гарантированно актуально
    head.store(next, std::memory_order_release);
    return true;
}

Освобождение памяти вынесли из горячего пути. Для SPSC достаточно схемы с dummy-узлом и отложенным удалением: консьюмер удаляет предыдущий узел, а не текущий, и никогда не трогает узел, который может быть последним. Для многопоточного случая (MPMC) сюда нужен hazard pointers или эпохальный реклейм — их вручную мы писать не стали.

Почему в итоге взяли готовое

После инцидента команда пересмотрела само решение «писать очередь руками». Сравнили варианты по цене владения, а не только по latency.

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

Где такой подход ломается дальше

• ABA-проблема. В MPMC-очереди с compare_exchange по указателю адрес может быть освобождён и переиспользован под новый узел — CAS пройдёт, хотя логически это уже другой объект. Лечится тегированными указателями или реклеймом, который не даёт переиспользовать адрес слишком рано.
• Ложное разделение (false sharing). head и tail в одной кеш-линии заставят ядра гонять линию туда-обратно. Выравнивайте по std::hardware_destructive_interference_size или вручную по 64 байта.
• Реклейм памяти. Это отдельная большая тема — hazard pointers, RCU, эпохи. Здесь мы её только обозначаем: для любого lock-free сложнее SPSC вопрос «когда безопасно удалить узел» сложнее, чем сама очередь.

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

Если у вас в проде живёт самописная lock-free структура:

1. Прогоните её под ThreadSanitizer с реальной параллельностью на разных физических ядрах, не меньше 10 минут под нагрузкой, близкой к боевой.
2. Соберите и прогоните под слабой моделью памяти (ARM), даже если прод на x86 — это отсеет код, который работает случайно.
3. Отдельно проверьте жизненный цикл узлов под AddressSanitizer: use-after-free здесь встречается чаще, чем ошибки порядка памяти.
4. Мерьте не только latency, но и то, реально ли мьютекс был узким местом. Профиль contention до отказа от блокировок — обязателен, иначе вы платите сложностью зря.

Стартовые точки для чтения — раздел про std::memory_order в cppreference и код проверенных реализаций lock-free очередей, где реклейм и порядок памяти уже разобраны.