Vector Clocks & CRDTs

Metadata

1. Overview

What problem does it solve?

In an AP database (like Cassandra or DynamoDB), when a network partition occurs, two replicas can independently accept conflicting writes.

When the partition heals, the database must merge the divergent data. The simplest approach is Last-Write-Wins (LWW), but LWW destroys data — it silently throws away one of the writes.

Vector Clocks solve the "Which write happened first?" problem by tracking causal ordering without relying on wall clocks (which can drift). They can also detect when two writes are truly concurrent (and therefore conflicting), allowing the system to present both versions to the application for resolution.

CRDTs (Conflict-free Replicated Data Types) go further. They are special data structures mathematically designed so that merging always produces the correct result — no conflicts, no data loss, no human intervention. Ever.

What breaks without it?

• Silent Data Loss: LWW in an AP database causes legitimate user writes to be silently discarded.
• Incorrect Merge: A shopping cart on Replica A has {Apple, Banana}. Replica B has {Apple, Cherry}. A naive union merge produces {Apple, Banana, Cherry}, but what if the user on Replica A deliberately removed Cherry? Without proper conflict tracking, the system resurrects deleted items.

2. Motivation

Amazon's Dynamo paper (2007) is the foundational work here. Amazon built Dynamo for their shopping cart, which must never lose an item a customer added. They explicitly chose AP (Availability over Consistency) and used Vector Clocks to detect conflicting shopping cart states during merges.

CRDTs were formalized by Marc Shapiro et al. around 2011 at INRIA. They provided a mathematical framework that guarantees convergence without any coordination. This made them ideal for collaborative editing (like Google Docs), distributed counters (like "likes"), and multi-datacenter databases (like Riak).

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

Part 1: The Problem with Wall Clocks (LWW)

Node A clock: 10:00:00 AM (NTP drifted 5 seconds behind)
Node B clock: 10:00:05 AM (Accurate)

