Happens-Before Relation

Зачем нужно знать

В одиночной системе порядок событий очевиден: всё, что происходит, происходит на одних часах одной программы. В распределённой системе этой роскоши нет. У каждой ноды свои wall-clock с расхождением до десятков миллисекунд при хорошем NTP, секунд при NTP-fail, и до минут при leap-second-баге или VM live migration. Когда ты держишь два события A и B с разных нод и хочешь спросить «что случилось раньше», ответ из physical timestamps будет в проценте случаев ложью, а в другом проценте — бессмыслицей: «A было на 0.5 мс раньше B» ничего не говорит про то, повлияло ли A на B.

Happens-before (1978, Leslie Lamport) — формальная модель причинности, не зависящая от physical clocks. Она отвечает не на вопрос «когда?», а на вопрос «было ли A причиной (потенциальной) B?». Без этой модели ты будешь либо доверять wall-clock в распределённой системе (катастрофически), либо изобретать причинность заново под каждый конкретный баг (медленно и неконсистентно).

Happens-before — это фундамент, на котором стоит почти всё в распределённых системах: ::concept{slug="lamport-clocks"} (scalar реализация), ::concept{slug="vector-clocks"} (различает causal от concurrent), ::concept{slug="hybrid-logical-clocks"} (HLC, в CockroachDB/MongoDB/Yugabyte), ::concept{slug="crdts"} (concurrent merge без conflict), causal consistency, snapshot isolation, Git DAG (commits — события, parent edges — happens-before), distributed tracing (span-ordering в OpenTelemetry), и ::concept{slug="consistency-models"} в целом.

Если ты собираешься читать DDIA Ch.5 / Ch.9, проектировать любую систему с репликацией, или дебажить race condition в multi-region setup — без happens-before никак.

Mental model

Отношение → ("happens-before") определяется индуктивно тремя правилами:

1. Program order: если A и B на одном процессе и A раньше в исходном порядке выполнения — A → B.
2. Send/receive: если A = send(msg) на одном процессе и B = receive(msg) на другом — A → B.
3. Transitivity: если A → C и C → B, то A → B.

Если ни A → B, ни B → A — A и B называют concurrent и записывают A || B.

Ключевое свойство — это partial order, не total. Не все пары событий сравнимы. Concurrent — это не «одновременно по часам», а «между ними нет ни одного пути из правил выше». На двух нодах без обмена сообщениями ВСЕ события concurrent, даже если по wall-clock одно случилось через час после другого.

Это контр-интуитивно для людей, привыкших к single-machine programming, но критично для корректности. Causal consistency обязана сохранять порядок только для тех пар, где есть →. Для concurrent пар порядок может быть любым на разных репликах — и это не баг, а математически корректное поведение.

Wall-clock дал бы total order (все пары сравнимы по числу), но врёт: physical timestamps не гарантируют, что ts(A) < ts(B) ⇒ A → B. Happens-before даёт partial order, но не врёт: если A → B, то любой causal-consistent наблюдатель увидит A до B.

Что показывает диаграмма

Три параллельных timeline'а (Process A, Process B, Process C), каждый — group с тремя последовательными events:

• Process A: A1: write x → A2: send msg1 → A3: local op
• Process B: B1: local op → B2: recv msg1 → B3: write y
• Process C: C1: write z → C2: local op

Edges — это rules происхождения, не network channels. Внутри одного процесса edges помечены po (program order, правило 1). Между процессами один edge A2 → B2 помечен msg1 (правило 2 — send/receive). Process C не имеет edges к A или B — у него нет communication, и поэтому ВСЕ его события concurrent с A и B.

ADR-001 на узле A1 фиксирует ключевое архитектурное решение: «happens-before — partial order causality, partial, не total; основа для всех логических clocks и causal consistency».

Транзитивный замыкатель этого графа даёт всё множество пар, для которых → определено. Всё остальное — concurrent.

Сценарии и что они учат

