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)

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

*Что такое "работа"?
read snapshot ==> validate ==> compute new state ==> try write
При retry повторяется всё:
Read: Снапшот устарел
Validate: На новых данных может не пройти
Compute: Результат зависит от текущего состояния
Write: Новая попытка CAS

---

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

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

Вопрос 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
        }
    }
}

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

---

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

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

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

Пример 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

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

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

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

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

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

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

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

---

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

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

На самом деле lock-free — это реализация существующих стратегий без обращения к ОС:

*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)

Читаемость: Средняя. 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)

Читаемость: Низкая при сложной логике. Блоки 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)

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

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

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

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

---

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

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

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

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

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

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

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

---

Сравнение рисков: сводная таблица

* Deadlock акторов — при синхронном ожидании ответа друг от друга.

---

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

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

---

Антипаттерны

«У нас всё на акторах»

Даже для счётчика создаём актора с mailbox.

Решение: AtomicLong.incrementAndGet() — одна инструкция CPU.

«CAS — это всегда быстрее»

При высокой конкуренции CAS-loop превращается в бесконечный retry.

Решение: Мониторьте retry rate. Если > 30% — переходите на Single Writer.

«Mutex — это медленно и стыдно»

Преждевременная оптимизация усложняет код и повышает риск ошибок.

Решение: synchronized в современных JVM оптимизирован. Начните с него, профилируйте, потом решайте.

«Напишем свою lock-free структуру»

Lock-free код сложен в написании, отладке и доказательстве корректности. Ошибки проявляются под нагрузкой через месяцы.

Решение: Используйте проверенные библиотеки: java.util.concurrent, JCTools, Disruptor.

«Локи разбросаем по методам — так гибче»

Чем больше мест с синхронизацией, тем выше риск deadlock и тем сложнее ревью.

Решение: Один лок на агрегат. Одна точка входа для изменений.

---

Итого

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

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

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

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

Всё остальное — реализации:

• Mutex, Monitor, synchronized ==> 2.1

• Actor, Channel, Event Loop ==> 2.2

• CAS, AtomicReference, STM, lock-free ==> 1

• Без синхронизации ==> 3

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

• First Win ==> livelock, starvation

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

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

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

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

Классификация полна — других веток в дереве решений нет.

Запомнить легко. Проектировать просто.

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

---

Ссылки

• The Art of Multiprocessor Programming — Herlihy, Shavit

• Java Concurrency in Practice — Brian Goetz

• The LMAX Architecture — Martin Fowler

• Erlang Processes

• Clojure STM

• CRDT Paper — Shapiro et al.

---

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

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

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

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

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

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

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

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

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

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

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

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

• Designing Data-Intensive Applications, Martin Kleppmann - знаменитая книга с кабанчиком

• Jepsen тесты распределённых систем на прочность

• CAP Theorem