Google Drive

0) Problem Restatement

Design a cloud storage service like Google Drive where users can upload files, sync across multiple devices, share files/folders with others, and access from anywhere. Core challenges include efficient file storage (with deduplication), reliable synchronization across devices, conflict resolution, handling large files, and managing sharing permissions at scale.

1) Requirements

1.1 Functional

• Upload/download files: Users can upload and download files.
• Sync across devices: Changes on one device propagate to all devices.
• File versioning: Keep history of file changes, allow restore.
• Sharing: Share files/folders with read/write/comment permissions.
• Offline access: Access and edit files offline, sync when online.
• Search: Search files by name, content, metadata.
• Notifications: Notify users of file changes, shares.
• Collaboration: Multiple users edit same file (real-time for Docs).
• Trash/restore: Deleted files moved to trash, recoverable for 30 days.

1.2 Non-Functional

• Scalability: Support 1 billion users, petabytes of data.
• Reliability: 99.99% availability, no data loss.
• Performance: Upload/download speed limited by user's bandwidth.
• Consistency: Eventually consistent across devices (sync within seconds).
• Security: Encryption at rest and in transit, access control.
• Storage Efficiency: Deduplication to save storage.

1.3 Scale Estimates

• Users: 1 billion users.
• Files per user: 1000 files avg.
• Total files: 1 trillion files.
• Avg file size: 1 MB.
• Total storage: 1 trillion × 1 MB = 1 EB (exabyte) raw.
• Daily uploads: 10M users upload 10 files/day = 100M uploads/day.
• Concurrent active users: 10M users syncing at any time.

1.4 API Design

The core APIs required for the service:

• Upload File: POST /v1/files/upload - Upload new file or version.
• Download File: GET /v1/files/:id/download - Download file content.
• Get Metadata: GET /v1/files/:id/metadata - specific file info.
• Sync Changes: GET /v1/sync/changes - Get latest updates since cursor.
• Share File: POST /v1/files/:id/share - Update file permissions.

2) High-Level Architecture

2.1 Overview

• Upload Pipeline: Client chunks + hashes → Block Index says which blocks are missing → Client uploads only those to Storage → Metadata commit.
• Sync Pipeline: Change Detection → Notification → Download → Merge.
• Sharing Pipeline: Permission Management → Access Control → Notification.
• Key components: Block storage, metadata service, sync coordinator, sharing service.

2.2 Architecture Diagram

flowchart TB
    %% Clients
    Client1["Client 1<br/>(Desktop)<br/>chunks + hashes locally"] -->|"U1. Commit: file + block hashes"| AG["API Gateway"]
    Client2["Client 2<br/>(Mobile)"] -->|"S1. Sync Request"| AG
    Client3["Client 3<br/>(Web)"] -->|"SH1. Share File"| AG
    
    %% Upload Flow: only hashes go through the API; block bytes go straight to storage
    AG -->|"U2. Which hashes are new?"| Dedup["Block Index Service"]
    Dedup -->|"U3. Check Hash"| BlockDB["Block Metadata<br/>(hash → block_id)"]
    Dedup -->|"U4. Missing hashes + signed upload URLs"| Client1
    Client1 -->|"U5. PUT missing blocks only"| BlockStorage["Block Storage<br/>(S3)"]
    Dedup -->|"U6. Commit new version"| MetadataDB[(Metadata DB)]
    
    %% Metadata Management
    MetadataDB -->|"M1. File Tree"| MetadataService["Metadata Service"]
    MetadataService -->|"M2. Query"| AG
    
    %% Sync Coordination
    Client1 -->|"S2. Watch Changes"| SyncCoord["Sync Coordinator"]
    Client2 -->|"S2. Watch Changes"| SyncCoord
    SyncCoord -->|"S3. Notify Clients"| Notif["Notification Service<br/>(WebSocket/Long Polling)"]
    Notif -->|"S4. Alert"| Client1
    Notif -->|"S4. Alert"| Client2
    
    %% Download Flow
    AG -->|"D1. Download File"| Assembler["File Assembler"]
    Assembler -->|"D2. Fetch Blocks"| BlockStorage
    Assembler -->|"D3. Get Metadata"| MetadataDB
    Assembler -->|"D4. Return File"| Client1
    
    %% Sharing
    AG -->|"SH2. Share File"| ShareService["Sharing Service"]
    ShareService -->|"SH3. Update ACL"| PermDB[(Permission DB)]
    ShareService -->|"SH4. Notify Users"| Notif
    
    %% Search
    AG -->|"SE1. Search Query"| SearchService["Search Service"]
    SearchService -->|"SE2. Query Index"| ElasticSearch["Elasticsearch"]
    MetadataDB -->|"SE3. Index Files"| ElasticSearch
    
    %% Versioning
    Dedup -->|"U7. Save Version"| VersionDB[(Version History DB)]
    
    %% Styling
    classDef client fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    classDef service fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef sync fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px;
    
    class Client1,Client2,Client3 client;
    class BlockStorage,MetadataDB,BlockDB,PermDB,VersionDB storage;
    class Dedup,Assembler,MetadataService,ShareService,SearchService service;
    class SyncCoord,Notif sync;

