System requirements

Functional:

• Real-time Collaboration:
• Multiple users should be able to simultaneously view and edit a document in real time.
• Changes made by one user should be immediately reflected for all other users.
• User Authentication:
• Users should be able to create accounts and log in securely.
• Authentication mechanisms should be in place to control access to documents.
• File Management:
• Users should be able to upload and download documents.
• Users should be able to sync files across multiple devices seamlessly.
• Document Versioning:
• The system should support document versioning. Users should be able to view and restore previous versions of a document.
• Document Formatting:
• Users should be able to format text, insert images, create tables, and make other formatting changes to the document.
• Comments and Suggestions:
• Users should be able to add comments, suggestions, and annotations to the document for collaboration purposes.
• Revision History:
• The system should maintain a detailed revision history of all changes made to a document.
• The system should also show who made the changes and when.
• Notifications:
• Users should receive real-time notifications for changes made by other collaborators, comments, and mentions.

Non-Functional:

• Scalability:
• The system should be able to handle 10 million daily active users (DAU).
• Should support a peak QPS of 480 for the upload API.
• Reliability:
• The system should have high availability, aiming for 99.9% uptime.
• Data integrity and consistency should be maintained across all users and devices.
• Security:
• User authentication should be secure and follow best practices.
• Document access should be controlled based on user roles and permissions.
• Data transmission should be encrypted.
• Performance:
• The real-time collaboration feature should have low latency, ensuring a smooth editing experience.
• File uploads and downloads should be optimized for efficiency.
• Document Size and Frequency:
• Support an average file size of 1 KB.
• Assume users upload 2 files per day.
• Auditability:
• Maintain detailed logs for all user actions, document changes, and system events.
• Support auditing and analysis of system usage.

Capacity estimation

Assumptions

• Consider we have 10 million active users
• Average file size is 10KB
• Each user creates 2 files per day.

Daily Storage:

File size per user per day: 2 files * 10 KB = 20 KB

Total daily storage for all users: 20 KB/user * 10 million users = 200,000,000 KB

Yearly Storage:

Total daily storage * Days in a year: 200,000,000 KB/day * 365 days = 73,000,000,000 KB/year

Storage for 5 Years:

Total yearly storage * 5 years: 73,000,000,000 KB/year * 5 years = 365,000,000,000 KB

Storage in PB: 365,000,000,000 KB = 3.6 PetaByte

API design

1. User Authentication API:
2. Description: Authenticate users and provide access to the system.
3. Input: User credentials (username, password).
4. Output: Authentication token or error message.
5. Document Upload API:
6. Description: Allow users to upload documents to the system.
7. Input: Document file, user authentication token.
8. Output: Success message or error response.
9. Document Fetch API:
10. Description: Enable users to download documents from the system.
11. Input: Document ID, user authentication token.
12. Output: Document file or error response.
13. Share Document API:
14. Description: Facilitate sharing of a document document.
15. Input: Document ID, user authentication token, collaborator user id.
16. Output: Updated document state or error response.
17. Document Versioning API:
18. Description: Manage document versions, allowing users to view and restore previous versions.
19. Input: Document ID, user authentication token, version information.
20. Output: Document with specified version or error response.
21. Comments and Suggestions API:
22. Description: Allow users to add comments, suggestions, and annotations to a document.
23. Input: Document ID, user authentication token, comment text.
24. Output: Updated document state with comments or error response.
25. Revision History API:
26. Description: Provide access to the revision history of a document.
27. Input: Document ID, user authentication token.
28. Output: Revision history log or error response.
29. Notifications API:
30. Description: Send real-time notifications for changes made by collaborators, comments, and mentions.
31. Input: User authentication token, notification preferences.
32. Output: Notification messages or empty response if no new notifications.

Database design

Here are a few tables that we will use for our design. This is not an exhaustive list but this is a good starting point.

Database Choices

1. User Data:
2. Database Type: Relational Database (e.g., PostgreSQL, MySQL).
3. Reasoning: User data involves structured information, and relational databases provide strong consistency and ACID transactions, ensuring accurate and secure user authentication and authorization.
4. Focus: Consistency-focused. Implications: Ensures the reliability and integrity of user authentication and authorization data, critical for security and access control.
5. File Content:
6. Database Type: Document Database (e.g., MongoDB).
7. Reasoning: File content, stored as documents, benefits from the flexible schema and scalability of NoSQL databases, supporting efficient handling of varying content structures.
8. Focus: Availability-focused. Implications: Prioritizes availability for real-time collaboration, allowing for efficient storage and retrieval of document chunks.
9. Metadata and Chunk Information:
10. Database Type: Relational Database.
11. Reasoning: Metadata and chunk information involve structured data and relationships, making a relational database suitable for consistency and relational queries.
12. Focus: Consistency-focused. Implications: Ensures reliable and consistent handling of metadata, access control, and versioning, supporting collaborative editing with a consistent version history.
13. Access Control Information:
14. Database Type: Relational Database.
15. Reasoning: Access control information requires maintaining relational integrity and consistency, making a relational database suitable for enforcing and managing access permissions.
16. Focus: Consistency-focused. Implications: Ensures accurate enforcement of access control rules, maintaining a consistent and secure access environment.
17. 
    

