11.13 — Collaborative Editing

Two people are looking at the word HELLO. Ana types ! at the end. At the same instant, Bo types ? at the end. A moment later Ana's screen reads HELLO?! and Bo's reads HELLO!?.

Both of them applied both edits. Neither made a mistake. Neither client dropped anything. And the two documents will now disagree forever, because every subsequent edit is built on a different foundation.

That is the entire problem of this study, and it is the hardest correctness problem in this Part. Every earlier study was about doing a lot of work quickly. This one is about two computers arriving at byte-identical answers with no lock, no "last save wins", and no lost keystrokes — which turns out to be a question about what an edit even means once the document it referred to has changed underneath it.

1. Requirements

Functional. Many people edit one document at the same time. Changes appear on other screens quickly. Live cursors and presence. Full version history with restore. Editing offline, merging on reconnect. Comments anchored to text that moves as the document changes.

Non-functional, with numbers.

• Remote edits visible within 200 ms.
• Strong eventual convergence: any two replicas that have seen the same set of operations display identical content. This is not a target, it is the definition of the system working.
• Intention preservation: after merging, an edit still means what the person meant. Convergence alone is not enough — two replicas agreeing on nonsense is still convergence.
• No data loss, ever.
• Documents up to about a million characters.

Out of scope today: the rendering engine, embedded media internals, and the permissions model beyond basic sharing.

The clarifying questions, and what each answer changes

"Is the content linear text, or a structure?" This decides the algorithm. A character sequence and a tree of objects with properties are different problems, and the technique that is simplest for one is painful for the other. The drill at the end works through the structured case.

"Does a server exist in this product anyway?" If yes — for accounts, sharing and storage — then one of the two families of solution gets its main prerequisite for free, and the other's main advantage buys nothing.

"How long can someone be offline and still merge?" Ten minutes and two weeks are different systems. One approach's merge cost grows with how much happened while you were away; the other's does not.

"Do we need every keystroke in the history, or named versions?" Keystroke-level history is powerful and it is also two terabytes a day at the volume in section 2. This is a retention decision with a real bill attached.

"What happens when someone deletes the text a comment is attached to?" Ask it early, because "the comment points at nothing" is a state the data model has to be able to express, and retrofitting it is unpleasant.

2. Estimation

Concurrency per document. The realistic extreme is 50 people editing one document; the common case is two or three. What that forces: not much. Fifty clients on one server is nothing. Scale here is the number of documents, not the concurrency within one, which is the opposite of most people's instinct and the reason this system shards trivially.

Operation rate. A person typing produces keystrokes faster than you want to send them, so a client coalesces them into an operation roughly every 200 ms — about 5 operations a second per active editor. With 1 million daily users and 5% editing at once, that is 50,000 active editors and ~250,000 operations a second across the fleet. What that forces: the coalescing itself. Without it, every keystroke is a message and the number is five times higher for no benefit — nobody can perceive the difference between a 200 ms and a 40 ms echo of somebody else's typing.

Broadcast volume. Each operation goes to the other clients on that document, averaging perhaps three, so ~750,000 outbound messages a second. What that forces: the connection tier from 11.7, reused unchanged. Nothing here is new.

Operation log growth. 250,000 operations a second × ~100 bytes = 25 MB a second ≈ 2 TB a day. What that forces: the log cannot be kept at full resolution forever. Snapshots plus compaction are not an optimisation, they are what makes the storage bill survivable — and the retention policy becomes a product decision about how fine-grained history needs to be, and for how long.

Document size and load time. A million-character document is about 1 MB of text plus formatting. Loading it by replaying every operation ever applied would mean replaying millions of them. What that forces: periodic snapshots, so a client loads the most recent snapshot plus the operations since. The snapshot cadence is a trade between storage and load time, and it is the thing you tune when opening a heavily edited document gets slow.

3. The protocol

The contract here is a small set of messages over a persistent connection, plus a couple of ordinary endpoints.

