«Блокировки — это goto конкурентного программирования», — Морис Херлихи

Оглавление

Глава 1: Разрыв в производительности

Глава 2: Иерархия памяти

Глава 3: Бенчмаркинг и профилирование

Глава 4: Массивы и локальность кэша

Глава 5: Связанные списки — убийцы кэша

Глава 6: Стеки и очереди

Глава 7: Хэш-таблицы и конфликты кэша

Глава 8: Динамические массивы и управление памятью

Глава 9: Двоичные деревья поиска

Глава 10: B-деревья и деревья, эффективно использующие кэш

Глава 11: Префиксные деревья и базисные деревья

Глава 12: Кучи и очереди с приоритетом

Глава 13: Структуры данных без блокировок

Проблема 60%

Наша система логгинга тратила 60% своего времени на ожидание снятия блокировок. Не на выполнение полезной работы, только на одно ожидание.

Восемь ядер, пытавшихся записывать сообщения логов, имели общий кольцевой буфер. Реализация была простой: буфер защищался мьютексом. При высокой нагрузке, когда все ядра записывали логи одновременно, профилировщик демонстрировал ужасный паттерн: 60% тактов CPU тратилось на операции с мьютексом.

Пропускная способность: 850 тысяч сообщений в секунду. В восьмиядерной системе она должна быть гораздо выше.

«Можно ли улучшить ситуацию, отказавшись от блокировок?», — спросил меня мой менеджер во время ревью производительности.

Этот вопрос привёл к полной смене архитектуры. Простое решение на основе мьютекса выглядело так:

typedef struct {
    char buffer[LOG_SIZE];
    int head;
    int tail;
    pthread_mutex_t lock;
} log_buffer_t;

void log_write(log_buffer_t *log, const char *msg) {
    pthread_mutex_lock(&log->lock);
    // Запись сообщения в буфер
    int next = (log->tail + 1) % LOG_SIZE;
    strcpy(&log->buffer[log->tail], msg);
    log->tail = next;
    pthread_mutex_unlock(&log->lock);
}

Простое, корректное... и медленное.

При большой нагрузке (одновременном логгинге всех восьми ядер) система тратила 60% своего времени на ожидание снятия блокировок:

$ perf stat -e cycles,instructions,cache-misses ./logger_mutex
  Performance counter stats:
    8,500,000,000 cycles
    2,100,000,000 instructions
       45,000,000 cache-misses
       
Lock contention: 60% of cycles spent in mutex operations
Throughput: 850,000 messages/second

Я реализовал кольцевой буфер без блокировок на основе атомарных операций. Результаты оказались такими:

$ perf stat -e cycles,instructions,cache-misses ./logger_lockfree
  Performance counter stats:
    3,200,000,000 cycles
    2,400,000,000 instructions
       12,000,000 cache-misses
       
Lock contention: 0%
Throughput: 2,400,000 messages/second

В 2,8 раза быстрее с нулевыми конфликтами блокировок. Однако код стал гораздо сложнее.

В этой главе мы поговорим о том, когда структуры данных без блокировок оправдывают свою сложность.

Что нам рассказывают учебники

Нам обещают, что структуры данных без блокировок:

• Не имеют блокировок: потокам не нужно ждать снятия блокировок

• Лучше масштабируются: производительность растёт с увеличением количества ядер

• Не имеют взаимных блокировок: без блокировок не получится и взаимных блокировок

• Гарантируют прогресс: по крайней мере, один поток всегда имеет прогресс

Благодаря такой рекламе из учебников они как будто идеально подходят для многоядерных систем.

Проверка реальностью

Программирование без блокировок — это сложная задача. Вот, на что не делают упор учебники:

1. Сложности порядка работы с памятью

В современных CPU порядок операций с памятью можно менять. Рассмотрим этот «простой» флаг без блокировки:

// Поток 1
data = 42;
ready = 1;  // Сигнализирует о том, что данные готовы

// Поток 2
if (ready) {
    use(data);  // Возможно, видит старое значение данных!
}

