Operational transformation (OT)

Why edits need rewriting

In the lesson on collaboration basics, Asha and Ben edited the line big cat at the same moment. Asha inserted black at position 4. Ben deleted 4 characters at position 0. Each editor applied the other's instruction as it arrived, and the two copies ended up different: catblack on one screen, black cat on the other.

Nothing was lost and nobody made a mistake. Asha's "position 4" was correct for the text she saw, big cat, but by the time it reached Ben his text was cat, and position 4 pointed past the end. A position only means something together with the document it was measured on.

Operational transformation (OT) is the fix that keeps the numbers and corrects them. Before an editor applies an edit that was made without knowing about some other edit, it rewrites the edit's position to account for what it missed. Ben's editor sees that Asha's insert came after a delete of 4 characters that sat entirely before it, so it moves the insert from 4 to 0. Both copies now read black cat.

Every edit has a context

The key idea in this whole lesson is the context of an edit: the exact version of the document the author was looking at when they made it. insert 4 "black " in the context big cat is a different instruction from the same words in the context cat. Two edits are concurrent when neither author had seen the other's edit, so each is missing the other.

Applying an edit outside its context is like looking for "the fourth house on the left" after a new house was built at the start of the street: you stop one house too early. The house you meant did not move; only the count did, and OT is the rule book for fixing the count.

Four ways out of the problem

Every collaborative product has to deal with stale positions somehow. There are four common ways, and it helps to see OT next to the others.

• Lock it. Only one person may edit a region at a time. Fine for a spreadsheet cell or a slide, useless for two people typing in the same paragraph.
• Last writer wins. Each client sends its whole copy and the newest one replaces the rest. Simple, and it silently throws away the other person's typing.
• Rewrite the positions. Keep plain numeric positions, and transform each concurrent edit against the edits it missed. This is OT.
• Stop using positions. Give every character a permanent unique id and say "insert after character a7" instead of "insert at 4". Ids never go stale, so no rewriting is needed. This is the idea behind CRDTs (conflict-free replicated data types), the topic of a later lesson.

OT is the older of the two main answers. Clarence Ellis and Simon Gibbs first described it in 1989, for a group editor called GROVE. In 1995 the Jupiter system at Xerox PARC showed how a central server makes it much simpler, and Google Wave (2009) and the rebuilt Google Docs (2010) use that server design. ShareDB, CKEditor 5, and Etherpad are built on transformation too.

The mental model: operations and the diamond

OT sends operations, small objects that each describe one change, never the whole document. For plain text two kinds are enough: insert puts some text at a position, and delete removes a number of characters starting at a position. Positions count characters from 0, so in the cat sat the t of the is at 0 and the c of cat is at 4.

type Insert = { type: "ins"; pos: number; text: string; site: number };
type Delete = { type: "del"; pos: number; len: number };
type Op = Insert | Delete;

function apply(doc: string, op: Op): string {
  if (op.type === "ins") return doc.slice(0, op.pos) + op.text + doc.slice(op.pos);
  return doc.slice(0, op.pos) + doc.slice(op.pos + op.len);
}

// "the cat sat" + { type: "ins", pos: 4, text: "big ", site: 2 }  ->  "the big cat sat"
// "the cat sat" + { type: "del", pos: 0, len: 4 }                 ->  "cat sat"

An operation is small, usually a few dozen bytes, whatever the size of the document. Typing a word into a 300-page report sends no more data than typing it into a one-line note.

One function does all the work

The heart of OT is a single function, transform(a, b). It takes two operations made on the same version of the text, and returns a new version of a that does what a meant, but can run after b has already been applied. Read it as "rewrite a so it knows about b".

Back to the cat sat: Asha inserts big at 4 while Ben deletes 4 characters at 0. transform(asha, ben) returns "insert big at 0", because Ben removed 4 characters before her position. transform(ben, asha) returns Ben's delete unchanged, because Asha's insert sits after the range he deleted.

The diamond: two paths, one answer