→ { "t":"op",   "docId":"d_44", "baseRev":118, "opId":"c9-7", "ops":[ {"retain":5}, {"insert":"!"} ] }
← { "t":"ack",  "opId":"c9-7", "rev":119 }
← { "t":"op",   "docId":"d_44", "rev":120, "author":"u_bo", "ops":[ {"retain":6}, {"insert":"?"} ] }
→ { "t":"cursor", "docId":"d_44", "anchor":6, "head":6 }      # ephemeral, not durable
← { "t":"presence", "users":[ {"id":"u_bo","anchor":5,"head":9,"colour":"#22c55e"} ] }
→ { "t":"sync", "docId":"d_44", "sinceRev":118 }              # reconnect

GET  /docs/d_44                    # → snapshot + rev, for the initial load
GET  /docs/d_44/history?from=…     # → named versions, not every operation
POST /docs/d_44/restore            # { "version": "v_9" } → creates a new revision

baseRev is the important field. An operation is not "insert ! at position 5" in the abstract — it is "insert ! at position 5 of revision 118". Without that, the server cannot know which concurrent operations the client had not yet seen, and transforming becomes impossible. Every operation carries the revision it was composed against, and this single field is what makes the whole mechanism work.

opId makes operations idempotent. A client that resends after a lost acknowledgement must not have its edit applied twice — the same reasoning as clientMsgId in 11.7, with a harsher consequence, since a duplicated insert corrupts a document rather than merely showing a message twice.

Operations are expressed as a sequence of retains, inserts and deletes rather than as absolute positions. [{retain:5},{insert:"!"}] means "leave five characters alone, then insert". This form composes and transforms much more cleanly than a position and a payload, and it extends naturally to formatting — {retain: 5, attributes: {bold: true}} marks five characters bold using the same machinery.

Cursor messages are deliberately outside the durable path. They are frequent, worthless a second later, and must never enter the operation log. Section 6.6 explains why routing them through the durable path is the most common and most expensive mistake in this design.

4. Data model

documents
  doc_id      UUID PRIMARY KEY
  owner_id    UUID
  current_rev BIGINT NOT NULL
  created_at, updated_at

operations                             -- the source of truth
  doc_id      UUID, rev BIGINT
  op_id       TEXT NOT NULL            -- UNIQUE (doc_id, op_id)
  author_id   UUID NOT NULL
  base_rev    BIGINT NOT NULL
  ops         JSONB NOT NULL           -- the retain/insert/delete sequence
  ts          TIMESTAMPTZ
  PRIMARY KEY (doc_id, rev)

snapshots                              -- a cache, not the truth
  doc_id      UUID, rev BIGINT
  content     BYTEA
  PRIMARY KEY (doc_id, rev)

comments
  comment_id  UUID PRIMARY KEY
  doc_id      UUID
  anchor_start, anchor_end   BIGINT     -- positions that move with edits
  orphaned    BOOLEAN NOT NULL          -- the anchored text was deleted
  body        TEXT

Access patterns:

Query	Frequency	Returns
Append an operation	250,000/s	—
Read operations since a revision	on reconnect	0–thousands
Read the latest snapshot	on document open	one row
Read named versions	rare	tens of rows

Partition by doc_id. Every operation belongs to one document, every read is scoped to one document, and there is no query that spans documents. This is as clean a partition key as exists in this book.

The operation log is the source of truth, and the document is a fold over it. That sentence is the design (10.8.4). Three things follow for free: version history exists because nothing was ever overwritten, restore is just replaying to a point, and convergence is replayable — if two clients disagree, the log says exactly what each of them should have seen.

Snapshots are a cache and must be treated as one. Losing every snapshot costs load time and nothing else, because they can be rebuilt from the log. The moment someone starts treating the snapshot as the truth and pruning the log beneath it, that property is gone and so is the history.

comments.orphaned is a small field carrying an important admission. When the text a comment points at is deleted, the comment does not point at nonsense and it does not silently disappear. It becomes orphaned, which is a state the interface can show honestly.

5. The core problem, and the two families of answer

Figure 1 — Why naive position-based edits diverge. An index into a changing document stops meaning anything the moment concurrent edits exist. The two families of solution either rewrite the positions so they stay meaningful, or remove positions from the operation entirely.

The comparison, honestly

	Transforming operations	Position-free identifiers
