CSE Roadmap

Specialist tier · about 5 hours · 8 parts

Part 4 of 8 · 2 min read

OT

Rewrite the operation.

Idea. A central server picks one order for operations. When an operation arrives that was made against an older version, the server transforms it against all operations that were applied since, so it means the same thing now.

Fixing the example. Text "CAT". Insert("H", 0) from user 1 and Delete(2) from user 2 are concurrent. The server accepts user 1's insert first, giving "HCAT". Now it transforms user 2's Delete(2): since an insert happened at position 0, before position 2, shift to Delete(3). Applying it removes "T", giving "HCA". User 2 receives user 1's insert, and applies it against "CA" as it was: "HCA". User 1 receives the transformed delete: Delete(3) on "HCAT" gives "HCA". All three agree and both intents are kept.

Rules for the basic cases (insert and delete).

  • Insert before another operation's position: that position moves right by 1.
  • Delete before another operation's position: that position moves left by 1.
  • Two inserts at the same position: the server's order decides, and the second shifts right.
  • Two deletes of the same character: the second does nothing.

Server-based protocol.

  1. Each client sends an operation together with the revision number it was based on.
  2. The server keeps a history of operations, each with a revision number.
  3. The server transforms the incoming operation against all operations after that revision, applies it, and gives it a new revision number.
  4. The server broadcasts the transformed operation to the other clients, and acknowledges it to the sender.
  5. A client that sent an operation waits for the acknowledgement before sending another (one in flight), and it transforms incoming operations against its own pending ones.

Because one server orders everything, a single document is always owned by one server. That is simple and correct, and it fits the "partition by document" finding.

A worked example (made up). The document is at revision 10. Client A and client B are both at revision 10. A inserts "X" at 5. B deletes at 2. The server receives A's first (revision 11). B's delete, based on revision 10, is transformed against A's insert (position 5 is after 2, so no change), applied as revision 12, and broadcast. A receives B's delete as revision 12, and B receives A's insert as revision 11, each after transformation against local pending changes. Everyone is at revision 12 with the same text.

Cost. OT is subtle. The transformation rules must be right for every pair of operation types (insert, delete, format, move). The number of pairs grows quickly with each new type, and bugs are hard to find.

Operational transformation

Operational transformation adjusts each edit to account for edits that happened concurrently, so every copy of the document ends the same.

Example: a delete at position 2 becomes a delete at position 3 after someone else inserted a character at position 0.

Check yourself: 1. What does the client send with each operation? 2. In the example, why does Delete(2) become Delete(3)? 3. Why does one server order all operations of a document?