Collaborative editing: operational transformation or CRDT

The interviewer says: "Design a shared document, like Google Docs. Two people type in the same sentence at the same moment. Both must see the same text, and nobody's typing may vanish."

A weak answer saves the whole file on each key press, or locks the document for one editor. A strong answer sends small edits, not files. It says how edits made at the same time are put in one order or merged, and what that costs. It also covers cursors, undo and saved history.

This is an SDE-3 question. At SDE-2 level you should know why whole-file saves lose edits. At SDE-3 level you should work an example of both methods and compare them.

Two people read the same shop list. Ravi says "put milk as the 1st item". At the same time Asha says "cross out the 3rd item". If Ravi's change lands first, Asha's "3rd" now points to a different item. Numbers shift when others edit.

Sending the whole file does not work either: the last save wins and the other edits vanish (last write wins, lesson 78). So we send operations. An operation is one small edit: "insert x at position 5" or "delete the character at position 2". There are two ways to keep operations correct.

Operational transformation (OT)

OT fixes the shifted numbers. One server puts all operations in a single order and keeps them in a log with revision numbers.

1. The client applies its own edit at once, so typing feels instant. It sends the operation with the revision it last saw.
2. The server may be on a newer revision. It transforms the operation against each operation that was applied since: it changes the position so that the operation means the same thing now.
3. The server adds it to the log and sends it to every client. A client transforms the incoming operation against any edit of its own that is still waiting.

The rules for inserts and for deletes of one character are short. "Earlier" means earlier in the server order.

• An insert moves right by the length of an earlier insert that is at the same position or before it. At the same position the earlier one goes first, or the copies would differ.
• An insert moves left by one if an earlier delete was before it.
• A delete moves right by the length of an earlier insert at or before it. It moves left by one if an earlier delete was before it.
• If two deletes hit the same character, the second one does nothing.

Google described this client and server design for Google Docs in 2010.

CRDT for text

From lesson 78, a conflict-free replicated data type (CRDT) is a data type that you can copy to many places. The authors of the idea define it so. Any copy can change without asking another copy. Any two copies that have received the same updates reach the same state.

For text, give every character a unique ID, such as a client number and a counter (like the clocks of lesson 77). An insert says "put this character after the character with ID x". IDs never change, so nothing shifts. A delete does not remove the character. It marks it as deleted, a tombstone, because another copy may still say "insert after x". If two people insert after the same character, a fixed rule on the IDs decides the order. For example, the larger ID goes first. So every copy agrees. Updates can arrive in any order, and no server is needed.

Comparing the two

Around the algorithm

• One server for each document. All editors of a document connect to the same server, by WebSocket (lesson 107). A lookup table or a hash of the document ID chooses the server. That server orders or relays operations.
• Cursors and presence (who is online). A cursor is not part of the document. Send it as a small message, and do not store it. In OT, shift a cursor like any position. In a CRDT, anchor it to a character ID, so it does not shift. A user with no heartbeat for a while is shown as offline.
• Undo. Undo must reverse your own last edit, not the last edit of anyone. Keep a stack of your own operations and apply the reverse of one, transformed against what came after.
• Reconnecting. A client that lost its connection sends the last revision it saw. The server replies with the operations it missed.
• History. Store every operation in a log. Save a snapshot of the whole text now and then. To open a document, load the newest snapshot and replay the operations after it.

A third option: settle each property

A design tool, such as a canvas, has many objects with a few properties each: x, y, colour. The server stays the single authority and keeps the latest value of each property. Two people who change different properties both win. Two who change the same property: the later one wins (last write wins for that property). This is simpler than OT and CRDTs. It is a poor fit for the characters inside one text. A whole paragraph would be one property, and one person's typing would be lost.

The document says HELLO at revision 0. Three people edit at the same time, all on revision 0. Positions start at 0.

• Ravi: insert ">> " (3 characters) at position 0.
• Sunita: delete the character at position 1, which is E.
• Asha: insert "!" at position 5, the end.

Step 1: whole-file saves. Each saves the file she sees. The last save wins, so 2 of the 3 edits are lost.

Step 2: OT. The server receives them in this order: Ravi, Sunita, Asha.

1. Ravi: no earlier edit. Insert at 0. Text: ">> HELLO", revision 1.
2. Sunita: Ravi's insert at 0 is before her position 1, so move right by 3: delete at 4. Text: ">> HLLO", revision 2.
3. Asha: against Ravi's insert, 5 moves to 5 + 3 = 8. Against Sunita's delete at 4, which is before 8, move left by 1: 7. Insert at 7. Text: ">> HLLO!".

Against Ravi alone the answer to the predict box is 8; Sunita's delete then moves it to 7. Without the transform, an insert at 5 would give ">> HL!LO", which is wrong. Every client reaches ">> HLLO!".

Two rows. The document is HELLO and Asha wants to insert an exclamation mark at position 5. Ravi inserted 3 characters at the start first, so the document is now two angle brackets, a space and HELLO, and her insert moves to position 8.

Step 3: a tie. Asha inserts "!" and Bina inserts "?", both at position 5. The server takes Asha first. Bina's position moves to 6. The result is "HELLO!?" in every copy.

Step 4: CRDT, the same edits. The letters have IDs c1 to c5. Asha's "!" is "after c5". Ravi's three characters are each "after" the one before, starting from the document start. Sunita marks c2 as deleted. The three updates can arrive in any order. Every order gives ">> HLLO!", and nothing is transformed.

Step 5: memory. Assumption: a document of 100,000 characters of 1 byte each, and 25 bytes of ID and links for each character. OT keeps 100,000 bytes of text. A CRDT keeps 100,000 x 25 = 2,500,000 bytes = 2.5 MB, which is 25 times more. If the editors also typed and deleted 200,000 more characters, the tombstones add 200,000 x 25 = 5 MB. Total 7.5 MB, 75 times the text. Real libraries pack runs of characters typed in order into one item, so they use less.

Step 6: offline. A phone types for 10 minutes at 5 operations per second: 3,000 operations. Others made 600 in that time. OT must transform each of the 3,000 against the 600: 3,000 x 600 = 1,800,000 transforms. Assumption: 1 microsecond each, so 1.8 seconds.

Step 7: history. A document has 500,000 operations of 50 bytes each: 25 MB. A replay of all operations at 100,000 per second takes 5 seconds. With a snapshot every 1,000 operations, opening replays at most 999: 0.01 seconds.

Step 8: servers. Assumption: 3,000,000 editors online at peak, and one server holds 50,000 connections (lesson 107). Servers: 3,000,000 / 50,000 = 60.

What companies wrote

• Google wrote on 23 Sep 2010 that Google Docs clients and a server use operational transformation. A client transforms a remote change against its own waiting change, and the server keeps a revision log. That post is from 2010, so today's design is not confirmed. Link: https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs.html (opens in a new tab)
• Figma wrote on 16 Oct 2019 that it chose not to use OT, which it called very complicated and hard to implement correctly. Its system is inspired by CRDTs but is not a true one. The server is the central authority, and the latest value of each property wins. Link: https://www.figma.com/blog/how-figmas-multiplayer-technology-works/ (opens in a new tab)

OT solves shifted positions with a small server state and a small log. It costs a central server and hard transform rules, and a long offline stretch costs a pile of transforms (1,800,000 here). A CRDT solves offline editing and having no server, and it costs memory (25 to 75 times the text here). Property-by-property settling is the simplest, and it costs lost typing inside one text. I would use OT for text with a server, a CRDT where offline editing matters, and property rules for canvases.

"A CRDT needs no server." The merge needs none. But users still need a place that stores the document and checks who may edit.

"OT just adds a number to each position." The shift depends on the type and place of every earlier operation, and ties need a rule. In step 2 the position moved right, then left.

"Deleted characters can be removed at once." Another copy may still insert after one. A tombstone can go only when every copy has seen the delete. The Yjs library, for example, throws away the content of a deleted item but keeps a small marker.

1. In OT, what does the server do to an operation made on an older revision? In a CRDT, why is a deleted character kept?
2. The text is ABCDE at revision 0. Ben inserts "XY" at position 1. Chen deletes position 3. Dev inserts "!" at position 5. All three work on revision 0. The server order is Ben, Chen, Dev. Give the final position of Chen's and Dev's edits, and the final text.
3. A team builds a design tool where users drag shapes (x, y, colour). They plan to use a text CRDT for everything. What do you say?