Google Docs (Real-time)

What is being asked

A deeper version of collaborative editing: compare operational transformation (OT) with conflict-free replicated data types (CRDTs), and say when you would choose each.

Requirements

Functional

• Concurrent text editing by many users with live cursors.
• Offline editing with later merge.
• Comments, suggestions and version history.

Non-functional

• Every copy converges to the same text.
• The intention of each edit is preserved as far as possible.
• Latency low enough to feel like typing locally.

Design

Operational transformation

1. Edits are operations such as "insert 'x' at position 5".
2. A central server gives operations a total order. An operation made against an older version is transformed against those it missed: if someone inserted before position 5, the position shifts to 6.
3. Clients transform their unacknowledged operations the same way.

CRDTs

1. Every character gets a unique, permanent identifier that also defines its position relative to its neighbours.
2. Insert and delete refer to identifiers, not to numeric positions, so operations commute: applied in any order they give the same result.
3. No central ordering is needed; any two copies can merge directly.

Key decisions and trade-offs

• OT is compact and well proven, but needs a server. The transformation functions are subtle and their number grows with each operation type.
• CRDTs suit offline and peer-to-peer use, because merging needs no coordinator. The cost is metadata: identifiers per character and tombstones for deletions, which must be compacted.
• Rich text (formatting spans, tables) is harder than plain text under either model.
• With a server available anyway, most products use OT or a server-ordered CRDT, and choose mainly on offline requirements.

Follow-up questions

• Two users insert at the same position at the same time. What does each approach produce?
• How do you clean up tombstones safely?
• How is undo defined when operations from others are interleaved?
• How would you store a long history without loading it all?