Mechanism	server orders operations; each is rewritten against concurrent ones	each character has a unique orderable id; operations commute
Needs a server?	yes, the ordering authority is essential	no
Metadata size	small — a position and a revision	larger — an id per character, plus markers for deletions
Where the difficulty is	the rewrite functions are subtle, and rich text multiplies the cases	the data structure is intricate, but correctness is structural
Long offline	a long chain of rewrites, expensive and most error-prone	merges the same whether you were away two seconds or two weeks
Best fit	linear text, with a server you already run	structured data, peer-to-peer, long offline

The decision, stated as a decision rather than a preference. If a central server exists anyway — and for any product with accounts, sharing and persistence it does — then transforming operations is the pragmatic choice for linear text, because its metadata is tiny and the ordering authority is free. Choose the position-free approach when the data is structured rather than linear, when peer-to-peer or long-offline operation is a first-class requirement, or when you want convergence to be a property of the data structure rather than of functions you must keep correct forever as features are added.

And the answer that shows judgement, for either choice: use a mature library. The failure mode of both families is not "it is slow", it is "replicas silently diverge" — which is the worst class of bug in this book, because it is invisible until a user notices their document is wrong. Neither is a reasonable thing to write from scratch under a deadline.

6. Deep dives

6.1 How transformation actually works

Figure 2 — The server's five steps. Every one of them is cheap. The single-owner property is what removes the need for any consensus protocol, exactly as the per-conversation sequence number did in the chat study.

Work the example from Figure 1 through properly.

Both clients are at revision 0 with HELLO. Ana sends [{retain:5},{insert:"!"}] with baseRev: 0. It arrives first, there is nothing to transform against, it becomes revision 1, and it is broadcast.

Bo sends [{retain:5},{insert:"?"}], also with baseRev: 0. The server sees that revision 1 has happened since Bo's baseline, so it transforms Bo's operation against Ana's: Ana inserted one character at position 5, so anything at or after position 5 shifts by one, and Bo's operation becomes [{retain:6},{insert:"?"}]. That becomes revision 2 and is broadcast.

Ana receives the transformed version and applies it to HELLO!, giving HELLO!?. Bo receives Ana's operation, transforms it against his own pending one on the client side, applies it, and also reaches HELLO!?. Converged.

Notice what broke the tie. Both inserted at exactly position 5, so there was a genuine choice about which goes first, and the server's ordering made it — consistently, for everyone. That is why the ordering authority is not an implementation detail but the thing that makes the rewrite well-defined at all.

And notice the property the rewrite functions must satisfy: applying Ana's operation and then the transformed Bo must produce exactly the same document as applying Bo's operation and then the transformed Ana. For plain text with insert and delete there are a handful of pairs to get right. Add formatting, tables, lists and embedded objects, and the number of pairs grows with the square of the operation vocabulary — which is precisely why this approach is subtle, and why section 8 makes divergence detection a production invariant rather than something you hope you got right.

6.2 The client applies edits before the server has seen them

Typing must never wait for a round trip. On a 200 ms connection, waiting would mean every character appearing a fifth of a second late, which is unusable.

So the client keeps three things: the last acknowledged revision, a pending buffer of operations it has sent but not had acknowledged, and the local document with those pending operations already applied.

When a remote operation arrives, the client transforms it against its own pending buffer before applying it — because the remote operation was composed against a document that did not include the local pending edits. When an acknowledgement arrives, the corresponding operation leaves the buffer and the acknowledged revision advances.

This loop is why the editor feels instant on a bad connection, and it is also where most client-side bugs live: applying the server's echo of your own operation a second time, mismanaging the pending buffer during reconnection, or dropping an operation that arrived while a sync was in flight.

6.3 Cursors and comment anchors move too

A cursor is a position, and positions shift under concurrent edits. If Bo's cursor is at position 10 and Ana inserts three characters at position 2, Bo's cursor must move to 13 — otherwise every remote edit above you drags your cursor backwards through your own text.

So cursors are transformed exactly like operations. The same is true of selections, and of the ranges that comments anchor to.