3) Components (what & why)

Client (Desktop/Mobile/Web)

• Monitor local file system for changes.
• Upload modified files to cloud.
• Download changes from cloud.
• Resolve conflicts (offline edits).

API Gateway

• Route requests to appropriate services.
• Authentication (OAuth), rate limiting.

Chunking (Client-Side)

• The client splits files into blocks (e.g., 4 MB) and hashes each block (SHA-256) on the device.
• Why on the client: the dedup and delta-sync savings are about *not sending bytes*. If the whole file travels to a server-side chunker first, you've already paid for the upload.

Block Index Service (Deduplication)

• Receives the list of block hashes for a new file version and answers "which of these don't you have?"
• If exists: Reuse existing block — nothing is uploaded.
• If new: Returns a signed URL; the client uploads the block directly to Block Storage.
• Impact: Depends heavily on the workload — near 100% for re-uploads and small edits to big files, much lower for unique photos and videos (which are already compressed).

Block Storage (S3)

• Store file blocks (immutable).
• Structure: /blocks/{hash_prefix}/{hash}.
• Redundancy: Multi-region replication.

Metadata Service

• Manage file/folder tree (hierarchy).
• Store file metadata: name, path, owner, size, modified_time, block_list.
• Fast lookups: Index by user_id, path.

Metadata DB

• Store file and folder metadata.
• DB Choice: Relational DB (PostgreSQL) for ACID transactions.
• Partitioning: Shard by user_id.

Sync Coordinator

• Track file changes per user.
• Notify clients of changes to sync.
• Implementation: Maintain version number per file.

Notification Service

• Notify clients of file changes via WebSocket or long polling.
• Scalability: Shard by user_id.

File Assembler

• Reconstruct file from blocks during download.
• Fetch blocks from Block Storage.
• Concatenate in correct order.

Sharing Service

• Manage file/folder sharing permissions.
• Create shareable links with expiration.
• Support read/write/comment permissions.

Permission DB

• Store Access Control Lists (ACL) for files/folders.
• Schema: {resource_id, user_id, permission}.

Version History DB

• Store snapshots of file changes.
• Allow restore to previous versions.
• Retention: Keep versions for 30 days.

Search Service

• Index file names, content (for docs), metadata.
• Use Elasticsearch for full-text search.

4) Data Model

User

User(
  user_id,
  email,
  storage_quota_gb,
  storage_used_gb,
  created_at
)

File/Folder

File(
  file_id,
  user_id,
  parent_folder_id,  -- NULL for root
  name,
  type,  -- FILE, FOLDER
  size_bytes,
  block_hashes[],  -- ordered list of block hashes
  version,
  modified_at,
  created_at
)

Block

Block(
  block_hash,  -- SHA-256
  block_id,
  storage_url,  -- S3 path
  size_bytes,
  ref_count  -- number of files referencing this block
)

Permission

Permission(
  resource_id,  -- file_id or folder_id
  user_id,
  permission,  -- READ, WRITE, COMMENT, OWNER
  granted_at
)

Version

Version(
  version_id,
  file_id,
  version_number,
  block_hashes[],
  modified_at,
  modified_by
)

5) Key Flows

5.1 Upload File Flow

1. User selects file to upload (e.g., 10 MB document).
2. Client app splits file into 4 MB chunks (3 chunks).
3. Client calculates SHA-256 hash for each chunk.
4. Client calls POST /upload {file_id, block_hashes[]}.
5. Deduplication Service checks each hash against Block Metadata DB.
6. For new blocks: Upload to Block Storage.
7. For existing blocks: Skip upload (deduplication).
8. Metadata Service creates/updates File record with block_hashes[].
9. Increment version number.
10. Sync Coordinator notifies other devices of change.

