Conflict Resolution - Learning Module

Loading content...

0/273

Conflict-free Replicated Data Types (CRDTs)

Data Structures That Can't Disagree

What if we could design data structures that, by their very mathematical construction, cannot have conflicts? Structures where any sequence of operations, applied in any order, always converge to the same final state?

Conflict-free Replicated Data Types (CRDTs) achieve exactly this. They are not conflict resolution strategies—they are conflict prevention strategies. By carefully constraining the operations a data structure supports, CRDTs guarantee that all replicas will eventually converge to the same state without any coordination, reconciliation, or human intervention.

This is not magic; it's mathematics. CRDTs leverage properties like commutativity (order doesn't matter), idempotency (duplicates don't matter), and monotonicity (values only 'grow' in a well-defined direction) to ensure convergence.

What You Will Learn

By the end of this page, you will understand the theoretical foundations of CRDTs, the distinction between state-based and operation-based CRDTs, common CRDT types (counters, sets, registers, maps), practical implementations, real-world use cases, and the inherent limitations of this approach.

The Mathematical Foundation

CRDTs are built on the theory of join-semilattices. Understanding this foundation illuminates why CRDTs work.

A semilattice is a set with a binary operation (join) that is:

Commutative: A ⊔ B = B ⊔ A
Associative: (A ⊔ B) ⊔ C = A ⊔ (B ⊔ C)
Idempotent: A ⊔ A = A

Any operation that satisfies these properties will converge regardless of the order operations are applied or how many times they're replayed.

Intuition: Growing Toward a Least Upper Bound

Imagine a set of values with a partial ordering. The 'join' operation takes two values and produces their least upper bound—the smallest value that is ≥ both inputs.

Example: Sets with Union

Set A = {1, 2}
Set B = {2, 3}
A ⊔ B = {1, 2, 3} (the smallest set containing both)

Sets with union form a semilattice. This is why set union can serve as a CRDT merge operation.

Example: Max of Integers

max(5, 7) = 7, max(7, 5) = 7 (commutative)
max(max(3, 5), 7) = max(3, max(5, 7)) = 7 (associative)
max(5, 5) = 5 (idempotent)

Max over integers forms a semilattice. Counters that only increase can use max as their merge.

Monotonically Increasing State

CRDTs fundamentally rely on state 'growing' in one direction. You can add elements to a set, increment a counter, or advance a timestamp—but you cannot undo these operations directly. This monotonicity is what enables conflict-free merging. Operations that violate monotonicity (like decrement or remove) require special handling.

Converting Mermaid diagram...

State-Based vs Operation-Based CRDTs

CRDTs come in two fundamental flavors: state-based (CvRDTs) and operation-based (CmRDTs). Both achieve eventual consistency but differ in synchronization approach.

State-Based (CvRDT)

•Syncs by sending full state
•Receiver merges incoming state with local
•Merge function must be join (commutative, associative, idempotent)
•Tolerates message loss, duplication, reordering
•State can be large → bandwidth intensive
•Simple to implement correctly

Operation-Based (CmRDT)

•Syncs by sending operations
•Receiver applies operations to local state
•Operations must commute
•Requires reliable, exactly-once delivery
•Small messages → bandwidth efficient
•More complex (need reliable broadcast)

crdt-types.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// STATE-BASED CRDT: G-Counter (Grow-only Counter)
// Each node tracks its own count; merge takes max of each
 
interface GCounterState {
    [nodeId: string]: number;
}
 
class StateBasedGCounter {
    private nodeId: string;
    private state: GCounterState = {};
    
    constructor(nodeId: string) {
        this.nodeId = nodeId;
        this.state[nodeId] = 0;
    }
    
    increment(): void {
        this.state[this.nodeId] = (this.state[this.nodeId] ?? 0) + 1;
    }
    
    value(): number {
        return Object.values(this.state).reduce((a, b) => a + b, 0);
    }
    
    getState(): GCounterState {
        return { ...this.state };
    }
    
    // Merge: component-wise maximum
    merge(remoteState: GCounterState): void {
        for (const [nodeId, count] of Object.entries(remoteState)) {
            this.state[nodeId] = Math.max(
                this.state[nodeId] ?? 0, 
                count
            );
        }
    }
}
 
// OPERATION-BASED CRDT: G-Counter
// Operations are broadcast; each node applies same ops
 
type CounterOp = { type: 'increment'; nodeId: string; delta: number };
 
class OpBasedGCounter {
    private counts: Map<string, number> = new Map();
    
    // Apply operation (from local or remote)
    apply(op: CounterOp): void {
        if (op.type === 'increment') {
            const current = this.counts.get(op.nodeId) ?? 0;
            this.counts.set(op.nodeId, current + op.delta);
        }
    }
    
    value(): number {
        return Array.from(this.counts.values()).reduce((a, b) => a + b, 0);
    }
    
    // Generate increment operation
    increment(nodeId: string): CounterOp {
        return { type: 'increment', nodeId, delta: 1 };
    }
}
 
// For op-based: operations must be delivered exactly once
// For state-based: delivery can be unreliable (merge handles it)

Comparison: State-Based vs Operation-Based
Aspect	State-Based (CvRDT)	Operation-Based (CmRDT)
Sync payload	Entire state	Single operation
Payload size	O(state size)	O(operation size)
Delivery requirements	At-least-once	Exactly-once, causal order
Complexity	Simple merge	Reliable broadcast needed
Failure handling	Naturally tolerant	Needs ack/retry logic
Best for	Unreliable networks, large state OK	Reliable networks, large state

Common CRDT Types

Several CRDT types are widely used and well-understood. Each addresses specific use cases.

G-Counter (Grow-only Counter)

Can only increase. Each node maintains its own count; total is sum of all.

PN-Counter (Positive-Negative Counter)

Supports increment AND decrement. Implemented as two G-Counters: one for increases, one for decreases. Value = P.value() - N.value().

counters.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// PN-Counter: Supports both increment and decrement
class PNCounter {
    private increments: GCounter;
    private decrements: GCounter;
    
    constructor(nodeId: string) {
        this.increments = new GCounter(nodeId);
        this.decrements = new GCounter(nodeId);
    }
    
    increment(): void {
        this.increments.increment();
    }
    
    decrement(): void {
        this.decrements.increment();  // Incrementing the decrement counter!
    }
    
    value(): number {
        return this.increments.value() - this.decrements.value();
    }
    
    merge(remote: PNCounterState): void {
        this.increments.merge(remote.increments);
        this.decrements.merge(remote.decrements);
    }
}
 
// Note: PN-Counter can go negative!
// It tracks "how many increments" and "how many decrements" globally,
// not a bounded inventory.

Counters and Inventory

PN-Counters are great for 'like counts' but dangerous for inventory. They can't enforce 'quantity ≥ 0' without coordination. Two nodes might decrement the same 'last item,' resulting in -1. Inventory with constraints requires either coordination or different modeling.

CRDTs in Production Systems

CRDTs have moved from academic research to production systems. Here's where they're used:

CRDTs in Real-World Systems
System	CRDT Usage	Use Case
Redis (Enterprise)	CRDTs for geo-replication	Global counters, distributed caching
Riak	CRDTs for data types (counter, set, map)	Shopping carts, analytics
Figma	Custom CRDT for design files	Real-time collaborative design
Apple Notes	CRDTs for sync	Offline-first note sync
Facebook/Meta	Internal CRDT frameworks	Collaborative features
SoundCloud	CRDTs for likes/plays	Distributed counters
Yjs/Automerge	General-purpose CRDT libraries	Collaborative apps, local-first

Case Study: Redis CRDB (CRDTs in Redis)

Redis Enterprise uses CRDTs for active-active geo-replication:

Strings: LWW-Register
Counters: PN-Counter (increment/decrement)
Sets: OR-Set (add/remove)
Hashes: Per-field LWW

Example: A counter incremented in EU and US regions merges automatically—both increments are preserved.

redis-crdt.sh
Redis CLI
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Redis CRDB counter example
# EU region:
EU> INCRBY pageviews 100
(integer) 100
 
# US region (concurrent):
US> INCRBY pageviews 50
(integer) 50
 
# After sync, both regions see:
> GET pageviews
(integer) 150   # 100 + 50, not LWW!
 
# This is a CRDT counter, not a regular string.
 
# Sets with OR-Set semantics:
EU> SADD cart item1 item2
(integer) 2
 
US> SREM cart item1
(integer) 1
 
# After sync: cart contains {item2}
# The remove is observed and wins over the add

Semantic Variation

Different systems implement CRDTs with varying semantics. Redis CRDB's sets use observed-remove semantics, while its strings use LWW. Understand the specific CRDT type your system implements to avoid surprises.

Implementing CRDTs

Let's implement a complete, production-grade PN-Counter with proper state management and merge semantics.

pn-counter-impl.ts
TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 * Production-grade PN-Counter CRDT
 * Supports increment, decrement, and merging across replicas.
 */
 
interface PNCounterState {
    p: { [nodeId: string]: number };  // Increments per node
    n: { [nodeId: string]: number };  // Decrements per node
}
 
export class PNCounter {
    private nodeId: string;
    private p: Map<string, number> = new Map();
    private n: Map<string, number> = new Map();
    
    constructor(nodeId: string) {
        this.nodeId = nodeId;
        this.p.set(nodeId, 0);
        this.n.set(nodeId, 0);
    }
    
    /**
     * Increment the counter by 1.
     */
    increment(): void {
        this.p.set(this.nodeId, (this.p.get(this.nodeId) ?? 0) + 1);
    }
    
    /**
     * Decrement the counter by 1.
     */
    decrement(): void {
        this.n.set(this.nodeId, (this.n.get(this.nodeId) ?? 0) + 1);
    }
    
    /**
     * Increment by a specific amount.
     */
    incrementBy(amount: number): void {
        if (amount < 0) throw new Error('Use decrement for negative values');
        this.p.set(this.nodeId, (this.p.get(this.nodeId) ?? 0) + amount);
    }
    
    /**
     * Decrement by a specific amount.
     */
    decrementBy(amount: number): void {
        if (amount < 0) throw new Error('Use increment for negative values');
        this.n.set(this.nodeId, (this.n.get(this.nodeId) ?? 0) + amount);
    }
    
    /**
     * Get the current value (sum of increments - sum of decrements).
     */
    value(): number {
        const pSum = Array.from(this.p.values()).reduce((a, b) => a + b, 0);
        const nSum = Array.from(this.n.values()).reduce((a, b) => a + b, 0);
        return pSum - nSum;
    }
    
    /**
     * Get the total number of increment operations (useful for analytics).
     */
    totalIncrements(): number {
        return Array.from(this.p.values()).reduce((a, b) => a + b, 0);
    }
    
    /**
     * Get the raw state for synchronization.
     */
    getState(): PNCounterState {
        return {
            p: Object.fromEntries(this.p),
            n: Object.fromEntries(this.n),
        };
    }
    
    /**
     * Merge another counter's state into this one.
     * This is the join operation—commutative, associative, idempotent.
     */
    merge(remoteState: PNCounterState): void {
        // Merge increments: take max for each node
        for (const [nodeId, count] of Object.entries(remoteState.p)) {
            const local = this.p.get(nodeId) ?? 0;
            this.p.set(nodeId, Math.max(local, count));
        }
        
        // Merge decrements: take max for each node
        for (const [nodeId, count] of Object.entries(remoteState.n)) {
            const local = this.n.get(nodeId) ?? 0;
            this.n.set(nodeId, Math.max(local, count));
        }
    }
    
    /**
     * Compare two states for debugging/testing.
     */
    equals(other: PNCounter): boolean {
        const thisState = this.getState();
        const otherState = other.getState();
        return JSON.stringify(thisState) === JSON.stringify(otherState);
    }
}
 
// Usage demonstration:
function demo() {
    // Two replicas
    const counterEU = new PNCounter('eu-node');
    const counterUS = new PNCounter('us-node');
    
    // Concurrent operations
    counterEU.increment();  // EU: +1
    counterEU.increment();  // EU: +1
    counterUS.increment();  // US: +1
    counterUS.decrementBy(2);  // US: -2
    
    console.log('Before merge:');
    console.log('EU value:', counterEU.value());  // 2
    console.log('US value:', counterUS.value());  // -1
    
    // Sync states
    counterEU.merge(counterUS.getState());
    counterUS.merge(counterEU.getState());
    
    console.log('After merge:');
    console.log('EU value:', counterEU.value());  // 1 (2 + 1 - 2)
    console.log('US value:', counterUS.value());  // 1 (converged!)
    console.log('States equal:', counterEU.equals(counterUS));  // true
}

Limitations of CRDTs

CRDTs are powerful but not a panacea. Understanding their limitations prevents misapplication.

CRDT Limitations

•Cannot Enforce Invariants — CRDTs can't guarantee 'counter ≥ 0' or 'inventory > 0'. Concurrent decrements can violate constraints. Invariants require coordination.
•Metadata Overhead — CRDTs carry version information (node IDs, tombstones, tags). For small values, metadata can exceed data size.
•Tombstone Accumulation — OR-Sets and similar CRDTs accumulate tombstones forever. Without garbage collection, state grows unbounded.
•Limited Operation Types — Not all operations can be CRDTified. 'Set X to 5 if X > 3' has a conditional that can't be made conflict-free without coordination.
•Complexity for Users — Multi-value registers return multiple values. Applications must handle this, which isn't always intuitive.
•Semantic Surprises — CRDTs have specific semantics. OR-Set add+remove behaves differently than 2P-Set. Users must understand the type they're using.
•No Transactions — CRDTs operate on individual values. 'Transfer $100 from A to B' spanning two counters can't be made atomic without coordination.

The Invariant Problem in Detail:

Consider an inventory system:

Time	EU Action	US Action	EU Stock	US Stock
T0	-	-	5	5
T1	Sell 3	-	2	5
T2	-	Sell 4	2	1
T3	Merge	Merge	-2	-2

Both regions checked 'stock ≥ quantity' locally and approved the sale. After merge, stock = -2.

Solutions:

Accept negative and compensate later (refunds)
Partition inventory (EU has 2, US has 3, no sharing)
Use coordination for critical operations
Model as reservations rather than immediate decrements

CRDTs Are Not Always-Available Coordination

CRDTs trade off expressiveness for availability. They work best for accumulating/growing data: likes, page views, tag collections, text documents. They struggle with bounded resources and strong invariants. Don't force a CRDT where strong consistency is actually needed.

When to Use CRDTs

CRDTs excel in specific scenarios. This decision framework helps choose between CRDTs and other strategies.

CRDT Decision Framework
Scenario	Best Approach	Reasoning
Like/view counters	✅ CRDT (PN-Counter)	Accumulating, no invariants, high frequency
Shopping cart	✅ CRDT (OR-Set)	Add/remove, eventual accuracy OK
Collaborative document	✅ CRDT (Text/JSON)	Real-time sync, merge needed
User profile	⚠️ LWW often sufficient	Single writer, conflicts rare
Inventory stock	❌ Strong consistency	Invariant: stock ≥ 0 required
Bank balance	❌ Strong consistency	Invariant: no overdraft without approval
Feature flags	⚠️ LWW or versioned config	Admin-controlled, conflicts rare
Comment threads	✅ CRDT (RGA/Yjs)	Append-heavy, ordering matters

CRDTs Are A Good Fit When:

•Data is additive/accumulating (counters, sets, logs)
•No hard invariants that can't be violated temporarily
•High conflict frequency makes coordination expensive
•Offline-first or edge computing scenarios
•Real-time collaboration is core to UX
•Data types map cleanly to CRDT primitives

Consider Alternatives When:

•Invariants must be enforced (bounded resources)
•Operations are conditional (read-modify-write patterns)
•Metadata overhead is unacceptable for data size
•Simple LWW semantic is actually what you need
•Team lacks CRDT expertise for debugging
•Cross-object transactions are required

Summary: Conflict-free Replicated Data Types

CRDTs represent a paradigm shift: instead of resolving conflicts after they occur, we use data structures that mathematically cannot conflict. This enables true eventual consistency without coordination. Let's consolidate the key insights:

Key Takeaways

•Mathematical foundation — CRDTs are built on join-semilattices. Merge is commutative, associative, and idempotent, guaranteeing convergence.
•Two flavors — State-based syncs full state (simple, tolerant); operation-based syncs ops (efficient, requires reliable delivery).
•Common types — G-Counter, PN-Counter for counts; G-Set, OR-Set for collections; LWW-Register, MV-Register for single values; Text CRDTs for documents.
•Production-proven — Redis Enterprise, Riak, Figma, Yjs, Automerge all use CRDTs in production.
•Cannot enforce invariants — CRDTs can't guarantee constraints like 'quantity ≥ 0'. Bounded resources need coordination.
•Tradeoff: expressiveness for availability — CRDTs work for accumulated data; struggle with conditional operations and transactions.
•Use when appropriate — Counters, sets, collaborative docs benefit. Inventory, banking need stronger guarantees.

Module Complete:

You have now explored the full spectrum of conflict resolution strategies in distributed systems:

Write Conflicts — Understanding why conflicts occur
Last-Write-Wins — Simple, lossy, appropriate for many use cases
Vector Clocks — Detecting true concurrency for informed resolution
Application-Level Merge — Domain-specific, semantic resolution
CRDTs — Conflict-free by construction

Armed with this knowledge, you can choose the right strategy for each data type in your distributed system—balancing availability, consistency, complexity, and correctness.

Module Complete

You have mastered conflict resolution strategies in distributed systems. From simple LWW to sophisticated CRDTs, you now have the theoretical foundation and practical patterns to handle data conflicts correctly. The next chapter will explore distributed data patterns that build on these concepts.