Module 12: Conflict Resolution in Distributed Systems

Why Conflicts Happen

In distributed systems with multiple writers, conflicts are inevitable. Understanding how to detect and resolve them is critical.
┌─────────────────────────────────────────────────────────────────┐
│                 WHY CONFLICTS OCCUR                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Scenario: Two users editing same document                      │
│                                                                 │
│      User A (NYC)              User B (London)                  │
│          │                          │                           │
│          ▼                          ▼                           │
│    ┌──────────┐               ┌──────────┐                      │
│    │ Edit: X  │               │ Edit: Y  │                      │
│    │ at t=100 │               │ at t=100 │                      │
│    └────┬─────┘               └─────┬────┘                      │
│         │                           │                           │
│         │    Network Partition      │                           │
│         │    or Latency             │                           │
│         ▼                           ▼                           │
│    ┌─────────────────────────────────────┐                      │
│    │         Both writes arrive          │                      │
│    │         Which one wins?             │                      │
│    └─────────────────────────────────────┘                      │
│                                                                 │
│  Conflict Types:                                                │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Write-Write: Two concurrent writes to same key        │     │
│  │ Read-Write:  Read based on stale data, then write     │     │
│  │ Delete-Update: Delete and update happen concurrently  │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Conflict Resolution Strategies Overview

┌─────────────────────────────────────────────────────────────────┐
│              RESOLUTION STRATEGIES                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  ┌─────────────────────────────────────────────────────────┐   │
│  │                 WRITE-TIME RESOLUTION                    │   │
│  │  (System decides immediately during write)               │   │
│  ├─────────────────────────────────────────────────────────┤   │
│  │ • Last-Write-Wins (LWW)                                 │   │
│  │ • First-Write-Wins                                      │   │
│  │ • Version vectors / Vector clocks                       │   │
│  │ • Merge functions (CRDTs)                               │   │
│  └─────────────────────────────────────────────────────────┘   │
│                                                                 │
│  ┌─────────────────────────────────────────────────────────┐   │
│  │                 READ-TIME RESOLUTION                     │   │
│  │  (Defer decision until read happens)                     │   │
│  ├─────────────────────────────────────────────────────────┤   │
│  │ • Return all versions (siblings)                        │   │
│  │ • Application-level merge                               │   │
│  │ • User intervention                                     │   │
│  └─────────────────────────────────────────────────────────┘   │
│                                                                 │
│  Trade-off:                                                     │
│  ┌─────────────────────────────────────────────────────────┐   │
│  │ Write-time: Simple, but may lose data                   │   │
│  │ Read-time:  No data loss, but complex reads             │   │
│  └─────────────────────────────────────────────────────────┘   │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Last-Write-Wins (LWW)

The simplest and most common strategy - but has data loss risks.
┌─────────────────────────────────────────────────────────────────┐
│                    LAST-WRITE-WINS                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Rule: Highest timestamp wins                                   │
│                                                                 │
│  Write A: {key: "user", value: "Alice", ts: 1000}              │
│  Write B: {key: "user", value: "Bob",   ts: 1001}              │
│                                                                 │
│  Result: Bob wins (timestamp 1001 > 1000)                       │
│                                                                 │
│  Timeline visualization:                                        │
│  ────────────────────────────────────────────────►             │
│       │                    │                                    │
│       ▼                    ▼                                    │
│   Write "Alice"      Write "Bob"                               │
│    ts=1000            ts=1001                                   │
│                            │                                    │
│                            ▼                                    │
│                    Final value: "Bob"                           │
│                                                                 │
│  Problems:                                                      │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ 1. Clock skew: ts=1001 might have happened BEFORE     │     │
│  │    ts=1000 in real time                               │     │
│  │                                                       │     │
│  │ 2. Data loss: Alice's write is silently dropped       │     │
│  │                                                       │     │
│  │ 3. No conflict detection: System can't tell you       │     │
│  │    a conflict occurred                                │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

LWW Implementation in Go

go
package lww

import (
    "sync"
    "time"
)

// LWWRegister implements a Last-Write-Wins register
type LWWRegister struct {
    mu        sync.RWMutex
    value     interface{}
    timestamp time.Time
    nodeID    string // Tie-breaker for equal timestamps
}

// LWWEntry represents a timestamped value
type LWWEntry struct {
    Value     interface{}
    Timestamp time.Time
    NodeID    string
}