5.2 Download File Flow

1. User requests file download.
2. Client calls GET /download/{file_id}.
3. Metadata Service returns file metadata and block_hashes[].
4. File Assembler fetches blocks from Block Storage.
5. Blocks concatenated in order and returned to client.
6. Client saves file locally.

5.3 Sync Flow (Device A edits, Device B syncs)

1. User edits file on Device A.
2. Device A detects change (file watcher).
3. Device A uploads new version (chunks + metadata).
4. Sync Coordinator increments file version.
5. Notification Service sends change event to Device B via WebSocket.
6. Device B receives notification, downloads new version.
7. Device B merges changes locally.

5.4 Share File Flow

1. User shares file with another user (read permission).
2. Client calls POST /share {file_id, recipient_email, permission: READ}.
3. Sharing Service creates Permission record.
4. Notification Service sends email/notification to recipient.
5. Recipient logs in, sees shared file in "Shared with me".
6. Recipient can view but not edit file.

5.5 Conflict Resolution Flow

1. User A edits file offline on Device 1.
2. User B edits same file offline on Device 2.
3. Both devices come online and upload changes.
4. Sync Coordinator detects conflict (diverging versions).
5. System saves both versions:

• User A's version → file.txt
• User B's version → file (conflicted copy).txt

6) Deep Dive A: File Chunking & Deduplication (~10 mins)

Problem

Storing entire files wastes storage (duplicate files, similar versions). Need efficient storage and fast incremental uploads.

Solution: Client-Side Chunking + Deduplication

Fixed-Size Chunking (Simple)

• Split file into fixed-size chunks (e.g., 4 MB).
• Example: 10 MB file → 3 chunks (4 MB, 4 MB, 2 MB).
• Hash: SHA-256 for each chunk.

Content-Defined Chunking (Advanced)

• Chunk boundaries determined by content (Rabin fingerprinting).
• Benefit: Better deduplication (inserting text at start doesn't shift all chunks).
• Choice: Start with fixed-size chunks (simple, used in the code below); switch to content-defined chunking if many edits insert data mid-file.

Deduplication Algorithm

# Runs on the client
def upload_file(file_id, path, parent_version):
    chunks = split_into_chunks(path, size=4 * MB)
    block_hashes = [sha256(c) for c in chunks]

    # One round trip: server says which blocks it doesn't have yet
    missing = api.find_missing_blocks(block_hashes)   # {hash: signed_upload_url}

    for chunk, h in zip(chunks, block_hashes):
        if h in missing:
            http_put(missing[h], chunk)               # straight to block storage

    # Commit the new version (fails with a conflict if parent_version is stale)
    api.commit_version(file_id, block_hashes, parent_version)

Deduplication Benefits

• User-level: User uploads same file twice → only stored once.
• Global-level: Multiple users upload same file (e.g., popular PDF) → stored once.
• Incremental edits: Changing 100 KB in 10 MB file → only upload new chunks.

Deleting Blocks (Garbage Collection)

• Blocks are shared across files and versions, so deleting a file can't delete its blocks directly.
• Track ref_count per block (or periodically mark-and-sweep from live file versions); delete a block only when nothing references it and it's older than the version-retention window.
• Decrement ref counts asynchronously and idempotently — a crash mid-delete must never drop a block that's still referenced.

Storage Savings

• Example: 1000 users upload same 10 MB file.
• Without dedup: 1000 × 10 MB = 10 GB.
• With dedup: 10 MB (stored once).
• Savings: 99.9%.

Chunking Architecture

flowchart LR
    File["File (10 MB)"] --> Chunker["Chunker"]
    Chunker --> C1["Chunk 1<br/>(4 MB)<br/>hash: a3f5"]
    Chunker --> C2["Chunk 2<br/>(4 MB)<br/>hash: b7e2"]
    Chunker --> C3["Chunk 3<br/>(2 MB)<br/>hash: c9d1"]
    
    C1 --> Dedup["Deduplication"]
    C2 --> Dedup
    C3 --> Dedup
    
    Dedup -->|"new chunk"| Upload["Upload to S3"]
    Dedup -->|"existing chunk"| Skip["Skip (Reuse)"]
    
    Upload --> S3["Block Storage"]
    
    classDef chunk fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    
    class C1,C2,C3 chunk;
    class S3 storage;

7) Deep Dive B: Sync Algorithm & Conflict Resolution (~10 mins)