Comments introduce a case that operations do not have. A comment anchors to a range, and the text inside that range can be deleted entirely. The anchor then collapses to a point, and the comment is attached to nothing. Products that ignore this end up showing comments attached to whatever text happens to be nearby, which is worse than useless because it looks deliberate. The honest handling is the orphaned flag from section 4: the comment survives, it is shown as detached from the document, and the user can read it and resolve it.

6.4 Undo, which is where naive implementations break

Undo must be per user. Pressing undo reverts your last edit, not the last edit that happened to the document — even if a collaborator has typed since.

That means undo is not "apply the inverse operation". The inverse was computed against the document as it was when you made the edit, and the document has moved. Applying it untransformed deletes the wrong characters, which is a spectacular bug: the user presses undo and watches somebody else's sentence disappear.

The correct undo takes the inverse of your operation and transforms it against everything that has happened since, exactly as a late-arriving operation would be transformed. Then it is applied and broadcast as a new operation — because undo is an edit like any other, and other clients must see it through the same path.

Every collaborative editor has shipped this bug at least once, which is a good reason to name it explicitly in the design rather than assume it will be noticed.

6.5 Snapshots, compaction, and what history costs

The operation log grows forever, and at 2 TB a day it grows expensively.

Snapshots bound the load time. Periodically, the current document is written as a snapshot at a revision. A client opening the document loads the latest snapshot plus the operations since, which is a few hundred operations rather than a few million.

Compaction bounds the storage. Fine-grained operations older than some window are collapsed into coarser named versions — "the document as it was at 14:00 on Tuesday" — and the individual keystrokes behind them are discarded.

That is a product decision with a bill attached, and it should be made explicitly. Full keystroke-level history forever is a wonderful feature and it costs two terabytes a day. Most products keep fine-grained history for a window measured in weeks and named versions forever, and that is the right default — but somebody has to choose it, because the alternative is discovering the storage growth as an incident.

6.6 Ephemeral data must not touch the durable path

Cursor positions, live selections, and the intermediate frames of a drag are high-frequency, worthless a second later, and safe to lose. Routing them through the operation log is the most expensive mistake available in this design, and it is a mistake in three separate ways at once.

It corrupts the history, filling the version timeline with mouse positions. It multiplies the durable write volume by an order of magnitude for data nobody will ever read. And it runs the merge machinery at cursor-movement frequency, which is far more often than edits happen.

So presence travels on a separate channel with different rules: unordered, unreliable, coalesced to the latest value per user, and dropped freely under load. Those are the presence rules from 11.7, applied more strictly, because here the durable path is a document rather than a message history.

6.7 Reconnecting after being offline

The client sends its pending operations with the revision they were based on, and the server transforms them against everything that has happened since — which for a long absence is a long chain.

Two honest limits. The transformation cost grows with how much happened while you were away, and it is precisely in this regime that the rewrite functions are most stressed, because the operations being transformed against include every kind of edit. And beyond some threshold the right answer is to tell the client to reload from the server's state rather than attempt the merge — which loses nothing that was acknowledged, and is far better than a merge nobody can verify.

The reconnect handshake itself is the one from 11.7: subscribe first so live operations buffer, then fetch the gap since your revision, then merge and go live. Fetching before subscribing leaves a hole, and here a hole in the operation sequence is not a missing message, it is a permanently wrong document.

7. Decision Ledger

Decision	Alternatives	Why this	What it costs
Transform operations against a server order	position-free identifiers; locking; last write wins	small metadata, and the ordering server exists anyway	the rewrite functions are subtle and must stay correct as features are added
One server owns one document, by lease	multiple writers with a consensus protocol	a total order becomes a local variable, not an agreement	a failover window; one very hot document is one server's problem
The operation log is the source of truth	store the document and overwrite it	history, restore and replayable convergence come free	unbounded growth, so snapshots and compaction are mandatory
Snapshots treated strictly as a cache	snapshot as truth, prune the log	losing snapshots costs load time and nothing else	you must resist the temptation to prune the log beneath them
Apply local edits optimistically	wait for the server to acknowledge	typing is instant regardless of latency	the client must reconcile, which is where most client bugs live
Per-user undo with a transformed inverse	one global undo stack	matches what the user means by "undo"	genuinely hard, and the classic correctness bug
Presence on a separate lossy channel	send cursors through the operation log	keeps history, storage and merge cost sane	a second channel with different guarantees to operate
Reject locking outright	pessimistic locks on sections	collaboration is the product	none — locking is simply the wrong model here