1. User writes "X=Apple" on Node A at (Node A's clock) 10:00:02 AM
2. User writes "X=Banana" on Node B at (Node B's clock) 10:00:01 AM

LWW says: Node A's write (10:00:02) happened AFTER Node B's (10:00:01).
Result: X=Apple. "Banana" is LOST!

Reality: Node B's write actually happened 4 seconds AFTER Node A's.
Correct Result: X=Banana.

Wall clocks cannot be trusted. Vector Clocks solve this.

Part 2: Vector Clock Causality

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#ffcc00', 'edgeLabelBackground':'#ffffff'}}}%%
sequenceDiagram
    participant A as Node A
    participant B as Node B

    Note over A,B: Initial: VC = {A:0, B:0}
    
    A->>A: Write X=Apple. VC={A:1, B:0}
    A->>B: Sync: X=Apple, VC={A:1, B:0}
    Note over B: Merge. My VC becomes {A:1, B:0}
    
    Note over A,B: 🔥 NETWORK PARTITION 🔥
    
    A->>A: Write X=Banana. VC={A:2, B:0}
    B->>B: Write X=Cherry. VC={A:1, B:1}
    
    Note over A,B: Partition heals. Sync!
    Note over A,B: {A:2,B:0} vs {A:1,B:1}<br/>Neither dominates! CONFLICT DETECTED.

If VC1's every component is ≥ VC2's, then VC1 happened after. If neither dominates, the writes are concurrent (conflicting).

6. Internal Working

Vector Clocks

A Vector Clock is a list of (NodeID, Counter) pairs.

Rules:

1. When a node does a local write, it increments its own counter.
2. When a node sends data, it includes its Vector Clock.
3. When a node receives data, it merges by taking the max() of each component.
4. Comparison:
   • VC_A > VC_B (A happened after B) if every component of A ≥ corresponding component of B, and at least one is strictly greater.
   • If neither A > B nor B > A, then the writes are concurrent (CONFLICT).

CRDTs (Conflict-free Replicated Data Types)

CRDTs eliminate the conflict entirely by using data structures whose merge operation is commutative, associative, and idempotent. This means the order of merges doesn't matter; the result is always the same.

Types of CRDTs:

1. G-Counter (Grow-only Counter)

   • Each node has its own local counter. Total = sum of all local counters.
   • Merge = max() of each node's counter.
   • E.g., "Likes" on a post across 3 datacenters.

2. PN-Counter (Positive-Negative Counter)

   • Two G-Counters: one for increments, one for decrements.
   • Value = Sum(P) - Sum(N).

3. G-Set (Grow-only Set)

   • Elements can only be added, never removed.
   • Merge = Union of two sets.

4. OR-Set (Observed-Remove Set)

   • Every element has a unique tag (UUID). Adding {Apple, tag-1} and removing {Apple, tag-1} are tracked independently.
   • Merge = Union of adds minus union of removes.

7. Implementation

Why Python? The comparison logic and merge functions are pure math operations that are clearest in Python.

"""
040 - Vector Clocks & CRDTs
Part 1: A Vector Clock implementation demonstrating causal ordering.
Part 2: A G-Counter CRDT demonstrating conflict-free distributed counting.
"""

# ══════════════════════════════════════════════
# PART 1: VECTOR CLOCKS
# ══════════════════════════════════════════════

class VectorClock:
    def __init__(self, node_id):
        self.node_id = node_id
        self.clock = {}  # {node_id: counter}

    def increment(self):
        """Local write: Increment my own counter."""
        self.clock[self.node_id] = self.clock.get(self.node_id, 0) + 1

    def merge(self, other_clock):
        """Merge: Take max() of each component."""
        all_nodes = set(self.clock.keys()) | set(other_clock.keys())
        merged = {}
        for node in all_nodes:
            merged[node] = max(self.clock.get(node, 0), other_clock.get(node, 0))
        self.clock = merged

    def compare(self, other):
        """
        Returns:
          'BEFORE'     if self happened before other
          'AFTER'      if self happened after other
          'CONCURRENT' if neither dominates (CONFLICT!)
        """
        all_nodes = set(self.clock.keys()) | set(other.clock.keys())
        
        self_gte = True   # Is every component of self >= other?
        other_gte = True   # Is every component of other >= self?
        
        for node in all_nodes:
            s = self.clock.get(node, 0)
            o = other.clock.get(node, 0)
            if s < o:
                self_gte = False
            if o < s:
                other_gte = False
        
        if self_gte and not other_gte:
            return "AFTER"
        elif other_gte and not self_gte:
            return "BEFORE"
        elif self_gte and other_gte:
            return "EQUAL"
        else:
            return "CONCURRENT"  # ⚠️ CONFLICT!

    def __repr__(self):
        return str(self.clock)


# ══════════════════════════════════════════════
# PART 2: G-COUNTER CRDT
# ══════════════════════════════════════════════

class GCounter:
    """A Grow-only CRDT Counter. Can never be decremented."""
    def __init__(self, node_id):
        self.node_id = node_id
        self.counts = {}  # {node_id: local_count}

    def increment(self, amount=1):
        """Only increment MY OWN local counter."""
        self.counts[self.node_id] = self.counts.get(self.node_id, 0) + amount

    def value(self):
        """The total count is the SUM of all local counters."""
        return sum(self.counts.values())

    def merge(self, other):
        """Merge: Take max() of each node's counter. ALWAYS converges!"""
        all_nodes = set(self.counts.keys()) | set(other.counts.keys())
        for node in all_nodes:
            self.counts[node] = max(
                self.counts.get(node, 0),
                other.counts.get(node, 0)
            )

    def __repr__(self):
        return f"GCounter({self.counts}) = {self.value()}"


# ══════════════════════════════════════════════
# TEST HARNESS
# ══════════════════════════════════════════════

if __name__ == "__main__":
    # ── Part 1: Vector Clocks ──
    print("=== PART 1: Vector Clocks ===\n")

    vc_a = VectorClock("A")
    vc_b = VectorClock("B")

    # Both start at {A:0, B:0}
    # Node A writes
    vc_a.increment()
    print(f"1. Node A writes.   VC_A = {vc_a}")

    # Sync A -> B
    vc_b.merge(vc_a.clock)
    print(f"2. Sync A -> B.     VC_B = {vc_b}")

    # Network Partition! Both write independently.
    vc_a.increment()
    vc_b.increment()
    print(f"\n3. 🔥 PARTITION 🔥")
    print(f"   Node A writes.   VC_A = {vc_a}")
    print(f"   Node B writes.   VC_B = {vc_b}")

    # Compare
    result = vc_a.compare(vc_b.clock)
    print(f"\n4. Comparing VC_A vs VC_B: {result}")
    if result == "CONCURRENT":
        print("   ⚠️  CONFLICT DETECTED! Must present both values to application for resolution.")
    
    # ── Part 2: G-Counter CRDT ──
    print("\n\n=== PART 2: G-Counter CRDT (Distributed 'Likes') ===\n")

    dc_us = GCounter("US-East")
    dc_eu = GCounter("EU-West")
    dc_ap = GCounter("AP-Tokyo")

    # Users in different datacenters "like" a post
    dc_us.increment(5)   # 5 likes in US
    dc_eu.increment(3)   # 3 likes in EU
    dc_ap.increment(7)   # 7 likes in Tokyo

    print(f"Before Sync:")
    print(f"  US sees: {dc_us}")
    print(f"  EU sees: {dc_eu}")
    print(f"  AP sees: {dc_ap}")

    # Sync (in any order — CRDTs guarantee the same result!)
    dc_us.merge(dc_eu)
    dc_us.merge(dc_ap)
    dc_eu.merge(dc_us)
    dc_ap.merge(dc_us)

    print(f"\nAfter Sync (All datacenters converge):")
    print(f"  US sees: {dc_us}")
    print(f"  EU sees: {dc_eu}")
    print(f"  AP sees: {dc_ap}")
    
    print(f"\n✅ All nodes agree: {dc_us.value()} total likes. No conflicts. No data loss.")

Sample Output

=== PART 1: Vector Clocks ===

1. Node A writes.   VC_A = {'A': 1}
2. Sync A -> B.     VC_B = {'A': 1}

3. 🔥 PARTITION 🔥
   Node A writes.   VC_A = {'A': 2}
   Node B writes.   VC_B = {'A': 1, 'B': 1}

4. Comparing VC_A vs VC_B: CONCURRENT
   ⚠️  CONFLICT DETECTED! Must present both values to application for resolution.


=== PART 2: G-Counter CRDT (Distributed 'Likes') ===

Before Sync:
  US sees: GCounter({'US-East': 5}) = 5
  EU sees: GCounter({'EU-West': 3}) = 3
  AP sees: GCounter({'AP-Tokyo': 7}) = 7

After Sync (All datacenters converge):
  US sees: GCounter({'US-East': 5, 'EU-West': 3, 'AP-Tokyo': 7}) = 15
  EU sees: GCounter({'US-East': 5, 'EU-West': 3, 'AP-Tokyo': 7}) = 15
  AP sees: GCounter({'US-East': 5, 'EU-West': 3, 'AP-Tokyo': 7}) = 15

✅ All nodes agree: 15 total likes. No conflicts. No data loss.

Notice how the G-Counter merge operation is completely order-independent. Even if EU syncs with AP first or US syncs with AP first, the final answer is always 15.

8. Complexity

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. What is a Vector Clock? Hint: A list of (NodeID, Counter) pairs attached to a piece of data. It tracks the causal history of writes. If VC_A > VC_B, then A happened after B. If neither dominates, the writes are concurrent (conflicting).

2. Why is Last-Write-Wins (LWW) dangerous? Hint: LWW relies on wall clocks, which are unreliable due to NTP drift. A write that actually happened earlier might have a later timestamp due to clock skew, causing a legitimate newer write to be silently overwritten.

3. What is a CRDT and what mathematical property does it guarantee? Hint: A Conflict-free Replicated Data Type. Its merge function is commutative (order doesn't matter), associative (grouping doesn't matter), and idempotent (merging the same data twice is harmless). This guarantees that all replicas eventually converge to the same state.

4. Give an example of a G-Counter CRDT. Hint: A "Likes" counter on a globally distributed social media post. Each datacenter maintains its own local count. The total is the sum. Merge is max() per datacenter. It always converges to the correct total.

13. Used By (Downstream Blocks)

• This is the capstone block. CRDTs and Vector Clocks are the most advanced conflict resolution tools in distributed systems.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: PN-Counter

Build a PNCounter class that supports both increment() and decrement(). Internally, it should use two GCounter instances: one for positive increments and one for negative increments (decrements). The value() should return P.value() - N.value().

Exercise 2: OR-Set (Observed-Remove Set)

Build an ORSet class that supports add(element) and remove(element). When adding, generate a unique UUID tag: {element: "Apple", tag: "uuid-abc"}. When removing, record the tag of the specific addition being removed. The merge of two OR-Sets should only resurrect an element if it was added after it was removed (i.e., its tag is not in the remove list).

Website Metadata