Draw the document versions as dots: from the starting text, Asha's edit goes one way and Ben's goes the other. Each side then applies the transformed version of the other person's edit. The two paths meet at the bottom, and OT is only correct if they meet at the same text. This shape is called the OT diamond, and it is the one picture to keep in your head.

Written as a rule, it is: applying a then transform(b, a) gives the same text as applying b then transform(a, b). Researchers call this TP1, transformation property 1. Every transform function must satisfy it for every pair of operations, or two people will end up looking at different documents with no error anywhere.

Converged is not the same as correct

TP1 promises that both copies match, not that the result is what the users wanted. A transform function that turned every concurrent pair into "delete everything" would converge perfectly. A good transform also keeps each author's intention: Asha's big still lands in front of cat, and Ben's the is still gone. The rules in the next chapter are chosen to keep both promises.

The transform rules, one pair at a time

With two kinds of operation there are four pairs, and each needs its own rule. In every rule a is the operation being rewritten and b is the one that already happened. The question is always the same: did b change anything before a's position, or inside a's range?

Insert against insert, and the tie

If b inserted text before a's position, a moves right by the length of that text. If b inserted after, a stays put. The hard case is a tie: both inserted at the same position. The text alone cannot say whose words should come first, and both sides must make the same choice, or one copy reads AB and the other BA.

The fix is a fixed rule that both sides can compute on their own. Each client gets a site id, a number unique to that editor session, and the insert from the lower site id goes first. Any rule works as long as every copy uses the same one; the site id is simply something both sides know.

// Rewrite a so it can run after b. Both were made on the same text.
// Returns a list: usually one op, sometimes none, sometimes two.
function transform(a: Op, b: Op): Op[] {
  if (a.type === "ins") {
    if (b.type === "ins") {
      const aFirst = a.pos < b.pos || (a.pos === b.pos && a.site < b.site);
      return [aFirst ? a : { ...a, pos: a.pos + b.text.length }];
    }
    if (a.pos <= b.pos) return [a];                          // before the deleted range
    if (a.pos >= b.pos + b.len) return [{ ...a, pos: a.pos - b.len }]; // after it
    return [{ ...a, pos: b.pos }]; // inside it: the text around a is gone, land at the gap
  }
  return transformDelete(a, b); // a is a delete, below
}

Insert against delete

If b deleted a range that ends at or before a's position, a moves left by the deleted length. If the range starts at or after a's position, nothing changes. If a was typing in the middle of text that b deleted, the surrounding characters are gone, so the insert lands where the gap now is. Asha's word survives even though the sentence around it was removed: her intention was to add text, and Ben's was to remove existing text, not hers.

Delete against insert: the split

Now flip it: a deletes a range, and b inserted text. If b's insert is at or before the start of the range, the range moves right. If it is at or after the end, nothing changes.

If b typed inside the range a wants to delete, a must not delete b's new words, because a's author never saw them. So the delete splits into two: the part before the new text and the part after it. This is why transform returns a list.

Delete against delete: the overlap

Two people often delete the same thing, for example when both select a typo and press Backspace. If the ranges do not touch, a only shifts left when b's range is before it. If they overlap, the characters both wanted gone are already gone, so a shrinks by the overlap, and it vanishes (an empty list) if b deleted all of it. Deleting the overlap twice would remove characters nobody selected.

function transformDelete(a: Delete, b: Op): Op[] {
  const aEnd = a.pos + a.len;
  if (b.type === "ins") {
    const n = b.text.length;
    if (b.pos <= a.pos) return [{ ...a, pos: a.pos + n }]; // text added before the range
    if (b.pos >= aEnd) return [a];                         // text added after it
    const before = b.pos - a.pos; // b typed inside a's range: keep b's text, split a
    return [{ ...a, len: before }, { ...a, pos: a.pos + n, len: a.len - before }];
  }
  const bEnd = b.pos + b.len;
  if (aEnd <= b.pos) return [a];                         // b removed text after a
  if (a.pos >= bEnd) return [{ ...a, pos: a.pos - b.len }]; // b removed text before a
  const overlap = Math.min(aEnd, bEnd) - Math.max(a.pos, b.pos);
  const len = a.len - overlap;                           // b already removed the overlap
  return len === 0 ? [] : [{ ...a, pos: Math.min(a.pos, b.pos), len }];
}

