Lamport Clocks

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

Wall-clock врёт. NTP даёт ±10–100 мс расхождения между узлами в одном датацентре, leap second может откатить часы на секунду назад, VM-пауза при live migration «съедает» десятки секунд для гостя. Если два write пришли «одновременно» с timestamps 12:00:00.123 и 12:00:00.124, ты не знаешь, что случилось раньше: возможно, у второго узла часы отстают, и реально его событие было первым.

Lamport clocks (1978) решают это без всяких physical clocks, NTP и TrueTime: дают каждому событию логический timestamp такой, что если A причинно предшествует B (A → B), то ts(A) < ts(B). Это база, на которой стоят: Cassandra writeTime для LWW, BigTable cell-timestamps, Kafka idempotent producer sequence numbers, optimistic concurrency control в DynamoDB/etcd/ZooKeeper, Percolator в pre-TrueTime Spanner, упорядочивание cross-service traces в OpenTelemetry.

Без понимания Lamport ты будешь либо изобретать его заново (плохо), либо доверять wall-clock в распределённой системе (катастрофически плохо: data loss, разъезжающиеся реплики, race conditions, которые «иногда» теряют деньги).

См. также ::concept{slug="happens-before"} — формализация causality, которую Lamport реализует, и ::concept{slug="vector-clocks"} — расширение, различающее concurrent от causal.

Mental model

Каждая нода держит локальный целочисленный счётчик. Три правила:

1. Local event: c++
2. Send msg: c++; piggyback c в payload
3. Receive msg: c = max(c, msg.ts) + 1

Этим простым правилом сохраняется partial order: всё, что причинно следовало за другим событием, получит больший timestamp. Ключевое слово — partial. Lamport НЕ говорит «A было раньше B по wall-clock». Он говорит «если A → B, то ts(A) < ts(B)». Обратное не работает: два события с разными timestamps могут быть concurrent — никакого причинного пути между ними нет, а ts всё равно различаются.

Чтобы получить total order (нужен для LWW, distributed locks), добавляем tie-break на уникальный node_id:

A < B  ⟺  (ts(A), node(A)) < (ts(B), node(B))   lex order

Этот tie-break — arbitrary: он не отражает реального physical порядка для concurrent событий, но даёт детерминированный и согласованный на всех репликах результат без coordination. Все реплики, видя одну и ту же пару (ts, node_id), приходят к одному winner'у.

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

Три ноды (node-a, node-b, node-c) с initial counter c=0. Между ними физические TCP-каналы для сообщений. Каждая нода — это process с иконкой server и видимым счётчиком в label. ADR-001 на node-a фиксирует ключевое архитектурное решение: «scalar counter per node + три правила evolve».

Edges — это физические каналы, не направления данных. Анимация в FlowBuilder идёт по этим edges в обе стороны (reverse animation), демонстрируя, что Lamport — это правило локального state'а, а не сетевой протокол.

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

1. Single Node Counter — базовый случай: одна нода, последовательные local events. Counter монотонно растёт 0 → 1 → 2 → 3. Учит: «без коммуникации между узлами Lamport вырождается в обычный счётчик».

2. Receive Jumps to max+1 — самое важное правило. node-a с c=5 отправляет сообщение на node-b (где c=2). node-b делает c = max(2, 5) + 1 = 6. Учит: «receive не просто инкрементит, а синхронизируется с отправителем». Именно это правило гарантирует, что ts(send) < ts(receive) всегда.

3. Causal vs Concurrent — фундаментальное ограничение. На канвасе два независимых события: node-a сделал local event с ts=3, потом отправил на node-b (ts=5, это causal: 3 → 5), а node-c независимо имел свои события ts=3 и ts=4 (без коммуникации с A). Numeric comparison 3 < 5 истинно в обоих случаях, но смысл разный: в первом случае есть causal link, во втором — concurrent. Lamport не различает. Этот сценарий — мотивация для vector clocks.

4. LWW в Cassandra (lost write) — production-grade пример. Два клиента concurrent пишут разные значения на разные реплики (x=5, ts=10 и x=7, ts=12). Replication распространяет оба write. LWW-rule: побеждает highest ts → x=7. Запись x=5 silently overwritten — никакого warning, никакого conflict marker, данные просто потеряны. Учит: «LWW поверх Lamport — это сознательный trade-off в пользу простоты ценой потенциальной потери данных, и Cassandra его приняла».

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

