Vector Clocks and Versioning

I once spent three days debugging a production issue where a user's shopping cart kept "losing items" after concurrent sessions. The root cause? Two application servers received write requests at nearly the same millisecond, and the database's "last write wins" policy silently discarded one session's changes. The user saw items vanish, support tickets flooded in, and we had no audit trail to explain what happened.

This is the fundamental problem of ordering in distributed systems: when events happen on different machines, how do you determine which happened first? And more importantly, how do you detect when two events are concurrent and need application-level reconciliation?

The Problem of Ordering Events

In a single-machine system, ordering is trivial. A single clock, a single memory bus, a single thread of execution. Event A happens at time T1, event B at time T2. Simple.

In a distributed system, you have N machines, each with its own clock. Network delays are unpredictable. Two writes can arrive at different replicas in different orders. Without a shared clock or centralized coordinator, determining the order of events becomes surprisingly hard.

Why Wall Clocks Fail

The naive approach: use timestamps from each machine's local clock. The server handling the request stamps the current time, and you order by that timestamp. This fails for three reasons:

Even with NTP keeping clocks within a few milliseconds of each other, the margin of error is large enough that concurrent operations from different machines can't be reliably ordered.

Causal vs Total Order

The key insight from Leslie Lamport's 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System" is that we don't need physical time. We need causal ordering.

The Happens-Before Relation

Lamport defined the "happens-before" relation (denoted as A -> B) with three rules:

Two events are concurrent if neither happened before the other. This is the critical distinction: total ordering (all events can be ordered) is a stronger property than causal ordering (only causally-related events are ordered).

Why Causality Matters

Consider a social media application:

1. User creates a post: "I'm moving to a new city"
2. User comments on their own post: "Just arrived in Berlin"
3. Friend sees the post and replies: "Welcome to Berlin!"

If the system displays the friend's reply before the original post or the user's "arrived in Berlin" comment, the conversation makes no sense. These events have a causal relationship: the reply depends on the post, which depends on the original announcement. But if two users post independent updates, neither causes the other, and they can be displayed in any order.

Lamport Timestamps

Lamport timestamps are the simplest logical clock implementation. Each node maintains a single monotonically increasing counter.

How They Work

Rules:

1. Each process increments its counter before each event
2. When sending a message, include the current counter value
3. When receiving a message, set counter = max(local_counter, message_counter) + 1

The Limitation

Lamport timestamps provide total ordering if you break ties using process IDs. But they have a critical flaw: they cannot detect concurrency.

If T(A) is less than T(B), we know that B did NOT happen before A. But we cannot conclude that A happened before B. The timestamps might have come from independent counters that advanced at different rates.

This is the fundamental limitation: Lamport timestamps give a partial view of causality that's insufficient for conflict detection.

Vector Clocks

Vector clocks solve the concurrency detection problem. Instead of a single counter, each node maintains a vector of counters—one entry for every node in the system.

The Data Structure

A vector clock is a map: [node_id -> counter]

Clock at Node A: [A=3, B=2, C=5]

Each entry represents the latest event from that node that this node knows about.

How They Work

Rules:

1. Each node increments its own counter before each event
2. When sending a message, include the full vector clock
3. When receiving, merge: for each entry, take max of local and received counter, then increment own counter

Comparing Vector Clocks

Conflict Detection Examples

The last row is the classic conflict case: both nodes received each other's updates, then both made independent changes. Neither clock dominates.

Dynamo's Versioning System

Amazon's Dynamo paper (2007) popularized vector clocks for production use. Dynamo powers Amazon's shopping cart service, where concurrent updates are common and data loss is unacceptable.

Shopping Cart Reconciliation

Write 1: Add "Headphones"
  Clock: [A=1]
  
Write 2: Add "USB Cable" (concurrent, different node)
  Clock: [B=1]
  
Read: Both writes are concurrent!
  Return: [Headphones, USB Cable] with clock [A=1, B=1]
  
Client merges: combines both items, writes merged state
  Write: Add "Headphones" + "USB Cable"
  Clock: [A=2, B=2]

The client receives both versions (called "siblings") and must reconcile them. For a shopping cart, the reconciliation is simple: take the union of items. For other data types, reconciliation may require application-specific logic.

Real-World Conflict Resolution

How Dynamo Handles Write Conflicts End-to-End

The full Dynamo write path with vector clock management:

1. Coordinator receives write request for key K
2. Coordinator reads the current vector clock for K from any replica
3. Coordinator increments its own counter in the vector clock
4. Coordinator sends the data + new clock to all N replicas
5. Waits for W acknowledgments
6. Returns success with the new clock

The full read path:

1. Coordinator receives read request for key K
2. Coordinator sends read requests to all N replicas
3. Waits for R responses
4. Collects all returned (value, clock) pairs
5. Compares all clocks to detect concurrent versions
6. If siblings exist: return all siblings + merged clock to client
7. Client reconciles siblings and writes merged result
8. The write in step 7 prunes the version history

Vector Clock Growth Problem