Test the rules before you trust them

Off-by-one mistakes in these rules are easy to make and hard to see, because the copies only drift apart for certain pairs of edits. The reliable way to check is a property test: generate random short strings and random pairs of operations, apply both sides of the diamond, and compare. The functions above pass TP1 for 200,000 random pairs, including tens of thousands of ties, overlaps, and splits. Write that test before anything else; it takes about 20 lines.

A worked example: two users, one server

Now follow one full session. Asha and Ben share the line the cat sat, with a server between them as in the collaboration basics lesson. Ben joined first, so his site id is 1; Asha's is 2. The server keeps a revision number, a counter that goes up by one for every operation it accepts, and it starts at 0.

What the two of them type

1. Asha inserts big at 4. Her screen shows the big cat sat at once (local echo), and her editor sends the operation, stamped "made on revision 0".
2. At the same moment Ben deletes the , 4 characters at 0. His screen shows cat sat, and his editor sends that delete, also stamped revision 0.
3. A moment later Ben types A at 0, so his screen shows A cat sat. His delete is still waiting for the server's reply, so this insert waits in a local buffer instead of being sent: one change in flight at a time, as in the basics lesson.

What the server does

Asha's insert arrives first. It was made on revision 0, the server's current revision, so it has missed nothing. The server applies it (text the big cat sat, revision 1), tells Asha "accepted as revision 1", and forwards the insert to Ben.

Ben's delete arrives next, also made on revision 0, but the server is now at revision 1, so the delete missed Asha's insert. The server runs transform(benDelete, ashaInsert). The delete covers positions 0 to 3 and the insert is at 4, outside the range, so the delete comes back unchanged. The server applies it (text big cat sat, revision 2) and forwards it to Asha.

What Ben's editor does with Asha's insert

Asha's insert reaches Ben while his delete is in flight and his A is in the buffer. His screen, A cat sat, already includes both of his edits, and Asha's insert knows about neither, so his editor transforms it twice, in order.

1. Against his in-flight delete: the delete removed 4 characters before position 4, so the insert moves to 0.
2. Against his buffered A at 0: now both inserts are at position 0, a tie. Ben's site id 1 is lower than Asha's 2, so Ben's text goes first and Asha's insert moves right by 2, to position 2.
3. His editor applies "insert big at 2" to A cat sat and shows A big cat sat.

Each step also rewrites Ben's own pending operations against Asha's insert, so they still make sense when they reach the server. When the server confirms the delete, Ben's editor sends the buffered A stamped revision 2. The server has nothing newer, so it applies it as revision 3 and forwards it to Asha, whose big cat sat becomes A big cat sat. Three copies, one text.

The server decides the order

The worked example leaned on the server for one thing above all: it puts every operation into a single numbered order. This is the Jupiter design that made OT practical. Each client talks only to the server, never to other clients, and the server's order is the truth.

The server's loop

The server keeps the current text, the current revision, and a history: the list of accepted operations, where entry n is the operation that turned revision n into revision n + 1. Every incoming operation carries the revision it was made on, called its base revision.

// One document on the server. Ops are lists (a transform can split one op into two).
const history: Op[][] = []; // history[n] turned revision n into n + 1
let doc = "the cat sat";

function receive(ops: Op[], baseRev: number, from: Client) {
  if (baseRev > history.length) throw new Error("client is ahead of the server");
  for (const done of history.slice(baseRev)) {
    ops = transformLists(ops, done)[0]; // catch up on everything it missed, in order
  }
  doc = ops.reduce(apply, doc);
  history.push(ops);
  const rev = history.length;
  from.send({ type: "ack", rev });
  for (const other of clientsExcept(from)) other.send({ type: "op", ops, rev });
}

Notice what the server never does: it never asks a client to retry, never waits, and never rolls anything back. An operation that arrives is transformed forward and accepted. A plain-text transform is only a handful of comparisons, so the cost per operation is small.

The client's three states

