Engineering Atlas › System Design Fundamentals

Merging concurrent edits with operational transformation

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The problem transform solves

Alice and Bob both see "cat". Alice inserts "s" at position 3 to make "cats". Bob deletes position 0 to make "at". If Bob applies Alice's operation unchanged, he inserts at index 3 of "at", which is past the end. Alice's operation must be shifted left by one, because Bob's delete removed a character before it. After transform, both sides reach "ats".

Transform rules for text

For insert versus insert at different positions, the later position shifts right by the length of the earlier insert. At the same position a deterministic tie-break such as site ID decides which goes first, and both sides must use the same rule. Insert versus delete shifts the insert left if the delete was before it. Delete versus delete of the same character becomes a no-op on the second side. Real systems use retain/insert/delete sequences that span the whole document, which compose and transform efficiently. Formatting adds a third kind of change: Google Docs reduces every edit to inserting text, deleting text, or applying a style to a range, and a style range grows when text is inserted inside it (Google Drive blog).

Convergence property

The requirement, often called TP1, is that for concurrent a and b, applying a then transform(b, a) gives the same document as b then transform(a, b). Peer-to-peer OT without a central order also needs TP2, a much harder property about transforming against different sequences. Many published algorithms were later shown to violate TP2. A 2003 study ran the published string transformation functions through a theorem prover, found counterexamples (Sun's set, for example, violates TP2), and concluded that all of them were incorrect or over-specified; even a plain string has 123 cases to check each time a function changes (Imine et al.). So production systems avoid peer-to-peer OT.

Client-server OT

The server keeps the authoritative document and a revision counter. A client sends an operation tagged with the revision it was based on. If the server is now at a later revision, it transforms the incoming op against every op committed since that revision, applies it, assigns the next revision, and broadcasts it. Each client keeps at most one operation in flight and buffers further local edits. When the server's acknowledgment arrives it sends the buffer. Remote operations arriving meanwhile are transformed against the in-flight and buffered ops before being applied locally. Because the server defines a single total order, only TP1 is needed. Google Wave added the one-in-flight rule to Jupiter's design so the server keeps a single history instead of a state space per client, at the cost of clients seeing others' edits in chunks about one round trip apart (Wave OT whitepaper). In distributed-systems terms, OT needs total order broadcast, which means a designated leader or a consensus protocol (Kleppmann's lecture notes).

Beyond plain text

Rich text adds formatting attributes on ranges. Structured documents like spreadsheets or JSON need transforms for operations on paths. Every new operation type multiplies the transform pairs you must write and test.

Newer designs blur the line between OT and CRDTs. Eg-walker (EuroSys 2025) stores a plain operation log like OT but builds a temporary CRDT only while merging concurrent branches, which its authors report uses an order of magnitude less steady-state memory than CRDTs and merges long-running branches orders of magnitude faster than OT (Gentle and Kleppmann).

Down the stack

Layer 1The contract

Client-server OT promises three things. Local edits apply immediately, so typing latency is a memory write, not a round trip. The server assigns every accepted operation a revision number, giving one total order that all clients replay. Once the system is quiet, every client's document equals the server's document at the latest revision. It does not promise that the merged text matches what both users meant, only that it is deterministic and the same everywhere. It also depends on the server: a client offline for an hour keeps editing locally, but its changes are not shared and not durable until the server accepts them, possibly after transforming them against thousands of operations.

Layer 2The mechanism

The design descends from Xerox PARC's Jupiter system (Nichols et al., UIST 1995) and was popularised by Google Wave and Google Docs. Google Docs stores each document as a revision log of changes and renders it by replaying that log (Google Drive blog). Open-source implementations show the moving parts. In ot.js an operation is a list of components spanning the whole document: retain(n), insert(str), delete(n). Two functions do all the work: compose(a, b) merges consecutive operations into one, and transform(a, b) returns the pair (a', b') that satisfies TP1. The client is a three-state machine: Synchronized, AwaitingConfirm (one operation in flight), and AwaitingWithBuffer (one in flight plus a composed buffer of later edits). When the ack arrives, the buffer is sent; when a remote operation arrives, it is transformed against the in-flight and buffered operations before it touches the editor (ot.js).

ShareDB, a Node.js server, applies the same idea to JSON documents. Each submit carries the document version it was based on. The server loads the operations committed since that version from its op log, transforms the incoming operation against them, and commits it with an atomic "insert version v+1 only if it does not already exist" in the backing database. That conditional write is the serialization point; a concurrent submit that loses the race is retransformed and retried, up to a configurable retry limit (ShareDB source). Snapshots let a client load a document without replaying its entire history.

