Design Google Docs (LLD)
Documents, collaborative editing, operational transforms/CRDTs, and version history modelled in objects.
Problem Statement
Design the object model for a Google Docs-like collaborative editor where multiple collaborators can edit the same document at the same time.
The LLD focus is the editing core: documents hold text and versions, insert/delete edits are modelled as Command objects, concurrent commands are reconciled through a pluggable conflict-resolution strategy, collaborator cursors are tracked as presence state, immutable Memento snapshots power version history, and observers push accepted changes to connected clients.
Business context
Collaborative editors sit behind products such as Google Docs, Office Online, Notion, and Figma-like whiteboards. The visible product feels simple, but the object model has to protect a difficult invariant: every participant must converge on the same document even when edits arrive out of order.
Interviewers use this problem to test whether you can separate local edit intent from accepted document state. A strong answer makes edits explicit commands, records versioned snapshots, talks about operational transform or CRDTs at the object level, and keeps network delivery, UI rendering, and persistence outside the core model.
Functional Requirements
Maintain a document id, current text, and monotonically increasing version number.
Accept insert and delete operations from collaborators as command objects carrying author id, base version, position, and payload.
Transform operations submitted against older versions so concurrent edits are reconciled before being applied.
Persist immutable document-version snapshots after accepted edit operations for version history and restore.
Track collaborator cursor positions separately from document versions as presence state.
Notify subscribed observers after accepted edits and cursor moves so clients can refresh without polling.
Expose read-only document text, current version, history, and collaborator cursors to application services.
Reject invalid operations such as negative positions, blank collaborator ids, or edits based on versions newer than the document.
Non-Functional Requirements
Convergence under concurrent editing
All accepted operations must be applied in a single total order, and operations based on older versions must be transformed against the committed operations they missed.
Interactive latency
Submitting an edit should be fast enough for keystrokes. The interview design uses a simple buffer and a short history scan; production can swap in a rope, piece table, or indexed operation log.
Version traceability
Every accepted edit creates an immutable DocumentVersion snapshot with author, operation type, position, payload, and full content so debugging and restore are straightforward.
Extensible conflict policy
Operational transform is represented behind ConflictResolutionStrategy. A CRDT policy, server-authoritative policy, or domain-specific merge can replace it without changing commands.
Safe observer boundaries
Observers receive immutable change events and cursor maps, not mutable document internals. UI, WebSocket, autosave, and metrics subscribers stay decoupled from the core document object.
Requirement Clarification
QAre we implementing full Google Docs with comments, formatting, sharing, and permissions?
No. Scope the base design to a plain-text collaborative editing core. Rich formatting, comments, ACLs, and file storage are extensions layered around the same edit/version model.
QShould conflict resolution be OT or CRDT?
Use an operational-transform style strategy for the LLD implementation because it is easy to show with base versions and position shifts. The strategy interface is the seam where a CRDT algorithm could be substituted.
QDo cursor moves create document versions?
No. Cursor moves are presence events. They update the collaborator cursor map and notify observers, but they do not change document text or create DocumentVersion snapshots.
QDo version snapshots store full text or deltas?
Full-text snapshots are acceptable for the interview because they make Memento clear. Production systems usually combine operation logs, periodic checkpoints, compression, and retention policies.
QWhat happens if an operation arrives with a stale base version?
The service asks the conflict strategy to transform the operation through all committed versions after that base. The transformed command is then applied to the current document version.
UML Class Diagram
Sequence Diagram
Entity Identification
Document
Aggregate root for one editable document. Owns text, current version, edit validation, snapshot creation, restore, and history queries.
Operation
Command interface for all edits. It carries the author's base version and knows how to execute itself against a Document after transformation.
InsertOperation
Concrete command for inserting text at a position. Transformation may shift its position before execution.
DeleteOperation
Concrete command for deleting a range from a position. The accepted snapshot records the actual text removed.
DocumentVersion
Memento of document state after an accepted edit. Stores full content plus metadata needed for history, restore, and later transforms.
ConflictResolutionStrategy
Policy seam for reconciling stale operations. The sample implementation performs a simple OT-style position transform across committed versions.
CollaborationService
Application-facing coordinator. Validates base versions, transforms commands, applies them atomically, updates cursors, and pushes events to observers.
DocumentObserver / ChangeEvent
Observer boundary for connected clients or infrastructure subscribers. Each event carries immutable text, version, operation type, and cursor state.
Design Patterns Used
Operation turns every edit into an object with author, base version, position, payload, and execute behavior. This lets the service queue, transform, audit, and replay edits uniformly.
DocumentVersion captures immutable snapshots of document state after accepted edits. The document can restore a version without exposing mutable internals.
DocumentObserver subscribers are notified after edits and cursor moves. UI sessions, WebSocket gateways, autosave, and metrics can react without being hard-wired into the document.
ConflictResolutionStrategy isolates how stale operations are reconciled. The sample uses OT-style position shifting, while a CRDT or server-specific algorithm can be injected later.
Step-by-Step Design
1Separate document state from collaboration orchestration
The Document owns text and version invariants. The collaboration service owns sessions, cursors, observers, and the transform-and-apply workflow.
public synchronized DocumentVersion apply(Operation operation) { return operation.execute(this); } public synchronized DocumentVersion save(String authorId, String operationType, int position, String payload, int affectedLength) { version++; DocumentVersion snapshot = new DocumentVersion(version, content.toString(), authorId, operationType, position, payload, affectedLength); history.add(snapshot); return snapshot; }2Represent insert and delete as commands
Each edit carries the user's intent and base version. The service can transform the command before execution without knowing whether it inserts or deletes.
public interface Operation { String authorId(); int baseVersion(); int position(); Operation withPosition(int position); DocumentVersion execute(Document document); }3Record accepted versions as mementos
After a command mutates the document, save captures full text plus operation metadata. This snapshot supports history display, restore, and future transform decisions.
4Transform stale commands before applying them
If an operation was based on version 10 but the document is at version 12, transform it through versions 11 and 12. Inserts before the command shift it right; deletes before it shift it left.
for (DocumentVersion change : document.historySince(incoming.baseVersion())) { if (change.isInsert() && transformed.position() > change.position()) { transformed = transformed.withPosition(transformed.position() + change.affectedLength()); } }5Track collaborator cursors as presence, not document history
Cursor moves are real-time collaboration state. They should be broadcast to observers, but they must not increment the document version or pollute version history.
6Push immutable change events to observers
The service publishes ChangeEvent objects after accepted edits and cursor moves. Subscribers get version, text, operation type, author, and a defensive cursor snapshot.
Complete Java Implementation
Explanation of Every Class
Document
Owns the mutable text buffer, current version, and list of immutable DocumentVersion snapshots. It validates edit positions, applies commands, saves mementos, and restores older versions without exposing its internal StringBuilder.
Operation
Command interface shared by all editing operations. It exposes author, base version, position, payload length, cursor result, and execute, giving the service one uniform workflow for transform and apply.
InsertOperation
Concrete command for inserting text. It validates author/base/position, can be copied to a transformed position, inserts into the document, and records an insert snapshot.
DeleteOperation
Concrete command for deleting text. It records the actual removed payload in the accepted version, which is useful for audit, transform metadata, and future undo extensions.
DocumentVersion
Immutable memento containing version number, full content, author, operation type, position, payload, affected length, and timestamp. It is the version-history unit and the restore input.
ConflictResolutionStrategy
Strategy interface with a static factory for the sample OT implementation. It walks committed versions after the incoming operation's base version and shifts positions for prior inserts/deletes, with deterministic tie-breaking for same-position inserts.
CollaborationService
Facade-like collaboration coordinator. It validates operation versions, transforms commands, applies them atomically, updates collaborator cursors, and notifies nested DocumentObserver subscribers with immutable ChangeEvent objects.
Main
Small demo showing observer registration, a cursor move, two concurrent edits based on version 0, OT-style transformation of Bob's delete, and restoring the document to Alice's snapshot.
Dry Run
Sample input
Initial document text is Hello world at version 0. Alice inserts ** brave** at position 5 based on version 0. Bob concurrently deletes 5 characters at old position 6 based on version 0.
| Step | Action | Base version | Transformed position | Document text | Published version |
|---|---|---|---|---|---|
| 1 | Alice cursor moves to 5 | 0 | n/a | Hello world | cursor event only |
| 2 | Alice inserts ** brave** | 0 | 5 | Hello brave world | v1 insert |
| 3 | Bob deletes 5 chars at old position 6 | 0 | 12 after Alice insert | Hello brave | v2 delete |
| 4 | Restore to Alice snapshot | v1 | n/a | Hello brave world | document version becomes v1 |
The important step is 3: Bob's command was authored against version 0, but the service transforms it through Alice's version 1 insert. His delete shifts from position 6 to position 12, so it still removes world instead of deleting part of Alice's inserted text.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| submit edit | O(H + N + O) | O(N) | H committed versions since the base version, N document length for StringBuilder shift/snapshot, O observers to notify. |
| move cursor | O(O + C) | O(C) | Updates one cursor, copies C cursor entries for an immutable event, and notifies O observers. |
| restore version | O(N + V) | O(N) | Copies snapshot text back into the document and prunes versions after the restored version. |
| history lookup | O(V) | O(V) | Returns a defensive copy of V accepted document versions. |
The sample intentionally favors clarity. Production editors avoid full snapshots on every keystroke by using operation logs, periodic checkpoints, compaction, and text structures such as ropes or piece tables.
Extensibility
Replace OT with CRDT
Implement a new ConflictResolutionStrategy that assigns stable character identifiers and merges operations commutatively. Commands and the collaboration service can remain mostly unchanged.
Richer document model
Replace plain text with paragraphs, style ranges, comments, or embedded objects. Operations become typed commands such as apply style, add comment, or insert block.
Per-user undo
Store author-scoped accepted operations and generate inverse commands that are transformed through later operations before being applied.
Durable history
Persist versions and operations through a repository. Keep periodic full snapshots and compact older operations for long-lived documents.
Alternative Designs
CRDT-first editor
Represent each character or span with a globally unique ordered id. Concurrent inserts/deletes merge without a central transform step because operations are designed to commute.
Tradeoffs
Excellent offline and peer-to-peer behavior, but object metadata is heavier and the LLD explanation is harder than a base-version OT strategy.
Event-sourced command log
Store only accepted commands as an append-only log and rebuild document state by replaying from checkpoints.
Tradeoffs
Great auditability and replay, but restore and open-document latency require checkpointing and compaction.
Single document actor
Route all operations for a document to one in-memory actor or queue. The actor serializes edits, transforms stale operations, and broadcasts results.
Tradeoffs
Simplifies locking and ordering but requires partitioning by document id and careful failover for hot documents.
Common Mistakes
- ×
Applying an edit directly to current text without carrying the operation's base version.
- ×
Treating cursor moves as document versions, which pollutes history and creates unnecessary conflicts.
- ×
Returning mutable history lists, cursor maps, or document buffers to observers.
- ×
Using last-write-wins for text edits, which loses user content instead of reconciling intent.
- ×
Creating snapshots without operation metadata, making later transform, audit, or undo logic harder.
- ×
Forgetting deterministic tie-breaking when two collaborators insert at the same position.
- ×
Hard-coding OT logic inside commands instead of behind a conflict-resolution strategy.
Follow-up Interview Questions
QHow do you handle two users inserting at exactly the same position?
Use deterministic tie-breaking such as author id, session id, or server sequence number. Every replica must choose the same ordering so documents converge.
QHow would you support offline editing?
Persist local commands with base versions, submit them when online, and transform or merge them against committed remote changes. CRDTs often simplify this compared with server-side OT.
QHow do you implement undo in a collaborative editor?
Undo should usually be per-user intent, not global rollback. Generate an inverse command for the user's accepted operation and transform that inverse through later operations before applying it.
QWhy not notify observers directly from Document?
The document should stay a pure domain object. The service has collaborator context, cursor state, and delivery concerns, so it is the better observer publisher.
QWhen would you choose CRDT over OT?
Choose CRDT when offline, peer-to-peer, or multi-region convergence is the main driver. Choose OT when a central server can order operations and the team wants a simpler mental model.
Production Considerations
Text storage structure
A StringBuilder is fine for the interview. Production editors use ropes, piece tables, or gap buffers to avoid O(N) shifts on large documents.
Snapshot retention
Full mementos per keystroke are too expensive. Batch edits, checkpoint periodically, compress old snapshots, and retain operation logs for audit.
Delivery architecture
Observers become WebSocket or pub/sub clients. Use per-document sequence numbers, acknowledgements, reconnect replay, and backpressure for slow collaborators.
Locking and scaling
Synchronizing one service instance is enough for LLD. At scale, shard by document id and serialize edits through a document actor, queue partition, or transactional operation table.
Security and abuse control
Validate permissions before accepting operations, cap operation size, rate-limit clients, and audit every accepted command with collaborator identity.
What Interviewers Look For
Did you make insert/delete explicit command objects rather than ad hoc methods on a controller?
Did you explain stale base versions and how a strategy transforms operations through committed history?
Did you separate document versions from cursor presence events?
Did you use immutable mementos for history and restore instead of exposing mutable document state?
Can you clearly discuss the OT versus CRDT tradeoff without trying to implement a full distributed system?
Quiz
0/6 answered
1.Why does each **Operation** carry a base version?
2.Which pattern best describes **DocumentVersion**?
3.What does **ConflictResolutionStrategy** buy the design?
4.Why are cursor moves not saved as **DocumentVersion** entries?
5.Two users insert text at the same position. What must the design guarantee?
6.What is the main tradeoff of full-text snapshots on every edit?
Practice Variants
Add per-user undo
AdvancedGenerate inverse commands for a user's accepted operations and transform those inverses through later history before applying them.
Replace text with styled ranges
AdvancedSupport bold/italic spans and comments while keeping inserts, deletes, and style changes as command objects.
Implement CRDT positions
ExpertAssign stable identifiers to characters and write a ConflictResolutionStrategy that merges inserts/deletes without central position shifting.
Flashcards
Cheat Sheet
Core objects: Document, Operation, InsertOperation, DeleteOperation, DocumentVersion, ConflictResolutionStrategy, CollaborationService, DocumentObserver.
Patterns: Command for edits, Memento for version snapshots, Observer for update pushes, Strategy for conflict resolution.
Edit flow: submit command -> validate base version -> transform through missed versions -> apply to Document -> save DocumentVersion -> update cursor -> notify observers.
Concurrency idea: a command based on an older version is not rejected by default; it is transformed so its original user intent maps onto the current document.
Presence: collaborator cursors are separate from text history and are published as lightweight events.
Production upgrades: rope or piece table for text, operation log plus checkpoints for history, WebSocket/pub-sub observers, per-document actor for ordering, CRDT for offline-first editing.
References
- BookDesigning Data-Intensive Applications — Martin Kleppmann
- PaperConcurrency Control in Groupware Systems — C. A. Ellis and S. J. Gibbs
- PaperA comprehensive study of Convergent and Commutative Replicated Data Types — Marc Shapiro et al.
- DocsRefactoring Guru — Command Pattern