Real-Time Backend

Message Ordering

В распределённой системе нет машины времени. Событие, которое «случилось раньше» на одном узле, может прийти позже на другой. Lamport, vector clocks и causal ordering - инструменты для того, чтобы рассуждать о времени там, где единого времени нет.

  • Cassandra использует Lamport timestamps (client-side microseconds) для last-write-wins разрешения конфликтов - clock skew между клиентами может привести к потере свежих данных
  • DynamoDB (оригинальный Dynamo) хранит vector clock per-key и возвращает concurrent версии клиенту для semantic reconciliation вместо автоматического разрешения конфликтов
  • Kafka гарантирует FIFO ordering внутри партиции через единственного partition leader, без cross-partition ordering - это намеренный trade-off в пользу масштабируемости
  • Slack держит per-channel sequence numbers для упорядочивания сообщений и thread replies, гарантируя causal order: ответ всегда доставляется после оригинала
  • Google Spanner использует TrueTime с атомными часами и GPS для гарантии external consistency без vector clocks - стоимость ~7ms wait per commit

Ordering Problem

В распределённой системе нет единых часов. Каждый узел живёт по своему времени, и два сообщения, отправленные «одновременно», могут прийти в противоположном порядке на разных узлах. Это не баг конкретной реализации - это физическое свойство систем без общей памяти.

Slack: удалённое сообщение появляется раньше оригинала

Пользователь A пишет «привет», затем удаляет. Пользователь B получает «удаление» раньше самого сообщения - сеть доставила пакеты в обратном порядке. Slack держит sequence number на канал, чтобы клиент мог буферизировать и переупорядочить события перед показом.

Существуют три уровня гарантий порядка, каждый дороже предыдущего:

  1. **FIFO order** - сообщения от одного отправителя приходят в порядке отправки. Самый дешёвый уровень.
  2. **Causal order** - если событие B causally зависит от A, то B никогда не будет доставлено раньше A. Средний уровень.
  3. **Total order** - все узлы видят все сообщения в одинаковом порядке. Требует консенсуса, дорого.

Kafka даёт FIFO внутри партиции бесплатно - partition key фиксирует порядок для одного producer. Между партициями порядка нет. Это намеренный trade-off: total order по всему топику убил бы горизонтальное масштабирование.

Kafka-топик с 3 партициями. Producer отправляет m1 в P0, затем m2 в P1. Consumer читает обе партиции. Какое утверждение верно?

Lamport Clocks

Лесли Лэмпорт в 1978 году предложил простую идею: вместо физического времени использовать логические счётчики. Каждый узел держит монотонно растущий счётчик. При отправке сообщения счётчик инкрементируется и вкладывается в сообщение. При получении - берётся max(local, received) + 1.

Ключевое свойство: если A happened-before B (A → B), то timestamp(A) < timestamp(B). Обратное неверно: одинаковые или возрастающие timestamps не означают причинной связи.

Cassandra: last-write-wins через Lamport timestamps

Cassandra использует client-supplied timestamps (микросекунды) как Lamport clock для разрешения конфликтов. Если два узла получили разные значения для одного ключа - побеждает запись с большим timestamp. Проблема: client clock skew. Если часы клиента A спешат на 1 секунду, его «устаревшая» запись перезатрёт свежую запись клиента B.

Google Spanner решает проблему clock skew иначе: TrueTime API возвращает интервал [earliest, latest] с гарантированной погрешностью < 7ms (атомные часы + GPS). Spanner ждёт, пока интервалы не перестанут пересекаться, прежде чем закоммитить транзакцию. Это даёт внешнюю согласованность (external consistency) - то, чего Lamport clocks не могут дать.

  • **Плюс:** минимальный overhead - один uint64 на сообщение
  • **Плюс:** partial order детерминирован и прост в реализации
  • **Минус:** concurrent events неразличимы - два события с разными timestamps могут быть параллельными
  • **Минус:** нельзя определить causality по timestamps без дополнительного контекста

Узел A отправил сообщение с Lamport timestamp 10. Узел B получил его, имея локальный счётчик 15. Каким будет счётчик B после получения?

Vector Clocks

Lamport clocks не могут различить «A случилось до B» от «A и B независимы». Vector clocks решают это: каждый узел хранит вектор счётчиков - по одному на каждый узел системы. Это позволяет точно определить causality и detect concurrent events.

DynamoDB: vector clock per-key versioning

