Mutex, CAS, акторы, STM, CRDT, иммутабельность, MVCC, Disruptor…

Когда читаешь про многопоточность, кажется, что способов — десятки, и каждый требует отдельного изучения.

На самом деле их ровно три. Всё остальное — реализации и комбинации.

Эта статья — попытка навести порядок в голове. После неё вы сможете:

  • за 5 секунд классифицировать любой подход к конкурентности;

  • понимать, почему Erlang выбрал акторы, а Java предлагает synchronized;

  • не изобретать велосипеды и не зацикливаться на «единственно правильном» решении;

  • проектировать многопоточный код, держа в голове простую модель.

Если статья покажется вам сложной идите сразу в комментарии. Там самое интересное. Как всегда.

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

Откройте любую статью про конкурентность. Вас накроет волной:

  • Mutex, Semaphore, Monitor, synchronized

  • Atomic, CAS, Lock-free, Wait-free

  • Actor Model, CSP, Channels

  • STM, MVCC, Snapshot Isolation

  • Immutable, Persistent Data Structures

  • CRDT, Eventual Consistency

  • Disruptor, Ring Buffer, Single Writer

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

Но это иллюзия.

Если задать правильный вопрос, всё становится простым.

Правильный вопрос

Вот он:

Что происходит, когда два потока одновременно хотят изменить один объект?

Не «как устроен mutex». Не «чем CAS лучше lock». А именно: что случится при конфликте?

Ответов ровно три:

  1. Один победит, другой переделает работу (First Win + Retry) - конфликт обнаруживается и разрешается

  2. Один подождёт, пока другой закончит (Single Writer) - конфликта нет

  3. Последний затрёт первого (Last Win) - конфликт игнорируется, результат часто случайный.

Всё. Это полный список. Других вариантов не существует.

*Что такое "работа", "конфликт" и почему "переделать"?

Потому что бизнес логика / валидатор дан на стейт. А стейт изменён в промежутке между:
1 чтением,
2 вычислением нового состояния,
3 валидацией,
4 записью нового состояния.

Изменен вот почему:
State_new = f(State_old, command)
Если один поток поменял состояние, то работа второго теперь зависит от нового состояния, надо всё переделать.

Оптимист начнет работу, надеясь что его не опередят.
Пессимист подождёт

Почему их ровно три?

Логика элементарная. Два вопроса:

Вопрос 1: Разрешаем ли мы двум потокам писать одновременно?

  • Нет ==> Кто-то должен ждать ==> Single Writer (стратегия 2)

  • Да ==> Переходим ко второму вопросу

Вопрос 2: Проверяем ли мы при записи, что данные не изменились?*

  • Да ==> При конфликте кто-то проигрывает ==> First Win (стратегия 1)

  • Нет ==> Последняя запись затирает ==> Last Win (стратегия 3)

*Проверка в случае first win делается именно в момент записи, в тот же момент (атомарно). Это должна быть одна неделимая операция.

На уровне процессора (CAS): Инструкция делает проверку и замену за один такт.
Если проверять заранее (отдельным шагом), то между проверкой и записью успеет вклиниться другой поток, и данные будут испорчены.

Дерево решений:

Параллельная запись разрешена?
├── Нет ==> [2] Single Writer (ждём очереди)
└── Да ==> Проверяем конфликт?
          ├── Да ==> [1] First Win (retry/abort)
          └── Нет ==> [3] Last Win (затирание)

Других веток нет. Математически.

Стратегия 1: First Win + Retry

Суть: Потоки работают параллельно. При попытке записать — проверяем, не изменилось ли состояние. Если изменилось — проигравший переделывает.

Схема:

Поток A: read v1 ==> compute ==> try write (v1==>v2) ✓ победил
Поток B: read v1 ==> compute ==> try write (v1==>v3) ✗ конфликт ==> retry

Пример: AtomicReference

class OrderService {
    private final AtomicReference<OrderState> ref = new AtomicReference<>(initial);

    public void apply(Command cmd) {
        while (true) {
            OrderState current = ref.get();              // снапшот
            OrderState next = current.apply(cmd);        // валидация + расчёт
            
            if (ref.compareAndSet(current, next)) {      // попытка записи
                return;                                  // победили
            }
            // кто-то успел раньше ==> retry
        }
    }
}

Характеристики

Плюсы

Минусы

Высокий параллелизм

При частых конфликтах — retry

Нет ожидания блокировок

CPU тратится на пересчёт

Простая модель

Работа может быть выброшена

Стратегия 2: Single Writer

Суть: В каждый момент времени пишет только один. Остальные ждут.

Два подварианта

2.1: OS Lock

2.2: Очередь

Механизм

Mutex / synchronized

Mailbox / Queue

Кто ждёт

Потоки (спят в ОС)

