Design a chat application

Problem Statement

Design a web-based collaborative document editor similar to Google Docs that allows multiple users to simultaneously edit the same document in real-time. Users should see each other's changes as they type, with cursor positions and text selections visible. The system needs to handle conflicts gracefully when multiple users edit the same section of text, maintain document history for version control, and support rich text formatting including bold, italic, lists, and headings.

The application should scale to support documents with thousands of concurrent editors and millions of total users. Focus on the core editing experience, conflict resolution mechanisms, and the infrastructure needed to synchronize changes across clients with minimal latency.

Key Requirements

Functional

• Real-time synchronization -- changes made by any user appear instantly on all other users' screens
• Conflict resolution -- handle simultaneous edits to the same text region without data loss
• Presence indicators -- show active users with their cursor positions and text selections
• Rich text formatting -- support basic formatting operations like bold, italic, and lists
• Document persistence -- save documents reliably and maintain edit history
• Offline editing -- allow users to continue editing when disconnected and sync when reconnected

Non-Functional

• Latency -- propagate changes to all connected clients within 200ms under normal conditions
• Scalability -- support up to 100 simultaneous editors per document and 10 million total documents
• Consistency -- ensure all users converge to the same document state eventually
• Reliability -- maintain 99.9% uptime with no data loss even during server failures

What Interviewers Focus On

Based on real interview experiences, these are the areas interviewers probe most deeply:

1. Operational Transformation vs CRDT Algorithms

The heart of collaborative editing is managing concurrent edits. Interviewers want to see if you understand the fundamental approaches to conflict-free synchronization.

Hints to consider:

• Operational Transformation applies operations in order but requires transformation functions when operations are concurrent
• CRDTs (Conflict-free Replicated Data Types) use commutative operations that can be applied in any order
• Position-based approaches can fail when multiple users insert at the same location simultaneously
• Consider how deletions interact with concurrent insertions in different parts of the document

2. WebSocket Connection Management and Scaling

Real-time collaboration requires persistent connections. Interviewers expect discussion of how to handle many concurrent connections efficiently.

Hints to consider:

• WebSocket servers are stateful, making horizontal scaling more complex than stateless HTTP services
• Connection pooling and sticky sessions may be needed to route users to the correct server
• Heartbeat mechanisms detect dead connections and clean up resources
• Message ordering guarantees must be preserved when routing through load balancers

3. Data Model and Storage Strategy

How you represent the document internally affects performance, conflict resolution, and feature support.

Hints to consider:

• Character-by-character representation vs operation logs vs structured trees each have tradeoffs
• Storing raw operations enables perfect version history but grows unbounded
• Periodic snapshots reduce replay time but add complexity
• Rich text formatting requires tracking styles alongside content positions

4. Network Partition and Offline Handling

When users lose connectivity, the system must handle divergent edits gracefully.

Hints to consider:

• Client-side queuing of operations allows optimistic UI updates
• Version vectors or logical clocks help detect causality when reconnecting
• Large edit backlogs after long offline periods may need special handling
• Consider whether to auto-merge or flag conflicts for manual resolution

Suggested Approach

Step 1: Clarify Requirements

Start by confirming the scope and priorities with your interviewer:

• What's the expected document size? Are we optimizing for short notes or book-length manuscripts?
• How many simultaneous editors per document is realistic? This drastically affects architecture choices.
• What formatting features are in scope? Complex features like tables or embedded media add significant complexity.
• How important is version history? Full edit replay vs simple undo/redo?
• What's the offline experience? Read-only vs full editing capability?
• Are we designing for a specific client platform (web, mobile, both)?

Step 2: High-Level Architecture

Sketch the major components:

Client Application: Web browser running a rich text editor component that captures keystrokes, applies local changes optimistically, and sends operations to the server while receiving and applying remote operations.

WebSocket Gateway: Stateful servers maintaining persistent connections to clients, routing messages between clients editing the same document, and handling connection lifecycle.

Collaboration Service: Manages active editing sessions, applies operational transformation or CRDT logic, broadcasts changes to all connected clients, and coordinates with storage.

Document Storage: Persists document snapshots and operation logs, typically using a database that supports fast writes and range queries for loading edit history.

Presence Service: Tracks which users are currently viewing or editing each document, manages cursor position updates, and handles session timeouts.

Step 3: Deep Dive on Synchronization Protocol

Walk through exactly how concurrent edits are handled:

When User A types "hello" at position 10 while User B types "world" at position 15, both clients immediately update their local view (optimistic updates). Each client assigns a logical timestamp or version number to their operation and sends it to the server.

The server receives both operations, potentially out of order due to network timing. Using Operational Transformation, the server transforms User B's operation to account for User A's insertion, adjusting the position from 15 to 20 (since 5 characters were inserted before it). The transformed operations are then broadcast to all clients.

Each client receives remote operations, transforms them against any concurrent local operations not yet acknowledged by the server, and applies them to the document. This ensures all clients converge to the same state: "hello" at position 10 and "world" at position 20.

For position tracking, use a combination of absolute positions for new operations and transformation functions that adjust positions based on preceding insertions/deletions. Discuss the complexity of handling delete operations that remove ranges being concurrently edited.

Step 4: Address Scalability and Reliability

Discuss how the system handles growth and failures:

Horizontal Scaling: Use consistent hashing to assign documents to WebSocket servers. Clients connect to the server hosting their document. When a server becomes overloaded, migrate some documents to other servers (requires reconnecting affected clients).

Data Persistence: Write operations to a log-structured store (like Kafka or a database transaction log) before broadcasting to clients. This ensures operations aren't lost if a server crashes mid-broadcast. Periodically snapshot the document state to avoid replaying thousands of operations on startup.

Network Failures: Implement exponential backoff for reconnections. When reconnecting, clients send their last acknowledged operation ID so the server can send any missed operations. If the gap is too large, fetch a fresh document snapshot instead of replaying operations.

Monitoring: Track key metrics like operation latency (time from client send to receiving acknowledgment), conflict rate (how often transformations are needed), and WebSocket connection churn (frequent disconnects may indicate network issues).