Overall Focus and Implications:

• Overall Focus: Balanced (Consistency and Availability).
• Implications: This balanced approach ensures a reasonable level of consistency while maximizing availability for real-time collaboration. Relational databases are used for structured data that demands strong consistency, while a document database is employed for the flexible and scalable storage of file content. This combination supports the collaborative document editing system's goals of providing a seamless user experience and maintaining the reliability and security of user and document-related data.

Data Partitioning

Best Partitioning Strategy:

Range-based partitioning based on user ID ranges would be the most suitable strategy for this problem. It allows for efficient distribution of user-related data across different nodes, ensuring that user-specific documents, access controls, and metadata are co-located, reducing cross-node communication.

Reasoning:

Range-based partitioning aligns well with the fact that users are likely to access and collaborate primarily on their own documents, leading to more localized data access patterns. This minimizes the need for data movement across nodes during user-specific operations, improving overall system performance.

The "jump" in Jump Consistent Hashing refers to the ability to quickly jump between partitions. This characteristic is essential for efficiently locating the partition associated with a given key while minimizing computational overhead.

Partitioning Algorithm:

A consistent hashing algorithm, such as the Jump Consistent Hashing (JCH) algorithm, can be employed for mapping user IDs to specific partitions. Consistent hashing ensures a balanced distribution of data and provides flexibility in scaling by minimizing the impact of adding or removing nodes in the system.

Sharding

Best Sharding Strategy:

Range-based sharding based on user ID ranges would be the most suitable strategy for this problem. It aligns well with the likely access patterns, as users are more likely to collaborate on their own documents, ensuring that related data is co-located on the same shard and minimizing cross-shard communication.

Reasoning:

Range-based sharding is efficient for distributing user-related data evenly across shards while maintaining the locality of data access for users. This strategy supports optimized retrieval of documents, access control information, and collaboration activities, contributing to better overall system performance.

Scaling Strategy: Horizontal or Vertical

The best scaling strategy for databases in the context of a collaborative document editing service is horizontal scaling. This allows for distributing the workload across multiple nodes, accommodating the potential growth in users and data, and improving overall system performance by adding more servers as needed.

Read/Write Separation

Read/Write Separation is beneficial for improving performance, especially in scenarios where there is a high volume of read operations compared to writes. In a collaborative document editing service, where users frequently read and collaborate on documents, implementing Read/Write Separation allows for optimized resource allocation, faster response times for read-heavy operations, and improved overall user experience.

High-level design

1. Web App / Mobile App:
2. User interfaces for accessing and collaborating on documents, supporting three user types: Owners, Commentors, and Editors.
3. API Gateway:
4. Facilitates communication between clients and backend services, routing requests to appropriate services like Authentication, Analytics, Document Service, Comment Service, and Notifications.
5. Auth Service:
6. Manages user authentication and authorization, ensuring secure access to the collaborative document editing service.
7. Analytics:
8. Provides monitoring and logging functionalities, offering insights into system performance and user interactions.
9. Document Service:
10. Handles document-related operations, such as storage, retrieval, and collaboration, interacting with Document DB and Relational DB.
11. Comment Service:
12. Manages comments and annotations on documents, storing data in both the Relational DB and utilizing an Event Queue for real-time updates.
13. Event Queue:
14. Enables asynchronous communication and event handling between different services, ensuring real-time collaboration and responsiveness.
15. Notifications Service:
16. Sends real-time notifications to users about changes, comments, and mentions in documents, enhancing collaboration awareness.
17. Document DB:
18. Dedicated database for storing document content, supporting efficient retrieval and updates during collaborative editing.
19. Relational DB:
20. Manages structured data, including user information, access controls, comments, and metadata, providing consistency for relational data.
21. In-Memory Cache:
22. Improves performance by caching frequently accessed data from Document Service and Comment Service, reducing latency in document-related operations.

Request flows

Have a look at the below sequence diagram for upload flow and add metadata flow.

Detailed component design

Since this design problems is complex and contains a lot of components, to simplify lets break down and discuss smaller flows and components.

For operations like, upload and download the design is very similar to google drive design, we have separate services that will help us with authentication, storing metadata, creating, uploading and downloading the files.

To efficiently handle upload, edit operation on files, the files are divided into chunks and then these chunks are uploaded to the server, each file is divided into multiple chunks, the file metadata table stores information about all these chunks. Storing files into multiple chunks also helps with versioning and providing user with the history of updates on the file.

Chunking and use of block servers

For large files that are updated regularly, sending the whole file on each update consumes a lot of bandwidth. Two optimizations are proposed to minimize the amount of network traffic being transmitted:

• Delta sync: When a file is modified, only modified blocks are synced instead of the whole file using a sync algorithm
• Compression: Applying compression on blocks can significantly reduce the data size. Thus, blocks are compressed using compression algorithms depending on file types.

In our system, block servers do the heavy lifting work for uploading files. Block servers process files passed from clients by splitting a file into blocks, compressing each block, and encrypting them. Instead of uploading the whole file to the storage system, only modified blocks are transferred.

Notification service and Real-Time collaboration

To maintain file consistency, any changes performed on the fule locally needs to be informed to other clients to reduce conflicts. Notification service is built to serve this purpose. At the high-level, notification service allows data to be transferred to clients as events happen. Here are a few options:

• Long polling. We can use long polling in client so they can always poll the server for any changes.
• WebSocket. WebSocket provides a persistent connection between the client and the server. Communication is bi-directional.

Even though both options work well, we opt for long polling for the following two reasons:

WebSocket is suited for real-time bi-directional communication and collaboration. WebSocket is a communication protocol that enables bidirectional, real-time communication between clients and servers. It facilitates instant updates and notifications.

Implementation: WebSocket can be used to establish a persistent connection between clients and the server, allowing for immediate transmission of edits and changes.

Access Control

Google Docs allows us to invite collaborators and assign them various levels of permission, such as read-only or owner. However, for more precise access control, we can use Role-Based Access Control (RBAC).

RBAC ensures that employees only have access to the information and resources needed to fulfill their specific job responsibilities, and cannot access information that is not relevant to their role. This helps to protect sensitive data and maintain network security.

In the RBAC model, access can be restricted to specific actions, such as reading, creating, or editing files, based on various variables including authorization, responsibility, and job expertise. This ensures that only those with the appropriate permissions can perform

certain actions, which helps to protect sensitive data and critical applications. RBAC has several advantages, including:

• Increasing operational effectiveness
• Increased visibility of the owner
• Cost reduction
• Reducing the risk of data breaches

Real time collaboration and algorithms to resolve conflicts

Real-time collaboration in a document editing system involves allowing multiple users to concurrently view and edit the same document while ensuring consistency and minimizing conflicts. Several algorithms and techniques can be employed to achieve real-time collaboration, we will discuss the following 2:

Conflict-Free Replicated Data Types (CRDTs):

• How it works: CRDTs are data structures designed to be conflict-free and convergent. They allow concurrent updates without the need for extensive coordination, making them suitable for real-time collaboration.
• Implementation: CRDTs are used for different types of collaborative data, such as text documents (Treedoc), sets (LWW-Element-Set), or counters (G-Counter).
• Merge Semantics: CRDTs define specific merge semantics for each data type. These semantics ensure that when concurrent updates occur on different replicas, the replicas can be merged together in a deterministic and conflict-free manner. Merge functions for CRDTs are carefully designed to guarantee convergence, often using techniques like Last-Writer-Wins (LWW) , First-Writer-Wins (FWW) or counter-based approaches

Let's consider a simple text document shared between two users, Alice and Bob, who are concurrently editing the document. We'll use a basic CRDT called a "G-Set" (Grow-Only Set) to demonstrate how changes made by both users can be merged without conflicts.

1. Initial Document State:
2. Both Alice and Bob start with an empty document.
3. User Actions:
4. Alice: Adds the word "Hello" to the document.
5. Bob: Adds the word "World" to the document.
6. CRDT Representation:
7. Each user maintains a G-Set to track the words they have added to the document.
8. Alice's G-Set: { "Hello" }
9. Bob's G-Set: { "World" }
10. Merging CRDTs:
11. When Alice and Bob synchronize their changes, their G-Sets are merged:
12. Merged G-Set: { "Hello", "World" }
13. Resulting Document State:
14. Both "Hello" and "World" appear in the document, reflecting the combined changes made by Alice and Bob.
15. Concurrency Handling:
16. Even if Alice and Bob had added words simultaneously, the G-Set ensures that all additions are included in the merged state, preventing conflicts. Merge Semantics decide how the words are ordered in the resultant document.

Operational Transformation (OT):

• Transform Functions: OT relies on transform functions to modify operations, ensuring that the effects of concurrent edits are properly integrated. Transform functions are applied both at the client and server sides.
• Synchronization and Consistency: OT requires regular synchronization between clients and the server to maintain a consistent view of the document. Synchronization involves exchanging operation logs and applying transformations.
• User Intent Preservation: OT aims to preserve user intent during concurrent edits. Even if operations are applied in a different order, the resulting document state should reflect the users' intended changes.

Let's consider a simple text document shared between two users, Alice and Bob, who are concurrently editing the document. 

1. Initial Document State:
2. Both Alice and Bob start with a document that contains “BC”.
3. User Actions:
4. Alice: Inserts the character "D" at position 2 
5. Bob: Inserts the character "A" at position 0.
6. Individual Representation:
7. Alice's Version: { "BCD" }
8. Bob's G-Set: { "ABC" }
9. Merging:
10. When Alice and Bob synchronize their changes, the OT functions are applied to create a merge, both of them pass a function to the server which applies transformation:
11. Alice => INSERT(“A at beginning”, “BCD”) => “ABCD” 
12. Bob => INSERT(“INSERT D at position 2”, “ABC”) => Here the server compares the versions and transform Alice’s changes to be made at position 3 => “ABCD”
13. Resulting Document State:
14. Both of them get “ABCD” in the document, reflecting the combined changes made by Alice and Bob. Transformation function takes care of merging the changes.

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.

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.