Design a Collaborative Editor

Operational transforms against CRDTs, where the presence layer belongs, and what offline editing actually costs you.

SyntaxY.applyUpdate(ydoc, update: Uint8Array, [transactionOrigin]) / Y.encodeStateAsUpdate(ydoc, [encodedTargetStateVector]): Uint8Array

Two people typing in the same paragraph is a concurrency problem with no lock to take. There are two families of answer, and the choice between them decides how much server you need.

Operational transformation

An operation is positional — insert "x" at 7, delete 3 characters at 12 — and is sent tagged with the revision it was written against. A central server holds the operation log, transforms each incoming operation over everything committed since that revision, and broadcasts the result. The payloads are tiny, the stored document is just text plus a revision number, and the server is authoritative, so it can validate and reject. The cost is that the transform function must handle every pair of operation types, which is where rich text, tables and comments get painful, and the server is not optional: the correctness lives in it.

CRDTs

Each inserted character gets a stable identifier, and merge is commutative, associative and idempotent: apply the same updates in any order, or twice, and replicas converge. Yjs implements YATA, Automerge implements an RGA-style sequence. No central transform is needed, so peers can sync directly and a replica can be offline for a week and still merge.

What offline costs

Identifiers and tombstones are per-character metadata that outlive deleted text until garbage collection, so an old document is larger than its text. Convergence is not intention: two people typing at the same position converge on something, and sequence CRDTs can interleave their words. And because merges happen on the client, per-operation authorisation is not available — permissions are per document.

Cursors and selections belong on a separate ephemeral channel. They are state, not history, and nobody wants them in the saved file.

Example

Example · javascript
import * as Y from 'yjs';
import { Awareness } from 'y-protocols/awareness';

const doc = new Y.Doc();

const text = doc.getText('body');        // shorthand
// const text = doc.get('body', Y.Text); // the longhand it is equivalent to

text.insert(0, 'Hello');                 // insert(index, content [, format])
text.format(0, 5, { bold: true });       // format(index, length, attributes)

// Group related edits so collaborators and the undo stack see one change, not
// three. Everything inside runs as a single transaction and emits one update.
Y.transact(doc, () => {
  text.delete(0, 5);
  text.insert(0, 'Goodbye');
}, 'local');

// Edits leave as binary updates. applyUpdate is commutative and idempotent:
// apply them in any order, or twice, and every replica converges to the same
// document - which is why the transport can be lossy and unordered.
doc.on('update', (update, origin) => {
  if (origin !== 'remote') transport.send(update);   // do not echo what we received
});
transport.on('message', (update) => Y.applyUpdate(doc, update, 'remote'));

// Cursors are NOT in the document. They live in an awareness channel that is
// dropped when the connection goes, and they are stored as relative positions
// so a remote insert before the caret does not move it.
const awareness = new Awareness(doc);

function publishCursor(index) {
  const rel = Y.createRelativePositionFromTypeIndex(text, index);
  // Encode to bytes: awareness state is serialised, and a RelativePosition is
  // an object graph, not a number.
  awareness.setLocalStateField('cursor', {
    anchor: Array.from(Y.encodeRelativePosition(rel)),
    user: { name: 'Priya', colour: '#4c7' },
  });
}

function renderRemoteCursors() {
  for (const [clientId, state] of awareness.getStates()) {
    if (clientId === doc.clientID || !state.cursor) continue;
    const rel = Y.decodeRelativePosition(Uint8Array.from(state.cursor.anchor));
    const abs = Y.createAbsolutePositionFromRelativePosition(rel, doc);
    // abs is null when the anchored character has been deleted by someone else:
    // that caret has no valid home, so draw nothing rather than guessing index 0.
    if (abs) drawCaret(abs.index, state.cursor.user);
  }
}

When to use it

  • Choosing OT or a CRDT for an editor that has to keep working on a plane.
  • Adding live cursors and selections without putting them in the saved document.
  • Explaining why a shared document file keeps growing after text has been deleted.
  • Deciding whether per-paragraph or per-field permissions are possible once merges happen on the client.

More examples

The OT server loop, where the correctness actually lives

This is the whole OT argument in one function. You get small positional operations and a plain-text document, and in exchange the transform matrix grows with the square of your operation types and a client can never merge with a peer on its own. Reach for OT when a server is already mandatory - because it enforces permissions, runs validation or stores the only copy - and when the document model is small enough that the transform pairs stay reviewable.

Example · javascript
// Operational transformation, server side. The server IS the order of truth:
// each client op arrives tagged with the revision it was written against, and
// the server rebases it over everything committed since.
const history = [];   // committed ops; array index == revision number