DynamoDB (в оригинальной Amazon Dynamo Paper) использует vector clocks для отслеживания версий объектов. Каждое обновление ключа добавляет запись (server, counter) к вектору версии. При конфликте (два вектора несравнимы - оба являются concurrent) DynamoDB возвращает обе версии клиенту. Клиент обязан разрешить конфликт вручную и записать merged версию. Это semantic reconciliation - система не навязывает политику разрешения конфликтов.

Проблема vector clocks - размер растёт с числом узлов. Amazon Dynamo Paper описывает оптимизацию: ограничить вектор N последними записями (clock truncation) и удалять старые. Это может потерять causality информацию, но на практике работает для большинства паттернов доступа.

  • Lamport Clock — Один uint64. Показывает partial order, но не различает concurrent от causal. O(1) overhead per message.
  • Vector Clock — Вектор из N uint64 (N = число узлов). Точно определяет causality и concurrent events. O(N) overhead per message.

Vector clock узла A: {A:3, B:2, C:1}. Vector clock узла B: {A:2, B:3, C:1}. Какое отношение между этими событиями?

Causal Order

Causal ordering - гарантия: если событие B causally зависит от A (пользователь увидел A перед отправкой B), то любой узел получит A раньше B. Это слабее total order (не требует одинакового порядка для независимых событий) и сильнее FIFO (отслеживает зависимости между разными отправителями).

Slack: threading через causal order

Когда пользователь отвечает на сообщение в треде, Slack прикрепляет sequence number исходного сообщения к ответу. Сервер гарантирует: thread reply доставляется только после parent message. Без этого клиент мог бы показать ответ без оригинала - типичный артефакт нарушения causal order.

Реализация causal broadcast через vector clocks: сообщение m с vector clock VC(m) от узла i доставляется узлу j только когда:

  1. VC(m)[i] = VC(j)[i] + 1 - это следующее сообщение от i
  2. VC(m)[k] <= VC(j)[k] для всех k != i - все зависимости уже доставлены

Causal consistency - одна из позиций в PACELC теореме. Cassandra предлагает eventual consistency по умолчанию и tunable consistency per-request. Causal consistency в Cassandra достигается через lightweight transactions (LWT) с Paxos - дорого, но иногда необходимо.

Causal order и total order - одно и то же, только total order требует больше ресурсов

Это качественно разные гарантии. Causal order упорядочивает только causally связанные события. Total order требует глобального согласования порядка даже для независимых событий.

При causal order два независимых события могут быть доставлены в разном порядке разным узлам - и это нормально, если между ними нет причинной связи. Total order запрещает это: все узлы должны видеть одинаковый порядок всех сообщений. Kafka достигает total order внутри партиции через единственного leader-брокера; Apache ZooKeeper использует ZAB (Zookeeper Atomic Broadcast) для total order записей.

Система использует causal broadcast. Узел C получил сообщение m2 с VC={A:1, B:1} от B, но ещё не получил сообщение m1 с VC={A:1, B:0} от A. Что сделает C?

Ключевые идеи

  • Физическое время ненадёжно в распределённых системах - clock skew, network delays, NTP погрешности делают «одновременность» неопределённой
  • Lamport clocks дают partial order за O(1) overhead: если A → B, то TS(A) < TS(B). Обратное неверно - нельзя определить causality только по timestamps
  • Vector clocks точно определяют causality и concurrent events за O(N) overhead - каждый узел хранит вектор счётчиков размером с количество узлов
  • Causal broadcast буферизует сообщения, пока все их зависимости не доставлены - это гарантирует causal order без total order overhead
  • Выбор гарантии - trade-off: FIFO дёшево, causal order требует буферизации и vector clocks, total order требует консенсуса (Paxos/Raft)

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

Message ordering пересекается с несколькими фундаментальными темами распределённых систем:

  • Consensus (Paxos/Raft) — Total order требует консенсуса - Raft log replication гарантирует одинаковый порядок записей на всех репликах
  • Eventual Consistency — Eventual consistent системы (Cassandra, DynamoDB) используют Lamport timestamps или vector clocks для разрешения конфликтов без координатора
  • Event Sourcing — Event log должен иметь total order для детерминированного воспроизведения состояния - поэтому event sourcing системы часто используют single writer или sequence numbers

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

  • Cassandra позволяет клиентам задавать timestamp вручную. Какие сценарии злоупотребления это открывает и как их митигировать?
  • Представьте чат-приложение. Какой уровень ordering гарантий нужен: FIFO, causal или total? Меняется ли ответ для личных сообщений vs групповых чатов?
  • DynamoDB возвращает conflicting versions клиенту. Назовите 3 разных стратегии semantic reconciliation и ситуации, где каждая уместна.

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

  • db-04-cap
Message Ordering

0

1

Войти