How to Ace a System Design Interview: Creating a Cloud File Storage Service Like Google Drive or Dropbox

Problem Statement:

Create a cloud storage platform akin to Google Drive or Dropbox that offers secure, synchronized, and efficient storage solutions for user data on remote servers. Ensure that users can effortlessly upload and download files from any of their devices. The service must be designed to be highly available, dependable, and scalable to accommodate growing user needs.

Requirement Clarification: (10 Mins)

Functional Requirements:

User Registration and Subscription: Users can easily sign up with their email address and choose a subscription plan. Those who opt not to subscribe will still get 1 GB of free storage.
Users should have the capability to upload and download their files from any device.
File Sharing: Users ought to have the ability to share files and folders with others.
File Size Limit: Users have the capability to upload files as large as 1 GB.
Automatic Synchronisation: The platform ought to facilitate seamless file synchronisation across multiple devices.
Offline Editing: Users need the ability to add, delete, and edit files while offline. When they reconnect, their changes should automatically sync with the remote server and any other connected devices.

Non-functional Requirements:

High Availability: It's crucial for the service to be highly available, allowing users to access their files whenever they need.
Reliability: It's crucial that uploaded files are securely stored and never misplaced, maintaining both data integrity and user confidence.
Support for Large Files: The system needs to efficiently manage large file uploads without any drop in performance.
ACID Operations consist of Atomicity, Consistency, Isolation, and Durability.

Not in Scope:

Working together on a file simultaneously.
Managing different versions of the file.

Quick Calculation: (5 Mins)

Total Users: approximately 500 million.
Daily Active Users: approximately 100 million.
The typical user has approximately 200 files stored.
Each file typically has an average size of 100 KB.
The overall count of active connections every minute equals 1 million.
The entire file count equals 500 million multiplied by 200, resulting in 100 billion.
Total storage necessary = 100 billion * 100 KB = 10 PB.

What is the best way for clients to stay updated on other clients' changes?

Utilize HTTP long polling, where the client asks the server for data, anticipating that the server might delay its response.
If the server doesn't have any new data for the client once the poll arrives, it doesn't just send back an empty response. Instead, it keeps the request open and waits until there's information to send back.
As soon as the server receives new data, it promptly sends an HTTP/S response back to the client, thereby finalizing the pending HTTP/S request.
Once the server's response is received, the client can promptly make another server request to get future updates.

Defining System Interfaces — API Design:- (10 Mins)

Upload Chunk

Request:

GET /api/v1/chunks/:chunk_id
X-API-Key: api_key
Authorization: auth_token

Response:

200 OK
Content-Disposition: attachment; filename="<chunk_id>"
Content-Length: 4096000

Upload Chunk

This API is designed to handle the upload of a file segment.

Request:

POST /api/v1/chunks/:chunk_id
X-API-Key: api_key
Authorization: auth_token
Content-Type: application/octet-stream
/path/to/chunk

Response:

200 OK

Upon a successful upload, the server will respond with an HTTP status code of 200. Here are some potential failure response codes you might encounter:

401 Unauthorized
400 Bad request
500 Internal server error

Get Objects

Clients can use this API to check Meta Service for new files or folders as they become available online.

Request:

GET /api/v1/objects?local_object_id=<Max object_id present locally>&device_id=<Unique Device Id>
X-API-Key: api_key
Authorization: auth_toke

The client will provide both the highest local object ID and the unique device ID.

Response:

200 OK
{
  new_objects: [
    {
      object_id:
      object_type:
      name:
      chunk_ids: [
        chunk1,
        chunk2,
        chunk3
      ]
    }
  ]
}

The Logical Design of the Database Schema :

Illustrated below is the database schema featuring the most essential tables:.

Every individual is required to possess a minimum of one device.
Every device will contain at least one item, such as a file or folder. After a user signs up, we generate a root folder specifically for them, ensuring they have at least one item.
Chunks can only be associated with files, not folders. While any object can have chunks, this property is exclusively for files.
Each item can be accessed by one or several users. This assignment is managed in the AccessControlList.

The database schema containing most important tables is illustrated below:

High-level design

For storage purposes, the files are divided into 4 MB blocks.
The client's device-A handles uploading file blocks and committing the metadata.
Device-B of the client keeps a long polling connection active to receive notifications about any file updates.
The updated metadata and the associated file blocks are retrieved by the client's device-B.
To conserve bandwidth, it's important to transfer just the updated file blocks.

Write Path:-

Path Explanation for Write Operations: When it comes to write operations, there is a specific path that is followed.

The customer starts an HTTP connection with the load balancer to upload the file.
The load balancer employs a round-robin algorithm to assign the client's HTTP connection to a web server that has capacity.
The web server sends the file upload request to the block service.
The block service keeps the file blocks in the block data store.
The web server sends the file metadata change request to the metadata service.
The metadata service saves the altered metadata in the metadata database.
The metadata service queues a message to notify other client devices about the changes to the file.
Optimistic locking is a method that helps handle simultaneous updates to the same file, thereby maintaining data integrity.
The metadata database keeps track of user information and file block metadata, making it handy for editing files while offline.
Consistent hashing is a technique that allows the metadata database to be divided based on either the user ID or file ID.
File deduplication can be achieved by generating hashes for file blocks, which can be done by either the client or server. This helps to minimize storage requirements and cuts down on bandwidth usage.
Concurrent write conflicts are often resolved through either the last-write-wins policy or by having the client manually resolve the conflict.
Files that haven't been accessed in a while can be archived and transferred to a cold data storage solution, helping to free up storage space.
The client's indexer service refreshes the internal metadata database.
The chunker service utilized by the client breaks the file down into segments, with each one being assigned a distinct hash value.
The client's metadata database holds details about files, their chunks, various versions, and file paths.
You can implement file versioning by using a SHA-256 hash or checksum on your files.
To save on storage space and reduce bandwidth usage, file blocks are compressed using either gzip or bzip2.
The client secures file blocks by using the 128-bit AES algorithm for encryption.
The client submits file patches for minor file edits, which helps minimize data transfer.
Exponential backoff helps enhance fault tolerance by steadily extending the intervals between retry attempts.
To enhance availability and durability, the block data store is replicated. This ensures that data remains accessible even if one of the replicas fails.

Read Path:-

Explanation of the Path for Read Operations:

The client initiates a DNS query to find the corresponding IP address for the domain name.
The client requests the Content Delivery Network (CDN) to verify if the most commonly accessed files are stored in the cache.
The client sets up an HTTP connection with the load balancer to access the file.
The load balancer directs the client's HTTP connection to a web server that has free capacity.
The client keeps a long polling connection open to get instant updates whenever there are any alterations to files.
The notification service checks the message queue for any updates to files by employing the request-response pattern.
When there are changes to files, the web server reaches out to the metadata service to obtain the latest metadata.
The metadata service verifies the metadata cache to ensure it has the latest metadata.
If the cache lacks the metadata, a query is made to the metadata database.
The web server contacts the block service to retrieve the latest file blocks.
The block service inspects the block cache for the latest file blocks.
In cases where the file blocks are missing from the cache, a query is made to the block data store.
The block service requests a preview (screenshot) of the files from the preview service.
The preview service queries the block store asynchronously to create previews of the requested files.
The preview service looks into the preview cache to find the previews of files that have been accessed recently.
If the preview isn't available in the cache, the system will fetch it from the preview data store.
The LRU cache eviction strategy is effective for cache servers to optimize the use of cache space.
For security purposes, the cached previews are kept encrypted.
Thin clients, like mobile users, have the ability to synchronize with remote servers on-demand, which helps to reduce bandwidth consumption.
The client has a few options to get real-time updates from the server: they can use long polling, HTTP/2, or Server-Sent Events (SSE).
The notification service can be set up by utilizing the request-response pattern within the message queue.
The request queue serves as a global repository, gathering updates from every device. In contrast, the response queues are specific to each individual device, ensuring that messages are deleted once they’ve been delivered.
A local search index is created to help in searching files more efficiently.
When a user shares a file with someone else, the Access Control List (ACL) table gets updated.
The client’s watcher service monitors alterations in workspace files to enable automated synchronization.
The client’s indexing service interacts with the remote notification service.
The client’s chunker service puts the file back together during the read operation by combining the file blocks.

