Loading...
Assumptions
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
Output: Notification messages or empty response if no new notifications.
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.
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.
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 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.
Have a look at the below sequence diagram for upload flow and add metadata flow.
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:
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:
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:
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):
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.
Let's consider a simple text document shared between two users, Alice and Bob, who are concurrently editing the document.
Choice of Conflict Resolution Strategy:
Data Partitioning Strategies:
Choice of Messaging Protocol for Real-Time Updates: