CRDT for conflict-free data synchronization in mobile app

Implementing CRDT for Conflict-free Synchronization in Mobile Applications

CRDT (Conflict-free Replicated Data Types) mathematically guarantee that any two replicas of one document, receiving same operations in any order, reach identical state. Without coordinating server. Without manual conflict resolution.

For mobile applications this especially valuable: user edits offline (metro), syncs at home (online), partner did same thing — merge happens automatically and deterministically.

What CRDT Is in Practice

Not one algorithm, but family of data structures. Each solves own task:

• G-Counter — counter that only grows. Merge = max per node.
• LWW-Register (Last-Write-Wins) — single value, last by timestamp wins. For individual fields (document name, status).
• OR-Set (Observed-Remove Set) — set with add and remove. Solves "deleted but partner added simultaneously" through unique tags per add operation.
• RGA (Replicated Growable Array) — array with insert/delete. Basis for text CRDT.
• YATA (Yet Another Transformation Approach) — Y.js algorithm, RGA variant.

Y.js: Detailed Breakdown

Y.js — most mature CRDT implementation for JavaScript/TypeScript. Uses YATA algorithm for YText and YArray, LWW for YMap.

Internal YText structure: linked list of elements (Item), each with id: {client, clock}. client — unique clientID (uint32, generated on Y.Doc creation). clock — logical clock, monotonically grows per client. Merging two YDoc = combining all Item with deterministic order on conflicts (smaller clientID first on same logical time).

Key: operation never lost. Even if insert happened offline on one device and other simultaneously deleted text around — insert applies, may end up in "empty" place, but won't lose.

Sync Providers in Y.js

Y.js — algorithm only. Transport — separate provider:

For mobile application: y-websocket for online sync + custom provider for SQLite (device persistence). No ready y-sqlite for React Native — implement via Y.encodeStateAsUpdate() and Y.applyUpdate() with react-native-sqlite-storage storage.

// Save to SQLite on each change
ydoc.on('update', (update, origin) => {
  if (origin !== 'sqlite') {  // don't save changes from SQLite
    const state = Y.encodeStateAsUpdate(ydoc);
    db.executeSql('INSERT OR REPLACE INTO docs (id, state) VALUES (?, ?)',
      [docId, Buffer.from(state).toString('base64')]);
  }
});

// Load on opening document
const [result] = await db.executeSql('SELECT state FROM docs WHERE id = ?', [docId]);
if (result.rows.length > 0) {
  const state = Buffer.from(result.rows.item(0).state, 'base64');
  Y.applyUpdate(ydoc, new Uint8Array(state), 'sqlite');
}

Automerge: Y.js Alternative

Automerge — CRDT library with different approach: document — JSON object with deep merge semantics. Automerge 2.x rewritten in Rust, compiled to WASM — performance order of magnitude better than first version.

For React Native: @automerge/automerge works via WASM in JSC/Hermes. On Hermes — need to verify WASM support (recent RN Hermes versions support WASM but not all builds).

Automerge advantage over Y.js: data schema — regular JSON, not special types. Minus: Y.js more actively maintained, more sync providers.

Vector Clocks and Conflict Detection

Y.js automatically tracks stateVector — map of {clientId: maxClock}. On syncing two replicas:

1. Exchange stateVector.
2. Request Y.encodeStateAsUpdateV2(ydoc, remoteStateVector) — delta from what remote side doesn't know.
3. Apply received delta via Y.applyUpdateV2().

Efficient sync without sending entire document. On reconnect after offline: send own stateVector, get only missing changes.

Convergence: What Guarantees, What Doesn't

CRDT guarantees Strong Eventual Consistency: if all replicas received same operations — converge to identical state.

Doesn't guarantee: semantic correctness. If user A renamed file to "Report Q1" and user B simultaneously deleted it — CRDT may restore file with new name. Mathematically correct (add wins over remove in OR-Set), but semantically unexpected for user.

Solution: UX layer showing user conflict and its auto-resolution. Don't break work, but give info.

Performance with Large Documents

Y.js lazy-loads document structure: parts not requested aren't decoded. For 1MB+ documents — important. Y.Doc with gc: true (default) auto-removes tombstones of deleted elements, compacting history.

With heavy edits history grows. Y.encodeStateAsUpdate() contains all changes since creation. Compaction via Y.encodeStateAsUpdate(ydoc, emptyStateVector) — snapshot of current state without history. For offline applications: store snapshot + delta after snapshot.

Assessment

CRDT sync via Y.js for text/JSON documents in React Native — 6–10 weeks (including persistence, reconnect logic, conflict awareness UI). For Flutter via Dart bindings to Y.js (via JS runtime) or native CRDT — 10–16 weeks. Automerge 2 on Rust FFI for native platforms — 12–20 weeks.