1. Causal Chain (A1 → B3) — демонстрация транзитивности. A1 → A2 (program order), A2 → B2 (send/recv), B2 → B3 (program order). По правилу 3: A1 → B3. Значит, B3 (write y) причинно зависит от A1 (write x). Любая causal-consistent система ОБЯЗАНА показать всем наблюдателям A1 до B3. Учит: «причинность строится индуктивно через цепочку send/recv и program order; transitivity делает короткие правила мощными».

2. Concurrent Events (A1 || C1) — фундаментальное ограничение partial order. A1 пишет x на процессе A. C1 пишет z на процессе C. Между A и C нет никакой коммуникации. Проверяем правила: A1 → C1? Нет пути. C1 → A1? Нет пути. ⇒ A1 || C1. Любая ordering между ними valid: реплика 1 может применить A1 перед C1, реплика 2 — наоборот, и обе правы. Учит: «concurrent — это не баг, а feature, дающая возможность CRDTs мерджить без conflict если operations commute».

3. Pitfall: wall-clock ≠ causality — production-grade ловушка. C1 имеет wall-clock 12:00

.100. A1 — 12:00.105 (на 5 мс позже). A2 (send) — 12:00.106. B2 (receive того же msg!) — 12:00.090, потому что часы B отстают на 16 мс. Если ты сортируешь по wall-clock: B2(090) < C1(100) < A1(105) < A2(106). Получаешь: B2 «раньше» A2, хотя B2 = receive(A2) — causality violated. И A1 || C1 (concurrent) получают фиктивный order. Учит: «NTP даёт ~10 мс в LAN, до 100 мс в WAN — недостаточно для ordering; нужны logical clocks; Spanner решает иначе через TrueTime интервалы + commit-wait».

Trade-offs (развёрнутые ADR)

ADR-001: Partial order, не total

Context. Нам нужна модель «было ли A причиной B» в распределённой системе. Альтернативы: (a) использовать physical wall-clock и получить total order; (b) построить partial order на основе observable причин (send/recv, program order); (c) глобальный sequencer для всех событий.

Decision. Lamport (1978): partial order через три индуктивных правила. Concurrent события — first-class concept.

Trade-off.

• Плюсы partial: не требует synchronized clocks; не врёт (если A → B, то реально A могло повлиять на B); concurrent явный — даёт возможность CRDT-merge без conflict; работает на любом размере кластера без coordination.
• Минусы partial: не отвечает на вопрос «что случилось раньше» для concurrent пар (но это честный ответ — для них «раньше» не определено); нельзя использовать для total-ordered logs без дополнительного tie-break.
• Плюсы wall-clock total: все пары сравнимы; интуитивно для разработчиков; легко индексировать.
• Минусы wall-clock total: врёт при clock skew (см. сценарий 3); concurrent события получают фиктивный order; не сохраняет causality.

Когда partial OK: всегда, когда нужна корректность распределённой системы. Это базовая модель — total order строится поверх через tie-break или consensus.

Когда нужен total order: distributed locks, leader election, LWW merge, regulatory ordering. Получается из partial через scalar Lamport clock + tie-break на node_id, либо через consensus (Raft/Paxos), либо через TrueTime (Spanner).

ADR-002: Why send/receive — единственный cross-process primitive

Context. Правило 2 говорит только про send/receive. Почему не «оба обращаются к одному файлу», «оба читают одну переменную в shared memory», «один пишет в БД, второй читает»?

Decision. Lamport ограничил cross-process causality message-passing'ом, потому что это единственный механизм, который наблюдаем в pure distributed system без shared state.

Trade-off.

• Плюсы: модель универсальна для любой message-passing системы (network, IPC, queue, log replication, gRPC, Kafka); легко формализовать.
• Минусы: не покрывает напрямую shared-state системы (shared memory, shared DB). Для них нужно либо моделировать read/write как messages, либо строить causality через application-level (например, читатель ROW V1, потом писатель ROW V2 — формально это send/recv через DB как посредник).

Применение к БД: Cassandra writeTime, BigTable cell-timestamps, version vectors в Riak — это application-level encoding happens-before через timestamps на data. Spanner делает иначе: TrueTime + commit-wait дают external consistency без message-passing causality.