System Design:-

One of the main difficulties is figuring out the best way and place to store files. Take file sharing, for example. Initially, putting a file of any size onto the cloud is straightforward. However, if you need to make updates later, having to edit and re-upload the whole file each time becomes cumbersome. This method is inefficient because:

Let’s improve the explanation by making it more concise and well-organized. Keep the same mood and tone, and refrain from rephrasing phrases and HTML tags.

Client Components:

Watcher: Keeps an eye on the sync folder to track user actions such as creating, updating, and deleting files, then alerts Indexer and Chunker.
Chunker: Breaks down files into smaller pieces, uploads those pieces to cloud storage with a unique identifier, and manages file updates effectively by only uploading the parts that have been changed.
Indexer: Refreshes the internal database in response to Watcher’s alerts, obtains chunk URLs and hashes from Chunker, and exchanges information with the Synchronisation Service via the Message Queuing Service.
Internal DB: Keeps track of file and chunk details, versions, and where they are stored within the file system.
Metadata Database (RDBMS or NoSQL):.
RDBMS: Maintains data consistency; however, it might encounter scalability challenges as data volume and traffic increase.
NoSQL: Provides eventual consistency, making it essential to manage data consistency effectively in environments with multiple clients.

Relational Database Scaling:

Vertical Scaling: Enhancing hardware performance.
Horizontal Scaling: Increasing the number of machines, although this can be challenging for relational databases that handle numerous read and write operations.

Caching

Cache Types:- (In-memory caching, Distributed caching, Client-side caching).
Cache Strategies:- (Cache-Aside, Write-Through, Write-Behind, Read-Through)...
We can utilize an off-the-shelf solution like Memcache to hold entire chunks along with their corresponding IDs/Hashes. Before Block servers access Block storage, they can swiftly check the cache to see if the needed chunk is available.
By analyzing clients' usage patterns, we can figure out the number of cache servers required.
A premium commercial server may boast as much as 144GB of memory, allowing it to cache around 36K chunks.

Database Sharding:

Definition: Horizontal partitioning involves splitting a large database into smaller, more manageable segments known as shards.
Benefits: Balances load, boosts query efficiency, increases scalability.
Challenges: Handling the intricacies of shard management, transaction coordination, upkeep, backups, and restoration.

Edge Wrapper:

Definition: A level of separation between applications and the common databases they utilize.
Purpose: Offers a cohesive interface while simplifying the intricacies of shard management.
Benefits: Streamlines how applications communicate with databases, controls query routing, and oversees transactions spread across shards.

Object-Relational Mapping (ORM):

Definition: Transforms data from the relational database format into the object-oriented format used by the application, and vice versa.
Benefits: Connects database tables to application objects, making it easier to work with databases and minimizing the requirement for complicated SQL queries.

Combining Edge Wrapper and ORM

Functionality: Edge wrapper incorporates ORM, offering an accessible interface for applications to communicate with shared databases.
Benefits: Streamlines database administration, facilitates horizontal scaling using shared databases, and preserves a developer-friendly interface.

Message Queuing Service:-

The queue for the messaging service will handle asynchronous communication between the clients and the synchronization service.

Capable of managing numerous reading and writing tasks.
Keep a substantial number of messages in a queue that is both highly available and dependable.
Exceptional performance and remarkable scalability.
Offers load balancing and scalability for several instances of the Synchronisation Service.

The service will feature two different kinds of messaging queues.