// NewLWWRegister creates a new LWW register
func NewLWWRegister(nodeID string) *LWWRegister {
    return &LWWRegister{
        nodeID:    nodeID,
        timestamp: time.Time{}, // Zero time
    }
}

// Set updates the value if timestamp is newer
func (r *LWWRegister) Set(value interface{}, ts time.Time) bool {
    r.mu.Lock()
    defer r.mu.Unlock()

    if r.shouldUpdate(ts, r.nodeID) {
        r.value = value
        r.timestamp = ts
        return true
    }
    return false
}

// SetWithNode updates with external node ID (for replication)
func (r *LWWRegister) SetWithNode(value interface{}, ts time.Time, nodeID string) bool {
    r.mu.Lock()
    defer r.mu.Unlock()

    if r.shouldUpdate(ts, nodeID) {
        r.value = value
        r.timestamp = ts
        return true
    }
    return false
}

// shouldUpdate determines if new write should win
func (r *LWWRegister) shouldUpdate(newTS time.Time, newNodeID string) bool {
    // New timestamp is strictly greater
    if newTS.After(r.timestamp) {
        return true
    }

    // Same timestamp: use node ID as tie-breaker
    if newTS.Equal(r.timestamp) && newNodeID > r.nodeID {
        return true
    }

    return false
}

// Get returns the current value and timestamp
func (r *LWWRegister) Get() (interface{}, time.Time) {
    r.mu.RLock()
    defer r.mu.RUnlock()
    return r.value, r.timestamp
}

// Merge combines two registers, keeping the winner
func (r *LWWRegister) Merge(other *LWWRegister) {
    otherValue, otherTS := other.Get()
    r.SetWithNode(otherValue, otherTS, other.nodeID)
}

// GetEntry returns the full entry for replication
func (r *LWWRegister) GetEntry() LWWEntry {
    r.mu.RLock()
    defer r.mu.RUnlock()
    return LWWEntry{
        Value:     r.value,
        Timestamp: r.timestamp,
        NodeID:    r.nodeID,
    }
}

LWW Map (for key-value stores)

go
package lww

import (
    "sync"
    "time"
)

// LWWMap implements a map with LWW semantics per key
type LWWMap struct {
    mu      sync.RWMutex
    entries map[string]*LWWEntry
    nodeID  string
}

// NewLWWMap creates a new LWW map
func NewLWWMap(nodeID string) *LWWMap {
    return &LWWMap{
        entries: make(map[string]*LWWEntry),
        nodeID:  nodeID,
    }
}

// Set a key with LWW semantics
func (m *LWWMap) Set(key string, value interface{}) {
    m.SetWithTimestamp(key, value, time.Now())
}

// SetWithTimestamp sets with explicit timestamp
func (m *LWWMap) SetWithTimestamp(key string, value interface{}, ts time.Time) {
    m.mu.Lock()
    defer m.mu.Unlock()

    existing, exists := m.entries[key]

    if !exists || m.shouldUpdate(existing, ts, m.nodeID) {
        m.entries[key] = &LWWEntry{
            Value:     value,
            Timestamp: ts,
            NodeID:    m.nodeID,
        }
    }
}

// Get retrieves a value
func (m *LWWMap) Get(key string) (interface{}, bool) {
    m.mu.RLock()
    defer m.mu.RUnlock()

    entry, exists := m.entries[key]
    if !exists {
        return nil, false
    }
    return entry.Value, true
}

// shouldUpdate checks if new entry should win
func (m *LWWMap) shouldUpdate(existing *LWWEntry, newTS time.Time, newNodeID string) bool {
    if newTS.After(existing.Timestamp) {
        return true
    }
    if newTS.Equal(existing.Timestamp) && newNodeID > existing.NodeID {
        return true
    }
    return false
}

// Merge combines another map into this one
func (m *LWWMap) Merge(other *LWWMap) {
    other.mu.RLock()
    otherEntries := make(map[string]*LWWEntry)
    for k, v := range other.entries {
        entryCopy := *v
        otherEntries[k] = &entryCopy
    }
    other.mu.RUnlock()

    m.mu.Lock()
    defer m.mu.Unlock()

    for key, otherEntry := range otherEntries {
        existing, exists := m.entries[key]
        if !exists || m.shouldUpdate(existing, otherEntry.Timestamp, otherEntry.NodeID) {
            m.entries[key] = otherEntry
        }
    }
}