Problem

Keep files synchronized across multiple devices with minimal data transfer and handle offline edits.

Sync Algorithm (Version-Based)

File Version Tracking

• Each file has a version number (incremented on change).
• Metadata: {file_id, version, modified_at, block_hashes[]}.

Sync Flow

1. Client pulls latest version:

• Client: "What's the latest version of file X?"
• Server: "Version 5, modified at T1."
• If client has version 4 → download version 5.

• Client: "I have version 6 (modified version 5)."
• Server: Accepts if current version is 5, rejects if conflict.

Change Detection

• Client-side watcher: Monitor file system for changes (inotify on Linux, FSEvents on Mac).
• Polling: Periodically check server for new versions.

Conflict Resolution Strategies

Last-Write-Wins (Simple)

• Newest modification time wins.
• Problem: May lose edits made during offline period.

Operational Transform (Complex)

• Used in Google Docs for real-time collaboration.
• Transform operations to maintain consistency.

Manual Merge (Google Drive Approach)

• Detect conflict, save both versions.
• file.txt + file (conflicted copy).txt.
• User manually merges.

Conflict Detection

def upload_new_version(file_id, new_version, parent_version):
    current_version = get_current_version(file_id)
    
    if current_version == parent_version:
        # No conflict
        save_version(file_id, new_version)
        notify_clients(file_id, new_version)
    else:
        # Conflict detected
        save_as_conflicted_copy(file_id, new_version)
        notify_user("Conflict detected, created conflicted copy")

Sync Optimization

• Delta Sync: Only upload changed blocks (incremental).
• Compression: Compress blocks before upload.
• Batch Updates: Upload multiple file changes in single request.

Sync Architecture

stateDiagram-v2
    [*] --> Idle
    Idle --> Detecting: File change detected
    Detecting --> Uploading: Changes found
    Uploading --> Syncing: Upload complete
    Syncing --> Notifying: Update metadata
    Notifying --> Idle: Notify other devices
    
    Uploading --> Conflict: Version mismatch
    Conflict --> ManualMerge: Save conflicted copies
    ManualMerge --> Idle

8) Deep Dive C: Sharing & Permissions (~8 mins)

Problem

Allow users to share files/folders with fine-grained permissions at scale (billions of files, collaborative editing).

Permission Model

Access Control List (ACL)

• Each file/folder has ACL with user permissions.
• Permissions: OWNER, WRITE, READ, COMMENT.
• Inheritance: Folder permissions propagate to children.

Schema

ACL(
  resource_id,  -- file_id or folder_id
  user_id,
  permission,  -- OWNER, WRITE, READ, COMMENT
  granted_by,
  granted_at
)

Sharing Flow

Direct Share

1. User A shares file with User B (READ permission).
2. Sharing Service creates ACL entry: (file_id, user_B, READ).
3. User B can now access file in "Shared with me".

Shareable Link

1. User A creates shareable link (anyone with link can view).
2. System generates unique token: https://drive.google.com/file/xyz?token=abc123.
3. Token stored in DB: {token: abc123, file_id, permission: READ, expires_at}.
4. Anyone with link can access (until expiration).

Permission Propagation (Folders)

• User shares folder with READ permission.
• All files in folder inherit READ permission.
• Implementation: Check parent folder ACLs up the tree — but not with one DB query per level on every request (see below).

Permission Checking

def can_access(user_id, file_id, required_permission):
    # Check direct file permission
    acl = get_acl(file_id, user_id)
    if acl and acl.permission >= required_permission:
        return True
    
    # Check parent folder permissions (recursive)
    parent = get_parent_folder(file_id)
    if parent:
        return can_access(user_id, parent, required_permission)
    
    return False

Revocation

• Remove ACL entry → user loses access immediately (invalidate cached effective ACLs for the subtree).
• Cascade: Revoke folder permission → all children permissions revoked.

Collaboration (Real-Time)

• For Google Docs: Use Operational Transform (OT) or CRDTs.
• Multiple users edit simultaneously.
• Changes merged in real-time via WebSocket.

Sharing Architecture

