Operational Transformation algorithm for collaborative editing(e.g. Google Docs)

Posted on by Simran Chawla

Ever wondered how tools like Google Docs allow multiple people to edit a document simultaneously, without chaos? The answer lies in Operational Transformation (OT), an algorithm designed to handle conflicts and ensure consistency in collaborative editing.

What is OT?

Operational Transformation is the backbone of real-time collaboration systems. It ensures that all users see a consistent document, even when edits happen at the same time. OT works by transforming conflicting operations (like insertions and deletions) so that they can be applied in any order while maintaining the intent of each user’s actions.

How OT Works: Examples of OT in Action

Scenario 1: Concurrent Insertions

  • Initial document: "Hello"
  • User A’s operation: Insert(5, "!") → "Hello!"
  • User B’s operation: Insert(3, "p") → "Helplo"

Conflict:

  • User A inserts "!" at position 5.
  • User B inserts "p" at position 3.
  • Both operations are based on the same initial state, but they modify different positions.

Resolution via OT:

  1. When User A’s operation is transformed relative to User B’s operation:
    • User B’s Insert(3, "p") shifts the position of User A’s insertion.
    • Adjust User A’s operation to Insert(6, "!").
  2. Similarly, User B’s operation is transformed to account for User A’s insertion, but since the insertion occurred at a different position, no changes are needed for Insert(3, "p").

Final document (consistent for both users): "Helplo!"

Scenario 2: Concurrent Deletion and Insertion

  • Initial document: "Hello"
  • User A’s operation: Delete(4, 1) → "Hell"
  • User B’s operation: Insert(5, "!") → "Hello!"

Conflict:

  • User A deletes the letter "o" at position 4.
  • User B inserts "!" at position 5.

Resolution via OT:

  1. Transform User A’s Delete(4, 1) relative to User B’s Insert(5, "!"):
    • Since User B inserts "!" at position 5, the position of User A’s deletion remains unchanged.
  2. Transform User B’s Insert(5, "!") relative to User A’s Delete(4, 1):
    • Since User A deletes "o", User B’s insertion position shifts to Insert(4, "!").

Final document: "Hell!"

Scenario 3: Concurrent Deletions

  • Initial document: "Goodbye"
  • User A’s operation: Delete(1, 2) → "Gdbye"
  • User B’s operation: Delete(0, 1) → "oodbye"

Conflict:

  • User A deletes "oo" starting at position 1.
  • User B deletes "G" at position 0.

Resolution via OT:

  1. Transform User A’s Delete(1, 2) relative to User B’s Delete(0, 1):
    • After User B deletes "G", the start position for User A’s deletion shifts to Delete(0, 2).
  2. Transform User B’s Delete(0, 1) relative to User A’s Delete(1, 2):
    • After User A deletes "oo", User B’s deletion is unaffected.

Final document: "dbye"

Scenario 4: Complex Conflicts

  • Initial document: "abc"
  • User A’s operation: Insert(1, "x") → "axbc"
  • User B’s operation: Delete(2, 1) → "ac"

Conflict:

  • User A inserts "x" at position 1.
  • User B deletes "b" at position 2.

Resolution via OT:

  1. Transform User A’s Insert(1, "x") relative to User B’s Delete(2, 1):
    • User B’s deletion shifts the position of User A’s insertion, so it becomes Insert(1, "x") (unchanged since the insertion occurs before the deletion).
  2. Transform User B’s Delete(2, 1) relative to User A’s Insert(1, "x"):
    • After User A’s insertion, the position of User B’s deletion shifts to Delete(3, 1).

Final document: "axc"

Why OT Works

Preserves Intent: Every user’s action (like an insertion or deletion) is preserved, even during conflicts.
Ensures Consistency: Regardless of the order in which edits are applied, all users see the same final document.
Enables Scalability: OT handles simultaneous edits efficiently, making it ideal for real-time collaboration.

Challenges: When OT Falls Short

While OT is robust, it’s not perfect:
Complexity: Implementing OT for large-scale systems with many concurrent users can be challenging.
Performance Bottlenecks: As the number of operations grows, the transformation process can become computationally expensive.
Not Ideal for All Scenarios: OT assumes all edits are text-based, making it less suited for non-linear content like graphics or complex structures.

Alternatives

OT is not the only algorithm for the purpose of conflict resolution. There are others like CRDTs, DiffSync, Woot, Logoot/Treedoc etc