Case study: File storage and sync (Dropbox, Drive)

You save a file on your laptop. A few seconds later it is on your phone. You change one line in a big file, and the app does not send the whole file again. The interviewer says: "Design Dropbox or Google Drive."

A weak answer stores each file whole and uploads the whole file after every change. It does not say what happens when two devices change one file. A strong answer keeps the bytes and the facts about them in different places. It cuts files into pieces, sends only the new pieces, and tells other devices what changed. It also says how a big upload survives a bad network, and what the app does with two edits of the same file.

At SDE-2 level you should explain the pieces, the metadata and the upload. At SDE-3 level you should also explain sync, conflicts and the cost of sharing pieces between users.

Think of a library with two parts: a warehouse and a record book. Each book is cut into pages of equal size. Every page is stored once in the warehouse, on a shelf named by a fingerprint of the page. The record book lists, for each version of each book, the fingerprints of its pages in order. If you change one page, you put one new page on a shelf and write a new line in the record book. Two people with the same page share one shelf.

A file app works in the same way.

What we build

The requirements:

1. Save and open files in folders from a laptop, a phone and a web page.
2. A change on one device reaches the other devices quickly, even after one was offline.
3. Big files (several GB) upload on a weak network and resume after a break.
4. Old versions can be restored for 30 days (our choice).
5. Two changes to one file never lose work silently.

Chunks and hashes

A chunk is a piece of a file of a fixed size. We use 4 MB. A hash (lesson 43) turns bytes into a number. We use SHA-256, which makes a 32-byte fingerprint. The same bytes always give the same fingerprint. Two different chunks give the same fingerprint with a chance so small that we ignore it.

Each chunk is stored as its own object, named by its fingerprint. A chunk is small, so it goes to the store as one request. A version of a file is a manifest: the ordered list of the fingerprints of its chunks. A 1 GB file is 250 chunks, so the manifest is 250 x 32 = 8,000 bytes.

Now a small change touches one chunk. The client hashes the chunks of the new file. It finds which fingerprints are new, and sends only those chunks. Fixed-size chunks have one weakness. If you insert one byte at the start of the file, every chunk shifts, and every fingerprint changes. Content-defined chunking fixes this. It cuts the file where the data itself matches a pattern, not at fixed places. An insert then changes only the chunks near it. It costs more CPU on the device.

Dedup

Dedup (deduplication) means storing identical data once. Because a chunk is named by its fingerprint, a second copy of the same chunk, in another file or from another user, is already there. The client sends the fingerprints first. The server answers with the ones it does not hold. The cost is a privacy leak. If the answer is "I already have it", an attacker learns that someone stored that exact file. A fix is to share chunks only inside one account, and give up some savings. Another fix is to ask for proof that the client holds the whole file.

Metadata

Keep the bytes and the facts apart. The metadata database has:

• files: file id, owner, parent folder, name, latest version number, deleted flag.
• versions: file id, version number, size, the manifest, time.
• changes: the change journal of a user. It has one row for each saved change, in order. Devices read it to get the latest changes.

A user's files are always read together, and a save changes several rows at once. So split the database by user id (lesson 43). A save then stays inside one database server, and one transaction can make it all-or-nothing (lesson 21).

The parts, put together

• Client: the app on each device. It watches the folder and keeps a local copy.
• Block store: object storage (lesson 24). It holds the chunks.
• Metadata service and database: files, folders, versions, and the list of chunks of each version.
• Chunk index: a key-value store that answers "do we hold this chunk?", so we do not ask the block store about each chunk.
• Queue and workers (lesson 58): background jobs after a save.
• CDN (lesson 36): fast downloads of popular shared files.

Uploading

1. The client cuts the file into chunks and hashes them.
2. It tells the metadata service: "Save this file at this path as the next version after version 7. These are the fingerprints." The service asks the chunk index which ones are missing, and returns pre-signed upload URLs (lesson 24) for those only.
3. The client sends the missing chunks straight to the block store, a few at the same time. If one fails, it sends only that chunk again.
4. The client sends commit, with a commit id. The service checks that every chunk exists. In one transaction it writes the new version, moves the latest version number, and adds an entry to the change journal. Only now is the file visible. The commit id works as an idempotency key (lesson 61), so a repeat does nothing new.
5. A queue (lesson 58) starts jobs that can wait: a virus check, a preview picture, and notices to other devices.

A resume needs no special state. After a break, the client repeats steps 1 and 2. The fingerprints are the same, so the service returns only the chunks that are still missing.

Chunks that were uploaded but never committed are orphans. A weekly job lists the fingerprints used by any version that we keep. It deletes stored chunks that no version uses and that are more than 7 days old (our choice). The age rule protects chunks of an upload that is still running.

Downloading

The client asks for the manifest of a version and gets pre-signed download URLs for the chunks that it lacks. A chunk never changes, and its name comes from its content. So a CDN can keep it for a very long time (the new-name idea of lesson 36). Private files use short-lived signed links.

Sync

Every commit adds one entry to the change journal of the user. The entry gets the next number from a counter for that user (the sequence number of lesson 49). A device keeps a cursor: the number of the last entry it has seen.

1. The server sends a short message to the user's other online devices: "something changed". It carries no data (lesson 75).
2. A device asks: "send the entries after my cursor."
3. For each changed file, the device compares the new manifest with its own. It downloads only the chunks it lacks.
4. It moves its cursor.

A device that was offline asks again when it is back, with the same cursor. A lost message only delays the sync, so a device also asks now and then, for example every 5 minutes (our choice). A new device starts at cursor 0 and receives the whole list.

Conflicts

A conflict happens when two devices change the same file, both starting from the same version, before either knows about the other. The commit says: "this is the version after version 7". The service uses an optimistic version check (lesson 22): it saves only if the latest version is still 7. If not, it does not overwrite.

