vector-clock-merge-reconcile
Core design: A VectorClock (map[string]int64) tracks per-replica event counts. Each Replica holds its own key-value store, local clock, and a wall-clock now() source. The MergeReconcile method implements causal reconciliation using four rules:
vclock.go – package vclock (~200 lines):
// Vector clock with Compare (Before/Equal/After/Concurrent), Copy, Merge, Increment
type VectorClock map[string]int64
func Compare(a, b VectorClock) CompareResult { ... }
// VersionedValue holds a value + vector clock + wall-clock timestamp
type VersionedValue struct {
Value string
Clock VectorClock
Timestamp int64
}
// Replica with thread-safe Get, Put, Delete, MergeReconcile, Snapshot
type Replica struct {
mu sync.RWMutex
ID string
store map[string]*VersionedValue
clock VectorClock
now func() int64
}
func (r *Replica) MergeReconcile(peerID string, entries map[string]*VersionedValue) {
// 1. Build peerClock from all incoming entries
// 2. For each key: compare clocks → keep/replace/resolve
// 3. Merge peerClock into local clock
}
Key algorithmic details:
Compare: collects all replica IDs from both clocks, checks a[id] <= b[id] (→ aLessEq) and b[id] <= a[id] (→ bLessEq). The switch on (aLessEq, bLessEq) yields the causal ordering.lwwResolve: picks the later wall-clock timestamp; if equal, compares Clock.String() lexicographically (sorted IDs provide a total order); if clocks are identical, compares values.Snapshot returns deep copies so mutation is safe.sync.RWMutex for concurrent safety.**32 tests, all passing, race-detector clean, 96% coverage:** | Category | Tests | What's verified | |---|---|---| | **Core clock** | `TestVectorClockIncrement`, `TestVectorClockCopy`, `TestVectorClockMerge` | Basic operations | | **Compare** | `TestCompare` (10 sub-tests) | Before/Equal/After/Concurrent + symmetry for all edge cases | | **Edge cases** | `TestCompareEdgeCases` | nil vs empty, all zeros, one-sided, different replicas | | **Store ops** | `TestPutAndGet`, `TestDelete`, `TestLocalClock`, `TestSnapshot` | Basic CRUD + deep copy | | **Merge new** | `TestMergeReconcile_NewKey` | New keys accepted | | **Merge dominated** | `TestMergeReconcile_DominatedLocal` | Stale values rejected; causally-later values accepted | | **LWW** | `TestMergeReconcile_ConcurrentLWW` | Later wall clock wins | | **Tiebreak** | `TestMergeReconcile_ConcurrentLWWTiebreak`, `TestTiebreakDeterminism`, `TestTiebreakLexicographicStability` | Equal timestamps → deterministic | | **Convergence** | `TestThreeReplicaConvergence`, `TestFullMeshConvergence`, `TestFullSyncTiebreakConvergence`, `TestHappensBeforeTransitivity` | N-replica mesh converges | | **Causal** | `TestCausalOrdering` | A→B→C chain; stale causal past rejected | | **Idempotency** | `TestRepeatedSyncIdempotency` | Repeated syncs don't flip values | | **Concurrency** | `TestConcurrentAccess` | 100 concurrent readers/writers + 50 concurrent merges | | **Multiple rounds** | `TestMergeSameKeyConcurrentMultipleTimes` | Round 1: A wins; Round 2: B wins – both converge | **Edge cases tested:** - Empty replicas, nil clocks, missing keys treated as zero - Concurrent writes with identical timestamps → lexicographic clock-string tiebreaker (total order) - Transitive causal chains propagating across replicas - Race condition safety under heavy concurrent load ---
{"model": "claude-sonnet-4-20250514", "problem_class": "vector-clock-merge-reconcile", "result": "passed", "tests": 32}