The client side is a small state machine. It needs only three pieces of data: the last revision it knows, the operation in flight (sent, not yet confirmed), and the buffer (typed since, not yet sent). Which of those are empty gives three states.

• Synchronized: nothing in flight. A local edit is sent at once and the client moves to awaiting confirm.
• Awaiting confirm: one operation in flight. A new local edit goes into the buffer, and the client moves to awaiting with buffer. An ack moves it back to synchronized.
• Awaiting with buffer: one in flight, more in the buffer. New local edits are added to the buffer. An ack sends the buffer as the new in-flight operation and moves back to awaiting confirm.

In every state, an operation from the server has to be transformed before it is applied, because the client's screen already shows its own unconfirmed edits. It is transformed against the in-flight operation first, then against the buffer, which is the order those edits happened on the screen. At the same time the in-flight operation and the buffer are rewritten against the incoming one, so they stay valid for the server.

function onServerOp(incoming: Op[]) {
  if (inFlight) [inFlight, incoming] = transformLists(inFlight, incoming);
  if (buffer) [buffer, incoming] = transformLists(buffer, incoming);
  editor.apply(incoming); // now it fits the text on screen
  rev += 1;
}

function onAck() {
  rev += 1;
  inFlight = buffer;      // may be null
  buffer = null;
  if (inFlight) socket.send({ ops: inFlight, baseRev: rev });
}

Why one change in flight keeps it simple

Because a client sends only after its previous operation is confirmed, every operation it sends is based on a revision the server has, and the base revision says exactly what the client has seen. Each transform happens between just two parties, the client and the server, along one agreed history. The next chapter shows why that matters so much.

We tested this client and server with three simulated clients, random edits, and random message delays. In 3,000 sessions of 60 actions each, every copy matched the server at the end.

TP2, and why the server makes it go away

TP1 is about two concurrent operations. With three or more people editing at once there is a second, much harder property, and it is the reason OT has a reputation for being tricky. One small example shows the problem, and how a central server avoids it.

Three editors, no server

Imagine an editor with no server, where every client sends its operations straight to every other client. The text is ab. Three people edit at the same moment, none having seen the others' edits.

• Asha (site 1) inserts x at 1, between a and b.
• Ben (site 2) deletes a, 1 character at 0.
• Cara (site 3) inserts z at 0, before a.

Everyone agrees on the intended result: z was typed before a, x after it, and a is gone, so the text should read zxb. Now suppose one peer received Asha's insert before Ben's delete, and another received them the other way round. When Cara's insert arrives, each peer transforms it against the other two along its own path.

• Path 1, Asha then Ben. Cara's z at 0 is before Asha's x at 1: unchanged. Ben's delete, rewritten against Asha, still deletes position 0, and z at 0 is not inside it: unchanged. Result: zxb. Correct.
• Path 2, Ben then Asha. Against Ben's delete, z stays at 0. Asha's x, rewritten against Ben's delete, moves from 1 to 0. Now z and x are both at 0: a tie, and site 1 beats site 3, so x goes first. Result: xzb. Wrong, and different from the other peer.

Each individual transform followed the rules and passed TP1. The failure comes from combining them. When Ben's delete removed a, it also erased the only fact that told the two inserts apart: one was left of a, the other right of it. Path 2 turned a clear order into a tie, and the tie-break guessed wrong.

What TP2 asks for

TP2, transformation property 2, says: transforming an operation against two concurrent operations must give the same result whichever order you take them in. Not just the same text in the end, but the same rewritten operation, because that operation may be transformed again later. Our functions break TP2, and so do most simple ones.

Fixing it is hard. One known approach keeps deleted characters as invisible tombstones, so positions never collapse and the left-of-a fact survives. In 2003, Imine and colleagues checked several published transform functions with an automated theorem prover and found TP2 counterexamples in them. Peer-to-peer OT is still largely research work.

How the server sidesteps TP2

With a central server, there is only one path. The server picks one order for all operations, and every operation is transformed against the history in that order and no other. A client only ever transforms between two parties: its own pending edits and the server's stream. No operation is ever transformed along two different paths, so TP2 is never needed: TP1 alone is enough.

