Todo

Google Doc(CRDT and OT)

April 11, 2026#tech#distributed-systems#crdt#ot#google-docs#collaboration

Notes on CRDTs, Operational Transform, and how Google Docs handles collaborative editing

CRDT

In distributed computing, a conflict-free replicated data type (CRDT) is a data structure that is replicated across multiple computers in a network, with the following features:

  1. The application can update any replica independently, concurrently, and without coordinating with other replicas.
  2. An algorithm, which is itself part of the data type, automatically resolves inconsistencies that might occur.
  3. Although replicas may have different state at any particular point in time, they are guaranteed to eventually converge.
  • This makes CRDTs ideal for optimistic replication, where updates converge later.
  • Traditional pessimistic replication systems try to guarantee from the beginning that all replicas are identical, as if there was only a single copy of the data all along.
  • Optimistic replication gives that up in favor of eventual consistency, meaning replicas are guaranteed to converge only when the system has been quiesced for some time.
  • Because of that, there is no need to wait for all copies to be synchronized before updating data, which helps concurrency and parallelism.
  • The trade-off is that different replicas may require explicit reconciliation later on, which can be hard or sometimes insoluble.

OT (Operational Transform) [Google Docs]

Reference:

  • https://en.wikipedia.org/wiki/Operational_transformation

  • The basic idea of OT can be illustrated with a simple text editing scenario.

  • Given a text document with a string "abc" replicated at two collaborating sites, and two concurrent operations:

    • O1 = Insert[0, "x"] to insert character "x" at position 0
    • O2 = Delete[2, "c"] to delete character "c" at position 2

  • These operations are generated by two users at collaborating sites 1 and 2 respectively.

Suppose the two operations are executed in the order O1 and O2 at site 1.

  • After executing O1, the document becomes "xabc".
  • To execute O2 after O1, O2 must be transformed against O1 to become:
    • O2' = Delete[3, "c"]
  • Its positional parameter is incremented by one due to the insertion of one character "x" by O1.
  • Executing O2' on "xabc" deletes the correct character "c" and the document becomes "xab".
  • If O2 is executed without transformation, it incorrectly deletes character "b" rather than "c".

The basic idea of OT is to transform, or adjust, the parameters of an editing operation according to the effects of previously executed concurrent operations so that the transformed operation can achieve the correct effect and maintain document consistency.

Google Docs

  • Google Docs typically handles this using a centralized server model.
  • Rather than direct client-to-client connections, which would be unmanageable at scale, a central coordination point is used.
  • It uses WebSockets to communicate back and forth between clients and servers for updates.

Rough Comparison

  • CRDT is more replica-first and convergence-first.
  • OT is more operation-transform-first.
  • Google Docs is the classic example people associate with OT.
  • CRDTs are often brought up more in offline-first or peer-heavy collaboration systems.