// All returns all key-value pairs
func (m *LWWMap) All() map[string]interface{} {
    m.mu.RLock()
    defer m.mu.RUnlock()

    result := make(map[string]interface{})
    for k, v := range m.entries {
        result[k] = v.Value
    }
    return result
}

Vector Clocks for Conflict Detection

Vector clocks detect conflicts but don't resolve them automatically.
┌─────────────────────────────────────────────────────────────────┐
│                   VECTOR CLOCKS                                 │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Each node maintains a vector of logical clocks                 │
│                                                                 │
│  Node A: [A:1, B:0, C:0] - "A has done 1 operation"            │
│  Node B: [A:0, B:2, C:0] - "B has done 2 operations"           │
│                                                                 │
│  Comparison Rules:                                              │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ V1 < V2 : All V1[i] <= V2[i] AND at least one <       │     │
│  │ V1 > V2 : All V1[i] >= V2[i] AND at least one >       │     │
│  │ V1 || V2: Neither < nor > (CONCURRENT!)               │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Example:                                                       │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ [A:1, B:2] vs [A:2, B:1]                              │     │
│  │                                                       │     │
│  │ A:1 < A:2 ✓                                          │     │
│  │ B:2 > B:1 ✓                                          │     │
│  │                                                       │     │
│  │ Result: CONCURRENT (conflict detected!)               │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  [A:1, B:2] vs [A:2, B:3]:                                     │
│  A:1 < A:2 ✓, B:2 < B:3 ✓                                      │
│  Result: [A:1, B:2] < [A:2, B:3] (no conflict)                 │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Vector Clock Implementation

go
package vectorclock

import (
    "encoding/json"
    "sync"
)

// VectorClock represents a vector clock
type VectorClock struct {
    mu     sync.RWMutex
    clocks map[string]uint64
}

// Comparison result
type Comparison int

const (
    Before     Comparison = -1 // This happened before other
    Concurrent Comparison = 0  // Concurrent (conflict!)
    After      Comparison = 1  // This happened after other
    Equal      Comparison = 2  // Identical
)

// New creates a new vector clock
func New() *VectorClock {
    return &VectorClock{
        clocks: make(map[string]uint64),
    }
}

// FromMap creates a vector clock from existing values
func FromMap(m map[string]uint64) *VectorClock {
    vc := New()
    for k, v := range m {
        vc.clocks[k] = v
    }
    return vc
}

// Increment the clock for a node (on local event)
func (vc *VectorClock) Increment(nodeID string) {
    vc.mu.Lock()
    defer vc.mu.Unlock()
    vc.clocks[nodeID]++
}

// Get returns the clock value for a node
func (vc *VectorClock) Get(nodeID string) uint64 {
    vc.mu.RLock()
    defer vc.mu.RUnlock()
    return vc.clocks[nodeID]
}

// Merge combines two vector clocks (take max of each component)
func (vc *VectorClock) Merge(other *VectorClock) {
    other.mu.RLock()
    otherClocks := make(map[string]uint64)
    for k, v := range other.clocks {
        otherClocks[k] = v
    }
    other.mu.RUnlock()

    vc.mu.Lock()
    defer vc.mu.Unlock()

    for nodeID, otherVal := range otherClocks {
        if otherVal > vc.clocks[nodeID] {
            vc.clocks[nodeID] = otherVal
        }
    }
}

// Compare this vector clock to another
func (vc *VectorClock) Compare(other *VectorClock) Comparison {
    vc.mu.RLock()
    defer vc.mu.RUnlock()

    other.mu.RLock()
    defer other.mu.RUnlock()

    // Collect all node IDs
    allNodes := make(map[string]struct{})
    for k := range vc.clocks {
        allNodes[k] = struct{}{}
    }
    for k := range other.clocks {
        allNodes[k] = struct{}{}
    }

    hasLess := false
    hasGreater := false

    for nodeID := range allNodes {
        thisVal := vc.clocks[nodeID]
        otherVal := other.clocks[nodeID]

        if thisVal < otherVal {
            hasLess = true
        }
        if thisVal > otherVal {
            hasGreater = true
        }
    }

    switch {
    case !hasLess && !hasGreater:
        return Equal
    case hasLess && !hasGreater:
        return Before
    case !hasLess && hasGreater:
        return After
    default:
        return Concurrent // hasLess && hasGreater
    }
}