Команды (лежат в очереди)

Накладные расходы

Context switch

Память под очередь

Пример

Java synchronized

Actor, Event Loop

Блокировка потока может быть реализована по-разному: mutex усыпляет поток (context switch), spinlock крутится в цикле ожидания, futex комбинирует оба подхода. Семантика одна - сериализация (строгая последовательность) доступа

Пример 2.1: synchronized

class Account {
    private long balance;
    
    public synchronized void withdraw(long amount) {
        if (balance < amount) throw new IllegalStateException();
        balance -= amount;
    }
}

Пример 2.2: Actor / Queue

class AccountActor {
    private long balance;
    private final Queue<Command> mailbox = new MpscQueue<>();
    
    // Вызывается из любых потоков
    public void send(Command cmd) {
        mailbox.offer(cmd);  // быстрая вставка
    }
    
    // Выполняется в одном потоке
    private void processLoop() {
        while (true) {
            Command cmd = mailbox.poll();
            if (cmd != null) {
                apply(cmd);  // никаких локов — мы единственный писатель
            }
        }
    }
}

Характеристики

Плюсы

Минусы

Гарантированный порядок

Ожидание в очереди

Никто не делает лишнюю работу

Точка сериализации

Простая отладка

Может стать узким местом

Стратегия 3: Last Win

Суть: Никакого контроля. Кто последний записал — тот и прав.

// Два потока, без синхронизации
obj.value = 1;  // поток A
obj.value = 2;  // поток B
// Результат: 2 (или 1 — как повезёт)

Когда это нормально

  • Логи (потеря нескольких записей не критична)

  • Метрики и счётчики (важен порядок величин, не точность)

  • Кэши с периодическим обновлением

  • Last-write-wins в распределённых системах

Характеристики

Плюсы

Минусы

Максимальная скорость

Потеря данных

Никаких накладных расходов

Нет гарантий порядка

Простота

Подходит не для всего

Большая таблица: куда что относится

Стратегия 1: First Win + Retry

Технология

Как реализует

AtomicReference / CAS

CompareAndSet

Immutable + swap

Новый объект + CAS ссылки

StampedLock (optimistic)

Штамп версии + валидация

STM (Clojure, Haskell)

Read-set + commit-time проверка

MVCC / Snapshot Isolation

Версии строк + конфликт при коммите

Optimistic Locking в ORM

Поле version + WHERE version = ?

Lock-free структуры

CAS для доступа к ячейкам

Стратегия 2: Single Writer

Технология

Подвариант

synchronized / Mutex

2.1 (OS Lock)

ReentrantLock

2.1 (OS Lock)

DB SELECT FOR UPDATE

2.1 (OS Lock)

Erlang/BEAM процессы

2.2 (Queue)

Akka/Orleans Actors

2.2 (Queue)

Go channels (single receiver)

2.2 (Queue)

Node.js Event Loop

2.2 (Queue)

Redis

2.2 (Queue)

LMAX Disruptor

2.2 (Queue)

Стратегия 3: Last Win

Технология

Применение

Запись без синхронизации

Обычно баг

High-throughput логгеры

Допускают потерю

Approximate счётчики

StatsD, метрики

Cassandra LWW

Last Write Wins policy

DNS / кэши

Последний ответ актуален

CRDT — особый случай

CRDT (Conflict-free Replicated Data Types) снимают проблему конфликта математически: операции коммутативны, порядок не важен. CRDT = данные + способы их объединения в одном флаконе, как Git Merge но с важным отличием: мерж встроен в тип данных, порядок применения не важен.

Но физически CRDT реализуются через те же стратегии:

  • CAS для локальных обновлений (стратегия 1)

  • Single Writer для репликации (стратегия 2)

Lock-free: не новая стратегия

Термин «lock-free» часто путает. Кажется, это что-то особенное.

На самом деле lock-free — это реализация существующих стратегий без обращения к ОС: AtomicReference + immutable, Bit packing* + AtomicLong, Lock-free Queue (стратегия 1 для очереди, 2.2 для обработчика).

*64 бита можно свапнуть за один такт командой процессора. Однако, очень часто требуется атомарно условно заменить две связанные переменные. Например: указатель на буфер и его длину, указатель на начало и конец данных и т. д. Для этих целей в процессорах Intel введены команды CMPXCHG (32-bit), CMPXCHG8B (64-bit) и CMPXCHG16B (x86 64).

Lock-free очередь — это «клей»:

Producers ==> [Lock-free Queue] ==> Single Writer
   (CAS)                              (no locks)

  • Producers используют стратегию 1 для вставки в очередь

  • Consumer использует стратегию 2.2 для обработки

Новых пунктов в классификации не требуется.

Риски и читаемость кода

Каждая стратегия несёт свои риски. И есть неочевидная связь: чем сложнее читать код — тем выше вероятность ошибки.

