Omij's blogs Collection

How Google Docs Scales Multi-User Sync

4 min read

Google Docs uses Operational Transformation (OT) to enable real-time collaboration across multiple users. OT ensures consistency and concurrency control by transforming user operations so that the final state of the document is the same across all clients, regardless of the order of edits.

“Operational transformation (OT) is a technology for supporting a range of collaboration functionalities in advanced collaborative software systems. OT was originally invented for consistency maintenance and concurrency control in collaborative editing of plain text documents. Its capabilities have been extended and its applications expanded to include group undo, locking, conflict resolution, operation notification and compression, group-awareness, HTML/XML and tree-structured document editing, collaborative office productivity tools, application-sharing, and collaborative computer-aided media design tools. In 2009 OT was adopted as a core technique behind the collaboration features in then-Google Wave and Google Docs.” - wikipedia1

🧠 What Is Operational Transformation?

Operational Transformation is an algorithmic framework designed to manage concurrent operations on shared documents. Originally developed for plain text editing, OT now supports complex use cases including:

  • Collaborative document editing (text, HTML, XML, tree-structured data)
  • Group undo/redo
  • Real-time conflict resolution
  • Application sharing and co-design tools

Google Docs and the now-retired Google Wave adopted OT to power their multi-user sync.

✍️ Basic OT Example

Imagine two users editing a shared document containing the string "abc":

  • O1 = Insert(0, “x”) → User inserts "x" at position 0
  • O2 = Delete(2, “c”) → User deletes "c" at position 2

If O1 is applied first, the document becomes "xabc". But now "c" has shifted to position 3. To maintain correctness, O2 must be transformed into O2′ = Delete(3, “c”). Without this transformation, the wrong character ("b") would be deleted.

🔒 Consistency Models in OT

OT systems maintain two key consistency guarantees, as defined by Ellis and Gibbs (1989):

  • Causality Preservation
    Operations that are causally related must be executed in their cause-effect order.

  • Convergence
    All document replicas must eventually reach the same state, even if operations are applied in different orders.

These guarantees ensure that collaboration feels seamless and accurate for all users.

🔧 OT Operation Models

OT supports two approaches for defining transformation logic:

1. Generic Operation Model

  • Defines transformation functions for primitive operations (e.g. insert, delete, update).
  • Application-specific actions must be adapted to these primitives.
  • Pros: Reusable across different applications.

2. Application-Specific Model

  • Defines transformation functions for each operation pair in the application.
  • For m operations, you need m × m transformation functions.
  • Pros: Tailored precision; Cons: Not reusable elsewhere.

🔄 OT Function Types

OT functions fall into two categories:

• Inclusion Transformation (IT)

Transforms operation Oa to include the effect of concurrent operation Ob.

Example: Adjusting the position of an insert operation when another insert has already occurred.

• Exclusion Transformation (ET)

Transforms Oa to exclude the effect of Ob, often used in undo or rollback logic.

💡 OT Functions

Below are sample transformation functions pseudocode for concurrent insert operations.

Inclusion Transformation

func T(ins1 PositionInsert, ins2 PositionInsert) PositionInsert {
  if ins1.p < ins2.p {
    return ins1
  } else if ins1.p == ins2.p && ins1.sid < ins2.sid {
    return ins1
  } else {
    return PositionInsert{p: ins1.p + 1, c: ins1.c, sid: ins1.sid}
  }
}

Exclusion Transformation

func TInverse(ins1 PositionInsert, ins2 PositionInsert) PositionInsert {
  if ins1.p < ins2.p {
    return ins1
  } else if ins1.p == ins2.p && ins1.sid < ins2.sid {
    return ins1
  } else {
    return PositionInsert{p: ins1.p - 1, c: ins1.c, sid: ins1.sid}
  }
}

Where:

  • p: position
  • c: character
  • sid: site (user) ID

🚀 Conclusion

Operational Transformation is a core technique that enables collaborative tools like Google Docs to deliver real-time, multi-user editing experiences. By transforming operations based on concurrency and context, OT ensures consistency, convergence, and a smooth user experience—no matter how many people are editing at once.

Footnotes

  1. Operational Transformation - Wikipedia. https://en.wikipedia.org/wiki/Operational_transformation ↩