cd ..

/ 1 min read

Operation Transformation

What is Operation Transformation?

Operation Transformation (OT) is a set of algorithms and data models specifically designed to support real-time collaborative editing. It helps maintain the consistency of a document across all user versions, even when they make simultaneous changes. Google Docs is one of the most well-known applications that uses OT.

Operation Transformation and Google Docs

Example:

Original Document is ABC

  • User A wants to insert X into index 1 (after A)
  • User B wants to insert Y into index 1 (after A)

In case without OT:

  • A requests “Insert X” into index 1. A’s document is AXBC
  • B requests “Insert Y” into index 1. B’s document is AYBC If the server only ordered apply. It’s going to override or misposition.

In case with OT:

  • A requests Insert('X', 1)
  • B requests Insert('Y', 1)
  • The server receives A’s request first and applies Insert('X', 1) to the document. The document will be AXBC
  • The server then receives B’s request:
    • Insert('Y', 1)
    • However, the document has been modified by A at index 1
    • OT will transform B’s request from Insert('Y', 1) to Insert('Y', 2) (to insert Y after X)
    • It applies this change, and the document becomes AXYBC
  • Finally, the new version is synced to A and B: both the documents of A and B are AXYBC