System Design Consistency

Vector clocks

A cart gets a book in one Amazon-style region while a friend adds a pen from another. Both writes succeed. Later the replicas meet, and wall clocks cannot tell you whether one update caused the other or whether they truly happened side by side.

A labels each version so the store can spot real instead of guessing from NTP time.

Conflict journey

Replicas accept local writes

Each bumps its own clock entry.

Does one dominate, or neither?

Incomparable clocks mean conflict.

Domain merge / CRDT / LWW

Product policy collapses the conflict.

Try it: compare two vector clocks

Two replicas attach a vector to each object version. Domination means one update causally follows the other; otherwise the updates are concurrent and the application must merge.

Relation: Concurrent siblings
Left vector: {A:1, B:0}
Right vector: {A:0, B:1}

Left version

{A:1, B:0}

Right version

{A:0, B:1}

Each writer bumps its own component. Compare two cart versions to see dominance, equality, or concurrency before choosing LWW versus merge.

Detection is not resolution. When the lab reports concurrent siblings, that is the signal to union carts, use a CRDT, or apply an explicit policy — not proof that last-writer-wins is safe.

Problem → naive → break

Problem: active-active replicas accept writes for the same key while disconnected or lagging. Later they must decide: did one update cause the other, or were they concurrent?

Naive move: last-writer-wins on wall-clock / NTP timestamps. Counterexample: replica A adds a book at skew-late time; B adds a pen concurrently; LWW drops one item even though neither write knew the other.

Break: users lose cart lines. Collaborative docs overwrite each other. Ops sees "no error" because LWW always picks a winner.

Correctness invariant