Vector clocks grow with the number of nodes that have touched a key. In a system with thousands of nodes, a frequently-updated key can accumulate a vector clock with hundreds of entries.

Without management, vector clocks grow unboundedly, consuming storage and making comparisons expensive.

Clock Truncation Strategies

Dynamo uses several strategies to limit clock size:

The most common approach: after a successful read-write cycle (client reads all siblings, merges them, and writes back), the new clock can be pruned. The coordinator creates a new clock that represents the merged state, removing redundant entries.

Hybrid Logical Clocks (HLC)

Hybrid Logical Clocks combine the best of physical (NTP) and logical clocks. They provide the causal consistency guarantees of vector clocks with human-readable timestamps and bounded clock drift.

The Problem HLC Solves

• Physical clocks (NTP): human-readable, bounded drift, but can go backwards
• Lamport clocks: monotonic, causal, but not human-readable (single counter)
• Vector clocks: full causality tracking, but unbounded size

HLC bridges these worlds. Each timestamp is a pair: (physical_component, logical_component).

How HLC Works

HLC = (physical_clock, logical_counter)

On local event:
  physical = max(local_NTP, last_physical)
  if physical == last_physical:
    logical = last_logical + 1
  else:
    logical = 0
  return (physical, logical)

On receiving message with (p_remote, l_remote):
  physical = max(local_NTP, p_remote, last_physical)
  if physical == last_physical AND physical == p_remote:
    logical = max(last_logical, l_remote) + 1
  elif physical == last_physical:
    logical = last_logical + 1
  elif physical == p_remote:
    logical = l_remote + 1
  else:
    logical = 0

The key insight: HLC uses NTP time as its primary component but falls back to Lamport-style logical counters when NTP time doesn't advance between events. This guarantees monotonicity even if NTP adjusts the clock backward.

CockroachDB's Use of HLC

CockroachDB uses HLC for its global timestamp service. Each node maintains an HLC, and timestamps are used for:

The NTP bound matters. CockroachDB assumes a maximum clock offset (default 500ms). If a node's clock drifts beyond this bound, the node is considered faulty and is removed from the cluster. This is why HLC's physical component is critical: it bounds how far timestamps can diverge.

Dotted Version Vectors

Standard vector clocks have a subtle problem: they create false conflicts during read-repair operations. Riak introduced "dotted version vectors" to solve this.

The False Conflict Problem

When a read-repair operation updates a replica without any actual data change, standard vector clocks increment the counter, creating a new version that appears concurrent with existing versions:

Initial state: key K has clock [A=1, B=1]
  
Read-repair on Node A:
  A increments its entry: [A=2, B=1]
  
Compare with existing [A=1, B=1]:
  [A=2, B=1] vs [A=1, B=1]
  A: 2 > 1, B: 1 = 1
  => A "happened after" (no conflict, correct)
  
BUT if both A and B do read-repair:
  A's repaired clock: [A=2, B=1]
  B's repaired clock: [A=1, B=2]
  Compare: neither dominates
  => FALSE CONFLICT!

How Dots Fix This

Dotted version vectors break the vector clock into two parts:

When a write happens, the coordinator creates a new dot (node_id, counter). The dot is added to the set of "dangling dots" on the receiving replicas.

When a read-repair happens, the coordinator sends the specific dots that need repair. The receiving replica only adds the dot, not an incremented counter. This avoids incrementing the counter for operations that don't represent new causal information.

Dotted version vector for key K:
  Dangling dots: {(A, 2), (B, 3)}
  Version vector: [A=1, B=2]
  
  This means:
  - We have seen events (A,2) and (B,3) as potential siblings
  - We know all events up to A=1 and B=2
  - The events that are "concurrent" are exactly the dangling dots

Benefits

Riak's production experience showed that dotted version vectors significantly reduced the number of spurious siblings in real-world workloads, especially under read-repair-heavy operations.

Comparison: Lamport vs Vector vs HLC

When to Use Each

Conflict Resolution in Practice

Different systems handle the conflict resolution step differently:

The choice depends on whether your data has natural commutative merge semantics or requires application-specific reconciliation.

Real-World Implementations

Implementation Considerations

When implementing vector clocks in a production system:

Key Takeaways

• Lamport timestamps provide causal ordering but cannot detect concurrent events
• Vector clocks solve concurrency detection by maintaining a per-node counter vector, but grow linearly with the number of nodes
• Dynamo-style reconciliation returns all concurrent versions (siblings) to the client for application-level merge
• Clock truncation is essential to prevent unbounded growth of vector clocks in production
• HLC combines the human-readability of NTP time with the monotonic guarantees of logical clocks
• Choose your clock based on the tradeoff between completeness of causality tracking and operational overhead
• CockroachDB uses HLC to achieve serializable isolation without a centralized timestamp authority
• The "happens-before" relation (causal ordering) is usually sufficient; total ordering is often unnecessary and expensive

In the next tutorial, we will explore cache eviction algorithms and how modern systems like Caffeine achieve near-optimal hit rates using TinyLFU.