// IsConcurrent checks if two clocks are concurrent (conflict)
func (vc *VectorClock) IsConcurrent(other *VectorClock) bool {
    return vc.Compare(other) == Concurrent
}

// Copy creates a deep copy
func (vc *VectorClock) Copy() *VectorClock {
    vc.mu.RLock()
    defer vc.mu.RUnlock()

    newVC := New()
    for k, v := range vc.clocks {
        newVC.clocks[k] = v
    }
    return newVC
}

// ToMap exports as a map
func (vc *VectorClock) ToMap() map[string]uint64 {
    vc.mu.RLock()
    defer vc.mu.RUnlock()

    result := make(map[string]uint64)
    for k, v := range vc.clocks {
        result[k] = v
    }
    return result
}

// MarshalJSON for JSON encoding
func (vc *VectorClock) MarshalJSON() ([]byte, error) {
    vc.mu.RLock()
    defer vc.mu.RUnlock()
    return json.Marshal(vc.clocks)
}

// UnmarshalJSON for JSON decoding
func (vc *VectorClock) UnmarshalJSON(data []byte) error {
    vc.mu.Lock()
    defer vc.mu.Unlock()
    return json.Unmarshal(data, &vc.clocks)
}

Using Vector Clocks in a Key-Value Store

go
package store

import (
    "sync"
    "vectorclock"
)

// VersionedValue represents a value with its vector clock
type VersionedValue struct {
    Value interface{}
    Clock *vectorclock.VectorClock
}

// ConflictStore stores values with conflict detection
type ConflictStore struct {
    mu      sync.RWMutex
    data    map[string][]VersionedValue // Multiple versions = siblings
    nodeID  string
}

// NewConflictStore creates a new store
func NewConflictStore(nodeID string) *ConflictStore {
    return &ConflictStore{
        data:   make(map[string][]VersionedValue),
        nodeID: nodeID,
    }
}

// Put stores a value, handling conflicts
func (s *ConflictStore) Put(key string, value interface{}, context *vectorclock.VectorClock) {
    s.mu.Lock()
    defer s.mu.Unlock()

    // Create new clock: merge with context, then increment
    newClock := vectorclock.New()
    if context != nil {
        newClock.Merge(context)
    }
    newClock.Increment(s.nodeID)

    newValue := VersionedValue{
        Value: value,
        Clock: newClock,
    }

    existing := s.data[key]

    // Filter out versions that are dominated by new clock
    var remaining []VersionedValue
    for _, ev := range existing {
        cmp := ev.Clock.Compare(newClock)
        if cmp == vectorclock.Concurrent {
            // Keep concurrent versions (siblings)
            remaining = append(remaining, ev)
        }
        // Discard versions that happened before newClock
    }

    remaining = append(remaining, newValue)
    s.data[key] = remaining
}

// Get retrieves all versions (may have siblings if conflicts exist)
func (s *ConflictStore) Get(key string) []VersionedValue {
    s.mu.RLock()
    defer s.mu.RUnlock()

    versions := s.data[key]
    if len(versions) == 0 {
        return nil
    }

    // Return copies
    result := make([]VersionedValue, len(versions))
    for i, v := range versions {
        result[i] = VersionedValue{
            Value: v.Value,
            Clock: v.Clock.Copy(),
        }
    }
    return result
}

// HasConflict checks if a key has multiple concurrent versions
func (s *ConflictStore) HasConflict(key string) bool {
    s.mu.RLock()
    defer s.mu.RUnlock()
    return len(s.data[key]) > 1
}

// Resolve merges siblings into a single value
func (s *ConflictStore) Resolve(key string, resolvedValue interface{}) {
    s.mu.Lock()
    defer s.mu.Unlock()

    existing := s.data[key]
    if len(existing) <= 1 {
        return // No conflict to resolve
    }

    // Merge all clocks
    mergedClock := vectorclock.New()
    for _, v := range existing {
        mergedClock.Merge(v.Clock)
    }
    mergedClock.Increment(s.nodeID)

    // Replace all siblings with resolved value
    s.data[key] = []VersionedValue{{
        Value: resolvedValue,
        Clock: mergedClock,
    }}
}

Version Vectors (Optimized for Replicas)