8. Scale and failure

Scale is the number of documents, not the concurrency inside one. Fifty simultaneous editors is the extreme case and it is trivially served by one process. Ten million documents shard perfectly by identifier. The genuinely awkward outliers are a document with thousands of viewers — solved by separating the read path, so viewers receive a broadcast stream and never send operations — and a document that has been edited continuously for years, which is a compaction problem.

What breaks	Blast radius	How you find out	What keeps it running	Recovery
Session server crashes	one document, briefly	lease expiry	a new owner takes the lease and rebuilds from the log	clients resend unacknowledged operations
Client based on an ancient revision	one client	base revision far behind current	transform if feasible	past a threshold, tell it to reload — better than an unverifiable merge
Replicas silently diverge	one document, permanently	content checksum comparison — see below	nothing catches it automatically without that check	the log is authoritative; clients reload from it
Operation log unavailable	that document is read-only	write error rate	refuse edits rather than accept unloggable ones	restore; nothing acknowledged is lost
Snapshot corrupt or missing	slow document open	open latency	rebuild from the log	snapshots are a cache by construction
Log growth unbounded	storage cost, silently	log bytes per day against the retention policy	compaction into named versions	this is a policy failure, not an incident
Presence channel flooded	cursors freeze	presence message rate	drop freely; presence is lossy by design	none needed — it is meant to be droppable

The third row is the one that matters, and it needs a mechanism rather than a hope. Divergence produces no error. No request fails, no log line appears, and both clients believe they are correct. The only way to notice is to look:

Add a content checksum to the protocol. Each client periodically sends a hash of its document together with its revision number. The server compares clients at the same revision and raises an alarm on a mismatch. That turns an invisible corruption into a monitored number, and it should exist before the first divergence bug rather than after — it is the single highest-value line of defence in this design.

And pair it with a recovery path. On a detected mismatch, the client reloads from the server's authoritative state. That loses nothing, because the operation log holds everything, and it prevents a client from persisting a corrupted view of the document into further edits (10.10).

What the interviewer will push on

"Show me exactly why two concurrent edits diverge." They want the worked example, not the phrase "conflict". Both replicas hold HELLO, both insert at position 5, each applies the other's operation verbatim, and the results are HELLO?! and HELLO!? — permanently different, with nothing dropped and nobody at fault. Then name the root cause in one sentence: position 5 was an index into a document that no longer exists, so an operation's parameters only mean something relative to the state they were written against.

"Which approach would you choose, and why?" The trap is to have a favourite. The answer is three questions: does a server exist anyway, is the data linear or structured, and how long can someone be offline. A server plus linear text points at transformation; structured data or long offline points at position-free identifiers. Then close with the judgement call — use a mature library either way, because the failure mode is silent divergence rather than slowness.

"Why don't you need a consensus protocol to order operations?" Because one server owns one document at a time, held by a lease, so the order is a local variable rather than something anyone has to agree on. This is the same move as the per-conversation sequence number in 11.7. Then name the cost you accepted: a failover window, and one very hot document being one server's problem.

"How does undo work?" This separates people who have built one. Undo is per user, so it reverts your last edit rather than the document's last edit. That means it cannot be "apply the inverse", because the inverse was computed against a document that has since moved — applying it untransformed deletes somebody else's text. The inverse must be transformed against everything since and then broadcast as an ordinary operation.

"Two users end up with different documents. How do you find out?" The correct first answer is that you would not, unless you built the detection — divergence throws no errors and fails no requests. So the answer is the checksum invariant: clients periodically send a hash with their revision, the server compares clients at the same revision, and a mismatch raises an alarm and triggers a reload from the authoritative log. A candidate who reaches for the detection mechanism before the debugging story has understood what makes this class of bug different.

"Someone was offline for two weeks. What happens on reconnect?" They send their pending operations with the revision those were based on, and the server transforms against everything since. Then the honest part: that chain is expensive and it is exactly where the rewrite functions are most stressed, so past a threshold the right answer is to refuse the merge and reload — which loses nothing acknowledged and is far better than a merge nobody can verify.

