System requirements

Functional:

1. User Authentication: Users should be able to create accounts, log in, and manage their profiles securely.
2. Document Creation and Editing: Users must be able to create, edit, and format documents in real-time.
3. Collaborative Editing: Multiple users should be able to edit the same document simultaneously and view changes in real time.
4. Version Control: The system should maintain a history of changes, allowing users to revert to previous versions of the document if needed.
5. Access Control: Document owners should be able to set permissions for other users, determining who can view or edit the document.
6. Export/Import Options: The ability to import documents from different formats (e.g., .docx, .pdf) and export the documents created in the platform as different formats.
7. Real-time Notifications: Users should receive notifications for comments, edits, or any changes made to the documents they're collaborating on.
8. Search Functionality: Users should be able to search for specific documents and content within documents.
9. Offline Editing: Users should have the ability to edit documents offline and sync changes when they reconnect to the internet.

Non-Functional:

• High availability: The system must be accessible at all times, minimizing downtime to ensure continuous collaboration.
• Low latency: End-to-end latency should be under 200 milliseconds.
• Eventual Consistency: All users should eventually see the same document state, even if edits arrive at different times.
• Read-Your-Writes Consistency: Users should see their own edits immediately to confirm their changes have been registered.

Capacity estimation

• DAU = 1 million users
• Traffic spike = 5x → 5 million active users
• Average read requests during peak hours = 5 million users * 10 reads/user/hour = 50 million reads/hour.
• Average write requests during peak hours = 5 million users * 1 writes/user/hour = 5 million writes/hour.
• Average document size = 100KB
• Total documents = 1 million users * 10 documents/user = 10 million documents → Total storage = 10 million * 100KB = 1TB.

API design

1. Document API
   • POST /documents: Create a new document.
   • GET /documents/{id}: Retrieve a document by its ID.
   • PUT /documents/{id}: Update a document's content.
   • DELETE /documents/{id}: Delete a document.
2. Notification API
   • GET /notifications: Retrieve notifications for the user.
   • POST /notifications/mark-read: Mark notifications as read.
3. Version Control API
   • GET /documents/{id}/versions: Retrieve the version history of a document.
   • POST /documents/{id}/versions/{version_id}/restore: Restore a specific version of a document.

Database design

Document Metadata

The document metadata includes:

• Document title, author, permissions, creation and last modified timestamps.
• Access control data (e.g., roles like owner, editor, viewer).
• Versioning pointers, references to document snapshots, and other attributes.

The metadata is typicall small and structured, and the typical queries we need to fulfill are:

• Fast queries and filter: For example, we want to query all documents created by a specific user or retrieving documents the user has permission to edit.
• Data Integrity: We want to make sure the metadata is consistent and correct. For example, the relationship users, documents, and permissions should be highly consistent.
• Transactional Consistency: Operations like adding or updating metadata (e.g., changing permissions or titles) should be atomic

Document Content

Based on the above requirements, we should use a relational database to store the document metadata because:

• It has strong consistency and ACID-compliant transactions.
• Relational databases are optimized for fast complex queries, making it easy for filtering and sorting.
• The constraints that comes with relational databases make it difficult to insert incorrect data and therefore ensure data integrity.

Document content tends to be larger and less structured than metadata, especially for text documents, images, and other rich media. Additionally, the system may need to store multiple snapshots or versions of the content for version history, which increases storage needs over time.

Cloud storage services (e.g., AWS S3, Google Cloud Storage) are designed to handle massive amounts of unstructured data. They are optimized for high throughput, scalability, and durability. They are also cost effective for large amounts of data. Therefore, we should use a cloud storage service to store the document content.

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

1. Client 1 Sends Edit: Client 1 sends an edit to the WebSocket Service over its WebSocket connection.
2. WebSocket Service Adds Edit to Queue: The WebSocket Service places the edit in the message broker queue (e.g., Kafka, RabbitMQ, or Redis Pub/Sub). This decoupling allows the WebSocket Service to quickly move on to handling other incoming messages.
3. Document Service Consumes Edit: The Document Service, acting as a consumer, reads the edit from the queue.
4. Document Service Processes and Persists Edit: The Document Service validates, processes, and persists the edit in the database.
5. Notify WebSocket Service: After updating the database, the Document Service can either:
   1. Notify the WebSocket Service (possibly through the queue) that the update is complete.
   2. Optionally, send the updated document state to the WebSocket Service for broadcasting.
6. WebSocket Service Broadcasts Update: Upon receiving the update or confirmation, the WebSocket Service broadcasts the updated state to all connected clients, including Client 1, Client 2.

Detailed component design

Handling conflicts

Last-Write-Wins

First, let's keep it simple and use the Last-Write-Wins strategy. In this approach, each edit is timestamped, and when conflicts occur, the edit with the latest timestamp is chosen as the winner.

Here's an example:

1. Initial document state: "Hello World"
2. User A starts editing at position 6 at timestamp 100
3. User B starts editing at position 6 at timestamp 101
4. User A sends edit: insert " beautiful" → "Hello beautiful World"
5. User B sends edit: insert " amazing" → "Hello amazing World"
6. Since User B's edit has a later timestamp (101 > 100), the final state becomes "Hello amazing World"

Pros:

• Simple to implement
• Works well for basic collaborative scenarios
• Low overhead in terms of storage and computation

Cons:

• Can lead to lost updates
• Not suitable for fine-grained collaboration where multiple users edit the same region
• May result in unexpected behavior from the user's perspective

This approach is suitable for simple collaborative scenarios where conflicts are rare and losing occasional edits is acceptable. However, for a professional collaborative editing system like Google Docs, we need a more sophisticated approach like Operational Transformation, which we'll discuss next.

Operational Transformation

The primary goal of Operational Transformation (OT) is to ensure that all users see the same final document state after a series of edits, even if those edits are made out of order. It does this by applying transformation functions to modify the conflicting operation so that they can be applied in a way that preserves the intention of each user's changes.

Let's use the same example as above to illustrate how OT works. At step 6, instead of choosing the latest edit, the OT will transform the edit

• Since A's edit comes first, it will be applied first.
• After applying this operation, the document becomes "Hello beautiful World"

OT will then transform User B's Operation Based on User A's Edit

User B wanted to insert " amazing" at position 6 in the original document. However, User A's insertion of " beautiful" has shifted the text "World" to the right.

New Position for User B's Edit: After User A's insertion of " beautiful," position 6 becomes position 16 (because " beautiful" is 10 characters long).

Transformed User B's Operation: Insert " amazing" at position 16 in the updated document.

Now we can apply User B's transformed operation to the document.

The document state becomes "Hello beautiful amazing World" and this is the final state.

This is a simple example. In a real-world collaborative editing system, the operations can be much more complex.

Pros:

• Preserves the intention of each user's changes
• Suitable for fine-grained collaboration

Cons:

• More complex to implement
• OT may have scalability limitations, especially when many users are making edits simultaneously. The transformation functions can become computationally expensive as the number of operations and conflicts increases, potentially leading to performance bottlenecks.

This is one of the reason why collaborative editing systems typically allow only a small number of concurrent users to edit the same document.

What are CRDTs and how do they compare to OT?

CRDTs (Conflict-free Replicated Data Types) are data structures that automatically resolve conflicts in distributed systems.

CRDT vs OT Comparison

Operational Transformation (OT)

• Transforms operations to preserve intentions
• Requires central server for coordination
• Used by Google Docs in early days

CRDTs

• Mathematically guaranteed convergence.
• No central coordination needed
• Each operation is commutative
• Used by Figma, Redis, Google Docs in recent years

How to handle offline editing?

Offline editing presents several challenges that need to be addressed:

1. Local Storage

Cache document state in IndexedDB/LocalStorage

Store pending operations queue

2. Conflict Resolution Strategies

Option 1: Optimistic Updates

Apply changes locally immediately

Queue for sync when online

Resolve conflicts during sync

Used by Google Docs

Option 2: Pessimistic Locking

Require online state for edits

Prevent offline modifications

Used by Dropbox Paper

Option 3: Branch-Based

Create local branch for offline changes, similar to how Git works

Merge when online

More complex but flexible

3. Sync Process

Detect online status

Upload pending changes

Fetch remote changes

Resolve conflicts

Update local state

Trade offs/Tech choices

Choice of Conflict Resolution Strategy:

• Trade-off: Operational Transformation (OT) offers precise conflict resolution but can be complex to implement and may require more computational resources. Conflict-Free Replicated Data Types (CRDTs) offer simpler conflict resolution but may have limitations in certain scenarios.

Data Partitioning Strategies:

• Trade-off: Partitioning data based on user IDs, document IDs, or geographical regions can improve query performance and reduce contention but may lead to uneven data distribution, hotspots, and increased complexity in managing data placement.

Choice of Messaging Protocol for Real-Time Updates:

• Trade-off: Using WebSocket for real-time communication offers low-latency, bidirectional communication but may require additional infrastructure for load balancing and handling large-scale deployments.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

• Optimized Conflict Resolution Mechanism: Implement more advanced conflict resolution mechanisms beyond basic OT or CRDTs, leveraging machine learning or natural language processing algorithms to intelligently merge conflicting edits and enhance collaboration efficiency.
• Integration of Real-Time Presence Indicators: Integrate real-time presence indicators to provide users with visibility into who else is currently viewing or editing a document, fostering better communication and coordination among collaborators.
• Enhanced Versioning and Rollback Functionality: Enhance versioning capabilities to allow users to create snapshots of document states at specific points in time and provide intuitive rollback functionality, enabling easy restoration of previous document versions in case of errors or unwanted changes.
• Geographically Distributed Storage and Caching: Implement geographically distributed storage and caching mechanisms to reduce latency for users accessing the system from different regions, improving overall responsiveness and user experience for global collaboration scenarios.