15. Google Drive

Chapter 15: Design Google Drive

Introduction

Google Drive is a cloud-based file storage and synchronization service that allows users to store, access, and share files from various devices. This chapter discusses designing a scalable system with the following features:

• File Upload and Download
• File Sync Across Devices
• File Sharing
• File Revision History
• Notifications for Edits, Deletes, and Shares

---

Step 1: Understanding the Problem

Key Requirements

Functional Requirements:

• Upload and download files.
• Sync files across multiple devices.
• Maintain file revisions.
• Enable file sharing with permissions.
• Send notifications on file edits, deletions, and shares.

Non-Functional Requirements:

• Reliability: Data loss is unacceptable.
• Fast Sync Speed: Avoid user impatience with delayed syncing.
• Bandwidth Efficiency: Minimize unnecessary data usage.
• Scalability: Handle 10 million daily active users (DAU).
• High Availability: Operate seamlessly during server failures or network issues.

Constraints and Assumptions

• Users get 10 GB free space.
• Maximum file size: 10 GB.
• Average file upload size: 500 KB.
• Upload frequency: 2 files per day per user.
• Total storage required: 500 PB.

---

Step 2: High-Level Design

Single-Server Setup

A basic setup includes:

1. Web Server: Handles uploads and downloads.
2. Metadata Database: to keep track of metadata like user data, login info, files info/
3. Storage Directory: Holds files organized by namespaces.

• A web server and a directory called drive/ is set up as the root directory to store uploaded files.
• Under drive/ directory, there is a list of directories called namespaces.
• Each namespace contains all the uploaded files for that user.
• Each file or folder can be uniquely identified by joining the namespace and the relative path.

This design serves as a starting point but is inadequate for scaling.

APIs

1. Upload a file to Google Drive: Two types of uploads are supported
   • Simple upload: Used when file size is small.
   • Resumable upload:
     • Endpoint: https://api.example.com/files/upload?uploadType=resumable
     • Send the initial request to retrieve the resumable URL.
     • Upload the data and monitor upload state
     • If upload is disturbed, resume the upload.
2. Download a file from Google Drive: To download a file
   • Endpoint: https://api.example.com/files/download
3. Get file revisions:
   • Endpoint: https://api.example.com/files/list_revisions

Moving to Distributed Systems

Improvements:

1. Sharding: Split storage across servers based on user_id.

2. Amazon S3: Use S3 for scalable and redundant file storage with cross-region replication.

   

3. Load Balancer: Distribute traffic across multiple web servers.

4. Metadata Database Replication: Ensure availability through database sharding and replication.

Sync Conflicts:

For a large storage system like Google Drive, sync conflicts happen from time to time. When two users modify the same file or folder at the same time, a conflict happens.

• In the example user 1 and user 2 tries to update the same file at the same time, but user 1’s file is processed by our system first.
• User 1’s update operation goes through, but, user 2 gets a sync conflict.
• The system presents both copies of the same file: user 2’s local copy and the latest version from the server.
• User 2 has the option to merge both files or override one version with the other.

Improved design

1. User Interaction:: Users access the application via browser or mobile app.

2. Block Servers:

   • Files are split into 4 MB blocks (maximum size) and assigned unique hash values.
   • Blocks are stored independently in cloud storage (e.g., Amazon S3).
   • File reconstruction involves joining blocks in a specific order.

3. Cloud Storage: Blocks are stored in cloud storage for scalability and redundancy.

4. Cold Storage: Inactive files are moved to cold storage to reduce costs.

5. Load Balancer: Distributes requests evenly among API servers to ensure efficient operation.

6. API Servers:

   • Handle user authentication, profile management, and file metadata updates.
   • Manage all non-uploading workflows.

7. Metadata Database and Cache:

   • Stores metadata for users, files, blocks, and versions.
   • Frequently accessed metadata is cached for faster retrieval.

8. Notification Service:

   • A publisher/subscriber system that notifies clients about file changes (add, edit, delete).
   • Ensures clients can pull the latest updates.

9. Offline Backup Queue: Temporarily stores file change information for offline clients to sync when back online.

---

Step 3: Design Deep Dive

Metadata Database

A highly simplified is shown below version as it only includes the most important tables and fields.

Schema Design:

• User Table: Stores user profiles and preferences.
• File Table: Maintains file metadata (e.g., size, name, path).
• Block Table: Tracks file blocks for reconstructing files.
• File Version Table: Stores file revision history.

---

File Upload Flow

1. File Upload:
   • File is split into blocks, compressed, and encrypted by the block server.
   • Blocks are uploaded to block servers and stored in S3.
2. Metadata Upload:
   • Client sends metadata to the API server.
   • Metadata is stored in the database with status pending.
3. Completion:
   • S3 triggers a callback to update the file status to uploaded.
   • Notification service informs relevant users.

---

File Sync

1. Delta Sync: Transfer only modified blocks instead of the entire file.

   

2. Compression: Blocks are compressed using compression algorithms depending on file types.

3. Conflict Resolution:

   • First processed version wins.
   • Conflicting versions are saved separately for user resolution.

---

File Download Flow

Download flow is triggered when a file is added or edited elsewhere. There are two ways a client can know:

• If client A is online while a file is changed by another client, notification service will inform client A.
• If client A is offline while a file is changed by another client, data will be saved to the cache. When the offline client is online again, it pulls the latest changes.

Once a client knows a file is changed, it first requests metadata via API servers, then downloads blocks to construct the file.

1. Trigger: Notification service informs the client of file updates.
2. Metadata Fetch: Client retrieves updated metadata via API.
3. Block Download: Client downloads updated blocks from block servers and reconstructs the file.

---

Notification Service

1. Purpose: Keeps clients updated about file changes.
2. Mechanism: Implements long polling for asynchronous notifications.
3. Example: When a file is added, edited, or deleted, notifications are pushed to all relevant clients.

---

Storage Optimization

1. De-duplication: Remove duplicate blocks at the account level using hash-based comparisons.
2. Versioning Strategy:
   • Limit the number of saved revisions.
   • Prioritize recent versions for frequently edited files.
3. Cold Storage: Move rarely accessed files to cheaper storage solutions (e.g., Amazon S3 Glacier).

---

Failure Handling

1. Load Balancer Failure: Secondary load balancer becomes active.
2. Block Server Failure: Pending tasks are reassigned to other servers.
3. Metadata Database Failure:
   • Promote a slave node to master.
   • Redirect traffic to remaining replicas.
4. Cloud Storage Failure: Use cross-region replication to fetch unavailable files.
5. Notification Service Failure: Clients reconnect to alternative servers.