Риски стратегии 1 (First Win / CAS)

Риск

Описание

Как проявляется

Livelock

Потоки бесконечно мешают друг другу

Все делают retry, никто не продвигается

Starvation

Один поток постоянно проигрывает

«Невезучий» поток никогда не запишет

ABA-проблема

Значение вернулось к исходному

CAS успешен, но данные испорчены

Читаемость: Средняя. CAS-цикл компактен, но retry-логика с условиями усложняет понимание всех путей исполнения.

// Легко пропустить edge case
while (true) {
    State current = ref.get();
    State next = compute(current);  // Что если тут исключение?
    if (ref.compareAndSet(current, next)) return;
    // А если retry 1000 раз?
}

Риски стратегии 2.1 (OS Lock)

Риск

Описание

Как проявляется

Deadlock

Взаимная блокировка

A ждёт B, B ждёт A — оба висят вечно

Priority Inversion

Низкоприоритетный держит лок

Высокоприоритетный поток ждёт

Забытый unlock

Исключение до освобождения

Лок никогда не отпустят

Вложенные локи

Неочевидный порядок захвата

Deadlock в неожиданном месте

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

// Классический deadlock — попробуйте найти с первого взгляда
class Transfer {
    void transfer(Account a, Account b, int amount) {
        synchronized (a) {
            synchronized (b) {
                a.withdraw(amount);
                b.deposit(amount);
            }
        }
    }
}
// Поток 1: transfer(X, Y) — захватил X, ждёт Y
// Поток 2: transfer(Y, X) — захватил Y, ждёт X
// Deadlock!

Коварство: Чем больше кода между lock и unlock, тем сложнее отследить все пути. Исключение в середине — и лок завис.

Риски стратегии 2.2 (Queue / Actor)

Риск

Описание

Как проявляется

Deadlock акторов

A ждёт ответа от B, B от A

Оба актора висят на receive

Переполнение очереди

Producers быстрее consumer'а

OutOfMemory или потеря сообщений

Сложность отладки

Асинхронность

Stack trace бесполезен

Читаемость: Высокая для изолированного актора. Логика сосредоточена в одном месте, нет разбросанных локов. Но взаимодействие между акторами может быть запутанным.

%% Логика актора читается линейно
loop(State) ->
    receive
        {Command, From} ->
            NewState = handle(Command, State),
            From ! {ok, NewState},
            loop(NewState)
    end.

Риски стратегии 3 (Last Win)

Риск

Описание

Как проявляется

Lost Update

Изменения затёрты

Данные пользователя исчезли

Torn Read/Write

Частичное чтение

Прочитали половину старого, половину нового

Race Condition

Непредсказуемый результат

«Иногда работает»

Читаемость: Высокая — кода синхронизации просто нет. Но это обманчивая простота: ошибка проявится в продакшене под нагрузкой.

Связь читаемости и рисков

Правило: Чем сложнее понять код синхронизации — тем выше вероятность ошибки.

Это не просто эстетика. Это математика:

Сложность кода

Вероятность ошибки

Время обнаружения

Очевидный лок в одном месте

Низкая

Code review

Локи разбросаны по классам

Средняя

Интеграционные тесты

Вложенные локи с условиями

Высокая

Продакшен под нагрузкой

Lock-free с ручным CAS

Очень высокая

Через полгода, в 3 часа ночи

Почему акторы часто безопаснее локов

Не потому что магия. А потому что:

  1. Локальность логики. Всё состояние и вся логика — в одном файле, в одном receive-блоке.

  2. Нет разбросанных локов. Не нужно помнить порядок захвата.

  3. Явный протокол. Сообщения — это контракт, его видно.

// Плохо. Локи: разбросаны по файлам, порядок в голове не удержать

// файл OrderService.java
synchronized (lockA) {
    synchronized (lockB) { ... }    // строка 47
}

// совсем другой файл - сначала найди его! PaymentService.java  
synchronized (lockB) {
    synchronized (lockA) { ... }    // строка 89 — DEADLOCK
}

// Хорошо. Актор: вся логика в одном месте

// OrderActor.java
void onMessage(Message msg) {
    state = handle(msg, state);     // один поток, нет локов
}

Рекомендации по снижению рисков

Для стратегии 1 (CAS):

  • Используйте готовые абстракции (AtomicReference.updateAndGet)

  • Ограничивайте число retry

  • Логируйте частоту конфликтов — если > 30%, меняйте стратегию

Для стратегии 2.1 (Locks):

  • Всегда используйте try-finally или try-with-resources

  • Один лок на агрегат, не на поле

  • Документируйте порядок захвата

  • Используйте tryLock с таймаутом

// Плохо
synchronized (a) {
    synchronized (b) { ... }
}