Queue of Requests:
There will be a queue for handling requests globally, accessible by all clients.
When a client gets any updates or modifications in the files or folders, it sends a request via the request queue.
The synchronization service receives this request to refresh the metadata database.
Queue for Responses:
Each client will have their own dedicated response queue.
The synchronisation service sends out the update via this response queue, which then delivers the updated messages to each client. These clients will subsequently update their respective files based on the new information.
Even if the client loses their internet connection, the message will still be preserved thanks to the messaging queue service.
We’re setting up multiple response queues, one for each client. This is because once a client receives a message, it's removed from their queue, and we need to be able to send the updated message to all the subscribed clients.

Synchronisation Service

The client interacts with the synchronization services to either download the most recent updates from the cloud storage or upload their latest requests or changes to the Cloud Storage.

The synchronization service picks up the request from the messaging service's request queue and refreshes the metadata database with the newest updates.
Additionally, the synchronization service sends the most recent updates to other clients (in cases where there are multiple clients) via the response queue. This allows the indexer on the other clients to retrieve the chunks from the cloud storage and reconstruct the files with the latest updates.
It also synchronizes the local database with the details stored in the Metadata Database. If a client has been offline or disconnected from the internet for a while, it checks for new updates immediately after reconnecting.

Cloud Storage

Any cloud storage service, such as Amazon S3, can be utilized to keep the file chunks uploaded by users. The client interacts with the cloud storage to execute various actions on the files or folders via the API offered by the cloud provider.

Resiliency

Our system demonstrates high resilience due to the following features:

Distributed Block Storage: Data files are split into segments and copied within the same data centre to maintain their durability. Additionally, these segments are spread across multiple data centers in different geographic locations to enhance redundancy.
Queuing: Our platform employs queuing to distribute notifications to clients. In the event a worker fails, the messages in the queue remain unacknowledged, allowing a different worker to take over the task.
Load Balancing: To ensure redundancy, several servers are positioned behind a load balancer.
Geo-redundancy: We operate duplicates of our services in data centers situated in different geographic regions.

Security

Our system boasts exceptional security thanks to the following:

HTTPS : The communication between the client and server is encrypted using HTTPS, ensuring that any intermediary cannot access the information, particularly the content of the files.
Authentication:- After logging in, each API request undergoes authentication by verifying the auth_token included in the Authorization HTTP header.

Followup Questions:-

Data Partitioning and Sharding:

How do you determine the most effective strategy for partitioning and sharding data in your cloud file storage system?
Could you describe the steps you would take to maintain balanced data distribution and optimize query performance?

Consistency Models:

What types of consistency models might be suitable for your cloud-based file storage solution, and what factors would guide your decision in selecting one?
How do you manage the challenges of maintaining consistency in a distributed environment?

Concurrency Control:

Which concurrency control techniques would you employ to manage simultaneous access to files?
How can you make sure that operations like updating or deleting files happen atomically?

Data Compression and Encryption:

What strategies would you use to implement data compression and encryption in your cloud file storage system?
What compromises would you evaluate when balancing security, performance, and storage efficiency?

Data Backup and Disaster Recovery: Safeguarding your information through regular data backups and having a solid disaster recovery plan in place is crucial for business continuity.

What approach would you take to create a system that guarantees data backup and disaster recovery?
What approaches would you implement to reduce data loss and minimize downtime during failures?

Monitoring and Metrics:

What metrics would you keep an eye on to guarantee the health and efficiency of your cloud file storage system?
How can monitoring tools and logging be employed to detect and resolve problems?

Integration with Other Services:

How would you combine your cloud file storage system with various services or applications?
What factors would you consider for smooth integration and data exchange?

Cost Management:

How can you oversee expenses tied to your cloud file storage system?
What approaches would you take to reduce expenses while still ensuring high performance and reliability?

Future Scalability and Extensibility:

How would you set up the system to allow for future expansion and additional capabilities?
What choices in architecture would you consider to guarantee the system maintains both scalability and extensibility?

Compliance and Security Audits:

How do you make sure that your cloud file storage system adheres to compliance standards and successfully passes security audits?
What steps would you implement to tackle any discovered weaknesses or compliance problems?