Упорядочивание событий

Цели урока

• Различать partial, causal и total order и знать, что каждый из них гарантирует
• Понимать, почему физические часы недостаточны для определения порядка событий
• Знать механизмы реализации causal order (vector clocks) и total order (consensus, sequencer)
• Выбирать минимально достаточный уровень ordering для конкретной задачи

Предварительные знания

• Понимание CAP-теоремы и trade-off между consistency и availability
• Базовое знание Lamport timestamps и happens-before отношения
• Знакомство с vector clocks на уровне концепции

Amazon S3, 2008: два сервера одновременно получили разные версии объекта. Чьи данные правильные? Без формальной модели ordering - вопрос без ответа.

• **Kafka** гарантирует total order внутри partition - именно поэтому event sourcing и CQRS работают надёжно
• **Google Spanner** использует GPS и атомные часы в каждом ЦОД чтобы дать глобальный total order без centralized sequencer
• **CRDTs** (Conflict-free Replicated Data Types) работают на causal order - позволяют Google Docs работать без блокировок
• **ZooKeeper** использует Zab (Zookeeper Atomic Broadcast) для total order - координация Hadoop и Kafka кластеров
• **DynamoDB** сознательно выбрал eventual consistency для shopping cart - 99.99% uptime важнее идеального порядка операций

Лесли Лэмпорт и happens-before

В статье 1978 года "Time, Clocks, and the Ordering of Events in a Distributed System" Лэмпорт ввёл отношение happens-before (->) - основу всех современных моделей упорядочивания. Идея: вместо физического времени (которое ненадёжно) использовать причинную связь между событиями. Эта работа получила более 15 000 цитирований и стала фундаментом для vector clocks, causal consistency и CRDT.

Partial Order: не всё можно сравнить

**Amazon S3, 2008 год. Два пользователя одновременно редактируют один документ на разных серверах. Сервер A получил версию 1 в 12:00:00.001, сервер B - версию 2 в 12:00:00.002. Но чьё время точнее? Часы серверов расходятся на 50 миллисекунд. Конфликт неустраним без дополнительного соглашения.** Это и есть суть проблемы упорядочивания: параллельные события в распределённой системе не имеют объективного порядка.

Partial order (частичный порядок) - формальная модель: некоторые пары событий сравнимы (одно случилось до другого), а некоторые - нет. Несравнимые события называются **concurrent** (параллельными, независимыми).

Partial order не говорит, какое из concurrent событий было раньше. Это не баг - это особенность: в распределённой системе такого понятия объективно не существует.

Causal Order: сохрани причинность

Causal order (причинный порядок) - гарантия: если событие A повлияло на событие B (прямо или через цепочку), то каждый узел системы увидит A до B. Concurrent события (без причинной связи) могут видеться в любом порядке.

**Vector Clocks** - основной инструмент реализации causal order. Каждый узел ведёт вектор счётчиков `[t1, t2, ..., tN]` - по одному на каждый узел. При отправке сообщения узел инкрементирует свой счётчик и прикладывает весь вектор. При получении берёт поэлементный максимум.

Causal order не упорядочивает все события - только связанные причинно. Ответы Bob и Charlie на вопрос Alice упорядочены относительно вопроса, но не относительно друг друга. Это компромисс: меньше координации, чем total order, но больше гарантий, чем partial order.

Total Order и FIFO: все видят одно и то же

**Total order** - самая строгая гарантия: существует единая глобальная последовательность всех событий, и каждый узел видит её одинаково. Без total order три узла, получившие записи `x=1`, `x=2`, `x=3` в разном порядке, придут к разным финальным значениям.

**FIFO order** - более слабая, но часто достаточная гарантия: сообщения от одного отправителя приходят в порядке отправки. FIFO не упорядочивает сообщения от разных отправителей между собой.

Total order требует координации при каждой записи. Kafka решает это элегантно: total order гарантируется внутри одной partition (один leader), но не между partition. Это позволяет масштабироваться горизонтально, жертвуя global order.

Выбор уровня ordering в реальных системах

Реальные системы не выбирают между ordering-уровнями раз и навсегда - они применяют разные уровни для разных операций. Kafka даёт total order на partition, но eventual consistency между partition. DynamoDB позволяет выбирать consistency level на каждый запрос.

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

Иерархия гарантий: FIFO - Causal - Total. Каждый следующий уровень строже предыдущего и дороже. Total order всегда включает causal order. Causal order всегда включает FIFO.

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

• В мессенджере типа WhatsApp сообщения иногда приходят не в том порядке, в котором были отправлены. Какой минимальный уровень ordering нужен чтобы переписка всегда читалась логично - и какой trade-off это потребует?

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

• dist-05-vector-clocks — Vector clocks provide causal order tracking
• ds-04-clocks — Logical clocks underpin all ordering guarantees
• dist-12-consistency — Message ordering directly determines consistency model
• dist-09-raft — Raft implements total order broadcast via the log
• alg-18-topological