CRDTs (Conflict-free Replicated Data Types)

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

## The Tombstone Problem Illustrated
 
Timeline without proper tombstone retention:
 
Time ──────────────────────────────────────────────────────────▶
 
Replica A:  add(X)         remove(X)      (garbage collect A:1)
            {X: {A:1}}  →  {X: ∅}     →   {}
                 │                              │
                 │         Network delay        │
                 └────────────────────────────▶│
                                               │
Replica B:                 (receives add)      ▼
            {}         →   {}             →   {X: {A:1}} ← RESURRECTION!        
 
The add message arrived AFTER the tombstone was garbage collected.
B has no way to know the element was deleted.
 
## Storage Growth Over Time
 
Without GC:  Tombstones accumulate forever
             
    Storage
        │                                    ╱
        │                               ╱
        │                          ╱
        │                     ╱
        │                ╱
        │           ╱
        │      ╱            Tombstones
        │ ╱
        └─────────────────────────────────▶ Time
        
In text CRDTs: Every deleted character becomes a tombstone.
A document with 100K edits might have 500KB visible text
but 50MB of tombstones from deleted content.

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

/**
 * Analyzing CRDT Metadata Overhead
 */
 
// Example: Text CRDT storage efficiency
interface RGAChar {
  id: { replica: string; seq: number };  // ~24 bytes
  after: { replica: string; seq: number } | null;  // ~24 bytes
  char: string;  // ~2 bytes (UTF-16)
  deleted: boolean;  // 1 byte
}
// Total: ~51 bytes per character (vs 2 bytes for raw character)
 
// For a 1000-word document (~5000 chars):
const rawTextSize = 5000 * 2;  // 10 KB
const rgaSize = 5000 * 51;     // 255 KB
const overhead = rgaSize / rawTextSize;  // 25.5x overhead!
 
// And that's BEFORE tombstones from deleted text
 
// Example: OR-Set overhead
interface ORSetElement<T> {
  value: T;
  tags: Set<string>;  // Each tag ~24 bytes (replicaId:seq)
}
 
// A set with 1000 elements, each added once:
// Tags: 1000 × 24 bytes = 24 KB just for tags
// If elements are re-added/removed: tags accumulate
 
// Example: Vector clock scaling
interface VectorClock {
  entries: Map<string, number>;
}
 
// With 100 replicas and 1000 MV-Register values:
// Each value tracks: 100 entries × 8 bytes = 800 bytes
// Total: 1000 values × 800 bytes = 800 KB just for clocks
 
function estimateOverhead(scenario: {
  crdtType: string;
  elementCount: number;
  replicaCount: number;
  averageEditsPerElement: number;
}): { dataSize: number; metadataSize: number; ratio: number } {
  const { crdtType, elementCount, replicaCount, averageEditsPerElement } = scenario;
  
  const estimates: Record<string, (s: typeof scenario) => { data: number; meta: number }> = {
    'G-Counter': s => ({
      data: 8,  // Single number
      meta: s.replicaCount * 8,  // Counter per replica
    }),
    'OR-Set': s => ({
      data: s.elementCount * 8,  // Assuming 8-byte elements
      meta: s.elementCount * s.averageEditsPerElement * 24,  // Tags
    }),
    'Text-RGA': s => ({
      data: s.elementCount * 2,  // Characters
      meta: s.elementCount * s.averageEditsPerElement * 50,  // ID + refs + tombstones
    }),
  };
  
  const estimator = estimates[crdtType];
  if (!estimator) return { dataSize: 0, metadataSize: 0, ratio: 0 };
  
  const result = estimator(scenario);
  return {
    dataSize: result.data,
    metadataSize: result.meta,
    ratio: result.meta / result.data,
  };
}
 
// Real-world estimate: Collaborative document
const docEstimate = estimateOverhead({
  crdtType: 'Text-RGA',
  elementCount: 50000,  // 50K characters
  replicaCount: 10,
  averageEditsPerElement: 2,  // Some chars inserted then deleted
});
 