Layer 3The machine

Operations are small. A keystroke as JSON is a few dozen bytes, and over WebSocket a small client-to-server frame adds about 6 bytes of header including the 4-byte masking key that every client frame must carry (RFC 6455), so typing traffic is negligible. The one-operation-in-flight rule also gives natural batching: with a 150 ms round trip, all keystrokes typed during that window are composed into a single buffered operation, so the message rate adapts to latency instead of growing with typing speed.

The real limits sit on the server. Every operation on a document must pass through one ordering point, so a document's write throughput is bounded by one process and one conditional database write per revision, typically a millisecond or a few. Transform cost is linear in the number of concurrent operations: a client reconnecting after a long offline session can force the server to transform its edits against thousands of revisions. Positions are another trap: JavaScript strings index UTF-16 code units, so an emoji is two positions, and a server that counts characters in a different unit corrupts text silently.

Why it's built this way

  1. Users notice input lag above roughly 100 ms, and network round trips often exceed that, so edits must apply locally first and be reconciled later.
  2. Reconciling concurrent edits without a referee requires TP2, which many published algorithms got wrong, so a central server imposes one order and only TP1 is needed.
  3. A central order makes each document a single serialization point, so documents are sharded by ID and each one's op log is an append-only table keyed by version.
  4. History grows with every keystroke, so servers store periodic snapshots and clients compose pending edits to keep both transform cost and message counts low.

Diagram

sequenceDiagram
    participant A as Alice
    participant S as Server rev 7
    participant B as Bob
    A->>S: ins(3,"s") based on rev 7
    B->>S: del(0) based on rev 7
    Note over S: commit ins as rev 8
    S-->>A: ack rev 8
    S-->>B: ins(3,"s") rev 8
    Note over B: transform against pending del(0) gives ins(2,"s")
    Note over S: del(0) transformed against rev 8 stays del(0), rev 9
    S-->>B: ack rev 9
    S-->>A: del(0) rev 9
    Note over A,B: both show "ats"

Worked example

A collaborative editor hosts documents with up to 50 simultaneous editors, each typing about 5 keystrokes per second. Clients batch keystrokes into one operation every 100 ms, so each editor sends up to 10 ops per second, and a busy document receives 500 ops per second.

Server work per op: transform against all ops committed since the client's base revision. With 100 ms client RTT, a client is about 50 revisions behind at that rate (500/s × 0.1 s), so about 50 transforms per op, each taking microseconds. One document needs a few ms of CPU per second, but all of it must happen on the single node that owns that document, so documents are sharded by ID with one owner each.

Storage: the op log grows about 50 bytes per op, so 500 ops/s for a one-hour session is 90 MB. The server snapshots the document every 1,000 revisions and keeps the log for history and undo. A client reconnecting after 10 minutes offline with 300 local edits sends them as one composed op, which the server transforms against the 300,000 ops committed since; for long gaps, rebasing against a snapshot diff is cheaper.

Failure case: the document's owner node crashes. A new owner loads the last snapshot plus the log tail from durable storage. Clients resend their in-flight ops with the same IDs, and the server deduplicates by (clientId, seq) so a retried op is not applied twice.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Client-server OTSmall metadata, mature, simple clientsServer required for every edit, per-document ownerOnline-first editors with a central backend
Peer-to-peer OTNo server orderingTP2 is hard to get rightRarely; prefer CRDTs
Sequence CRDTOffline and peer-to-peer, no server logicLarger metadata, possible interleavingLocal-first or multi-region active writes
Server-authoritative LWW per propertyVery simpleNot suitable for character-level textDesign tools, forms, object trees
Locking sectionsTrivial to buildUsers block each otherLow concurrency workflows

Pitfalls in production

Leadership lens

Check yourself

  1. Why does client-server OT need only TP1 while peer-to-peer OT needs TP2 as well?

    Show answer

    The server imposes one total order, so every op is transformed along the same path. Without it, ops can be transformed against concurrent sequences in different orders, which TP2 must reconcile.

  2. Why must the tie-break for two inserts at the same position be deterministic and shared?

    Show answer

    Each side resolves the tie independently; if they choose differently the texts diverge permanently.

  3. Why does a client keep only one operation in flight?

    Show answer

    It lets the client know exactly which server revision its op was based on and transform incoming ops against a single known pending op plus a buffer.

  4. What happens if a transform shifts an insert incorrectly by one?

    Show answer

    Clients silently diverge and stay diverged until a checksum or resync detects it.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →