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.

Output: Notification messages or empty response if no new notifications.

Database design

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.

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

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...

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

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

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?