console.log('Document overhead ratio:', docEstimate.ratio);  // High!

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

## Why Some Operations Can't Be CRDTs
 
### The Commutativity Requirement
 
For operations A and B, they must commute:
  apply(apply(state, A), B) = apply(apply(state, B), A)
 
Increment commutes:      (5 + 1) + 2 = (5 + 2) + 1 = 8  ✓
Set-to-value doesn't:    set(set(_, 1), 2) ≠ set(set(_, 2), 1)  ✗
                         Final is 2 or 1 depending on order
 
### The Negative Test Problem
 
Consider: "add X if X not in set"
 
Replica A: sees {Y, Z}, adds X  → {Y, Z, X}
Replica B: sees {Y, Z}, adds X  → {Y, Z, X}
 
After merge: {Y, Z, X} — seems fine?
 
But what if:
Replica A: sees {Y}, adds X     → {Y, X}
Replica B: sees {Y, X}, skips   → {Y, X}
Replica C: sees {Y}, adds X     → {Y, X, X_tag2}
 
Did we want duplicate adds of X? The "check if not present"
is inherently racy without coordination.
 
### The Global Constraint Problem
 
Invariant: "Total inventory ≤ 100"
 
Replica A: inventory=90, sells 8  → inventory=82  ✓
Replica B: inventory=90, sells 15 → inventory=75  ✓
 
After merge: sold 23 items with only 10 available!
 
Global constraints require global coordination.
CRDTs cannot enforce cross-replica invariants.

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

## Debugging Eventual Consistency
 
### The Classic Bug Report
 
User: "My document shows different content on two devices!"
 
Is it:
a) Normal eventual consistency lag (wait and it'll sync)
b) Network partition preventing sync
c) Bug in merge function
d) State corruption
e) Clock skew causing wrong conflict resolution
 
### Debugging Checklist
 
1. CHECK VECTOR CLOCKS
   - Export vector clocks from both replicas
   - Compare: If one dominates, sync should resolve it
   - If concurrent (neither dominates), conflict resolution applies
   
   ReplicaA clock: {A: 47, B: 32, C: 15}
   ReplicaB clock: {A: 45, B: 35, C: 15}
   
   Concurrent! Neither has seen all of the other's updates.
   This is EXPECTED during partition.
 
2. CHECK SYNC STATUS
   - When did last successful sync occur?
   - Are there pending operations in queue?
   - Is network connectivity working?
   
   Last sync: 2 hours ago
   Pending ops: 156
   Network: WebSocket disconnected
   
   → Network issue, not bug
 
3. COMPARE MERGE INPUTS
   - Export state from both replicas
   - Run merge locally, verify output
   - Compare expected vs actual
   
   If merge(A, B) locally produces correct result
   but deployed doesn't, check for:
   - Different library versions
   - Serialization issues
   - Partial state due to interrupted sync
 
4. CHECK TOMBSTONES
   - Is an element missing that should exist?
   - Check tombstone set for that element
   - Verify add/remove ordering via operation log
   
   Element "X" missing even though user added it
   Tombstone found: {id: X, removed_by: B:42}
   
   → Another replica removed it. Intentional?
 
### Recommended Logging
 
Log on each sync:
- Local vector clock before/after
- Remote vector clock received
- Delta size (bytes, operation count)
- Merge duration (ms)
- State size after merge
 
Log on each operation:
- Operation type
- Affected element(s)
- Assigned unique ID/tag
- Local clock at operation time

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

/**
 * Performance Characteristics of CRDT Operations
 */
 
// Merge cost can dominate in high-sync scenarios
interface BenchmarkResult {
  operation: string;
  stateSize: number;
  duration: number;
  memoryUsed: number;
}
 
