CRDT: Conflict-Free Replicated Data Types

What is a CRDT?

CRDT stands for Conflict-free Replicated Data Type - a data structure that can be replicated across multiple peers and automatically resolves conflicts without coordination. GUN uses CRDTs to ensure that when multiple peers modify data simultaneously (especially while offline), they can eventually converge to the same state without manual conflict resolution.

// Two peers write simultaneously
gunA.get('counter').put(5); // Peer A
gunB.get('counter').put(7); // Peer B at the same time

// No conflict! Both peers eventually converge to: 7
// The write with the higher timestamp wins

CRDTs enable strong eventual consistency - all replicas that have received the same updates will have the same state.

Why CRDTs Matter

The Problem: Distributed Conflicts

In distributed systems, conflicts are inevitable:

// Alice edits from her phone (offline)
gun.get('doc').put({title: 'Alice version'});

// Bob edits from his laptop (offline)  
gun.get('doc').put({title: 'Bob version'});

// Both come online - now what?
// Without CRDTs: ❌ Conflict error, manual resolution needed
// With CRDTs: ✅ Automatic resolution, no intervention needed

Traditional Approaches (Don’t Work)

Last Write Wins

❌ Unreliable - clock skew ❌ Loses data arbitrarily

Manual Merge

❌ Requires user intervention ❌ Doesn’t scale

Locking

❌ Requires coordination ❌ Doesn’t work offline

CRDTs

✅ Automatic resolution ✅ Works offline ✅ Mathematically proven

GUN’s CRDT Implementation

GUN implements state-based CRDTs using vector clocks (timestamps). The implementation is in src/state.js:

function State(){
  var t = +new Date;
  if(last < t){
    return N = 0, last = t + State.drift;
  }
  return last = t + ((N += 1) / D) + State.drift;
}

Every write gets a state vector - a high-resolution timestamp:

{
  '_': {
    '#': 'user',           // Soul (node ID)
    '>': {                 // State vector
      'name': 1234567890.001,  // Timestamp for 'name' key
      'age': 1234567890.002    // Timestamp for 'age' key  
    }
  },
  'name': 'Alice',
  'age': 30
}

State Vector Structure

From src/state.js:18:

State.ify = function(n, k, s, v, soul){ 
  (n = n || {})._ = n._ || {};
  if(soul){ n._['#'] = soul }
  var tmp = n._['>'] || (n._['>'] = {});
  if(u !== k && k !== '_'){
    if('number' == typeof s){ tmp[k] = s } // Add state
    if(u !== v){ n[k] = v } // Add value
  }
  return n;
}

Each field gets its own timestamp, not the whole document:

gun.get('user').put({name: 'Alice'}); // Time: 1000
// State: {name: 1000}

gun.get('user').put({age: 30}); // Time: 2000  
// State: {name: 1000, age: 2000}

// Fields have independent state vectors!

How Conflict Resolution Works

Rule: Higher Timestamp Wins

GUN uses Last-Write-Wins (LWW) semantics based on state vectors:

// Peer A writes at time 1000
gunA.get('x').put('A');
// State: {x: 1000}

// Peer B writes at time 1001
gunB.get('x').put('B');
// State: {x: 1001}

// When peers sync:
// 1001 > 1000, so 'B' wins
// Both converge to: 'B'

Per-Field Resolution

Conflicts are resolved per field, not per document:

// Peer A writes at time 1000
gunA.get('user').put({
  name: 'Alice',
  age: 25
});
// State: {name: 1000, age: 1000}

// Peer B writes at time 2000
gunB.get('user').put({
  name: 'Bob'
});
// State: {name: 2000}

// After sync, merged state:
{
  name: 'Bob',   // 2000 > 1000, B's write wins
  age: 25        // No conflict, A's age kept
}
// State: {name: 2000, age: 1000}

This per-field CRDT allows concurrent updates to different fields without conflicts.

Deduplication

From src/state.js:13, GUN checks states before accepting updates:

State.is = function(n, k, o){ 
  var tmp = (k && n && n._ && n._['>']) || o;
  if(!tmp){ return }
  return ('number' == typeof (tmp = tmp[k]))? tmp : -Infinity;
}

If incoming state ≤ current state, the update is ignored:

// Current state: {name: 2000}
gunA.get('user').get('name').put('Alice'); // State: 2000

// Receive update with older state: {name: 1000}
// 1000 < 2000, IGNORE

// Receive update with newer state: {name: 3000}
// 3000 > 2000, ACCEPT

State Synchronization

When peers sync, they exchange state vectors:

Sync Protocol

