Проблема конкурентных правок

В 18:00 пятницы два сотрудника Figma одновременно двигают один и тот же компонент дизайна. Чья правка победит - и почему это вопрос архитектуры, а не удачи?

• Google Docs обрабатывает ~4,5 млрд правок в день - без решения проблемы concurrent edits каждый документ при совместной работе превращался бы в мусор
• Cassandra (используется в Netflix, Instagram, Discord) по умолчанию применяет LWW - при clock skew между нодами >1ms возможна потеря актуальных данных
• Knight Capital Group потеряла $440 млн за 45 минут в 2012 году из-за lost update в торговом алгоритме - отсутствие защиты от concurrent writes в критической системе

Concurrent Edits

Concurrent edit - это ситуация, когда два или более клиента изменяют одни и те же данные одновременно, не зная друг о друге. Google Docs обрабатывает ~4,5 млрд правок в день - каждая из которых потенциально конкурирует с другими.

Проблема возникает из-за сетевой задержки: клиент A отправляет изменение, клиент B тоже отправляет изменение - и оба считают, что работают с актуальной версией документа. Сервер получает два конфликтующих состояния и должен принять решение.

Concurrent edits - это не баг конкретной системы, а фундаментальное следствие теоремы CAP: если система доступна (A) и устойчива к разделению (P), то она не может гарантировать согласованность (C) в момент конкурентных правок.

• Figma: ~8 млн пользователей редактируют дизайны одновременно - конкурентные правки на уровне отдельных узлов дерева
• Notion: multi-cursor редактирование блоков - каждый блок обновляется независимо
• VS Code Live Share: совместное редактирование кода - операции на уровне символов

Lost Updates

Lost update - это когда изменение одного клиента полностью перезаписывается изменением другого клиента, и первое изменение исчезает бесследно. Это самый распространённый вид конфликта при работе с общим состоянием.

В 2012 году баг с lost update в системе Knight Capital Group привёл к потере $440 млн за 45 минут: алгоритм торгов выполнял конкурентные записи в общее состояние позиций без блокировок.

Классические решения lost update: пессимистические блокировки (lock перед чтением), оптимистический concurrency control (версионирование), атомарные операции типа INCREMENT вместо READ-MODIFY-WRITE.

1. Pessimistic lock: SELECT FOR UPDATE блокирует строку до завершения транзакции - работает, но убивает пропускную способность при высоком contention
2. Optimistic lock: читаем version=5, пишем WHERE version=5 - если кто-то изменил, получаем 0 affected rows и повторяем
3. Atomic op: вместо UPDATE SET balance=1500 пишем UPDATE SET balance=balance+500 - атомарно на уровне БД

Last-Write-Wins

Last-Write-Wins (LWW) - стратегия разрешения конфликтов: при нескольких конкурентных записях побеждает та, у которой наибольший timestamp. Это самая простая стратегия - и самая опасная.

Amazon DynamoDB использует LWW по умолчанию при включённом multi-master (Global Tables). В 2019 году Slack столкнулся с проблемой: при clock skew >50ms между дата-центрами LWW давал непредсказуемые результаты при обновлении статуса пользователей.

LWW безопасен только для идемпотентных операций с монотонно возрастающими значениями (например, последнее местоположение GPS, последний статус онлайн/оффлайн). Для аккумулирующих операций (счётчики, корзина покупок) LWW гарантированно теряет данные.

• Redis: LWW через MULTI/EXEC с проверкой версии - используется в 50%+ production Redis-инсталляций
• Cassandra: LWW по умолчанию для всех записей, Lamport clock для порядка
• Riak: LWW как одна из трёх стратегий (наряду с vector clocks и CRDT)

Типы конфликтов

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

• Write-write conflict: два клиента изменяют одно поле - требует явной стратегии (LWW, merge, reject)
• Read-write conflict: клиент читает данные, которые изменяются другим клиентом в процессе чтения - приводит к torn reads
• Phantom conflict: два клиента вставляют строки с пересекающимися диапазонами - классика при параллельной вставке в range-partitioned таблицы

Linear conflict resolution (порядок применения операций) работает только для commutative операций. Для текстовых редакторов нужна либо Operational Transformation (Google Docs), либо CRDT (Figma, Notion) - оба подхода гарантируют eventual consistency без потери правок.

Практическое правило: если операция commutative и associative (перестановочная и сочетательная) - её можно слить автоматически. Примеры: Add(x) + Add(y) = Add(y) + Add(x). Если нет - нужна OT, CRDT или пользовательский merge.

Итоги

• Concurrent edit возникает когда два клиента читают одно состояние и независимо его изменяют - сеть делает это неизбежным при любой distributed системе
• Lost update - частный случай concurrent edit: одна запись молча перезаписывает другую; решается атомарными операциями, OCC или пессимистическими блокировками
• LWW (Last-Write-Wins) разрешает конфликты по timestamp - прост в реализации, но опасен при clock skew и непригоден для аккумулирующих операций
• Тип конфликта определяет стратегию: commutative операции (Add-to-Set) можно слить без потерь, non-commutative (текстовые вставки) требуют OT или CRDT

Связанные темы

Проблема concurrent edits - точка входа в архитектуру реального времени:

• CRDT — CRDT - математически строгое решение concurrent edits для commutative операций без координирующего сервера
• Operational Transformation — OT решает concurrent edits для последовательных структур (текст, списки) через трансформацию операций с учётом контекста
• Vector Clocks — Vector clocks дают causally consistent порядок событий - замена wall-clock timestamps в LWW для устранения clock skew проблемы

Вопросы для размышления

• Если система использует LWW и clock skew между серверами составляет 500ms - какой процент записей рискует быть потерян при интенсивной concurrent нагрузке?
• Почему корзина покупок в e-commerce - классический пример, где LWW неприемлем, а счётчик просмотров страницы - наоборот, где LWW достаточен?
• При каком условии optimistic concurrency control (версионирование) превращается из решения проблемы в источник новой проблемы (retry storm)?

Связанные уроки

• db-14-mvcc