Volunteer this, because nobody asks: the operation log being the source of truth is what makes every hard thing here tractable. History is free because nothing was overwritten. Restore is a replay. A crashed server rebuilds by folding the log. And crucially, a divergence is reproducible — the log records exactly which operations each client saw and what each was based on, so a corruption that would otherwise be a mystery becomes a deterministic replay. The moment someone proposes storing the document and pruning the log beneath a snapshot, all four of those properties leave together.

Next: 11.14 — from a system where the worst outcome is a wrong character to one where the worst outcome is a wrong number with a currency symbol in front of it, and where "we are not sure whether that happened" is a state you must be able to survive.

Recall

• The core problem: an integer position indexes a document that changed, so two concurrent inserts at position 5 leave replicas permanently different with nothing dropped and nobody at fault.
• Two families: transform the operations against a server-assigned order (small metadata, needs an ordering server, subtle rewrite functions that grow with the feature set) or abolish positions by giving every character a unique orderable id (no server needed, larger metadata and deletion markers, correctness is structural).
• Choosing: a server exists anyway + linear text ⇒ transformation. Structured data, peer-to-peer, or long offline ⇒ position-free. Either way, use a mature library — the failure mode is silent divergence, not slowness.
• baseRev on every operation is what makes transformation possible; opId makes it idempotent, and a duplicated insert corrupts a document rather than merely repeating a message.
• One server owns one document, by lease ⇒ total order with no consensus protocol, exactly like the per-conversation sequence in 11.7. Durability precedes broadcast.
• The operation log is the source of truth; the document is a fold over it; snapshots are a cache. History, restore and reproducible divergence all come from that one decision.
• Clients apply optimistically and reconcile against a pending buffer — which is where most client bugs live. Cursors and comment anchors are transformed like operations, and a comment whose text was deleted becomes explicitly orphaned.
• Undo is per user and must transform the inverse against everything since. An untransformed inverse deletes somebody else's text.
• Ephemeral data must never enter the durable path — cursors on a separate lossy channel, or you corrupt history, multiply writes, and run the merge machinery at cursor frequency.
• Divergence is silent. The only detection is a content checksum compared between clients at the same revision, with a reload as the recovery path.

Self-test: Work the divergence example and say what the root cause is. Give both families in one line each and the three questions that choose between them. Why does one owner per document remove the need for consensus? Why can undo not be "apply the inverse"? How would you ever find out that two replicas disagree?

Quiz Bank

FoundationalShow precisely why concurrent edits diverge, and how transforming operations fixes it.

The divergence, step by step. Both replicas hold "HELLO". Ana inserts "!" at position 5, producing "HELLO!". Concurrently, Bo inserts "?" at position 5, producing "HELLO?". Each now receives the other's operation verbatim.

Ana applies insert("?", 5) to "HELLO!" and gets "HELLO?!". Bo applies insert("!", 5) to "HELLO?" and gets "HELLO!?".

Both applied both operations. Nothing was dropped, nothing was reordered by the network, and neither client has a bug. The documents differ permanently, and every future edit compounds the difference.

The root cause in one sentence: position 5 was an index into a document that no longer exists. An operation's parameters are only meaningful relative to the state they were composed against (10.3).

How transformation fixes it. A server establishes a total order: Ana's operation becomes revision 1, Bo's becomes revision 2. Bo's operation was composed against revision 0, so before it can be applied to revision 1 it is rewritten — Ana inserted one character at position 5, so everything at or after 5 shifts by one, and insert("?", 5) becomes insert("?", 6). Ana applies that to "HELLO!" and gets "HELLO!?". Bo receives Ana's operation, transforms it against his own pending edit, applies it, and also reaches "HELLO!?".

Converged — and notice what broke the tie. Both inserted at exactly position 5, so there was a real choice about which came first. The server's order made that choice, consistently, for everybody. That is why the ordering authority is not an implementation detail: without it, "transform against the concurrent operation" is not even well defined, because the two sides would disagree about which one was concurrent with which.