ADR-003: Concurrent ≠ simultaneous

Context. Слово «concurrent» в happens-before — не «одновременно по часам». Это «между ними нет причинного пути». Два события, разделённые часом по wall-clock, могут быть concurrent, если за этот час не было ни одного сообщения между процессами.

Decision. Принять, что concurrent — чисто causal свойство, не temporal. И не путать с concurrency в multi-threaded programming.

Trade-off.

• Плюсы: математически чисто; не зависит от физики (relativity, network delays); работает в asynchronous моделях без bound на message delay.
• Минусы: контр-интуитивно при debugging; разработчики, привыкшие к «concurrent = одновременно», делают неправильные выводы; нужно явно учить эту разницу в team onboarding.

Practical implication: при write-conflict resolution в Cassandra/DynamoDB ты НЕ можешь спросить «было ли действительно одновременно». Ты можешь только спросить «есть ли causal link». Нет link — это concurrent, мерджи по бизнес-логике (CRDT, last-write-wins с явным risk acceptance, или sibling resolution).

ADR-004: Когда happens-before недостаточно

Context. Happens-before — model potential causality. Если A → B, A могло повлиять на B (информация физически могла дойти). Но не значит, что реально повлияло. И если A || B, они не были causally connected через observable пути — но могли быть связаны через hidden channel (общая БД, side channel через файл, человек-оператор).

Decision. Принять, что happens-before — модель видимой через message-passing causality. Hidden channels — отдельная категория, требующая других механизмов.

Trade-off.

• Плюсы: модель замкнута и проверяема на основе только observable events.
• Минусы: не ловит causality через hidden channels. Classic пример: client делает write в DB, потом пишет в Slack «готово». Bot читает Slack, делает read из DB — но replication lag, и bot видит старое значение. По happens-before это всё concurrent (если bot и DB не обмениваются сообщениями напрямую), но по бизнес-смыслу — causal.

Решение в проде: session tokens (read-your-writes guarantees), causal context tokens (Cassandra LWT + paxos для compare-and-set), bounded staleness reads (Spanner), external causal context (передавать version через все каналы, включая «человеческие»).

Реальные системы

Apache Cassandra — каждая cell хранит writeTime (микросекунды, по сути Lamport scalar). При read с нескольких реплик возвращается значение с max writeTime. Сознательный trade-off: LWW поверх happens-before-aware timestamps, accepting silent data loss на concurrent writes как цена operational simplicity.

Riak / Voldemort / early Dynamo — vector clocks как прямая реализация happens-before для conflict detection. При read возвращаются all sibling versions, app решает merge (shopping cart union, last-write-wins, custom logic). Использует partial order напрямую: concurrent = sibling.

Git — DAG commits — буквальная реализация happens-before. Parent edges — это →. Merge commits с несколькими parents — concurrent branches. git merge/git rebase — стратегии resolve'а concurrent updates. git log --graph визуализирует causality.

Google Spanner / TrueTime — отказ от чисто-логических clocks в пользу bounded-uncertainty physical clocks. TrueTime даёт interval [earliest, latest] с GPS+atomic clock backing. Commit-wait гарантирует external consistency, что сильнее causal: если commit A завершён до начала commit B по wall-clock у любого наблюдателя, то A → B в системе.

CockroachDB / MongoDB / YugabyteDB — Hybrid Logical Clocks (HLC): (physical, logical). Physical part ≈ wall-clock, logical bump'ится при concurrent в одну мс. Получают approximate wall-clock + happens-before guarantees за O(1) bytes.

OpenTelemetry / Jaeger / Zipkin — distributed tracing. Span timestamps дополнены parent_span_id (явный → через causality propagation в headers). Trace = DAG, where → известно из инструментации, а не выводится из timestamps.

Kafka idempotent producer + transactions — per-partition sequence number в духе Lamport scalar. Broker rejects out-of-order или duplicate sequences. Cross-partition ordering обеспечивается transactions через coordinator.

Anti-patterns

