◐ Off-By-One · answer catalog

vector-clock-crdt-merge

1 answer(s)gogo1.26

vector-clock-crdt-merge

📦 Source in repository (JSON)

Answer

Overview

The CRDT merge engine uses vector clocks per key to track causal history across replicas. Each key-value entry stores:

Merge Algorithm

  1. Collect all keys from both maps.
  2. For each key present in only one replica: include it unless it is a tombstone (deleted).
  3. For each key present in both replicas:
  4. Compare vector clocks using causal (happens-before) comparison:
    • If v1 happens-before v2 → e2 wins
    • If v2 happens-before v1 → e1 wins
  5. Concurrent writes → Last-Writer-Wins:
    1. Higher max counter value across all replica dimensions wins
    2. If tied, lexicographic replica ID comparison determines the winner
  6. If the winner is a tombstone (empty value), the key is excluded from the result.

Key Code

Vector clock comparison determines causal ordering:

func Compare(v1, v2 VectorClock) int {
    v1LessOrEqual, v2LessOrEqual := true, true
    for id := range allReplicas {
        c1, c2 := v1[id], v2[id]
        if c1 > c2 { v1LessOrEqual = false }
        if c2 > c1 { v2LessOrEqual = false }
    }
    if v1LessOrEqual && !v2LessOrEqual { return -1 }  // v1 before v2
    if v2LessOrEqual && !v1LessOrEqual { return 1 }   // v1 after v2
    return 0 // concurrent
}

Entry merge with LWW tie-breaking:

func mergeEntries(e1, e2 Entry) Entry {
    cmp := Compare(e1.VClock, e2.VClock)
    if cmp == -1 { return e2 }
    if cmp == 1  { return e1 }

    // Concurrent: LWW by max counter, then replica ID lexicographically
    t1, t2 := LWWTimestamp(e1.VClock), LWWTimestamp(e2.VClock)
    if t1 > t2 { return e1 }
    if t2 > t1 { return e2 }
    if e1.ReplicaID > e2.ReplicaID { return e1 }
    if e2.ReplicaID > e1.ReplicaID { return e2 }
    // Truly identical: prefer non-tombstone
    if e1.Value != "" { return e1 }
    return e2
}

Top-level merge handles all keys and tombstone filtering:

func Merge(m1, m2 CRDTMap) CRDTMap {
    result := make(CRDTMap)
    for k := range allKeys {
        e1, has1 := m1[k]
        e2, has2 := m2[k]
        if !has1 { if e2.Value != "" { result[k] = e2 }; continue }
        if !has2 { if e1.Value != "" { result[k] = e1 }; continue }
        merged := mergeEntries(e1, e2)
        if merged.Value != "" { result[k] = merged }
    }
    return result
}

Helper functions Increment, NewEntry, UpdateEntry, DeleteEntry provide ergonomic construction of vector clock metadata for testing and application code.

Evidence & signatures

All 30 tests pass successfully, verified with `go test -v` and `go test -race`:

| Test | What It Verifies |
|------|-----------------|
| `TestCompareEqual` | Equal clocks → concurrent (0) |
| `TestCompareBefore` | `{a:1,b:1}` before `{a:2,b:1}` → -1 |
| `TestCompareAfter` | `{a:3,b:2}` after `{a:2,b:2}` → 1 |
| `TestCompareConcurrent` | `{a:2,b:1}` vs `{a:1,b:2}` concurrent → 0 |
| `TestCompareConcurrentReplicaSubset` | Subset replica sets → concurrent |
| `TestCompareDisjoint` | Disjoint replica sets → concurrent |
| `TestCompareEmpty` | Empty clock before any non-empty → -1 |
| `TestIncrement*` | Increment preserves original, adds new replicas |
| `TestMergeCausalDominanceLeft` | Causally-dominant entry wins |
| `TestMergeCausalDominanceRight` | Causally-dominated entry loses |
| `TestMergeConcurrentLWWTimestamp` | Higher max counter wins |
| `TestMergeConcurrentLWWReplicaID` | Equal max → replica ID tiebreaker |
| `TestMergeConcurrentLWWReplicaIDReverse` | Replica ID order matters |
| `TestMergeIdenticalEntries` | Fully identical → non-tombstone |
| `TestMergeDisjointKeys` | Disjoint keys preserved |
| `TestMergeOverlappingSameValue` | Same value doesn't duplicate |
| `TestMergeCausalUpdate` | r1 writes, r2 reads & updates |
| `TestMergeConcurrentUpdates` | Two concurrent writes resolved |
| `TestMergeDeleteWins` | Causal delete removes key |
| `TestMergeDeleteAfterUpdate` | Concurrent delete beats update via max counter |
| `TestMergeThreeReplicas` | 3-way concurrent tie resolved by replica ID |
| `TestMergeIdempotent` | `Merge(m, m) == m` |
| `TestMergeCommutative` | `Merge(m1, m2) == Merge(m2, m1)` |
| `TestMergeAssociative` | `Merge(Merge(a,b),c) == Merge(a,Merge(b,c))` |
| `TestMergeEmpty` | Merge with empty map is identity |
| `TestMergeBothEmpty` | Both empty → empty result |
| `TestMergeConcurrentSumTiebreaker` | Max counter + replica ID deterministic |
| `TestMergeComplexScenario` | 4-way multi-replica scenario |
| `TestMergePreservesNonConflicting` | All 4 keys from 2 replicas preserved |
| `TestDeleteVsConcurrentAdd` | Concurrent add vs delete resolved deterministically |

### Edge Cases Covered

- **Empty vector clocks** — handled as causally before any non-empty clock
- **Disjoint replica sets** — correctly identified as concurrent
- **Tombstones** — deleted entries (value="") are excluded from results unless resurrected by a newer concurrent write
- **Identical entries** — deterministic resolution without duplication
- **3+ replicas** — binary merge is associative, so any merge order produces the same result
- **CRDT properties** — verified idempotency, commutativity, and associativity

---
{"model": "claude-sonnet-4-20250514", "problem_class": "vector-clock-crdt-merge", "result": "passed", "tests": 30}
Generated from the verified corpus · MIT licensedBack to the catalog