Classic Designs
Design Google Drive or Dropbox. Covers file chunking, sync conflicts, metadata vs blob storage, versioning, and real-time collaboration.
A cloud file storage service like Google Drive or Dropbox lets users upload, download, sync, and share files across devices. This question tests your understanding of chunked uploads, deduplication, sync conflict resolution, the separation of metadata from blob storage, and real-time notifications. The key challenge is keeping files in sync across multiple devices while handling concurrent edits gracefully.
Assumptions:
- 500M users, average 200 files, average file size 1 MB
- Total files: 100 billion files
- Total storage: 100B x 1 MB = 100 PB
- DAU: 100M users, each syncing ~10 file changes/day
- Sync operations: 1 billion/day ≈ 11,500 ops/sec
Upload bandwidth:
- Average file change: 500 KB (delta, not full file)
- 1B x 500 KB / 86400 = 5.8 GB/sec ≈ 46 GbpsLarge files should not be uploaded or downloaded as a single blob. Instead, break them into fixed-size chunks (typically 4 MB).
File: report.pdf (16 MB)
Chunking (4 MB per chunk):
┌──────────┬──────────┬──────────┬──────────┐
│ Chunk 0 │ Chunk 1 │ Chunk 2 │ Chunk 3 │
│ 4 MB │ 4 MB │ 4 MB │ 4 MB │
│ hash: a1 │ hash: b2 │ hash: c3 │ hash: d4 │
└──────────┴──────────┴──────────┴──────────┘
Each chunk is identified by its content hash (SHA-256).Fixed-size chunking has a problem: if you insert a single byte at the beginning of a file, every chunk boundary shifts, and every chunk hash changes. Content-defined chunking (CDC) uses a rolling hash (like Rabin fingerprint) to determine chunk boundaries based on the content itself.
def content_defined_chunking(data, min_chunk=2*1024*1024, max_chunk=8*1024*1024):
"""Split data into variable-size chunks using rolling hash."""
chunks = []
start = 0
pos = min_chunk # minimum chunk size
while pos < len(data):
# Rolling hash over a window of bytes
if rabin_hash(data[pos-48:pos]) % 4096 == 0 or pos - start >= max_chunk:
chunks.append(data[start:pos])
start = pos
pos += min_chunk
else:
pos += 1
chunks.append(data[start:]) # last chunk
return chunksWith CDC, inserting bytes at the beginning only affects the first chunk. All subsequent chunk boundaries remain the same, so their hashes do not change and they do not need to be re-uploaded.
Since chunks are identified by their content hash, identical chunks are automatically deduplicated.
User A uploads report_v1.pdf → chunks: [a1, b2, c3, d4]
User A uploads report_v2.pdf → chunks: [a1, b2, c3, e5]
Only chunk e5 is new. Chunks a1, b2, c3 already exist in storage.
User B uploads the same report_v1.pdf → chunks: [a1, b2, c3, d4]
All chunks already exist. No data transfer needed!Upload flow with dedup:
This can reduce upload bandwidth by 50-90% for common workloads (many users store similar documents, and version updates change only a few chunks).
A critical architectural decision: separate file metadata from file content.
Metadata Database (SQL - PostgreSQL):
┌──────────────────────────────────────────────────────────────────┐
│ files │
│ ───── │
│ file_id (PK) │ user_id │ name │ path │ size │ version │ updated_at│
│ chunk_list (JSON array of chunk hashes in order) │
│ is_deleted │ sharing_permissions │
└──────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────┐
│ chunks │
│ ────── │
│ chunk_hash (PK) │ reference_count │ storage_location │
└──────────────────────────────────────────────────────────────────┘
Blob Storage (S3 / GCS):
Stores the actual chunk bytes, keyed by chunk_hash.
Provides 11-nines durability through replication and erasure coding.Why separate them?
1. Client detects a file change (filesystem watcher).
2. Client chunks the file using content-defined chunking.
3. Client computes SHA-256 hash for each chunk.
4. Client sends chunk hash list to the Metadata Service.
5. Metadata Service returns the list of missing chunks.
6. Client uploads missing chunks to Blob Storage (direct upload to S3 via presigned URL).
7. Client notifies Metadata Service that upload is complete.
8. Metadata Service updates the file record with the new chunk list and increments the version.
9. Metadata Service sends a notification to other devices via the Notification Service.1. Client receives a notification that a file changed (or polls for changes).
2. Client requests the file's chunk list from the Metadata Service.
3. Client checks which chunks it already has locally.
4. Client downloads only the missing chunks from Blob Storage (via presigned URLs).
5. Client reassembles the file from chunks in order.The client never uploads or downloads chunks through the application server. Instead, the Metadata Service generates presigned URLs (temporary, authenticated URLs) for direct access to S3. This offloads bandwidth from the application tier to the storage tier.
When two users (or two devices of the same user) edit the same file simultaneously, a conflict occurs. There are several strategies:
The simplest approach: the most recent edit overwrites the previous one. Determined by server-side timestamp when the upload completes.
Pros: Simple to implement. Cons: Silently discards one user's changes. Unacceptable for collaborative editing.
When a conflict is detected, save both versions and let the user resolve it manually.
1. Alice edits report.pdf offline (version 3 → version 4a).
2. Bob edits report.pdf offline (version 3 → version 4b).
3. Alice comes online first. Her upload succeeds. File is now version 4.
4. Bob comes online. His upload detects a conflict (his base version 3 is stale).
5. System saves Bob's version as "report (Bob's conflicted copy).pdf".
6. Bob sees both files and manually resolves the conflict.For real-time collaborative editing (like Google Docs), use Operational Transform (OT) or Conflict-free Replicated Data Types (CRDTs) to merge concurrent edits automatically. This is more complex but enables simultaneous editing without conflicts.
For a file storage service like Dropbox (as opposed to a document editor), the branching approach is standard.
Every time a file is updated, a new version is created. This allows users to view and restore previous versions.
┌──────────────────────────────────────────────────────┐
│ file_versions │
│ ────────────── │
│ file_id │ version │ chunk_list │ size │ modified_at │
├─────────┼─────────┼────────────┼──────┼──────────────┤
│ f_001 │ 1 │ [a1,b2,c3] │ 12MB │ Jan 10 09:00 │
│ f_001 │ 2 │ [a1,b2,d4] │ 12MB │ Jan 10 14:00 │
│ f_001 │ 3 │ [a1,e5,d4] │ 12MB │ Jan 11 10:00 │
└─────────┴─────────┴────────────┴──────┴──────────────┘Since chunks are immutable and reference-counted, old versions simply point to the same chunks. No data is duplicated. Deleting an old version just decrements the reference count on its chunks. When a chunk's reference count reaches zero, it can be garbage collected from blob storage.
When a file changes, all devices that have that file need to know. This is a classic fan-out problem.
Each device maintains a persistent connection to the Notification Service. When a file changes, the service pushes the update to all connected devices that have that file.
Notification Flow:
1. Metadata Service publishes event: { file_id: "f_001", version: 3, user: "alice" }
2. Notification Service looks up subscribers for file f_001.
3. For each online subscriber, push the event over their WebSocket.
4. For offline subscribers, queue the event. Deliver on reconnect.Subscription Registry:
file_id: f_001 → [device_alice_laptop, device_bob_phone, device_carol_tablet]
file_id: f_002 → [device_alice_laptop, device_alice_phone]At scale, maintaining per-file subscriptions in memory is expensive. A practical optimization: subscribe at the folder level. If Alice shares a folder with Bob, Bob's devices subscribe to all changes in that folder.
┌──────────────┐
Clients ────────>│ Load Balancer│
└──────┬───────┘
│
┌────────────┼────────────┐
▼ ▼ ▼
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ Metadata │ │ Notification │ │ Auth/Sharing │
│ Service │ │ Service (WS) │ │ Service │
└────┬─────┘ └──────────────┘ └──────────────┘
│
┌────┼───────────────┐
▼ ▼ ▼
┌──────────┐ ┌──────────────┐
│ Metadata │ │ Blob Storage │
│ DB (SQL) │ │ (S3 / GCS) │
└──────────┘ └──────────────┘