• Использовать wall-clock timestamps для ordering событий с разных нод. NTP drift = silent data loss. См. сценарий 3 на канвасе. Это самая частая и самая дорогая ошибка в распределённых системах.
• Считать, что concurrent = одновременно по часам. Concurrent — это causal property, не temporal. Два события, разделённые часом, могут быть concurrent, если за этот час не было обмена сообщениями.
• Игнорировать concurrent в LWW. «У нас timestamps монотонные — значит порядок правильный». При concurrent writes ты теряешь данные молча. Нужен либо CRDT, либо vector clocks с app-level sibling resolution, либо сознательное risk acceptance (Cassandra-style).
• Строить causality через hidden channels. «Bot читает Slack, потом читает DB — должно работать». Без явного causal context (session token, version vector) replication lag даёт stale read. По happens-before эти события concurrent — модель не виновата, виноват дизайн.
• Изобретать happens-before заново под каждый баг. Если ты добавляешь if (event_a.ts > event_b.ts) ... где-то в коде распределённой системы — стоп, читай Lamport 1978 и используй проверенные primitives (vector clocks, HLC, version vectors).
• Путать happens-before с linearizability. Happens-before — partial order, eventual consistency primitive. Linearizability — total order по real-time, требует consensus или single-writer. Happens-before — слабее.
• Думать, что A → B означает «A causes B». Это значит «A could have caused B» (информация физически могла дойти). Реальная causation требует semantic анализа.
• Игнорировать happens-before в дизайне новых протоколов. «Мы просто будем передавать timestamps». 30 лет CS-исследований уже показали, что это не работает. Используй существующие clocks (Lamport, vector, HLC) или явный consensus.

Когда НЕ использовать

• Single-node системы. Happens-before избыточен — program order даёт total order на одном процессе, тебе хватит Date.now() или autoincrement.
• Системы с TrueTime / atomic clocks. Spanner показал, что с bounded clock uncertainty можно получить external consistency напрямую через physical time + commit-wait. Happens-before remains useful intellectually, но не нужен как primitive.
• Когда нужна строгая корреляция с wall-clock (compliance, forensics, billing с regulatory requirement). Happens-before не маппится в physical time. Используй HLC (даёт approximate wall-clock) или сохраняй оба timestamp'а.
• Total order по real-time для regulatory requirement. Happens-before partial. Total order через scalar Lamport + tie-break arbitrary для concurrent — не отражает real time. Бери consensus (Raft/Paxos) с physical clock anchoring или TrueTime.
• Strongly consistent reads (linearizability). Happens-before — eventual / causal consistency primitive. Linearizability требует consensus или single-writer.
• Системы с тривиальным concurrency (low-throughput admin tools, batch jobs с single coordinator). Overhead на formal causality модель не оправдан — берёт сложность без выгоды.

Дальше читать

• Lamport (1978): «Time, Clocks, and the Ordering of Events in a Distributed System» — оригинальная статья (8 страниц), читать обязательно. Это один из самых цитируемых CS papers в истории, и впервые формулирует happens-before и Lamport clocks.
• DDIA, Ch.5 (Replication) и Ch.9 (Consistency and Consensus) — Kleppmann разбирает causal consistency, ordering guarantees, и почему happens-before нужен для понимания всего, что происходит между eventual и strong consistency.
• System Design Space: Clock synchronization.
• Martin Kleppmann talk: «Distributed Systems 4.1: Logical time» — visual intuition за 15 минут, идеальный вход.
• Mattern (1989) / Fidge (1988): vector clocks papers — расширение Lamport до detection concurrent vs causal.
• Связанные концепты: ::concept{slug="lamport-clocks"}, ::concept{slug="vector-clocks"}, ::concept{slug="hybrid-logical-clocks"}, ::concept{slug="crdts"}, ::concept{slug="consistency-models"}, ::concept{slug="cap-theorem"}, ::concept{slug="consensus-overview"}, ::concept{slug="replication"}.
• Применяется в кейсах: [CASE]twitter-system-design (timeline causal ordering), [CASE]instagram-system-design (feed merge с concurrent writes), [CASE]chat-system-design (message ordering across regions, причинность через reply chains).