vector-clocks.js·4 scenarios
Vector Clocks concept page: per-replica vector counter that exactly distinguishes causal vs concurrent events. 3-replica Dynamo-style cluster + 2 clients. 4 scenarios: causal chain detection, concurrent writes returning siblings, VC vs Lamport comparison showing concurrency info loss, sibling explosion anti-pattern.
::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 точно реализует).
Vector clock = массив счётчиков
V[N], по одному на каждую реплику. Три правила:
- Local event на ноде i:
V[i]++- Send msg с ноды i:
V[i]++; piggyback V целиком в payload- 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]<V_E[P3] → честно concurrent, caller решает. Учит: «Lamport даёт total order ценой потери concurrency info; VC сохраняет, но платит O(N)».
4. Sibling explosion (Riak anti-pattern) — production-grade bug. Client делает три PUT'а подряд без чтения (ctx=null каждый раз): network retry, mobile fallback, что угодно. Каждый PUT создаёт новый VC counter, и потому что у всех ctx=null, ни один не super-set другого — 3 siblings на один key. Value blob blow up до десятков KB, read latency растёт, ops paged. Fix'ы: (1) always read-before-write — клиент подтянет актуальный ctx; (2) DVV (Dotted Version Vectors, Riak 2.0+) — client-dot вместо per-write counter; (3) CRDT-typed bucket — auto-merge без app logic; (4) TTL / max sibling count → force merge старых. Учит: «VC не магия — без правильного клиента он становится bug generator».
Context. Lamport scalar говорит «A раньше B» только для causally-related events, но молча путает concurrent (A||B) с causal (A->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.
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.
Context. VC растёт O(N) на каждый event и не справляется с dynamic node sets (auto-scaling 1000+ нод → vector blow up, dead IDs накапливаются). Альтернативы решают разные проблемы.
Decision tree.
Trade-off. Нет «лучшего» — есть осознанный выбор по domain'у. Shopping cart → VC/DVV/CRDT. Time-series log → HLC. Social like-counter → Lamport+LWW или G-Counter CRDT.
Context. При concurrent write одного key реплика обнаружила, что новый VC не super-set текущего и не sub-set. Что делать?
Decision. Хранить обе версии как siblings. На следующем READ возвращать массив values + соответствующие VCs. App обязан merge и записать обратно с merged ctx.
Trade-off.
Альтернатива: 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 ок. Корзина у залогиненного юзера на двух девайсах — нет.
max(ts) wins — ты построил Lamport через VC. Либо siblings + app merge, либо CRDT.::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).