// Peer A has:
{
  '#': 'user',
  name: 'Alice',
  age: 25,
  _: {'>': {name: 1000, age: 1000}}
}

// Peer B has:
{
  '#': 'user', 
  name: 'Bob',
  city: 'NYC',
  _: {'>': {name: 2000, city: 1500}}
}

// After sync, both have:
{
  '#': 'user',
  name: 'Bob',      // max(1000, 2000) = 2000
  age: 25,          // Only on A, kept
  city: 'NYC',      // Only on B, kept
  _: {'>': {name: 2000, age: 1000, city: 1500}}
}

Merge Algorithm

From the source, merging is field-by-field:

function merge(nodeA, nodeB) {
  const merged = {_: {'#': nodeA._['#'], '>': {}}};
  const stateA = nodeA._['>'];
  const stateB = nodeB._['>'];
  
  // All keys from both nodes
  const keys = new Set([...Object.keys(stateA), ...Object.keys(stateB)]);
  
  for(let key of keys) {
    const timeA = stateA[key] || -Infinity;
    const timeB = stateB[key] || -Infinity;
    
    if(timeA > timeB) {
      merged[key] = nodeA[key];
      merged._['>'][key] = timeA;
    } else if(timeB > timeA) {
      merged[key] = nodeB[key];
      merged._['>'][key] = timeB;
    } else {
      // Equal timestamps - both have same value
      merged[key] = nodeA[key];
      merged._['>'][key] = timeA;
    }
  }
  
  return merged;
}

High-Resolution Timestamps

From src/state.js:5-9, GUN generates sub-millisecond timestamps:

var N = 0, D = 999;

function State(){
  var t = +new Date;
  if(last < t){
    return N = 0, last = t + State.drift;
  }
  return last = t + ((N += 1) / D) + State.drift;
}

This allows multiple writes per millisecond with deterministic ordering:

// Millisecond 1234567890:
State(); // Returns: 1234567890.000
State(); // Returns: 1234567890.001
State(); // Returns: 1234567890.002
// ... up to 999 writes per millisecond

// Next millisecond 1234567891:
State(); // Returns: 1234567891.000

GUN can handle 999 writes per millisecond on a single peer without timestamp collisions.

Clock Skew and Drift

The Problem

Different devices have different clocks:

// Phone clock: 1000 (behind by 10 seconds)
gunPhone.get('x').put('phone');

// Laptop clock: 1010 (ahead by 10 seconds)
gunLaptop.get('x').put('laptop');

// Laptop write always wins due to clock skew!

GUN’s Solution: Drift Adjustment

State.drift = 0; // From src/state.js:11

// Adjust drift based on peer clocks
function adjustDrift(peerTime, localTime) {
  const diff = peerTime - localTime;
  if(Math.abs(diff) > 1000) { // > 1 second skew
    State.drift += diff * 0.1; // Gradually adjust
  }
}

GUN gradually adjusts timestamps to converge peer clocks.

Large clock skew (hours/days) can cause issues. Ensure devices have reasonably synchronized clocks (NTP recommended).

CRDT Guarantees

GUN’s CRDT implementation provides:

1. Eventual Consistency

// All peers eventually converge to same state
gunA.get('x').put('A');
gunB.get('x').put('B');

// After sync, both have same value
gunA.get('x').once(x => console.log(x)); // 'B'
gunB.get('x').once(x => console.log(x)); // 'B'

2. Commutativity

// Order of applying updates doesn't matter
// Peer A receives: [update1, update2]
// Peer B receives: [update2, update1]
// Both converge to same state

3. Associativity

// Grouping of updates doesn't matter  
// (A + B) + C === A + (B + C)

4. Idempotence

// Applying same update multiple times = applying once
gun.get('x').put('A'); // State: 1000
gun.get('x').put('A'); // State: 1000 (ignored, same value)

Limitations

1. Last-Write-Wins Semantics

GUN uses LWW-Register CRDT, which means:

// Both writes valid, but one is lost
gunA.get('counter').put(5);
gunB.get('counter').put(7);

// Result: 7 (not 12!)
// The write with higher timestamp wins, other is discarded

For counters, use custom CRDT logic or operational transforms. LWW-Register may lose data.

2. Tombstones

Deleting data requires tombstones:

// Delete by setting to null
gun.get('user').put(null);

// Internally stored as:
{
  _: {'>': {':': 1234567890}},
  ':': null // Tombstone
}

// Tombstones remain forever (garbage collection needed)

3. Causal Consistency

GUN doesn’t guarantee causal order:

// Peer A:
gun.get('x').put('A'); // Time: 1000
gun.get('y').put('B'); // Time: 1001, depends on x

// Peer B might receive out of order:
// y=B (1001) arrives before x=A (1000)
// Causality not preserved

For causal consistency, use version vectors (not implemented in GUN core).

Advanced: Custom CRDTs

You can implement custom CRDT logic:

Counter CRDT

// Instead of LWW, use increment-only counter
function increment(path) {
  gun.get(path).once(counter => {
    const current = counter || 0;
    gun.get(path).put(current + 1);
  });
}

// Better: Store per-peer counters
function incrementCounter(counterId, peerId) {
  gun.get(counterId).get(peerId).once(count => {
    gun.get(counterId).get(peerId).put((count || 0) + 1);
  });
}

// Sum across peers
function getCounter(counterId, callback) {
  let sum = 0;
  gun.get(counterId).map().once((count, peerId) => {
    sum += count;
    callback(sum);
  });
}

Set CRDT

// GUN's .set() is already a grow-only set CRDT
gun.get('tags').set('javascript');
gun.get('tags').set('database');
gun.get('tags').set('p2p');

// Elements can be added but not removed (grow-only)
// To remove, use tombstones
gun.get('tags').get(elementId).put(null);

Best Practices

Design for eventual consistency

Don’t assume immediate consistency. Design UIs that show “syncing” states.

Use per-field updates

Update fields individually to minimize conflicts.

// Good: Per-field
gun.get('user').get('name').put('Alice');
gun.get('user').get('age').put(30);

// Bad: Whole object (overwrites other fields)
gun.get('user').put({name: 'Alice'});

Avoid counters with LWW

Use custom counter CRDT or operational transforms for counters.

Handle clock skew

Ensure devices have synchronized clocks (NTP).

Debugging CRDTs

Inspect State Vectors

gun.get('user').once(user => {
  console.log('Data:', user);
  console.log('State:', user._['>']);
});

// Output:
// Data: {name: 'Alice', age: 30}
// State: {name: 1234567890.001, age: 1234567890.002}

Track Conflicts

gun.on('in', function(msg){
  if(msg.put) {
    const soul = msg.put['#'];
    const key = msg.put['.'];
    const state = msg.put['>'];
    const value = msg.put[':'];
    
    console.log(`Update: ${soul}.${key} = ${value} @ ${state}`);
  }
});

Performance

State overhead: ~16 bytes per field (timestamp)
Merge cost: O(fields) per node
Memory: Minimal, states stored with data
Network: States sent with every update (+~16 bytes/field)

GUN’s CRDT overhead is minimal. The trade-off for automatic conflict resolution is worth it in most distributed applications.

​What is a CRDT?

​Why CRDTs Matter

​The Problem: Distributed Conflicts

​Traditional Approaches (Don’t Work)

Last Write Wins

Manual Merge

Locking

CRDTs

​GUN’s CRDT Implementation

​State Vector Structure

​How Conflict Resolution Works

​Rule: Higher Timestamp Wins

​Per-Field Resolution

​Deduplication

​State Synchronization

​Sync Protocol

​Merge Algorithm

​High-Resolution Timestamps

​Clock Skew and Drift

​The Problem

​GUN’s Solution: Drift Adjustment

​CRDT Guarantees

​1. Eventual Consistency

​2. Commutativity

​3. Associativity

​4. Idempotence

​Limitations

​1. Last-Write-Wins Semantics

​2. Tombstones

​3. Causal Consistency

​Advanced: Custom CRDTs

​Counter CRDT

​Set CRDT

​Best Practices

​Debugging CRDTs

​Inspect State Vectors

​Track Conflicts

​Performance

​Further Reading

​Next Steps

Graph Database

API Reference

What is a CRDT?

Why CRDTs Matter

The Problem: Distributed Conflicts

Traditional Approaches (Don’t Work)

GUN’s CRDT Implementation

State Vector Structure

How Conflict Resolution Works

Rule: Higher Timestamp Wins

Per-Field Resolution

Deduplication

State Synchronization

Sync Protocol

Merge Algorithm

High-Resolution Timestamps

Clock Skew and Drift

The Problem

GUN’s Solution: Drift Adjustment

CRDT Guarantees

1. Eventual Consistency

2. Commutativity

3. Associativity

4. Idempotence

Limitations

1. Last-Write-Wins Semantics

2. Tombstones

3. Causal Consistency

Advanced: Custom CRDTs

Counter CRDT

Set CRDT

Best Practices

Debugging CRDTs

Inspect State Vectors

Track Conflicts

Performance

Further Reading

Next Steps