ADR-001: Lamport как scalar counter, не как vector

Context. Нам нужна causality между событиями в распределённой системе без physical clocks. Альтернатив две: scalar (Lamport, одно число per ноду) или vector (Mattern/Fidge, массив из N чисел, по одному на каждую ноду в кластере).

Decision. Используем scalar counter.

Trade-off.

• Плюсы scalar: O(1) bytes overhead per message; простая модель (один int); легко serialize; работает на любом размере кластера без membership changes.
• Минусы scalar: теряем способность различать concurrent от causal. ts(A) < ts(B) не означает A → B, может быть A || B. Это приводит к lost updates при LWW merge.
• Плюсы vector: различает concurrent от causal точно; обнаруживает conflict для app-level resolution (Riak siblings, Dynamo causal context).
• Минусы vector: O(N) bytes per message — растёт с размером кластера; нужно обрабатывать membership changes (нода ушла → её координата устаревает); сложнее compactify.

Когда scalar OK: high-throughput системы, где LWW data loss приемлем (analytics, кеши, social counters, lossy metrics). Cassandra осознанно выбрала scalar+LWW: «we accept potential data loss for operational simplicity at scale».

Когда нужен vector: shopping carts, collaborative editing, конфигурация, любые domain'ы, где silent overwrite концепции данных недопустим. Riak Dynamo+vector clocks делает sibling reconciliation на app-уровне.

ADR-002: Tie-break на node_id для total order

Context. Lamport даёт partial order. Distributed locks, LWW merge, leader election требуют total order — детерминированный результат «кто победил» при одинаковых timestamps.

Decision. Лексикографический tie-break: (ts, node_id). Уникальный node_id гарантирует, что никакие два события не могут быть полностью равны.

Trade-off.

• Плюсы: детерминированный winner без coordination; все реплики приходят к одинаковому результату, видя одну пару (ts, node_id).
• Минусы: arbitrary — не отражает реального физического порядка; узлы с «меньшим» node_id систематически выигрывают tie-break'и (statistical unfairness при concurrent writes на разные ноды).

Альтернативы: broadcast + consensus для каждого conflict (Paxos round) — корректно, но дорого (медленнее на orders of magnitude). Vector clocks + app resolution — корректно, но требует понимания domain'а.

ADR-003: Monotonic timestamp generator на клиенте

Context. Если ts берётся напрямую из Date.now(), NTP backwards jump (resync, leap second) может откатить ts назад. Тогда write, сделанный «позже», получит меньший ts и проиграет в LWW write'у, сделанному «раньше». Lost write через clock skew.

Decision. Cassandra Java/Python драйверы используют max(local_wall_clock, last_emitted_ts + 1) — гарантируют монотонность в рамках клиента.

Trade-off.

• Плюсы: locally монотонно даже при NTP откате; не требует server coordination.
• Минусы: не помогает при concurrent writes от разных клиентов с расходящимися часами; ts «забегает вперёд» относительно wall-clock, что путает debugging.

Антипаттерн: использовать сырой wall-clock без monotonicity guard в любой LWW-системе. Один NTP jump = silent data loss.

ADR-004: Когда не Lamport, а HLC

Context. Lamport timestamp оторван от physical time. Это значит, что нельзя задать вопрос «дай все события за последние 5 минут» — у тебя нет mapping от ts к wall-clock.

Decision. Если нужна привязка к wall-clock для query / debugging, использовать Hybrid Logical Clocks (::concept{slug="hybrid-logical-clocks"}): (physical, logical) где physical ≈ wall-clock, а logical bump'ится при concurrent events в той же миллисекунде.

Trade-off. HLC даёт «approximate wall-clock» + Lamport-style causality за O(1) bytes. Используется в CockroachDB, MongoDB, YugabyteDB. Минус: чуть сложнее в реализации и debugging ((t, l) vs scalar).

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

Apache Cassandra — каждая cell хранит writeTime (микросекунды). При read с нескольких реплик возвращается значение с max writeTime. Default — wall-clock с клиента, но Java/Python drivers умеют monotonic timestamp generator. Tie-break внутри cluster по replica_id. Сознательный trade-off: LWW data loss vs operational simplicity.