async function benchmarkORSetMerge(): Promise<BenchmarkResult[]> {
  const results: BenchmarkResult[] = [];
  
  for (const size of [1000, 10000, 100000]) {
    // Create two OR-Sets with 'size' elements each
    // Half overlapping, half unique
    
    const start = performance.now();
    const memBefore = process.memoryUsage().heapUsed;
    
    // Simulated merge (implementation omitted)
    // merge(setA, setB);
    
    const duration = performance.now() - start;
    const memAfter = process.memoryUsage().heapUsed;
    
    results.push({
      operation: 'OR-Set merge',
      stateSize: size,
      duration,
      memoryUsed: memAfter - memBefore,
    });
  }
  
  return results;
}
 
// Text CRDT insert complexity
// With tombstones, finding the right position requires
// traversing the internal structure
 
interface TextInsertBenchmark {
  documentSize: number;
  tombstoneRatio: number;  // % of chars deleted
  insertPosition: 'start' | 'middle' | 'end';
  duration: number;
}
 
// Worst case: insert at start of heavily-edited document
// Must traverse all tombstones to find position
 
// Optimization: Index structures (skip lists, B-trees)
// Trade O(n) traversal for O(log n) with O(n) extra space
 
/**
 * Real-world performance tips:
 * 
 * 1. Batch operations: Multiple local edits before sync
 * 2. Lazy value computation: Cache sum/count, invalidate on merge
 * 3. Incremental merge: For large states, don't recompute from scratch
 * 4. Background merge: Don't block UI on merge operations
 * 5. Throttle sync: Don't sync every keystroke; batch deltas
 */
 
const performanceTips = {
  syncThrottleMs: 50,  // Batch changes for 50ms
  mergeInWorker: true,  // Use Web Worker for merges
  cacheQueryResults: true,  // Don't recompute value() every render
  incrementalMerge: true,  // Only process new deltas
  compressWireFormat: true,  // Gzip for large syncs
};

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

## CRDT Production Mitigation Playbook
 
### 1. TOMBSTONE MANAGEMENT
 
Problem: Storage grows unboundedly with deletes
Solutions:
├── Implement periodic garbage collection
│   └── Coordinate checkpoint epochs across replicas
├── Use TTL-based pruning (with resurrection risk)
│   └── Document the assumption (e.g., "messages arrive within 7 days")
├── Snapshot-based compaction
│   └── Generate fresh state without tombstones periodically
└── Choose CRDTs without tombstones when possible
    └── G-Counter, G-Set, LWW-Register don't need tombstones
 
### 2. METADATA OVERHEAD
 
Problem: Storage overhead (10-50x for text CRDTs)
Solutions:
├── Use optimized binary encoding (Yjs > Automerge for size)
├── Enable compression for sync and storage
├── Match CRDT to actual requirements (minimal expressiveness)
├── Prune metadata for inactive replicas
└── Store derived/rendered views separately from CRDT state
 
### 3. SEMANTIC LIMITATIONS  
 
Problem: Can't express certain operations
Solutions:
├── Accept weaker semantics where business allows
├── Use hybrid architecture (CRDT + consensus)
├── Implement reservations for constrained resources
├── Partition data by owner to reduce conflicts
└── Document limitations for product team
 
### 4. OPERATIONAL COMPLEXITY
 
Problem: Hard to debug and monitor
Solutions:
├── Log vector clocks on every sync
├── Implement state export/comparison tools
├── Build dashboards for sync health metrics
├── Create runbooks for common issues
├── Practice incident response for consistency issues
└── Write property-based tests for merge correctness
 
### 5. PERFORMANCE
 
Problem: Merge operations can be slow
Solutions:
├── Batch multiple local operations before sync
├── Run merges in background threads
├── Cache computed values (invalidate on change)
├── Throttle sync frequency (e.g., every 50ms, not every keystroke)
├── Use incremental/delta merges when possible
└── Profile and optimize hot paths
 
### 6. LIBRARY CHOICE
 
Problem: Choosing the right library
Decision Framework:
├── Text collaboration? → Yjs (performance) or Automerge (rich types)
├── Multi-language needed? → Automerge (Rust core + bindings)
├── Database integration? → Riak or Redis Enterprise CRDTs
├── Simple counters/sets? → Consider implementing yourself
└── Performance critical? → Benchmark with real data patterns