Crdt basics

CRDT Basics for Mobile

Instructions

CRDTs (Conflict-free Replicated Data Types) let multiple replicas of data converge without coordination. They are powerful -- and often overkill. Know when to use them.

1. When CRDTs Help

Use CRDTs when all of these hold:

• Clients edit shared state offline or concurrently.
• Automatic, lossless merge is required (not just "good enough" LWW).
• The data shape fits an available CRDT (counter, set, map, ordered list, text).
• You can accept the storage overhead (CRDT metadata often 2–10x the raw data size).

Good fits:

• Collaborative text editing (notes, docs).
• Shared lists (to-do, shopping).
• Presence / cursor positions.
• Counters without exact-once semantics (reaction counts, views).

Poor fits:

• Money, inventory, reservations. Anything requiring a global invariant or strong consistency.
• Simple single-writer data with an authoritative server. Plain optimistic concurrency is cheaper.

2. Flavors

• State-based (CvRDT): replicas send full state; merge is a join. Simple but costly for large state.
• Operation-based (CmRDT): replicas send operations; requires reliable, exactly-once broadcast.
• Delta-state: middle ground; send small deltas that apply via join.

Most modern mobile libraries (Yjs, Automerge 2) are delta-state under the hood.

3. Libraries

• Yjs (JS/TS, with ports to Rust and iOS/Android bridges) -- mature, fast, excellent for text and structured docs.
• Automerge 2 (Rust core, JS/Swift/Kotlin bindings) -- strong API, slower writes than Yjs for large documents but simpler mental model.
• y-crdt (Rust port of Yjs) -- good for native mobile.
• Loro (Rust) -- newer, competitive performance.
• Build-your-own for simple types (G-Counter, OR-Set) when you do not need full documents.

Pick based on language bindings available on your mobile platform and the document shape.

4. Server Role

Even with CRDTs, a server is usually present to:

• Relay operations between replicas (the "sync server").
• Persist snapshots for new clients joining later.
• Authorize access, throttle bad actors, and enforce rate limits.

The server can be "dumb" (a pub/sub relay) or "smart" (validates ops, applies domain rules). For multi-tenant systems, "smart" is almost mandatory.

// Node/TS: Yjs server relay (pseudo)
const docs = new Map<string, Y.Doc>();
ws.on("connection", (conn, { docId, userId }) => {
  const doc = docs.get(docId) ?? load(docId);
  const awareness = new Awareness(doc);
  syncProtocol.readSyncMessage(conn, doc);      // initial handshake
  conn.on("message", buf => {
    // validate user can write
    Y.applyUpdate(doc, buf);
    broadcast(docId, buf, conn);                // fanout to peers
    scheduleSnapshotSave(docId);
  });
});

5. Storage

• Snapshot: a compacted state of the document.
• Updates: a log of encoded ops since the snapshot.
• Periodically compact: apply updates into a new snapshot, truncate the log.

Plan for 2–10x storage overhead vs plain JSON. Old peer metadata (tombstones) grows indefinitely unless you garbage-collect carefully.

6. Pitfalls

• Causality bugs: delivering an op before its dependencies causes subtle divergence. Use the library's transport; do not roll your own.
• Tombstone growth: every deleted element leaves a tombstone. Long-lived documents need periodic GC, which requires coordination.
• Identity: CRDTs identify elements by a (replica_id, counter) pair. If replica_id repeats (e.g., client reuses an id across reinstalls), divergence follows. Generate a fresh replica_id on first app launch and persist it.
• Large documents on slow devices: merging a 10 MB Yjs doc on a low-end Android can be slow. Shard documents (per chapter, per board).
• Binary format stability: the CRDT's binary encoding must not change between app versions without a migration plan.

7. Auth and Multi-Tenancy

• Sign every op with the user id; the server validates before relaying.
• Per-document ACLs; do not trust the client to enforce them.
• Rate-limit ops per user per document.
• For billed tenants, account for CRDT storage in the pricing model -- tombstones and history are real costs.

8. Mobile Integration Sketch

iOS (Swift + y-crdt via C bindings):

let doc = YDoc()
let text = doc.getText("body")
doc.observe { update in
  syncChannel.send(update)
}
syncChannel.onUpdate { update in
  doc.applyUpdate(update)
}

Android (Kotlin + y-crdt JNI):

val doc = YDoc()
val text = doc.getText("body")
doc.onUpdate { update -> syncChannel.send(update) }
syncChannel.setListener { update -> doc.applyUpdate(update) }

9. Degrade Gracefully

If the CRDT approach does not fit one endpoint, do not force it. Most apps use CRDTs for specific collaborative screens and plain REST + optimistic concurrency for the rest.

Checklist

• Use case verified (offline concurrent edits + lossless merge needed).
• Library chosen with bindings on both mobile platforms.
• Server role defined (relay vs authoritative).
• replica_id generated once per install and persisted.
• Snapshot + update log storage with periodic compaction.
• Tombstone GC strategy documented.
• Binary format versioning / migration plan in place.
• Authz and rate limiting applied at the relay.