flowchart TD
    UserA["User A<br/>(Owner)"] -->|"share file"| ShareService["Sharing Service"]
    
    ShareService -->|"create ACL"| PermDB[(Permission DB)]
    ShareService -->|"send notification"| UserB["User B<br/>(Recipient)"]
    
    UserB -->|"access file"| AuthCheck["Authorization Check"]
    AuthCheck -->|"check ACL"| PermDB
    PermDB -->|"READ permission"| Download["Download Allowed"]
    PermDB -->|"no permission"| Deny["Access Denied"]
    
    classDef user fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef service fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    
    class UserA,UserB user;
    class ShareService,AuthCheck service;

9) Scaling & Performance (~5 mins)

Horizontal Scaling

• API Gateway: Stateless, scale with load balancer.
• Metadata Service: Shard by user_id.
• Block Storage: S3 auto-scales.
• Sync Coordinator: Shard by user_id.

Database Sharding

• Metadata DB: Partition by the owner of the file tree (user or shared drive), so a folder and its contents live on one shard and moves/renames stay single-shard transactions.
• Shared files: A file shared with you lives on its owner's shard. Keep a small "shared with me" index per recipient (recipient_id → file_id, owner_shard) and read those files from the owner's shard. Don't copy them into the recipient's shard — every edit would then have to update both.
• Permission DB: Partition by resource_id.

Caching

• Metadata Cache: Redis for frequently accessed file metadata.
• Block Cache: CDN for popular files (public files).

Performance Metrics

• Upload: Limited by user bandwidth + chunking overhead (< 10%).
• Download: Limited by user bandwidth.
• Sync latency: < 5 seconds (notification + download).

10) Failure Modes & Recovery

Client Failure (Mid-Upload)

• Resumable Upload: Client tracks uploaded blocks, resumes from last block.

Metadata DB Failure

• Replication: Use read replicas for failover.
• Backup: Daily snapshots.

Block Storage Failure

• Multi-Region Replication: Store blocks in 3 regions.

Sync Coordinator Failure

• Redundancy: Multiple coordinators, clients reconnect to healthy instance.

11) Trade-offs & Alternatives

Fixed vs Content-Defined Chunking

• Fixed: Simple, predictable chunk size.
• Content-Defined: Better deduplication for edits.
• Choice: Content-defined for advanced systems.

Strong vs Eventual Consistency

• Strong: Immediate sync, complex coordination.
• Eventual: Simpler, acceptable for file storage.
• Choice: Eventual consistency with conflict detection.

Global vs User-Level Deduplication

• Global: Maximum storage savings, but it leaks information: if uploading a block returns "already have it", a user can test whether *anyone* has stored a given file (a confirmation-of-file attack).
• User-Level: Private, less savings.
• Encryption interaction: Per-user encryption keys make identical files look different, which breaks cross-user dedup. Only *convergent* encryption (key derived from the content) keeps dedup working, and it has the same leak.
• Choice: Dedup within a user (or organization), encrypt at rest with service-managed keys. Cross-user dedup only for public content, if at all.

12) Security & Privacy

Encryption

• At Rest: AES-256 encryption for all blocks.
• In Transit: TLS for all API calls.

Access Control

• OAuth 2.0 for authentication.
• ACL for authorization.

Privacy

• Zero-Knowledge Option: End-to-end encryption (user holds keys).
• Audit Logs: Track all file access.

13) Interview Time Allocation (45 min)

• 5 min: Requirements & scope (functional, non-functional, scale).
• 10 min: HLD & architecture diagram (upload, sync, sharing).
• 5 min: Data model & key flows (upload, download, sync, share).
• 10 min: Deep dive on file chunking & deduplication.
• 10 min: Deep dive on sync algorithm & conflict resolution.
• 5 min: Sharing/permissions, scaling, failure handling.

14) Summary

• Core Challenges: Efficient storage (deduplication), reliable sync (conflict resolution), scalable sharing (ACL), handling large files.
• Key Components:
• Chunking: Split files into 4 MB blocks, hash with SHA-256.
• Deduplication: Block-level dedup within a user/org; only missing blocks are ever uploaded.
• Sync: Version-based with conflict detection, manual merge.
• Sharing: ACL with permission inheritance, shareable links.
• Scaling Strategy: Shard metadata by user_id, global block storage, multi-region replication.
• Performance: Sync within 5 seconds, upload/download limited by bandwidth.

This design supports 1 billion users storing exabytes of data with efficient deduplication, reliable cross-device sync, and collaborative sharing.