In the example, the server might accept Asha, then Ben, then Cara. Cara's insert is transformed against Asha's, then against Ben's rewritten delete: path 1, every time, on every client. That is the Jupiter insight, and it is why Google Wave and Google Docs route every edit through a server.

Where the complexity really lives

Plain text with insert and delete is the friendly version of OT: four rules, about 30 lines, and a property test. Real editors are not plain text. A Google Docs document has bold and italic ranges, headings, lists, tables, images, comments, and suggestions. Every one of those is a new kind of operation, and that is where OT gets expensive.

Every new operation type multiplies the rules

Each kind of operation must be transformable against every kind, including itself. Two kinds need 4 rules. Add format (make a range bold), split (press Enter inside a paragraph), and merge (press Backspace at the start of one), and five kinds need 25 rules. Each rule has its own edge cases, like overlaps and ties, and each must pass TP1 for every input.

Some pairs have no obvious right answer. Asha makes a sentence bold while Ben deletes half of it: bold the half that is left. Asha splits a paragraph while Ben merges it with the one above: probably both, in some order, but which text ends up in which paragraph? Ben moves a list item while Asha edits it: the edit should follow the item.

The CKEditor 5 team wrote that applying OT to their tree-shaped documents needed new operations such as rename, split, and merge. Their first implementation took over a year, with several significant reworks over the next two years.

Batching: operations that compose

Sending one operation per keystroke works, but real systems batch. While an operation is in flight, the buffer may collect 20 keystrokes, and editors compose them, merging them into one operation. Many production formats express an operation as a walk over the whole document: retain 12, insert "big ", retain 7, delete 3. That shape composes and transforms neatly, and it is used by ot.js, ShareDB's text types, and Quill's Delta format, which ships compose and transform methods.

{ "ops": [
  { "retain": 4 },
  { "insert": "big " },
  { "retain": 3, "attributes": { "bold": true } },
  { "delete": 4 }
] }

Cursors and undo are transforms too

A cursor is a position, so it goes stale exactly like an insert does. When Asha's insert lands before Ben's cursor, Ben's own cursor must move right, or his next keystroke appears in the wrong place. Remote cursors and selections shown for presence must be transformed the same way. Libraries expose this as a small helper, such as transformPosition in Quill's Delta.

Undo is harder. In a shared document, Ctrl+Z should undo your last edit, not whatever happened last in the document. So the editor keeps the inverse of each of your operations (the inverse of a delete is an insert of the deleted text, which means deletes must remember what they removed) and transforms that inverse against every operation that happened since. Undo of an edit that someone else has since edited around is a classic source of bugs.

What goes wrong in production

A correct transform function is necessary but not enough. Many OT bugs in real products come from the code around it: how positions are counted, how reconnects are handled, and how the server scales. Here are the common ones, how you notice them, and how you fix them.

Counting characters differently

A position is a count of something, and the client and server must count the same thing. JavaScript strings count UTF-16 code units, so an emoji like a thumbs-up is 2 units long. A server in Python counts code points (1 for that emoji), and one in Go or Rust often counts UTF-8 bytes (4). The moment someone types an emoji, every later position is off by one or more, and text gets inserted in the middle of words or of the emoji itself.

You notice it as corruption that only appears in documents with emoji or non-Latin scripts. The fix is to pick one unit, write it in the protocol, and convert at the edges. Many teams pick UTF-16 code units because the editor runs in the browser.

Reconnects that apply an edit twice

A client sends an operation, the connection drops before the ack arrives, and the client reconnects and sends it again. If the first copy did reach the server, the text now has the insert twice. The fix: every operation carries the client's id and a per-client sequence number, so the server can spot a resend, acknowledge it again, and not apply it twice. ShareDB, for example, compares a resent operation's src and seq fields with the operations committed since its base version, and treats a match as already applied.

Clients that fall far behind

The server must keep history back to the oldest base revision any client might send. A laptop that sleeps for a day and wakes up with edits at revision 1,200, while the server is at 9,000, needs 7,800 transforms, and the server must still have all of them. Many servers keep a bounded window, for example the last few thousand operations, plus periodic snapshots. A client whose base revision is older than the window gets the latest snapshot and must rebase or show its unsent edits to the user.