One simple rule is last write wins: the newest commit replaces the other. It loses one person's work in silence, and "newest" by a clock is unsafe (lesson 49). We keep both. The late commit is saved as a new file named "report (Asha's phone conflicted copy).docx". Both files appear on every device, and a person joins them by hand. A delete against an edit keeps the edit (our choice).

A file app for 10 million users.

Assumptions (made up to teach with, not real data):

• 10 million users store 4 GB each, in 2,000 files each. The average file is 4,000 MB / 2,000 = 2 MB.
• 3 million users are active in a day. Each saves 20 files and uploads 50 MB. The peak is 3 times the average (lesson 14).
• A device uploads at 2.5 MB per second, and hashes at 500 MB per second.
• Dedup saves 25% of the bytes. The rows of one file (the file, its versions and its manifests) take 200 bytes together, and one database server holds 1 TB.
• A call to the metadata service takes 5 ms on 4 cores. A server has a 1 Gbps link. We plan for 70%.

Step 1: size. 10,000,000 x 4 GB = 40,000,000 GB = 40 PB. After dedup: 40 x 0.75 = 30 PB.

Step 2: traffic. 3,000,000 x 50 MB = 150,000,000 MB = 150 TB a day. 150,000,000 / 86,400 = 1,736 MB per second = 13.9 gigabits per second. The peak is 41.7 gigabits per second. If the bytes went through app servers, each with a 1 Gbps link: 41.7 / 0.7 = 59.5, so 60, plus 1 spare = 61 servers. With pre-signed URLs, the bytes go straight to the block store, and the app only handles calls. Commits: 3,000,000 x 20 = 60,000,000 a day = 694 per second, and 2,083 at the peak. Each save makes 3 calls: prepare, commit, and the changes request of the other device. That is 6,250 calls per second. A server takes 4 x 1,000 / 5 = 800, and 560 at 70%. 6,250 / 560 = 11.2, so 12, plus 1 = 13 servers.

Step 3: metadata. 10,000,000 x 2,000 = 20 billion files. 20,000,000,000 x 200 bytes = 4 TB. At 1 TB a server, that is 4 shards. We choose 8, to leave room. Each takes about 2,083 / 8 = 260 commits per second at the peak. The chunk index has 30 PB / 4 MB = 30,000,000,000 MB / 4 = 7,500,000,000 chunks. At 40 bytes for a fingerprint and its place, that is 300 GB.

Step 4: a small change. The 1 GB file has 250 chunks. Sending the whole file takes 1,000 / 2.5 = 400 seconds, about 6.7 minutes. One chunk takes 4 / 2.5 = 1.6 seconds. Hashing the file takes 1,000 / 500 = 2 seconds. The manifest is 8 KB. This answers the predict box: about 4 MB.

Step 5: an insert at the start. With fixed chunks, all 250 chunks change, and the upload takes 400 seconds again. With content-defined chunking, only 1 or 2 chunks change.

Step 6: dedup. A 100 MB installer is 25 chunks. A second user sends 25 x 32 = 800 bytes of fingerprints and no chunk. For 1,000,000 users: without dedup, 1,000,000 x 100 MB = 100 TB. With dedup, 100 MB of chunks, and 1,000,000 x 800 bytes = 800 MB of manifests.

Step 7: a large upload. A 5 GB video is 5,000 / 4 = 1,250 chunks, and a manifest of 40 KB. At 2.5 MB per second, it takes 5,000 / 2.5 = 2,000 seconds, 33 minutes. The link breaks at 80%. A whole-file upload loses 1,600 seconds of work. With chunks, the client loses at most the chunk in flight, 4 MB, which is 1.6 seconds. After the break it sends only the missing chunks.

Step 8: a conflict. The laptop and the phone both have version 7 of budget.xlsx, and both are offline. The laptop commits first, and the file becomes version 8. The phone commits "after 7". The latest is 8, so the service saves a new file, budget (Asha's phone conflicted copy).xlsx, as its version 1. Both files stay.

Step 9: sync. A user makes 20 changes a day. An entry is 100 bytes, so 2 KB a day. A laptop that was off for 7 days asks for 7 x 20 = 140 entries, which is 14 KB.

• Chunks with fingerprints solve big uploads and small changes: 4 MB, not 1 GB. They cost hashing on the device, a manifest for each version, and a weak spot at inserts. I would use content-defined chunking when users edit big files in the middle.
• Dedup across users solves storage: 30 PB, not 40 PB. It costs a privacy leak about who holds a file. I would share chunks only inside an account when privacy matters more than 25%.
• Keeping both files in a conflict solves silent loss. It costs work for the person, and extra files. I would change the rule when conflicts are so common that people stop checking the copies.
• A journal with cursors solves sync after any time offline. It costs one more table and a counter for each user. I would keep it, because the counter is cheap (260 commits per second for each shard).

"When a file changes, the app uploads the whole file again." Only the changed chunks. In Step 4, 4 MB instead of 1,000 MB.

"Last write wins is fine, because it is the newest." It deletes one person's work in silence, and a clock cannot tell which write is newest (lesson 49). In Step 8 both edits stay.

"Dedup is only a saving, so it is always good." The answer "I already have this chunk" tells a stranger that someone stored that exact file. Dedup inside one account avoids this.

1. What is a manifest? Why does a resume after a network break need no special state?
2. A 2 GB file has 4 MB chunks. A device uploads at 4 MB per second. (a) How many chunks are there, and how big is the manifest at 32 bytes for each? (b) How long does the whole file take? (c) You change one chunk. How long does the upload take?
3. Two devices edit the same file from version 12. Device A commits first. Device B commits "after 12" two minutes later. What does the service do, and why not use the newest clock time?