Version vectors are similar to vector clocks but optimized for replica-to-replica communication.
┌─────────────────────────────────────────────────────────────────┐
│               VERSION VECTORS                                    │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Difference from Vector Clocks:                                 │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Vector Clock: One entry per CLIENT                    │     │
│  │ Version Vector: One entry per REPLICA/SERVER          │     │
│  │                                                       │     │
│  │ Advantage: Fixed size (number of replicas is known)   │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Example with 3 replicas:                                       │
│                                                                 │
│  Replica A receives write:                                      │
│    Before: [A:5, B:3, C:4]                                     │
│    After:  [A:6, B:3, C:4]  (increment A's counter)            │
│                                                                 │
│  Replica B receives write:                                      │
│    Before: [A:5, B:3, C:4]                                     │
│    After:  [A:5, B:4, C:4]  (increment B's counter)            │
│                                                                 │
│  When syncing:                                                  │
│    A's version: [A:6, B:3, C:4]                                │
│    B's version: [A:5, B:4, C:4]                                │
│                                                                 │
│    These are CONCURRENT → Conflict!                             │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Dotted Version Vectors

An optimization that handles "sibling explosion" problem.
┌─────────────────────────────────────────────────────────────────┐
│              DOTTED VERSION VECTORS                             │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Problem with basic version vectors:                            │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Client reads [A:1], writes new value                  │     │
│  │ Concurrent: another client also reads [A:1], writes   │     │
│  │                                                       │     │
│  │ Both get version [A:2]                               │     │
│  │ Server can't distinguish them → siblings accumulate!  │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Solution: Add a "dot" (single event identifier)               │
│                                                                 │
│  Value: {                                                       │
│    data: "hello",                                               │
│    dot: (A, 2),           ← Exact event that created this      │
│    version_vector: [A:2, B:1]  ← Causal context                │
│  }                                                              │
│                                                                 │
│  Now server can tell:                                           │
│  - Value with dot (A,2) created by event A:2                   │
│  - Value with dot (B,2) created by event B:2                   │
│  - Even if both have same version vector context               │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Dotted Version Vector Implementation

go
package dvv

import (
    "sync"
)

// Dot represents a single event
type Dot struct {
    NodeID  string
    Counter uint64
}

// DVV represents a Dotted Version Vector
type DVV struct {
    mu     sync.RWMutex
    dot    *Dot                // The event that created this value
    vector map[string]uint64   // Causal context
}

// Value with DVV
type DVVValue struct {
    Data interface{}
    DVV  *DVV
}

// New creates a new DVV
func New() *DVV {
    return &DVV{
        vector: make(map[string]uint64),
    }
}

// NewWithDot creates a DVV with a dot
func NewWithDot(nodeID string, counter uint64) *DVV {
    return &DVV{
        dot:    &Dot{NodeID: nodeID, Counter: counter},
        vector: make(map[string]uint64),
    }
}

// DVVSet manages multiple values with their DVVs
type DVVSet struct {
    mu      sync.RWMutex
    nodeID  string
    counter uint64
    values  map[string][]DVVValue // key -> list of concurrent values
}

// NewDVVSet creates a new DVV set
func NewDVVSet(nodeID string) *DVVSet {
    return &DVVSet{
        nodeID: nodeID,
        values: make(map[string][]DVVValue),
    }
}

// Update creates a new version, potentially resolving siblings
func (s *DVVSet) Update(key string, value interface{}, context *DVV) {
    s.mu.Lock()
    defer s.mu.Unlock()

    // Increment counter
    s.counter++

    // Create new DVV with dot
    newDVV := NewWithDot(s.nodeID, s.counter)

    // Merge context into vector
    if context != nil {
        for k, v := range context.vector {
            if v > newDVV.vector[k] {
                newDVV.vector[k] = v
            }
        }
        // Include the context's dot in vector
        if context.dot != nil {
            if context.dot.Counter > newDVV.vector[context.dot.NodeID] {
                newDVV.vector[context.dot.NodeID] = context.dot.Counter
            }
        }
    }

    newValue := DVVValue{
        Data: value,
        DVV:  newDVV,
    }

    existing := s.values[key]

    // Filter: remove any value whose dot is dominated by new context
    var remaining []DVVValue
    for _, ev := range existing {
        if ev.DVV.dot == nil {
            continue
        }
        // Check if this value's dot is dominated by the new context
        contextContains := newDVV.vector[ev.DVV.dot.NodeID] >= ev.DVV.dot.Counter
        if !contextContains {
            // This is a concurrent value, keep it
            remaining = append(remaining, ev)
        }
    }

    remaining = append(remaining, newValue)
    s.values[key] = remaining
}

// Get returns all values for a key (may have siblings)
func (s *DVVSet) Get(key string) []DVVValue {
    s.mu.RLock()
    defer s.mu.RUnlock()

    return s.values[key]
}

// GetContext returns a merged context for reading
func (s *DVVSet) GetContext(key string) *DVV {
    s.mu.RLock()
    defer s.mu.RUnlock()

    values := s.values[key]
    if len(values) == 0 {
        return nil
    }

    // Merge all DVVs into a single context
    context := New()
    for _, v := range values {
        for k, val := range v.DVV.vector {
            if val > context.vector[k] {
                context.vector[k] = val
            }
        }
        if v.DVV.dot != nil {
            if v.DVV.dot.Counter > context.vector[v.DVV.dot.NodeID] {
                context.vector[v.DVV.dot.NodeID] = v.DVV.dot.Counter
            }
        }
    }

    return context
}

Application-Level Merge Strategies

When conflicts are detected, application logic can resolve them.
┌─────────────────────────────────────────────────────────────────┐
│            APPLICATION-LEVEL MERGE STRATEGIES                   │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. UNION (Sets/Lists)                                         │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Version A: {tags: ["go", "rust"]}                     │     │
│  │ Version B: {tags: ["go", "python"]}                   │     │
│  │ Merged:    {tags: ["go", "rust", "python"]}           │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  2. MAX VALUE (Counters)                                       │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Version A: {views: 100}                               │     │
│  │ Version B: {views: 95}                                │     │
│  │ Merged:    {views: 100}                               │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  3. FIELD-BY-FIELD (Documents)                                 │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Version A: {name: "Alice", city: "NYC"}               │     │
│  │ Version B: {name: "Alicia", city: "NYC"}              │     │
│  │                                                       │     │
│  │ Field 'city': same → keep                            │     │
│  │ Field 'name': different → need decision              │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  4. OPERATIONAL MERGE                                          │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Instead of storing values, store operations:          │     │
│  │                                                       │     │
│  │ Op A: ADD_ITEM("apple") at t=1                       │     │
│  │ Op B: ADD_ITEM("banana") at t=2                      │     │
│  │ Op C: REMOVE_ITEM("apple") at t=3                    │     │
│  │                                                       │     │
│  │ Replay all operations to get final state             │     │
│  │ Result: ["banana"]                                    │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Merge Function Interface

go
package merge

import (
    "reflect"
)

// MergeFunc defines how to merge conflicting values
type MergeFunc func(values []interface{}) interface{}

// Common merge strategies

// UnionMerge combines sets/slices
func UnionMerge(values []interface{}) interface{} {
    seen := make(map[interface{}]struct{})
    var result []interface{}

    for _, v := range values {
        slice := reflect.ValueOf(v)
        for i := 0; i < slice.Len(); i++ {
            item := slice.Index(i).Interface()
            if _, exists := seen[item]; !exists {
                seen[item] = struct{}{}
                result = append(result, item)
            }
        }
    }
    return result
}

// MaxMerge keeps the maximum numeric value
func MaxMerge(values []interface{}) interface{} {
    if len(values) == 0 {
        return nil
    }

    max := values[0]
    for _, v := range values[1:] {
        if compare(v, max) > 0 {
            max = v
        }
    }
    return max
}

func compare(a, b interface{}) int {
    switch va := a.(type) {
    case int:
        vb := b.(int)
        if va > vb {
            return 1
        } else if va < vb {
            return -1
        }
        return 0
    case int64:
        vb := b.(int64)
        if va > vb {
            return 1
        } else if va < vb {
            return -1
        }
        return 0
    case float64:
        vb := b.(float64)
        if va > vb {
            return 1
        } else if va < vb {
            return -1
        }
        return 0
    default:
        return 0
    }
}

// SumMerge adds numeric values (useful for counters that track increments)
func SumMerge(values []interface{}) interface{} {
    var sum int64
    for _, v := range values {
        switch n := v.(type) {
        case int:
            sum += int64(n)
        case int64:
            sum += n
        }
    }
    return sum
}

// FieldMerger for document-level merging
type FieldMerger struct {
    strategies map[string]MergeFunc
    defaultStrategy MergeFunc
}

// NewFieldMerger creates a field merger
func NewFieldMerger() *FieldMerger {
    return &FieldMerger{
        strategies: make(map[string]MergeFunc),
        defaultStrategy: func(values []interface{}) interface{} {
            // Default: LWW (return first value)
            if len(values) > 0 {
                return values[0]
            }
            return nil
        },
    }
}

// SetStrategy sets a merge strategy for a field
func (fm *FieldMerger) SetStrategy(field string, strategy MergeFunc) {
    fm.strategies[field] = strategy
}

// Merge merges multiple document versions
func (fm *FieldMerger) Merge(docs []map[string]interface{}) map[string]interface{} {
    result := make(map[string]interface{})

    // Collect all field names
    fields := make(map[string]struct{})
    for _, doc := range docs {
        for field := range doc {
            fields[field] = struct{}{}
        }
    }

    // Merge each field
    for field := range fields {
        var values []interface{}
        for _, doc := range docs {
            if v, ok := doc[field]; ok {
                values = append(values, v)
            }
        }

        strategy := fm.strategies[field]
        if strategy == nil {
            strategy = fm.defaultStrategy
        }

        result[field] = strategy(values)
    }

    return result
}

CRDTs: Conflict-Free Resolution

CRDTs (Conflict-free Replicated Data Types) are data structures designed to always merge without conflicts.
┌─────────────────────────────────────────────────────────────────┐
│                     CRDTS OVERVIEW                              │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Key Property: MERGE IS ALWAYS POSSIBLE                        │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Associative: (A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)             │     │
│  │ • Commutative: A ⊕ B = B ⊕ A                          │     │
│  │ • Idempotent:  A ⊕ A = A                              │     │
│  │                                                       │     │
│  │ Result: Order of merge doesn't matter,                │     │
│  │         duplicate merges are safe                     │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Two types:                                                     │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ State-based (CvRDT):                                  │     │
│  │   - Send entire state                                 │     │
│  │   - Merge by combining states                         │     │
│  │   - More bandwidth, simpler                           │     │
│  │                                                       │     │
│  │ Operation-based (CmRDT):                              │     │
│  │   - Send operations                                   │     │
│  │   - Replay operations                                 │     │
│  │   - Less bandwidth, requires reliable delivery        │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Common CRDTs:                                                  │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • G-Counter: Grow-only counter                        │     │
│  │ • PN-Counter: Increment/decrement counter             │     │
│  │ • G-Set: Grow-only set                                │     │
│  │ • 2P-Set: Two-phase set (add/remove)                  │     │
│  │ • OR-Set: Observed-remove set                         │     │
│  │ • LWW-Register: Last-writer-wins register             │     │
│  │ • MV-Register: Multi-value register                   │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘
We'll cover CRDTs in detail in Module 29. Here's a quick preview:

G-Counter (Grow-only Counter)

go
package crdt

import "sync"

// GCounter is a grow-only counter CRDT
type GCounter struct {
    mu     sync.RWMutex
    counts map[string]uint64 // node -> count
}

// NewGCounter creates a new G-Counter
func NewGCounter() *GCounter {
    return &GCounter{
        counts: make(map[string]uint64),
    }
}

// Increment the counter for a node
func (g *GCounter) Increment(nodeID string) {
    g.mu.Lock()
    defer g.mu.Unlock()
    g.counts[nodeID]++
}

// Value returns the total count
func (g *GCounter) Value() uint64 {
    g.mu.RLock()
    defer g.mu.RUnlock()

    var total uint64
    for _, count := range g.counts {
        total += count
    }
    return total
}

// Merge combines two G-Counters
func (g *GCounter) Merge(other *GCounter) {
    other.mu.RLock()
    otherCounts := make(map[string]uint64)
    for k, v := range other.counts {
        otherCounts[k] = v
    }
    other.mu.RUnlock()

    g.mu.Lock()
    defer g.mu.Unlock()

    for nodeID, count := range otherCounts {
        if count > g.counts[nodeID] {
            g.counts[nodeID] = count
        }
    }
}

Conflict Resolution in Real Systems

┌─────────────────────────────────────────────────────────────────┐
│            REAL-WORLD CONFLICT RESOLUTION                       │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  DynamoDB:                                                      │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • LWW by default                                      │     │
│  │ • Conditional writes for conflict avoidance           │     │
│  │ • Transactions for strong consistency                 │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Cassandra:                                                     │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • LWW with timestamps                                 │     │
│  │ • Counters use PN-Counter CRDT                        │     │
│  │ • Collection types have special merge logic           │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Riak:                                                          │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • DVV for conflict detection                          │     │
│  │ • Returns siblings on read                            │     │
│  │ • Built-in CRDT support (counters, sets, maps)        │     │
│  │ • allow_mult: true enables conflict detection         │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  CouchDB:                                                       │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Revision trees (_rev field)                         │     │
│  │ • Deterministic winner selection                      │     │
│  │ • Conflicts stored, can be resolved later             │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  Git:                                                           │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Three-way merge                                     │     │
│  │ • Conflict markers for manual resolution              │     │
│  │ • Content-addressable storage (DAG)                   │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Best Practices

┌─────────────────────────────────────────────────────────────────┐
│                    BEST PRACTICES                               │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  1. DESIGN TO AVOID CONFLICTS                                  │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Use unique IDs (UUIDs) for resources                │     │
│  │ • Partition data by owner/user                        │     │
│  │ • Use CRDTs for naturally mergeable data              │     │
│  │ • Make operations idempotent                          │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  2. CHOOSE RESOLUTION BASED ON DATA TYPE                       │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ Counters     → PN-Counter CRDT                        │     │
│  │ Sets/Lists   → OR-Set or grow-only                    │     │
│  │ Last value   → LWW with hybrid clock                  │     │
│  │ All values   → Keep siblings, app resolves            │     │
│  │ Documents    → Field-by-field merge                   │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  3. USE HYBRID LOGICAL CLOCKS                                  │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Combines wall clock with logical clock              │     │
│  │ • Better ordering than pure logical clocks            │     │
│  │ • More stable than pure wall clock (handles skew)     │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  4. MAKE CONFLICTS VISIBLE                                     │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Log when conflicts occur                            │     │
│  │ • Metric: conflicts per second                        │     │
│  │ • Alert on high conflict rates                        │     │
│  │ • Consider if conflicts indicate design problems      │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
│  5. TEST CONFLICT SCENARIOS                                    │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ • Simulate network partitions                         │     │
│  │ • Test concurrent writes to same key                  │     │
│  │ • Verify merge results are correct                    │     │
│  │ • Test conflict resolution under load                 │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘

Interview Questions

  1. What is the difference between LWW and vector clocks?
    • LWW: Simple, always resolves to one value, may lose data
    • Vector clocks: Detect conflicts, keep all concurrent versions
  2. When would you use siblings vs automatic resolution?
    • Siblings: When data loss is unacceptable (shopping cart, user preferences)
    • Automatic: When latest value is sufficient (sensor readings, caches)
  3. How do you handle delete conflicts?
    • Tombstones: Mark as deleted rather than removing
    • Include in version vector
    • "Delete wins" or "Update wins" policy
  4. What is sibling explosion and how do you prevent it?
    • Problem: Siblings accumulate without resolution
    • Solutions: DVV, automatic resolution after N siblings, read-repair
  5. Design a shopping cart with conflict resolution
    • Use OR-Set CRDT for items
    • Each add creates unique tag
    • Remove only affects locally observed items
    • Merge: union of all items minus removed items

Summary

┌─────────────────────────────────────────────────────────────────┐
│                 CONFLICT RESOLUTION SUMMARY                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                 │
│  Strategy          When to Use                  Trade-off       │
│  ─────────────────────────────────────────────────────────────  │
│  LWW               Simple, loss OK              May lose data   │
│  Vector Clocks     Detect conflicts             Complex reads   │
│  Version Vectors   Replica sync                 Fixed size      │
│  DVV               High-volume writes           More complex    │
│  CRDTs             Automatic merge              Limited types   │
│  App Merge         Custom logic needed          App complexity  │
│                                                                 │
│  Key Insight:                                                   │
│  ┌───────────────────────────────────────────────────────┐     │
│  │ The best conflict resolution is conflict avoidance.   │     │
│  │ Design your data model to minimize concurrent writes  │     │
│  │ to the same keys.                                     │     │
│  └───────────────────────────────────────────────────────┘     │
│                                                                 │
└─────────────────────────────────────────────────────────────────┘
Next Module: Module 13 - Horizontal vs Vertical Scaling
Previous Module: Module 11 - Apache Kafka Deep Dive
All Blogs
Tags:conflict-resolutioncrdteventual-consistency