## Зачем `::concept{slug="lamport-clocks"}` дают partial-order: если `A -> B`, то `ts(A) < ts(B)`. Но обратное неверно — два события с разными timestamps могут быть concurrent, и Lamport их не различает. На практике это значит: при LWW merge ты **молча теряешь** один из concurrent writes. Cassandra с этим живёт (выбрала simplicity), Dynamo с этим жить не смогла — корзина пользователя не должна терять товары, добавленные с двух девайсов одновременно. Vector clocks (Mattern 1989, Fidge 1988 — независимые открытия) решают ровно эту дыру. Каждая реплика держит **массив** счётчиков длины N — по одному на каждую реплику в системе. После любого event ты можешь поэлементно сравнить два VC и точно ответить: `A -> B` (causal), `B -> A` (causal в обратную сторону), `A == B` (равны), или `A || B` (concurrent). Это первый примитив в distributed systems, который даёт **biconditional** causality: `A -> B` ⟺ `V_A < V_B`. Lamport даёт только импликацию в одну сторону. Платишь за это `O(N)` bytes на каждый message (вместо `O(1)` у Lamport) плюс необходимость хранить siblings (две concurrent версии value), пока приложение их не сольёт. Это база Amazon Dynamo (2007), Riak 1.x, Voldemort, AntidoteDB, CouchDB revision trees. Без понимания VC ты не поймёшь, почему Dynamo возвращает несколько values на один key, почему Cassandra сознательно от этого отказалась, и почему shopping cart на Riak умеет «воскрешать» удалённые items если её плохо имплементировать. См. также `::concept{slug="lamport-clocks"}` (предшественник), `::concept{slug="crdts"}` (как убрать siblings вообще ценой ограниченной семантики), `::concept{slug="happens-before"}` (формализация causality, которую VC точно реализует). ## Mental model > Vector clock = массив счётчиков `V[N]`, по одному на каждую реплику. Три правила: > 1. **Local event на ноде i:** `V[i]++` > 2. **Send msg с ноды i:** `V[i]++; piggyback V целиком в payload` > 3. **Receive msg на ноде i:** `V = pointwise max(V, msg.V); V[i]++` Сравнение двух vectors `V_A` и `V_B`: - `A -> B` ⟺ `∀i: V_A[i] <= V_B[i]` AND `∃i: V_A[i] < V_B[i]` - `B -> A` симметрично - `A == B` ⟺ все равны - `A || B` (concurrent) ⟺ существуют `i, j` такие что `V_A[i] < V_B[i]` И `V_A[j] > V_B[j]` — vectors «разошлись» в разные стороны Главное отличие от Lamport: вместо одного скаляра — N чисел, и `max` теперь pointwise, а не обычный. За эту ценность платишь `O(N)` памяти на каждый event/message. На кластере из 3 реплик это копейки. На кластере из 1000 auto-scaling нод — катастрофа (см. anti-patterns). Ключевая интуиция: `V[i]` отвечает на вопрос «сколько events на ноде i видела эта реплика». Когда P1 принимает сообщение от P2, она «учится» обо всех events, которые P2 успела видеть к моменту отправки — поэтому pointwise max. Concurrent events это ситуация, когда у двух нод накопилось **разное знание** о происходящем в кластере, и ни одна не subset другой. ## Что на диаграмме Три реплики (`p1`, `p2`, `p3`) в группе «3-replica cluster (Dynamo-style)» с label вида `P1 V=[0,0,0]` — текущий vector прямо в названии ноды. Между ними физические gossip-каналы (`p1<->p2`, `p2<->p3`, `p1<->p3`) — full mesh, потому что Dynamo-style системы плоские, без leader. Внизу два клиента (`client-a` mobile, `client-b` browser) с write-edges к репликам `p1` и `p2`. Edges физические — анимация в FlowBuilder идёт по ним в обе стороны (reverse animation для READ-responses). По правилу из CLAUDE.md мы НЕ создаём отдельные edges «server -> client» для ответов — это вызвало бы false impression, что есть прямой канал в обратную сторону. ADR-001 на ноде `p1` фиксирует ключевое решение: «vector clock = массив счётчиков длины N (по одному на реплику)», ADR-002 — «Vector Clocks vs Version Vectors vs HLC» с разбором, когда что выбирать. ## Сценарии **1. Causal chain (A->B detected)** — happy path. `P1` делает local event, `V[P1]++ -> [1,0,0]`. Отправляет на `P2`, после receive у `P2` получается `V = max([0,0,0], [2,0,0]) = [2,0,0]; V[P2]++ -> [2,1,0]`. `P2` делает свой local event и шлёт на `P3`. В конце `P3` сравнивает `V_A=[1,0,0]` против `V_B=[2,2,0]`: все элементы `<=`, есть строго `<` — значит `A -> B` точно. Учит: «pointwise comparison даёт exact causal detection через цепь произвольной длины». **2. Concurrent writes return siblings** — мотивация существования VC. `Client A` пишет `cart=apples:1` в `P1`, `Client B` одновременно пишет `cart=apples:2` в `P2`. После gossip `P2` сравнивает `[1,0,0]` (от P1) против `[0,1,0]` (своё): `V_A[P1]=1 > V_B[P1]=0` И `V_A[P2]=0 < V_B[P2]=1` — vectors разошлись. **Siblings**, обе версии сохраняются. На следующем READ клиент получает обе, делает app-level merge (union semantics: `apples:3`) и пишет обратно с `ctx=merged_vc=[1,1,0]`. После этого новая запись supersedes обе siblings (она их proper superset). Учит: «Dynamo не молчаливо overwrite, как Cassandra LWW — он отдаёт conflict наверх и доверяет app логике». **3. VC vs Lamport (concurrency info loss)** — прямое сравнение. Те же два независимых события (`P1.A` и `P3.E`, между ними ни одного сообщения). Lamport: `ts(A)=1, ts(E)=1` — tie, tie-break по `(ts, node_id)` даёт `(1, P1) < (1, P3)` — **arbitrary** порядок без причинной основы. VC: `V_A=[1,0,0]` vs `V_E=[0,0,1]` — `V_A[P1]>V_E[P1]` И `V_A[P3]B). Tie-break `(ts, node_id)` даёт total order ценой silent lost writes при LWW. Для multi-master eventual consistency (Dynamo, Riak, Voldemort) нужна **точная** детекция concurrent — иначе нельзя честно вернуть siblings приложению. **Decision.** Каждая реплика держит `V[N]` длины = число реплик. Local event: `V[self]++`. Send: `V[self]++`, piggyback V. Receive: `V = pointwise max(V, msg.V); V[self]++`. Compare: `A -> B` iff `∀i V_A[i] <= V_B[i] AND ∃i V_A[i] < V_B[i]`; иначе если симметрично — `B -> A`; иначе concurrent. Property: `A -> B` ⟺ `V_A < V_B` (biconditional — отличие от Lamport). **Trade-off.** - **Плюсы:** exact causality detection; siblings вместо silent lost writes; app/CRDT может resolve осознанно. - **Минусы:** `O(N)` bytes на каждый message (vs `O(1)` Lamport); membership churn ломает (нода ушла → её координата dead но остаётся); siblings нужно где-то хранить и app должен уметь merge. **Used:** Amazon Dynamo (2007), Riak 1.x, Voldemort, AntidoteDB, CouchDB revision trees. ### ADR-002: Vector Clocks vs Version Vectors vs HLC vs CRDTs **Context.** VC растёт `O(N)` на каждый event и не справляется с dynamic node sets (auto-scaling 1000+ нод → vector blow up, dead IDs накапливаются). Альтернативы решают разные проблемы. **Decision tree.** - **Choose VC** когда: bounded N реплик (3-10, не tenants/clients); нужна точная concurrent-detection; app/CRDT может resolve siblings. - **Choose DVV** (Dotted Version Vectors, Preguiça 2012) когда то же + write-heavy retries: client-dot не плодит false-concurrent siblings от idempotent retries. Riak 2.0+ перешёл. - **Choose HLC** когда нужен approximately-physical timestamp для UI / time-range queries (логи, scans). CockroachDB, MongoDB 3.6+, YugabyteDB. - **Choose CRDTs** когда хочется убрать siblings вообще ценой ограниченной семантики (G-Counter, OR-Set, LWW-Register). - **Choose Lamport+LWW** когда simplicity ops > correctness concurrent. Cassandra сознательно. Готов жить с silent data loss. **Trade-off.** Нет «лучшего» — есть осознанный выбор по domain'у. Shopping cart → VC/DVV/CRDT. Time-series log → HLC. Social like-counter → Lamport+LWW или G-Counter CRDT. ### ADR-003: Siblings вместо silent overwrite **Context.** При concurrent write одного key реплика обнаружила, что новый VC не super-set текущего и не sub-set. Что делать? **Decision.** Хранить **обе** версии как siblings. На следующем READ возвращать массив values + соответствующие VCs. App обязан merge и записать обратно с merged ctx. **Trade-off.** - **Плюсы:** no silent data loss; app видит conflict и обрабатывает осознанно (union для cart, max для counter, manual для documents). - **Минусы:** возможен sibling explosion (см. anti-patterns); read latency и blob size растут; app сложнее (нужна merge logic). **Альтернатива:** CRDT-typed bucket — merge встроен в data type, siblings никогда не вылезают наружу. Riak Data Types (counters, sets, maps) — exactly это. ## Реальные системы **Amazon Dynamo (2007 paper)** — оригинальное production-использование VC. Returns siblings при concurrent, app resolves. Shopping cart use case прямо в paper: «adds resurrected after delete» — фича, не bug, потому что пользователь явно хотел add'нуть. Recommendations engine, session store аналогично. **Riak 1.x → 2.0+** — изначально классический VC, потом DVV (Dotted Version Vectors). DVV решает «client retry создаёт false siblings» через client-dot: track «какие writes были инициированы этим клиентом» вместо «сколько events видела эта реплика». Backward-compatible на API уровне. Riak 2.0 ввёл также CRDT Data Types — для users которые не хотят писать sibling-merge logic. **Voldemort (LinkedIn, 2009)** — open-source Dynamo-clone. VC + read-repair + hinted-handoff. LinkedIn ушли в Espresso (MySQL-based), но Voldemort остался reference implementation для academic курсов. **AntidoteDB / SwiftCloud (research)** — VC + CRDTs для geo-distributed transactional databases. Cure consistency model: causal+ (causality preserved across all replicas). **CouchDB / PouchDB** — vc-like revision trees для multi-master replication между mobile и server. Conflicts видны API клиенту как multiple `_rev` — application resolves. **Cassandra explicitly rejected VC** (~2008) — выбрала Lamport + LWW: «accept potential data loss for operational simplicity, predictable read latency, avoidance of sibling explosion». Это не «Cassandra хуже» — другие приоритеты. Если app-level гарантируешь, что одна сущность не пишется concurrent — LWW ок. Корзина у залогиненного юзера на двух девайсах — нет. ## Anti-patterns - **Unbounded vector size.** N в production может быть 1000+ нод (auto-scaling fleet). VC становится heavy → используй DVV или client-side IDs (только клиенты, не все сервера). - **Игнорирование siblings («просто возьмём first / last»).** Теряешь данные так же, как Cassandra LWW. Resolve через CRDT semantics (union для sets, max для counters) или поднимай на пользователя. - **Static node IDs при rolling restart.** Новая нода берёт другой ID при каждом перезапуске → VC забивается dead ID'ами. Use stable IDs (persistent membership) или GC'й dead positions. - **Использовать VC как database timestamp.** VC говорит про causality, не про время. Range scans «от 12:00 до 13:00» VC не поможет — для этого HLC / TrueTime. - **Не tracking missed concurrent events.** Если два write попали на разные реплики и одна replica умерла до gossip — VC не «магически» обнаружит. Anti-entropy / read-repair / Merkle trees всё ещё нужны. - **Write без читки context'а.** Главная причина sibling explosion. Клиент должен делать read-modify-write, attach'ить полученный ctx к PUT. - **VC + LWW вместе.** Если у тебя VC, но при concurrent ты всё равно делаешь `max(ts) wins` — ты построил Lamport через VC. Либо siblings + app merge, либо CRDT. ## Когда НЕ использовать - **Single-master системы.** Если у тебя один writer (leader), causality тривиальна — sequence number достаточен. VC overhead не оправдан. - **High-throughput counters/metrics, где LWW data loss приемлем.** Use Lamport+LWW (Cassandra), G-Counter CRDT, или просто atomic increment в Redis. VC + siblings перебор. - **Когда нужна точная wall-clock корреляция** (audit, forensics, compliance). VC не маппится в physical time. Use HLC или сохраняй оба timestamp'а. - **Auto-scaling fleets с 100+ ephemeral нод.** Membership churn убивает classic VC. Use DVV (client-side dots) или CRDTs. - **App не может merge siblings осмысленно.** Если у тебя document store и siblings = «manual conflict resolution через UI», подумай, действительно ли тебе нужна eventual consistency. Может, лучше strong consistency (Raft/Paxos) и оптимистичные блокировки. - **Strongly consistent reads (linearizability).** VC — eventual consistency primitive. Linearizability требует consensus или single-writer. ## Дальше читать - **Mattern (1989):** [«Virtual Time and Global States of Distributed Systems»](https://www.vs.inf.ethz.ch/publ/papers/VirtTimeGlobStates.pdf) — академическое введение VC. - **Fidge (1988):** independent discovery of vector clocks. Тот же примитив, разные мотивации. - **DeCandia et al. (Amazon, 2007):** [«Dynamo: Amazon's Highly Available Key-value Store»](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) — production usage, siblings, conflict resolution. Section 4.4 про VC обязательно. - **Preguiça et al. (2012):** [«Dotted Version Vectors: Logical Clocks for Optimistic Replication»](https://arxiv.org/abs/1011.5808) — почему classic VC плох для retries и как DVV решает. - **Basho blog:** [«Why Vector Clocks Are Easy / Hard»](https://riak.com/posts/technical/why-vector-clocks-are-hard/) — pragmatic Riak experience, реальные post-mortems. - **Almeida, Baquero, Fonte (2008):** Interval Tree Clocks paper — VC-альтернатива для dynamic node sets через fork/join без centralized ID assignment. - **DDIA Ch.5 (Replication)** — Kleppmann разбирает VC, siblings, sibling-explosion на простых примерах. - **Связанные концепты:** `::concept{slug="lamport-clocks"}`, `::concept{slug="happens-before"}`, `::concept{slug="hybrid-logical-clocks"}`, `::concept{slug="crdts"}`, `::concept{slug="cap-theorem"}`. - **Применяется в кейсах:** `:case{slug="twitter-system-design"}` (timeline merge), `:case{slug="chat-system-design"}` (message ordering across regions), `:case{slug="instagram-system-design"}` (feed merge с concurrent likes).