// Лучше — фиксированный порядок
void transfer(Account a, Account b) {
    Account first = a.id < b.id ? a : b;
    Account second = a.id < b.id ? b : a;
    synchronized (first) {
        synchronized (second) { ... }
    }
}

Для стратегии 2.2 (Actors):

  • Избегайте синхронных вызовов между акторами (ask ==> deadlock)

  • Настройте backpressure для очередей

  • Используйте supervision trees (Erlang/Akka)

Для стратегии 3 (Last Win):

  • Явно документируйте, что потеря допустима

  • Используйте volatile для visibility

  • Не применяйте для бизнес-данных

Erlang/BEAM: отличный выбор, но не единственный

Привет упорному евангелисту Erlang/BEAM!

Erlang возвёл стратегию 2.2 в абсолют:

  • Всё — процессы с mailbox

  • Никакого shared state

  • Коммуникация только через сообщения

Это прекрасно работает для:

  • Телекома (изолированные сессии)

  • Чатов (пользователь = актор)

  • IoT (устройство = процесс)

Но это не серебряная пуля:

Java: все стратегии в одной коробке

Java интересна тем, что предлагает всё:

// Стратегия 1: Optimistic
AtomicReference<State> ref = new AtomicReference<>(initial);
ref.updateAndGet(state -> state.apply(cmd));

// Стратегия 2.1: OS Lock
synchronized (lock) {
    state = state.apply(cmd);
}

// Стратегия 2.2: Single Writer Queue
executor.submit(() -> state = state.apply(cmd));

// Стратегия 3: Last Win
volatile State state;
state = state.apply(cmd);

Даже synchronized внутри адаптивен: Biased Lock ==> Thin Lock ==> Fat Lock.

ООП: по умолчанию Last Win

Важное наблюдение: классическое ООП не имеет модели конкурентности.

order.setTotal(100);  // поток A
order.setTotal(200);  // поток B

Без синхронизации это стратегия 3 — Last Win.

ООП родилось в эпоху однопоточности (Simula 1967, Smalltalk 1972). Многопоточность потребовала внешних инструментов:

Шпаргалка для проектирования

  1. FIRST WIN Проигравший переделывает
    (Optimistic) ==> CAS, STM, MVCC, версии
    Риск: livelock, starvation

  2. SINGLE WRITER Один пишет, остальные ждут
    (Pessimistic) ==> 2.1 Lock (поток спит)
    Риск: deadlock, priority inversion
    ==> 2.2 Queue (команда ждёт)
    Риск: переполнение, actor deadlock

  3. LAST WIN Последний затирает
    (No control) ==> Потеря данных ОК
    Риск: lost update, race condition

Когда что выбирать

Ситуация

Стратегия

Почему

Конфликты редки

1 (First Win)

Retry почти не случается

Конфликты часты

2 (Single Writer)

Не тратим CPU на retry

Важен строгий порядок

2 (Single Writer)

FIFO гарантирован

Нужна скорость записи

1 или 3

Нет ожидания

Потеря допустима

3 (Last Win)

Зачем платить за sync?

Важна читаемость

2.2 (Queue/Actor)

Логика локализована

Итого

Фундаментальных стратегий — три:

  1. First Win — оптимистично пробуем, при конфликте retry

  2. Single Writer — сериализуем доступ (lock или queue)

  3. Last Win — не контролируем, последний затирает

У каждой стратегии свои риски:

  • First Win ==> livelock, starvation

  • OS Lock ==> deadlock, сложный код

  • Queue/Actor ==> переполнение, actor deadlock

  • Last Win ==> потеря данных

Читаемость влияет на надёжность. Сложный код синхронизации = ошибки в продакшене.

Не нужно изучать каждый фреймворк. Достаточно понять, какую из трёх стратегий он реализует — и вы уже знаете его trade-offs.

Ссылки

За пределами одного процесса. Что появляется в распределенных системах.

Всё, что описано выше — про in-memory конкурентность в одном процессе.

Когда данные уходят в сеть (БД, другой сервис), классификация остаётся той же:

  • First Win ==> Optimistic Locking (WHERE version = ?)

  • Single Writer ==> SELECT FOR UPDATE, distributed locks

  • Last Win ==> Прямая запись, LWW в eventual consistent системах

Но появляются новые проблемы:

  • Частичные отказы (запрос ушёл, ответа нет)

  • Необходимость идемпотентности

  • Распределённые транзакции (Saga, 2PC)

  • Консенсус между узлами (Paxos, Raft)

Это тема для отдельного разговора. Хорошие точки входа:

P.S.
Если железа много на все пересчёты, то оптимистическая блокировка (first win) обычно быстрее.
А ещё можно шахматной доской по голове и разбить единый стейт на шарды, уходя в eventual consistentcy