Silent divergence

When a transform rule is wrong, nothing throws. Two people simply see different text and keep editing, and each edit makes the damage worse. Detect it: the server sends a short hash of the document every so often (say every 50 revisions), and the client compares it with a hash of its own copy at the same revision. On a mismatch the client reloads the snapshot and logs the operations that led there, so the bug can be reproduced with the property test.

One writer per document

The server's loop must handle one operation at a time per document, because each one is transformed against the one before it. Two server processes accepting operations for the same document would each build their own history. So production systems route every document to exactly one process, and scale out by spreading documents across processes, not by splitting one document.

A single writer per document is likely one reason products cap how many people can edit one file at once. Google's help pages say a Docs file can be edited on up to 100 open tabs or devices at a time; beyond that, only the owner and some editors can keep editing.

In real products, and when to pick something else

Several widely used collaborative editors run on OT today, and knowing which ones, and why, is useful in an interview.

Who uses OT

• Google Docs. Since 2010, every edit boils down to three kinds of change (insert text, delete text, apply a style to a range) sent to Google's servers, which order them and transform concurrent ones. Each document is saved as a revision log of those changes.
• ShareDB. An open-source Node.js server and client for OT on JSON documents and text. It grew out of ShareJS, written by Joseph Gentle, a former Google Wave engineer. It handles revisions, history, deduplication, and presence, so you only supply the document type.
• CKEditor 5. A rich-text editor whose real-time collaboration uses OT on a tree of elements, with transforms for operations like split, merge, and move.
• Etherpad. An open-source editor whose changesets (called Easysync) are transformed against each other on a central server.

Plenty of products chose differently. Figma's multiplayer uses a central server that resolves each property of each object with last-writer-wins, because design files are trees of objects with properties, not flowing text. Newer editors and local-first apps often pick CRDTs, through libraries like Yjs and Automerge, because they merge without a server.

Performance, security, and accessibility

Performance. The cost per keystroke is small. The cost that grows is catching up: a client that missed m operations with n of its own pending needs about m times n transforms. Batching keystrokes into one composed operation, for example every 50 to 100 ms, keeps both numbers small.

Security. The server must treat every operation as untrusted input. Check that positions and lengths fit the document, cap operation size, and check permissions per operation: a user with comment access must not be able to send an insert. The server always does its own transforming; it never accepts a client's claim about what the result should be.

Accessibility. Remote edits move text under a screen reader user's reading position. Transform the local caret and selection so they stay on the same words, and never move focus because of someone else's edit. Announce remote activity sparingly through a polite live region, such as "Ben is editing paragraph 3", rather than reading out every keystroke.

Using OT in a system design interview

OT comes up in any question about a collaborative editor: design Google Docs, a shared notes app, a code pairing tool, or comments on a live document. You will rarely be asked to write transform functions on a whiteboard. You will be asked how two people's edits merge, and the interviewer wants to hear that you know positions go stale, how OT fixes them, and what a central server buys you.

What to draw

1. The editor on each client with its local copy, an in-flight slot, and a buffer.
2. A WebSocket to a document server that owns one document at a time, with a revision counter and an operation log.
3. Storage: the operation log plus periodic snapshots, which also gives you version history.
4. One concurrent example on the side, like insert at 4 against delete at 0, showing the transformed position.

What to say, by level

Traps to avoid

Spend about two minutes on OT unless the interviewer pulls you deeper. Draw the diamond for one concurrent pair, name the server's role, and move on to storage, presence, and offline behavior. If they ask for more, go to TP2, the history window, and the comparison with CRDTs.

• Saying "we use WebSockets" as if the transport solves merging. It only delivers operations; something still has to fix their positions.
• Proposing last-writer-wins for document text. It loses typing the moment two people edit the same paragraph.
• Claiming OT works peer-to-peer just as easily. It needs TP2 there, which is the hard part.
• Forgetting cursors. Remote and local cursors are positions too and must be transformed.