Google BigTable / Spanner pre-TrueTime — multi-version cells с timestamps. Percolator (snapshot isolation поверх BigTable) использовал Lamport-style ordering для cross-table transactions до появления TrueTime.

Apache Kafka idempotent producer — per-partition sequence number в духе Lamport: producer держит monotonic counter, broker reject'ит out-of-order или duplicate sequences. Это даёт exactly-once семантику в рамках одного partition.

DynamoDB conditional writes / etcd compare-and-swap / ZooKeeper version checks — optimistic concurrency control через «version = ts». Клиент читает (value, version), модифицирует, пишет с условием version == old. Если кто-то писал — ts вырос, CAS отказал, retry.

OpenTelemetry / distributed tracing — span timestamps часто Lamport-like для cross-service ordering, особенно когда spans собираются с разных серверов с расходящимися часами.

Anti-patterns

• Reliance на LWW для concurrent merges. «У меня timestamps монотонные — значит порядок правильный». Нет: при concurrent writes ты теряешь данные. Используй CRDT (G-Counter, OR-Set) или vector clocks с app-level resolve.
• Wall-clock как Lamport timestamp без monotonicity guard. Если NTP откатил часы назад — твой ts может уменьшиться, и более поздний write проиграет более раннему в LWW. Нужен max(local_now, last_ts + 1).
• Игнорирование node_id в tie-break. Без него два события с одинаковым ts на разных нодах дают разный total order на разных репликах → eventual divergence cluster'а.
• Использование Lamport ts для read-your-writes guarantees. Lamport ничего не говорит про физическое время, только про causal. Read-your-writes требует session token / sticky routing / HLC.
• Считать Lamport == HLC. Hybrid Logical Clocks комбинируют physical wall-clock с Lamport-style logical bump. Это разные вещи: Lamport не привязан к wall-clock вообще, HLC — приблизительно привязан.
• Глобальный distributed counter «для простоты». «Давайте просто будем брать ts из centralized service». Это вводит single point of failure и latency penalty на каждое событие. Lamport специально решает проблему без central coordinator.
• Считать что больший ts = «более новое» событие в человеческом смысле. Concurrent событие на «забегающей вперёд» ноде может иметь больший ts, чем причинно более позднее событие на «отстающей» ноде. Это математически корректно (partial order соблюдается), но контр-интуитивно при debugging.

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

• Когда у тебя есть TrueTime / atomic clocks (Google Spanner). С bounded clock uncertainty можно делать external consistency без Lamport-логики.
• Single-node системы. Lamport избыточен — wall-clock или autoincrement primary key достаточны.
• Когда нужна точная wall-clock корреляция для compliance / forensics. Lamport ts не маппится в wall-clock. Используй HLC или сохраняй оба timestamp'а.
• High-conflict workloads, где silent data loss недопустим. Shopping carts, collaborative documents, configuration management. Бери vector clocks + sibling resolution или CRDT.
• Когда нужна total order по реальному времени (financial transactions с regulatory requirement on order). Lamport total order arbitrary для concurrent — может не совпадать с физическим порядком. Бери consensus (Raft/Paxos) с physical-clock anchoring или TrueTime.
• Strongly consistent reads (linearizability). Lamport — eventual consistency primitive. Linearizability требует consensus или single-writer.

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

• Lamport (1978): «Time, Clocks, and the Ordering of Events in a Distributed System» — оригинальная статья, читать обязательно (всего 8 страниц).
• DDIA, Ch.5 (Replication) и Ch.9 (Consistency and Consensus) — Kleppmann разбирает Lamport, LWW pitfalls, и почему vector clocks нужны для Dynamo-style систем.
• System Design Space: Clock synchronization.
• Cassandra docs: Atomicity, isolation, and durability — про writeTime и LWW trade-off.
• Martin Kleppmann talk: «Distributed Systems 4.1: Logical time» — visual intuition за 15 минут.
• Связанные концепты: ::concept{slug="happens-before"}, ::concept{slug="vector-clocks"}, ::concept{slug="hybrid-logical-clocks"}, ::concept{slug="crdts"}.
• Применяется в кейсах: :case{slug="twitter-system-design"} (timeline event ordering), :case{slug="instagram-system-design"} (feed merge), :case{slug="chat-system-design"} (message ordering across regions).