Проблема: CPU может изменить порядок записи в Потоке 1, поэтому Поток 2 увидит ready = 1 до data = 42.

Решение: барьеры памяти (fence):

// Поток 1
data = 42;
__atomic_store_n(&ready, 1, __ATOMIC_RELEASE);  // Снимаем барьер

// Поток 2
if (__atomic_load_n(&ready, __ATOMIC_ACQUIRE)) {  // Ставим барьер
    use(data);  // Теперь поток гарантированно увидит data = 42
}

2. Проблема ABA

У классического стека без блокировок есть малозаметный баг:

typedef struct node {
    int value;
    struct node *next;
} node_t;

node_t *top;  // Вершина стека

void push(int value) {
    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = value;
    do {
        new_node->next = top;
    } while (!__atomic_compare_exchange_n(&top, &new_node->next, new_node,
                                          0, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
}

Проблема ABA:

1. Поток 1 считывает top = A

2. Поток 2 извлекает A, извлекает B, снова записывает A (на вершине снова A)

3. Операция сравнения с обменом (CAS) Потока 1 завершается успешно (на вершине по-прежнему A), но стек повреждён!

Решение: использовать тегированные указатели или указатели опасности (сложно!).

3. Пинг-понг линий кэша

Отсутствие блокировок не означает удобство для кэша. Рассмотрим счётчик без блокировок:

atomic_int counter = 0;

// Все восемь потоков выполняют инкремент
__atomic_fetch_add(&counter, 1, __ATOMIC_SEQ_CST);

Каждый инкремент заставляет линию кэша перескакивать между ядрами:

Ядро 0: считывание счётчика (промах кэша)
Ядро 0: инкремент, запись обратно
Ядро 1: считывание счётчика (промах кэша - инвалидирован Ядром 0)
Ядро 1: инкремент, запись обратно
Ядро 2: считывание счётчика (промах кэша - инвалидирован Ядром 1)
...

Результат: при сильных конфликтах хуже, чем мьютекс!

Я измерил это в нашей системе логгинга:

8 ядер, атомарный счётчик:
  Промахи кэша: 45 миллионов (столько же, сколько и с мьютексом!)
  Пропускная способность: 900 тысяч операций/с (чуть лучше, чем с мьютексом)

8 ядер, счётчики для каждого ядра (не общий):
  Промахи кэша: 2 миллиона
  Пропускная способность: 6,5 миллиона операций/с

Вывод: по возможности следует избегать общих атомарных переменных между ядрами.

Кольцевой буфер без блокировок: практический пример

Позвольте показать, как я реализовал кольцевой буфер для нашей системы логгинга.

Архитектура

Важнейшее решение: отдельные индексы чтения и записи, использование атомарных операций только для обновлений индексов.

typedef struct {
    char buffer[LOG_SIZE];
    atomic_int head;  // Индекс чтения
    atomic_int tail;  // Индекс записи
} lockfree_log_t;

bool log_write(lockfree_log_t *log, const char *msg, int len) {
    int current_tail, next_tail, current_head;

    do {
        current_tail = __atomic_load_n(&log->tail, __ATOMIC_ACQUIRE);
        next_tail = (current_tail + len) % LOG_SIZE;
        current_head = __atomic_load_n(&log->head, __ATOMIC_ACQUIRE);

        // Проверка буфера на заполненность
        if (next_tail == current_head) {
            return false;  // Буфер заполнен
        }

    } while (!__atomic_compare_exchange_n(&log->tail, &current_tail, next_tail,
                                          0, __ATOMIC_RELEASE, __ATOMIC_ACQUIRE));

    // Теперь мы владеем диапазоном [current_tail, next_tail)
    memcpy(&log->buffer[current_tail], msg, len);

    return true;
}

Почему это работает

1. Операция CAS с хвостом: затребовать диапазон может только один поток

2. Отсутствие блокировок данных: после получения диапазона запись выполняется без конфликтов

3. Порядок операций с памятью: ACQUIRE/RELEASE обеспечивает видимость

Бенчмарк

Я сравнил три реализации:

Тест: 8 ядер, 10 миллионов сообщений логов

На основе мьютекса:
  Такты: 8,5 миллиарда
  Промахи кэша: 45 миллионов
  Пропускная способность: 850 тысяч сообщений/с
  Конфликты блокировок: 60%

На основе спин-блокировки:
  Такты: 7,2 миллиарда
  Промахи кэша: 52 миллиона (хуже!)
  Пропускная способность: 1,1 миллиона сообщений/с
  Конфликты блокировок: 45%

Без блокировок (атомарные CAS):
  Такты: 3,2 миллиарда
  Промахи кэша: 12 миллиона
  Пропускная способность: 2,4 миллиона сообщений/с
  Конфликты блокировок: 0%

Версия без блокировок оказалась в 2,8 раз быстрее, чем версия с мьютексом, и в 2,2 раза быстрее, чем со спин-блокировкой.

Почему:

• Отсутствие системных вызовов (мьютекс использует фьютекс)

• Отсутствие циклов (спин-блокировка тратит такты)

• Меньше трафика когерентности кэша (атомарны только индексы)

Когда разумно не пользоваться блокировками

Реализовав множество структур данных без блокировок, я понял, когда они оправдывают свою сложность.

1. Высокая конфликтность, короткие критические части

Если потоки постоянно конфликтуют за один ресурс, а работа внутри него выполняется быстро (всего несколько команд), то отсутствие блокировок может быть выгодным.

Пример: наша система логгинга

• Высокая конфликтность: 8 ядер выполняют логгинг одновременно

• Короткие критические части: просто обновление индекса

• Результат: ускорение в 2,8 раза

2. Системы реального времени

В системах с жёстким реальным временем невозможно допускать инверсию приоритетов (поток с низким приоритетом удерживает блокировку, препятствуя потоку с высоким приоритетом).

Структуры без блокировок обеспечивают гарантии отсутствия ожидания и отсутствия блокировок.

Пример: обработчики прерываний

• Невозможность блокировки контекста прерывания

• Запросы без блокировок обеспечивают возможность связи прерывание → поток

• Используется в кольцевых буферах ядра Linux

3. Нагрузки с большой долей операций чтения

Если количество операций чтения сильно превышает количество операций записи, то RCU (Read-Copy-Update) может полностью устранить блокировки на стороне чтения.

Пример: RCU ядра Linux

• Читатели: без блокировок, без атомарных операций, только барьеры памяти

• Писатели: редки, используют синхронизацию

• Результат: миллионы операций чтения в секунду с нулевыми конфликтами

4. Когда НЕ использовать структуры данных без блокировки

Низкая конфликтность: если потоки редко конфликтуют, мьютекс проще и имеет такую же скорость.

Тест: 2 ядра, низкая конфликтность
  Мьютекс: 1,2 миллиона операций/с
  Без блокировки: 1,3 миллиона операций/с (всего на 8% быстрее, не оправдывает повышения сложности)

Сложные операции: если критическая часть велика (много команд), структуры данных без блокировок становятся крайне сложными.

Отладка: баги с отсутствием блокировок крайне сложно воссоздавать и отлаживать. Если доказанной проблемы с производительностью нет, используйте блокировки.

Пример из реального мира: переменные ядра Linux для каждого CPU

Чтобы не использовать атомарные операции, в ядре Linux применяется хитрый трюк: переменные каждого CPU.

Вместо одного общего счётчика:

atomic_int global_counter;  // Общий счётчик, приводящий к пинг-понгу кэша

применяется по одному счётчику на каждый CPU:

DEFINE_PER_CPU(int, local_counter);  // По одному на CPU, без общего счётчика

void increment_counter(void) {
    int cpu = smp_processor_id();
    per_cpu(local_counter, cpu)++;  // Атомарность не нужна!
}

int read_total(void) {
    int total = 0;
    for_each_possible_cpu(cpu) {
        total += per_cpu(local_counter, cpu);
    }
    return total;
}

Почему это работает:

• У каждого CPU есть собственная линия кэша

• Отсутствие трафика когерентности кэша

• Операции чтения редки (только когда нужна общая сумма)

Я использовал этот паттерн в нашей системе логгинга для статистики:

По одному счётчику на CPU (сообщения логируются для каждого ядра):
  Промахи кэша: 0 (у каждого ядра есть собственная линия кэша)
  Производительность: 8 миллионов инкрементов/с (8 ядер × 1 миллион на каждое)

Общий атомарный счётчик:
  Промахи кэша: 45 миллионов
  Производительность: 900 тысяч инкрементов/с

Ускорение в 8,9 раза благодаря отсутствию общего счётчика!

Порядок операций с памятью RISC-V

RISC-V имеет relaxed-модель памяти (RVWMO - RISC-V Weak Memory Ordering). Из-за этого ему нужны явно задаваемые fence.

Команды fence

# Полный fence (для всех операций с памятью)
fence rw, rw

# Fence получения (загрузка-загрузка, загрузка-хранение)
fence r, rw

# Fence освобождения (загрузка-хранение, хранение-хранение)
fence rw, w

Атомарные операции C11 на RISC-V

GCC сопоставляет атомарные операции C11 с командами RISC-V:

// __ATOMIC_ACQUIRE
__atomic_load_n(&x, __ATOMIC_ACQUIRE);

Это компилируется в следующий код:

ld   a0, 0(a1)      # Загрузка
fence r, rw         # Fence получения

// __ATOMIC_RELEASE
__atomic_store_n(&x, 42, __ATOMIC_RELEASE);

Компилируется в:

fence rw, w         # Fence освобождения
sd   a0, 0(a1)      # Хранение

Затраты на fence

Fence не бесплатны. Я измерил оверхед:

Тест: 1 миллион атомарных загрузок (RISC-V U74 @ 1.2 GHz)

Relaxed (без fence):
  Такты: 1,2 миллиона (1 такт на загрузку)

Получение (fence r, rw):
  Такты: 8,5 миллиона (8,5 тактов на загрузку)

Последовательная (fence rw, rw):
  Такты: 12,3 миллиона (12,3 такта на загрузку)

Вывод: используйте корректную самый слабый порядок операций с памятью. Не выбирайте по умолчанию __ATOMIC_SEQ_CST.

Подведём итог

Проблема 60 процентов была решена. Кольцевой буфер без блокировок увеличил производительность с 850 тысяч до 2,4 миллиона сообщений в секунду (ускорение в 2,8 раза). Конфликты блокировок снизились с 60% до нуля. Однако код стал существенно сложнее, он требует большого внимания к порядку операций с памятью и проблеме ABA.

Ключевые наблюдения:

1. Отсутствие блокировок не всегда быстрее. В частях кода с малым количеством конфликтов или сложным критичным кодом мьютексы проще и имеют такую же скорость.

2. Необходимо внимание к порядку операций с памятью. Для обеспечения видимости между ядрами нужны барьеры ACQUIRE/RELEASE. Из-за relaxed-модели памяти RISC-V они должны быть явными.

3. Важная когерентность кэша. Атомарные операции приводят к пинг-понгу линий кэша. По возможности избегайте общих атомарных переменных между ядрами.

4. Проблема ABA. Чтобы избежать повреждений, стекам и очередям без блокировок нужны тегированные указатели или указатели опасности.

5. Наличие переменных для каждого CPU позволяет устранить конфликты. Если можно разбить данные на CPU, то можно полностью избежать атомарных операций. Часто это оказывается в 5-10 быстрее, чем общие атомарные операции.

Показатели нашей системы логгинга:

• Мьютекс: 850 тысяч сообщений/с, конфликты блокировок 60%

• Без блокировок: 2,4 миллиона сообщений/с, 0% конфликтов

• Статистика для каждого CPU: 8 миллионов инкрементов/с (при общем атомарном счётчике 900 тысяч)

Структуры данных без блокировок — мощный инструмент, но использовать его следует только тогда, когда при профилировании оказывается, что реальным узким местом стали конфликты блокировок. Такая система имеет высокие затраты на сложность.

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