The property the rewrite functions must satisfy is that applying Ana's operation and then the transformed Bo must give exactly the same document as applying Bo's and then the transformed Ana. For plain text with inserts and deletes, that is a handful of cases. Add formatting, lists, tables and embedded objects and the number of pairs grows with the square of the operation vocabulary — which is exactly why this approach is subtle, and why the checksum invariant in section 8 exists rather than a hope that all the cases were covered.

InterviewTransformation or position-free identifiers — how do you decide, and what does each actually cost?

Three questions, in this order.

Does a central server exist in the architecture anyway? For any product with accounts, permissions and server-side persistence the answer is yes. If it is, then transformation's chief prerequisite — an ordering authority — is free, and the position-free approach's chief advantage, not needing one, buys nothing.

What shape is the data? For linear text, transformation is well trodden and its metadata is tiny: an operation carries a position and a revision, and nothing else. For structured data — a canvas of objects with properties, a tree of nested blocks — the position-free approach is dramatically simpler, because per-property "last writer wins" registers and per-set add and remove semantics compose naturally, while transformation needs a bespoke rewrite function for every pair of operation types on every node type.

How important is long-offline or peer-to-peer operation? Position-free merges are order-independent, so a two-week offline edit merges as cheaply as a two-second one. Transformation must rewrite a long chain of pending operations against everything that happened, which is both expensive and the regime where correctness is most stressed.

The costs, stated fairly rather than as advocacy.

Transformation costs correctness effort forever. The rewrite functions are subtle, the number of pairs grows with the operation vocabulary, and every new feature — tables, comments, formatting — adds cases. The mitigation is not careful review, it is a production invariant that detects divergence when it happens anyway.

Position-free costs space and structural complexity. Every character carries a unique identifier, deleted characters leave markers that cannot always be collected, and a document heavily edited over years accumulates them. The structures that keep insertion ordering both dense and stable are intricate. The mitigation is a mature library rather than an in-house implementation.

The answer that shows judgement, and it applies to both: use a well-tested library. The failure mode here is not "it is slow" but "replicas silently diverge", which is the worst class of bug in this book because nothing errors, nothing is logged and nobody finds out until a user reads a document that is wrong. Neither algorithm family is a reasonable thing to implement from scratch against a deadline.

StaffUsers report that documents occasionally lose text after concurrent editing sessions. Find and fix it.

First, establish that it is divergence and not something ordinary. The same symptom is produced by a failed save, an overwriting restore, a client crash losing unacknowledged operations, or a permissions-driven revert. The distinguishing test is precise: do two clients that saw the same set of operations show different content? If yes, it is divergence. If both show the same wrong content, it is loss somewhere else and a completely different investigation. Confusing the two costs days.

Second, make it detectable, because right now it is not. Divergence produces no error, no failed request and no log line — both clients believe they are correct. So add a content checksum to the protocol: each client periodically sends a hash of its document plus its revision, the server compares clients sitting at the same revision, and a mismatch raises an alarm. This converts an invisible corruption into a monitored number, and it is the single highest-value change to come out of this incident. It should have existed before the first bug rather than after.

Third, reproduce it deterministically. Because the operation log is the source of truth, the exact operation sequence and each client's base revision are recoverable. Replay them against the transformation functions in isolation.

If the replay diverges, the bug is in the rewrite functions and you now have a deterministic reproduction — which is most of the work.