function receive(op, baseRevision) {
  let rebased = op;
  for (const committed of history.slice(baseRevision)) {
    rebased = transform(rebased, committed);
  }
  history.push(rebased);
  broadcast(rebased, history.length);  // clients ack this revision
  return history.length;
}

// Transform a against an already-committed b, for a text document with two
// operation types. The pair count is the problem: adding one op type means
// writing its transform against every existing type.
function transform(a, b) {
  if (a.type === 'insert' && b.type === 'insert') {
    // Tie at the same index is broken deterministically, so every replica that
    // applies these two ops ends up with the same string.
    const before = b.index < a.index || (b.index === a.index && b.clientId < a.clientId);
    return before ? { ...a, index: a.index + b.text.length } : a;
  }
  if (a.type === 'insert' && b.type === 'delete') {
    if (b.index + b.length <= a.index) return { ...a, index: a.index - b.length };
    if (b.index >= a.index) return a;
    return { ...a, index: b.index };          // our anchor was inside the deletion
  }
  if (a.type === 'delete' && b.type === 'insert') {
    return b.index <= a.index ? { ...a, index: a.index + b.text.length } : a;
  }
  // delete/delete: clip a to whatever b left behind.
  const start = Math.max(a.index, b.index);
  const end = Math.min(a.index + a.length, b.index + b.length);
  const overlap = Math.max(0, end - start);
  const index = b.index < a.index ? a.index - Math.min(a.index - b.index, b.length) : a.index;
  return { ...a, index, length: a.length - overlap };
}

Syncing a client that was offline for a week

Shows why a CRDT is the usual pick for offline-first: the merge needs no server and no knowledge of what happened in between, so the reconnect path is the same code as the live path. It also shows where the cost sits - the state vector grows with the number of distinct clients that have ever edited, which is why ephemeral or per-session client ids are a bad idea in a long-lived document.

Example · javascript
// A week offline must not mean replaying a week of operations. Each side sends
// a compact state vector describing what it already has; the peer answers with
// exactly the difference. This is the y-protocols sync handshake.

// Step 1: "here is what I have" - a few bytes per contributing client, not per edit.
socket.send(encode({ type: 'sync-step-1', sv: Y.encodeStateVector(doc) }));

// Step 2 (peer): compute only the updates the other side is missing.
socket.on('sync-step-1', (msg) => {
  socket.send(encode({ type: 'sync-step-2', update: Y.encodeStateAsUpdate(doc, msg.sv) }));
  // Ask for our own missing half in the same round trip; sync is symmetric.
  socket.send(encode({ type: 'sync-step-1', sv: Y.encodeStateVector(doc) }));
});

socket.on('sync-step-2', (msg) => Y.applyUpdate(doc, msg.update, 'remote'));

// Local persistence is the other half of offline: edits made with no socket go
// to IndexedDB as updates and are merged on reconnect by the same code path.
const pending = [];
doc.on('update', (update, origin) => {
  if (origin === 'remote') return;
  if (socket.readyState === WebSocket.OPEN) socket.send(encode({ type: 'update', update }));
  else pending.push(update);          // same bytes, sent later, merged identically
});

Authorisation and compaction, the two things the CRDT does not give you

These are the two operational surprises after a CRDT editor ships. Permissions become document-shaped, so a requirement like "this reviewer may only edit the comments" needs a separate document rather than a rule inside one; and the update log grows without bound unless something compacts it, which is a scheduled job you have to write. Reach for both before launch - retrofitting a split document model later is a migration.

Example · javascript
// A relay server for a CRDT cannot inspect an update meaningfully, so access
// control is per document and happens before the socket is joined - not per op.
server.on('connection', async (socket, req) => {
  const user = await authenticate(req);
  const role = await acl.roleFor(user.id, req.params.docId);   // 'editor' | 'viewer' | none
  if (!role) return socket.close(4403, 'forbidden');

  // A viewer is enforced by refusing to relay their updates, because the
  // document itself has no concept of who wrote which character.
  socket.on('message', (data) => {
    if (role !== 'editor') return;
    room.broadcast(data, socket);
    room.persist(data);
  });
});

// Compaction: the stored history is the sum of every update ever applied.
// Periodically collapse it into one update so loading a two-year-old document
// does not mean replaying two years of keystrokes.
async function compact(docId) {
  const doc = new Y.Doc();
  for (const update of await store.listUpdates(docId)) Y.applyUpdate(doc, update);
  // encodeStateAsUpdate with no state vector returns the whole document as one
  // update, with tombstones garbage-collected where it is safe to do so.
  await store.replaceUpdates(docId, Y.encodeStateAsUpdate(doc));
}

Related

sd consistency modelssd cap pacelcsd idempotencysd clockssd design chat

Discussion

  • Be the first to comment on this lesson.