If version V1 V2, any correct replica that has seen both must retain V2 (or a merge that includes V2's effects), never silently prefer an ancestor. If neither dominates, the store must expose (or apply a declared merge/), not invent a total order from wall clocks. Clients must send prior version context on write; blind overwrite violates the invariant.

Failure timeline: concurrent cart + LWW loss

Two regions write the same cart while partitioned. Vector clocks correctly spot concurrency; what you do next is a product choice.

T0
Both replicas agree
Empty cart, shared starting version.
cart[]vv{A:1, B:1}
T1
Region A adds book
A increments its own counter. B has not seen this write yet.
cart[book]vv{A:2, B:1}
T2
Region B (partitioned) adds pen
B increments its own counter from the old base. Neither side has the other’s item.
cart[pen]vv{A:1, B:2}
T3
Clocks are incomparable
Neither vector dominates the other → concurrent siblings. Detection is correct.
cartsiblingsvv{A:2,B:1} vs {A:1,B:2}
T4
Naive LWW by NTP
Wall-clock “later wins” keeps only pen. The book disappears even though A never saw B’s write.
cart[pen]vvLWW pick
T5
Domain merge / OR-Set
Union the concurrent adds. Cart keeps both intents; merged version advances both counters.
cart[book, pen]vv{A:2, B:2}
T6
Conflict collapses on later read
A later read of {A:2, B:2} dominates both siblings. The fight is over; one merged value remains.
cart[book, pen]vv{A:2, B:2}

T3: clocks detect the fight

T4: LWW can drop an item

T5–T6: merge keeps both intents

Vector clocks find the fight; product policy ends it. LWW is a policy choice with known loss, not a causality proof.

What actually happens

Physical clocks drift. NTP can be milliseconds or worse off, so “later timestamp wins” can drop a concurrent add. Logical clocks track relationships without trusting wall time.

A Lamport timestamp preserves one implication: when event A causally precedes B, A has a smaller counter. The reverse implication is false. Independent processes can produce counters 3 and 100 without communicating, so different numbers do not establish causality. Vector clocks retain a separate component for each participant, providing enough information to distinguish causal precedence from concurrency under the stated participant model.

Detection is not resolution. Shopping carts often union items; counters may use a ; some stores still choose and accept rare loss.

Vector clocks do not automatically resolve conflicts. They tell you whether one update safely supersedes another or whether the application must merge concurrent versions.

Object version {A:1, B:0}

Can one clock dominate the other?

Replica A path

A updates cart

{A:2, B:0}

No dominance vs B

Replica B path

B updates cart

{A:1, B:1}

No dominance vs A

Concurrent updates → siblings or merge

Domain merge: cart = union of items

How to choose a conflict strategy

1. Can two places write the same key? If only a primary accepts writes, you may not need vector clocks. If active-active replicas can diverge, you need causality labels or an equivalent.

2. Is silent data loss acceptable? Profile views or analytics may tolerate . Carts, inventory, and collaborative docs usually need merge or semantics.

3. Can you afford metadata growth? Full vectors are O(writers) per object. Consider pruning, , or a when N is large.

Simple rule of thumb

Use vector clocks (or version vectors) to detect conflicts; define the merge before shipping multi-writer keys. Always attach prior version context on write so clients cannot overwrite blindly.

In simple terms: clocks find the fight; your product decides how to end it.

Lamport timestamps first

Each process maintains a counter C:

Rule 1: Before each local event, increment C → C = C + 1
Rule 2: When sending a message, attach C
Rule 3: When receiving message with timestamp T → C = max(C, T) + 1

Happens-before:

If A happened before B, then C(A) is smaller than C(B). However, a smaller Lamport timestamp alone does not prove that A influenced B. Sorting by the pair (counter, process identifier) produces a deterministic total order consistent with known causality, but arbitrarily orders concurrent events. This is useful for ordering protocols while remaining insufficient for detecting application conflicts.

Problem: A writes X=1 at C=3, B writes X=2 at C=3 → same timestamp. You need vector clocks to tell if they are concurrent.

Vector clocks: causality and concurrency

VC = array of counters, one per node: e.g. [A:0, B:0, C:0]

Rules

Local event on node X: increment VC[X]
Send message: attach entire VC
Receive: VC[i] = max(VC[i], VC_msg[i]) for all i; VC[self] += 1

Comparing vector clocks

• VC1 < VC2 (happened before): every VC1[i] ≤ VC2[i] AND at least one <
• VC1 = VC2: same event
• VC1 || VC2 (concurrent): neither < → conflict
• [2,0,0] vs [2,1,0] → A before B | [2,0,0] vs [0,0,1] → concurrent

Version vectors and dotted version vectors

Object: { value, vv: {A:2, B:1} }. On conflict: both versions to client for merge (e.g. union of cart items).

A dotted version vector separates a version’s causal context from the unique event that created that version, called its dot. The dot is typically a writer identifier and counter. This lets the system distinguish several updates associated with a coordinating replica more precisely than a coarse summary alone. It can reduce unnecessary sibling creation, but does not eliminate real concurrent writes or supply the application’s merge policy.

Conflict resolution strategies

Last writer wins (LWW)

Higher timestamp wins. Simple but can lose data when two writes were concurrent.

Client-side resolution

Return all conflicting versions. Client or application service merges them using business rules such as union, max value, or manual review.

CRDT-based auto-resolution

G-Counter, OR-Set. Mathematically guaranteed convergence for supported types.

Application-level merge

Custom merge per type (e.g. “highest bid wins”). Domain-aware and automatic when rules are clear.

Shopping cart causality drill

Step	Replica A	Replica B	Meaning
Start	cart=[], clock {A:1,B:1}	cart=[], clock {A:1,B:1}	Both replicas agree.
Write 1	add book -> {A:2,B:1}	not seen	A has a newer causal event.
Write 2	not seen	add pen -> {A:1,B:2}	B writes concurrently with A.
Read	{A:2,B:1}	{A:1,B:2}	Neither clock dominates, so return siblings.
Merge write-back	cart=[book, pen], clock {A:2,B:2}		Product logic resolves by union of cart items.

Comparison rules

Compare vectors component by component, treating an absent participant as zero. For example, [A:2, B:1] is an ancestor of [A:2, B:2], because only B advances. In contrast, [A:3, B:1] and [A:2, B:2] are concurrent: each contains an update the other lacks. Equal context vectors represent the same summarized causal history under a correct versioning scheme; they are not a checksum proving that two arbitrary payloads contain identical bytes.

Metadata overhead

Assume an encoded writer identifier and counter cost sixteen bytes together. Three active writer entries then cost about 48 bytes per object, while one hundred cost about 1.6 KB before map overhead and sibling payloads. For fifty million keys and eight entries each, the raw vector metadata alone is 6.4 GB. Pruning an entry requires a safe knowledge or retirement rule; deleting an inconvenient counter can make a later concurrent update appear causally older.

Merge write-back (concrete)

plaintext

Siblings returned to client:
  vA = {items:[book], clock:{A:2,B:1}}
  vB = {items:[pen],  clock:{A:1,B:2}}

Domain merge (shopping cart):
  items = union(vA.items, vB.items) = [book, pen]
  merged_clock = element-wise max = {A:2,B:2}

Write-back to any replica with merged_clock.
Later read of {A:2,B:2} dominates both siblings,
so conflicts collapse after successful merge.

Do not LWW on wall clock here: concurrent adds
would drop one item.

Pruning rule of thumb: drop a writer entry only after every replica has seen a clock that dominates that writer's last contribution, or after a durable anti-entropy snapshot. Aggressive pruning of still-active writers can make concurrent updates look ordered and silently lose data.

Physical clocks vs logical clocks

Physical clock problems

• NTP: ±1–10ms typical, ±100ms worst
• Leap seconds, VM drift
• Cannot reliably order events 5ms apart

Bounded-time commit

GPS + atomic clocks, uncertainty intervals, and commit-wait can give globally consistent reads, but need specialized clock infrastructure.

Vector clock limitations

• Size: O(N) per object. Prune or use compact representations.
• Client must read-before-write (include VC as context)
• No global ordering for concurrent events
• Hybrid logical clocks: compact timestamps that preserve useful causality information

Quantify: metadata vs writers

Per-object overhead

~16 B × writers

3 writers ≈ 48 B; 20 ≈ 320 B; 100 ≈ 1.6 KB: before sibling values themselves explode.

Sibling tax

k siblings × value size

During a partition, k independent versions of a value of size v can require roughly k×v bytes plus their metadata. A hard sibling cap cannot safely mean “drop the extra versions” unless the product explicitly accepts that loss. Merge in a type-aware way, reject or throttle further conflicting writes, or move the hot key to a single-writer design. Compact causal representations reduce redundant metadata but do not make independent business updates disappear.

NTP trap

±1–10 ms typical, ±100 ms+ worst

Events 5 ms apart cannot be ordered by wall clocks. That is why vector clocks exist.

Watch: sibling count p99, conflict merge latency, clock entry cardinality per key, and unsafe prune attempts.

Still fails when…

Clients write without prior version context and overwrite blindly.
Aggressive pruning of active writers hides real concurrency and loses data.
Raw siblings hit end users without merge UX and fill support queues.
Hundreds of writers per tiny key increase metadata; consider dotted vectors or single-writer keys. HLCs are compact ordering timestamps, not a replacement for detecting every concurrent version.

From the basic idea to a production design

Beginner explanation

Use vector clocks when two replicas can update the same item independently and you need to know whether one update supersedes another or both must be merged.

Advanced answer

Explain metadata growth, client context, pruning, dotted version vectors, and why many products choose domain-specific merges or CRDTs instead of exposing raw conflicts.

What to watch in production

Attach version context to writes
Define merge behavior for each conflict type
Prune old clock entries safely
Track sibling/conflict growth per key

Questions worth answering

How do you compare two vector clocks?
Who resolves concurrent writes?
When would LWW be acceptable despite data loss risk?

Failure modes to cover

Clock metadata grows with replica count
Clients overwrite without sending context
Conflict queues become user-visible backlog

Choosing and explaining vector clocks

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

Use them to distinguish causally ordered updates from truly concurrent updates.

A clock dominates another when every counter is greater-or-equal and at least one is greater.

They detect conflicts; the product still needs a merge policy.

When it belongs

Multiple replicas can accept writes for the same key.

Last-writer-wins would lose user data.

Shopping carts, collaborative docs, or active-active stores need conflict visibility.

How it fails

Clients write without sending prior version context.

Sibling versions grow until reads become expensive.

Clock entries are pruned too aggressively and hide real conflicts.

Trade-offs to weigh

Better conflict detection versus larger per-object metadata.

Application merges preserve data but complicate UX.

CRDTs remove some merges but constrain data modeling.

Common misunderstandings

Using wall-clock timestamps as if they prove causality.

Assuming vector clocks provide a total order.

Not explaining who resolves concurrent versions.

Going deeper

Production deep dive: preserve causality without unbounded metadata

Vector clocks detect whether one version descends from another or is concurrent. They expose conflicts; the application still chooses how to merge, present, or reject concurrent values.

What must stay true

A clock entry is pruned only after retained context proves no live or recoverable writer can produce an unseen event that depends on that entry.

How the pieces fit

Base {A:1,B:1}

shared context

A writes {A:2,B:1}

add pen

B writes {A:1,B:2}

remove book

Concurrent siblings

neither dominates

Merge {A:2,B:2}

domain resolution

Writers seen

200

Naive vector can require 200 counters per object.

Entry bytes

≈ 16

Writer ID + counter before encoding overhead.

Metadata

≈ 3.2 KB/object

200 × 16 bytes; 1B objects means ≈3.2 TB.

Metadata growth and pruning

Vectors grow with distinct writers, not current replica count. Prefer stable replica actors over client IDs, compact retired actors after a durable anti-entropy frontier, and use server-side write proxies. TTL-only pruning can erase causal history and turn a true conflict into false dominance.

Dotted version vectors

A dot identifies the single new event, such as (A,3), while a compact context records all events already observed. This distinguishes siblings created from the same context without retaining every sibling clock and supports safe compaction of contiguous counters.

Lamport versus HLC versus vector

Lamport timestamps cheaply order events but cannot prove concurrency. Hybrid logical clocks combine approximate wall time with a logical counter for compact sortable versions, but still do not fully encode causality. Vectors detect concurrency precisely at O(number of writers) metadata.

Comparison rule

X dominates Y when every X component is ≥ Y and at least one is greater. If X dominates, Y is an ancestor; if neither dominates, they are concurrent. Equality is the same causal version, not necessarily proof that payload bytes match.

Merge write-back

Read all siblings and their context, apply a deterministic domain merge, take the component-wise maximum clock, increment the resolving writer, and write the merged value with that context. This new version dominates both siblings so later reads can discard them.

Worked example: Complete concurrent-cart merge

1Base cart {book}, clock {A:1,B:1}. Replica A adds pen → {book,pen}, {A:2,B:1}. Replica B removes book and adds mug → {mug}, {A:1,B:2}.
2Neither clock dominates: A has 2>1 and B has 2>1. The store must return siblings rather than silently choosing by physical time.
3Domain merge applies observed remove and both independent adds → {pen,mug}. Resolver C writes clock max({2,1},{1,2}) + C increment = {A:2,B:2,C:1}.

The resolved version dominates both siblings. Future replicas can discard the old values while retaining the causal fact that both were observed.

Clock choice and failure matrix

Scenario	Consequence	How to contain it
Need compact sort order	Vector is excessive.	Use Lamport or HLC; accept that concurrency is not fully detected.
Client omits read context	New write looks unrelated and creates extra sibling.	Require context token or route merge through authoritative service.
Retired writer pruned too early	Delayed event can hide a conflict.	Prune only behind durable replication/anti-entropy frontier.

What to watch in production

Track vector entries/object, sibling count, unresolved-conflict age, merge failures, pruned actors, and delayed events from retired writers.
Set a sibling cap with a safe fallback; never drop an arbitrary value merely to satisfy the cap.
Test merges for commutativity, associativity, and idempotence under permuted delivery order.

A scenario to reason through

Compare X={A:4,B:2,C:1} and Y={A:3,B:5,C:1}. Which wins?

One solid approach

Neither. X is ahead on A, Y is ahead on B, and they tie on C, so they are concurrent. Return/merge both, then write a clock that dominates both.

Going deeper

Vector clocks

The mechanism and its boundary

Vector clocks compare versions by causality, not wall time. They can tell when one version includes another and when two versions are concurrent, but they do not decide how to merge business data.

Causality comparison

Clock A

Clock B

Dominates?

Merge if concurrent

Work through the sizing assumptions

Clock A={A:2,B:0,C:0} and B={A:2,B:1,C:0}: A happened-before B because every A counter is <= B and one is lower.

Clock X={A:3,B:0,C:0} and Y={A:2,B:1,C:0}: neither dominates, so the writes are concurrent and need merge.

Clock data grows with writers: 20 replica entries * 8 bytes/counter plus ids can be hundreds of bytes per object before pruning.

When it belongs

Multiple replicas can accept writes to the same key. Wall-clock ordering would lose user intent. The product has a merge rule for concurrent versions.

Assumptions that matter

Replica count or writer identity count is bounded or compacted. Reads return enough context for safe writes. Concurrent writes are rare enough to resolve.

Easy mistakes

A vector clock identifies the relationship between versions but cannot decide whether to union cart items, keep both documents, or reject a conflicting update. Pruning clock entries discards causal history, so the system must define how that loss changes conflict detection instead of assuming the original guarantees remain intact. A blind write without the prior version context cannot express which versions the writer observed, making safe causal comparison and merging harder.

How it fails

Sibling versions accumulate and make reads expensive. Clients overwrite using stale context. Clock metadata grows beyond object payload size for tiny values.

Trade-offs to name

A vector preserves enough per-writer history to distinguish causal succession from concurrency, but its metadata grows with the writer identities retained for each object. Keeping concurrent versions lets an application merge user intent explicitly, while adding sibling storage, merge logic, and sometimes a user-visible conflict-resolution step. A single timestamp is cheaper to store but cannot establish that two writes were concurrent, so use that simplification only when its conflict policy is acceptable.

Wrap-up

You have seen how vector clocks detect concurrency when wall clocks cannot. Use these exercises to rehearse comparison and client context, then follow the primary papers.

Exercises

Compare three clocks. Given {A:2,B:1,C:0}, {A:2,B:2,C:0}, and {A:1,B:0,C:3}, which pairs are causal vs concurrent? What merge policy fits a shopping cart vs a profile display name?
Budget metadata. 50M keys, average 8 active writers historically, 16 bytes/entry. Estimate vector metadata footprint. Propose pruning or DVV rules that do not hide concurrency.
Client forgot context. A mobile client retries a write without the version vector after a timeout. Draw the failure and name the API change that prevents silent overwrite.

Topic-specific references

Lamport: Time, Clocks, and the Ordering of Events : happens-before and logical clocks.
DeCandia et al.: Dynamo (SOSP 2007) : version vectors and shopping-cart conflict visibility.
Almeida et al.: Dotted Version Vectors : reducing sibling explosion in causal stores.

Key takeaway

Vector clocks (and version vectors) detect real conflicts when wall clocks cannot. They identify causal order and concurrency; LWW, CRDTs, or domain merges decide what users see next. Pay the metadata and read-before-write cost only where silent loss is unacceptable.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Represent causality and concurrency with vector, dotted-version, Lamport, or hybrid clocks while controlling metadata growth and merge semantics.

Explain the decision

What can vector clocks tell that Lamport clocks cannot?

Read the reasoning

Vector comparison can identify concurrency versus happens-before; Lamport order alone cannot distinguish concurrent events.

Apply it to a production scenario

Two offline devices edit different fields and sync. How do you merge?

Read one approach

Detect concurrency via versions, apply domain-aware field merge or surface conflict, and emit a new version causally after both.

Work through the numbers

A full vector clock for 500 writers uses 8-byte counters. Raw metadata size?

Read the worked calculation

About 4,000 bytes per version before IDs/encoding, motivating pruning or dotted version vectors.

Reason through a failure

What must pruning preserve?

Read the recovery reasoning

It cannot erase causal context needed to distinguish a stale write from a concurrent one within the supported replica/history model.

Sources and further study

Continue with Conflict-Free Replicated Data Types (CRDTs).