If the replay converges, the bug is in the client: a mismanaged pending buffer, an operation applied twice (typically a local edit plus the server's echo of it), or an operation dropped during reconnection. In practice this is where these bugs more often live, and the checksum telemetry is what localises them, because it tells you which client diverged and at which revision.

Fourth, fix the class rather than the instance. Repair the rewrite pair or the client state machine, then make the checksum comparison a permanent production invariant with an alarm, and add a client-side recovery path: on a detected mismatch, reload from the server's authoritative state. That loses nothing, because the log holds everything, and it stops a client from building further edits on top of a corrupted view — which is what turns a one-character discrepancy into a document nobody can reconcile.

The staff-level point, said plainly: in a convergence system, correctness cannot be established by inspection or by argument. It is established by the structure of the data, or by the properties of the rewrite functions — and in either case it must be backed by a production invariant that detects the cases the reasoning missed. A design without that third layer is not observably correct; it is only unobservably incorrect.

Flashcards

FlashWhy edits diverge

Positions index a document that changed. Two inserts at 5 give HELLO?! on one replica and HELLO!? on the other — same operations, different result, permanent, with nothing dropped.

FlashThe two families

Transform: a server orders operations and each is rewritten against the concurrent ones. Small metadata, subtle functions. Position-free: every character carries a unique orderable id so operations commute. No server, larger metadata, deletion markers.

FlashChoosing between them

Server exists anyway + linear text ⇒ transformation. Structured data, peer-to-peer, or long offline ⇒ position-free. Either way use a mature library — the failure mode is silent divergence.

FlashThe operation log

Source of truth; the document is a fold over it; snapshots are a cache. That one decision gives history, restore, crash recovery, and reproducible divergence — all four leave together if you prune the log.

FlashUndo

Per user, not global. The inverse must be transformed against everything since, then broadcast as an ordinary operation. An untransformed inverse deletes somebody else's text.

FlashHow you detect divergence

You do not, unless you built it. Clients send a content checksum with their revision; the server compares clients at the same revision and alarms on mismatch. Recovery is a reload from the authoritative log.

Scenario Drill

DrillExtend this to a design canvas: thousands of objects with properties, nesting, ordering, and live cursors at 60 frames a second. What changes fundamentally?

The data stops being linear, and that changes the algorithm choice decisively. A document is no longer a sequence of characters but a tree of objects, each with properties — position, size, fill, text — a parent, and an ordering among its siblings. Transformation would need a rewrite function for every pair of operation types across every object type: move against delete, reparent against reparent, set-property against delete. That is a combinatorial burden that grows with every feature the product ships.

Position-free identifiers fit this shape naturally, which is why real design tools use them. Each object's scalar properties become last-writer-wins registers — two people setting the fill colour concurrently genuinely is a case where one of them wins, and any deterministic tie-break is acceptable because both intentions cannot be honoured. The set of objects is an add-and-remove set. Sibling ordering uses a dense ordering key so that inserting between two objects never requires renumbering everything after it.

And the payoff is a behaviour users expect and would not get otherwise: concurrent edits to different properties of the same object merge perfectly. Ana recolours a shape while Bo resizes it, and both intentions survive. A document-level lock, or last-writer-wins on the whole object, would silently destroy one of them.

Three hard cases remain, and they should be named rather than glossed.

Concurrent reparenting can create a cycle. Ana moves object A into B while Bo moves B into A. Applied naively, the result is a loop with no root, which is not a tree at all. The structure must detect this and resolve it deterministically — usually by rejecting one of the moves — and it is a genuinely hard known problem rather than an edge case someone forgot.

Delete against edit. Ana deletes a shape that Bo is styling. Delete wins and the styling is dropped, which is defensible, but it must be visible to Bo rather than silent. A change that quietly evaporates is indistinguishable from a bug.

Grouping and ungrouping concurrent with edits to members is the operation most likely to produce a result that is technically converged and visually surprising.

The performance dimension is a separate system entirely, and conflating it is the classic mistake. Live cursors and in-progress drags at 60 frames a second are ephemeral, high-frequency and safe to lose. They must not touch the merge structure or the durable log. Routing them through it fills the version history with mouse positions, multiplies durable writes by an order of magnitude, and runs the merge machinery sixty times a second per user for data nobody will ever read.

They travel on a separate presence channel: unordered, unreliable, coalesced to the latest value per user, dropped freely under load. The durable path receives the committed result of a drag — one operation at the moment the mouse is released — not the four hundred intermediate frames that led to it.

Rendering becomes a first-class constraint too. Applying remote operations must not block the frame loop, so operations are applied in batches once per frame, and the renderer works from a derived scene graph rather than reading the merge structure directly.

The sentence for the design document: a design canvas is three systems — a convergent structure for durable content, an ephemeral presence channel for cursors and in-progress manipulation, and a render pipeline that consumes both. The most common failure is routing ephemeral data through the durable path, which is simultaneously a correctness problem, a storage problem and a frame-rate problem, and it is much cheaper to prevent than to unwind.