"CRDTs vs operational transformation"

How collaborative editors merge concurrent edits: the problem of concurrent operations, operational transformation with a central server, CRDTs for text and data, convergence and intent preservation, metadata and performance costs, presence and cursors, and which to choose.

Reading is half of it. See this used in a real interview: walk through Design Google Docs →

Google Docs, Figma, Notion and many other tools let several people edit the same document at once, each seeing their own changes instantly. When two people type at the same place at the same moment, both edits must survive and every copy must end up identical. Two families of algorithms solve this: operational transformation (OT) and conflict-free replicated data types (CRDTs). "Design Google Docs" is mostly about choosing between them and building the system around the choice.

The problem

Alice and Bob both start with "abc".

• Alice inserts "X" at position 1: "aXbc".
• Bob, at the same time, deletes the character at position 2 ("c"): "ab".

If each applies the other's operation naively, Alice deletes position 2 of "aXbc" (which is "b", the wrong character), and the copies diverge. Positions shift under concurrent edits, so operations cannot be applied blindly.

Requirements:

• Convergence: all replicas reach the same state once they have seen the same operations.
• Intent preservation: each edit has the effect its author intended (Bob meant to delete "c").
• Responsiveness: local edits apply instantly, without waiting for the server.

Operational transformation

Each operation is transformed against concurrent operations that were applied first, adjusting positions. In the example, Bob's "delete at 2" is transformed against Alice's "insert at 1" to become "delete at 3".

How it is deployed (as in Google Docs):

• A central server receives operations, decides a single order, transforms incoming operations against those already applied, and broadcasts the result.
• Each client applies its own operations immediately, sends them with the document version they were based on, and transforms incoming server operations against its own unacknowledged ones.

Characteristics:

• Compact operations and documents; little metadata.
• Requires a central authority for ordering in practical implementations; offline editing and peer-to-peer are hard.
• Transformation functions are notoriously tricky to get right for rich content (tables, formatting).

CRDTs

A CRDT is a data structure designed so that concurrent updates commute: applying the same set of operations in any order gives the same result, with no central coordination.

For text, sequence CRDTs give each character a unique, ordered identifier (based on replica id and a counter, positioned relative to its neighbours). Inserts reference identifiers, not positions, so they do not shift; deletes mark identifiers as removed (tombstones). Libraries such as Yjs and Automerge implement this efficiently.

Other CRDTs cover counters (grow-only, increment and decrement), sets (observed-remove sets), registers (last-writer-wins) and maps, so whole JSON-like documents can be CRDTs. See offline-first apps and sync.

Characteristics:

• Works offline and peer-to-peer; any replica can merge any other's changes.
• The server can be a simple relay and store, not a transformation engine.
• Metadata overhead: identifiers and tombstones per character; modern implementations compress this heavily, but large, long-lived documents need garbage collection or compaction.
• Some merge results are surprising for users (interleaving of concurrent inserts in older algorithms), though newer algorithms reduce this.

Comparison

The system around the algorithm

Either way, you need:

• Real-time transport: WebSockets from each client to a collaboration server that hosts the document session. See WebSockets vs SSE vs long polling.
• Session routing: all editors of a document connect to the same server (or a small group), found through consistent hashing or a session registry. See presence and connection management.
• Persistence: an append-only log of operations plus periodic snapshots, so loading a document does not replay its whole history. See event sourcing and CQRS.
• Presence and cursors: ephemeral, high-frequency updates sent to collaborators but not stored.
• Permissions checked on connect and on each operation. See authorization and permissions.
• Version history: named snapshots and the ability to restore.

Choosing

• Always-online collaboration with a central service, rich text, and a team ready to own transformation logic: OT is proven.
• Offline editing, mobile apps, peer-to-peer, or a general data model beyond text: CRDTs.
• Many new systems choose CRDTs with a server that relays, persists and compacts, combining easy offline support with central storage.

In the interview

For Design Google Docs: explain the concurrent edit problem with a two-user example, choose OT with a central session server (or a CRDT with a relay server) and justify it, then cover WebSocket sessions routed by document id, an operation log with snapshots, presence, permissions and version history.

Checklist

• State the convergence and intent preservation requirements.
• OT: central ordering and transformation; CRDT: commutative merges with unique ids.
• Session routing so a document's editors share a server.
• Operation log plus snapshots; tombstone or history compaction.
• Ephemeral presence; permissions on every operation.