Design Google Drive

An interactive walk through Chapter 15 of System Design Interview (Vol. 1) by Alex Xu. The chapter designs a file storage and sync service like Google Drive, Dropbox, OneDrive or iCloud. Users store files in the cloud, reach them from any device, share them, and every device stays in sync. Each idea below comes with something to click: estimates, uploads that break mid-way, conflicts, real chunking, compression and encryption, the sync flows, and failures.

1The problem

Google Drive stores documents, photos, videos and other files in the cloud. You can reach them from a computer, phone or tablet, and share them with friends, family and coworkers. The design has to do this for millions of people without ever losing a file, while keeping every device in sync quickly and cheaply.

Chapter map

Scope and requirements

Designing all of Drive is too big for an interview, so the candidate asks questions first. The interviewer’s answers fix the scope:

Back-of-the-envelope estimation

The book assumes 50 million signed-up users and 10 million DAU, 10 GB of free space each, 2 uploads per user per day averaging 500 KB, and a 1:1 read-to-write ratio. That gives 500 PB of space allocated, an upload rate of about 240 QPS, and a peak of about 480 QPS. Try your own numbers:

2Start with one server

Rather than drawing the final diagram first, the chapter starts with everything on one machine and scales it up step by step, revisiting ideas from earlier chapters.

One server, one folder per user

A few hours of setup give us an Apache web server, a MySQL database for metadata (users, logins, file info), and a directory drive/ with 1 TB of space for the files. Inside it, each user gets a directory called a namespace. Files keep their original names, so namespace + relative path uniquely identifies any file or folder (Figure 15-3):

drive/
├── alice/                      ← namespace
│   ├── recipes/
│   │   ├── chicken_soup.txt
│   │   └── soup/
│   │       └── best_soup.txt   ← alice + /recipes/soup/best_soup.txt
│   └── photos/
└── bob/                        ← another namespace
    └── notes.txt

Three APIs

All APIs require authentication and use HTTPS, so data is encrypted between client and servers (the book says SSL).

Simple vs resumable uploads

A simple upload sends the whole file in one request, which is fine for small files. A resumable upload is for large files and unreliable networks, in three steps (as in Google Drive’s real API):

1. Send an initial request to get a resumable session URL.
2. Upload the data in chunks and track the upload’s progress.
3. If the upload is interrupted, ask the server how much it received and resume from there.

Try uploading a 2 GB file with each method on a network that drops every few minutes:

With simple uploads, a file that takes longer to send than the typical gap between drops almost never finishes. Resumable uploads only ever lose the chunk that was in flight.

Moving off one server

Eventually the disk fills up. The first fix is to shard: store files on several storage servers, chosen by user_id. That stops the fire, but every file still lives on one machine. On the advice of a friend (“Netflix and Airbnb use S3”), the files move to Amazon S3, which replicates data within a region and across regions. A region is a geographic area where AWS has data centers.

With web servers, metadata database and file storage decoupled, each can scale and fail independently:

• Load balancer: distributes traffic evenly and, if a web server goes down, redistributes its traffic.
• Web servers: easy to add or remove as traffic changes.
• Metadata database: off the web server, so it is no longer a single point of failure, then replicated and sharded.
• File storage: S3, with files replicated in two separate regions.

Sync conflicts

With many users and devices, two of them will sometimes modify the same file or folder at the same time. The book’s strategy: the version processed first wins; the one processed later gets a conflict. The losing user is shown both copies, their local one and the latest from the server, and can merge them or keep one. How does the server notice? Each commit says which version it was based on.

Keeping a document synchronized while several people type into it at once is a different and harder problem (differential synchronization, operational transformation, CRDTs). That is Google Docs territory and out of scope.

3High-level design

The design separates two paths: file content flows through block servers into cloud storage, while metadata (who owns what, which version is latest, which blocks make it up) flows through the load balancer and API servers into the metadata database. A notification service ties the devices together.

The components

Click a component to see what it does, or switch to the upload and download paths.

4Block servers

Sending a whole large file on every small change wastes bandwidth. Block servers do the heavy lifting of uploads (Figure 15-11):

1. A file is split into smaller blocks.
2. Each block is compressed.
3. Each block is encrypted, for security, before it leaves for cloud storage.
4. The blocks are uploaded to cloud storage.

Two optimizations follow from working in blocks: delta sync and compression.

Delta sync

When a file is modified, only the modified blocks are synced, not the whole file (Figure 15-12 shows blocks 2 and 5 changing). A block’s hash identifies its content, so comparing the new file’s block hashes with the stored ones reveals what changed. The book points to the rsync algorithm and librsync for how to do this. The method matters more than it looks:

Try Insert a line at the top in each mode. Fixed-size blocks handle in-place edits and appends well, but an insertion shifts every later boundary. rsync’s rolling checksum and content-defined chunking both find unchanged data even after it moves.

Compression and encryption

Compressing blocks can shrink them a lot, using an algorithm suited to the file type: gzip or bzip2 for text, and different algorithms for images and video. Then each block is encrypted, because files in storage must be encrypted. The order is not arbitrary:

5Metadata

Strong consistency

The system needs strong consistency by default: a file must never look different to different clients at the same time. That applies to the metadata cache and the database.

Memory caches are eventually consistent by default: replicas may hold different data. To make them strongly consistent:

• data in the cache replicas and the master must be consistent;
• invalidate caches on every database write, so cache and database hold the same value.

For the database itself, relational databases make strong consistency easy because they provide ACID transactions (atomicity, consistency, isolation, durability). NoSQL databases don’t support ACID by default, so those guarantees would have to be built into the sync logic by hand. The design therefore picks a relational database.

The database schema

A highly simplified version of Figure 15-13, with only the most important tables:

Run some queries against example rows to see how the tables fit together:

6Sync flows

Upload flow

When a client uploads a file, two requests go out in parallel: one adds the file metadata, the other uploads the content to cloud storage. The metadata’s upload status starts as pending and only becomes uploaded once cloud storage confirms all blocks arrived. Other clients are told at both moments. Editing a file works the same way.

Download flow

Downloads are triggered when a file is added or edited elsewhere. A client finds out in one of two ways:

• Online: the notification service tells it that changes were made somewhere, so it should pull the latest data.
• Offline: the changes are saved, and when the client comes back online it pulls them.

Once a client knows something changed, it first fetches the metadata from the API servers, then downloads the blocks and rebuilds the file.

Notification service

To keep files consistent, every change made on one device must be announced to the others, which also reduces conflicts. The options considered:

Both work. The book picks long polling for two reasons: communication is not bi-directional (the server tells the client about changes, never the reverse), and notifications are infrequent, with no bursts of data. WebSocket suits real-time two-way traffic like chat. With long polling, each client keeps a long-poll connection open. When a change is detected the server answers and the connection closes; the client then fetches the latest changes from the metadata (API) servers. After any response, or a timeout, the client immediately sends a new request.

Offline clients

A client that is offline when a change happens can’t receive a notification. The offline backup queue keeps the information so the change is synced when the client comes back online. Switch the client to “offline” in the upload and download simulations above to watch it. (The download section of the book says these changes are “saved to the cache”; the high-level design calls the component the offline backup queue. They are the same idea.)

7Saving storage space

Keeping a version history and storing copies in several data centers makes storage fill up fast. Three techniques reduce the cost:

De-duplicate data blocks

Two blocks are identical if they have the same hash, so each distinct block needs to be stored only once. Eliminating redundant blocks at the account level is an easy win: the same file saved twice, or two versions that share most of their blocks, cost almost nothing extra. Use Upload a copy of it and Sync this version in the delta sync lab to see it, and the “Blocks vs objects” query in the schema explorer.

Keep fewer versions

An intelligent backup strategy has two options:

• Set a limit on the number of versions; when it is reached, the oldest version is replaced by the new one.
• Keep valuable versions only. A heavily edited document might otherwise be saved over 1,000 times in a short period. Give more weight to recent versions, and experiment to find the right number to keep.

Move infrequently used data to cold storage

Cold data is data nobody has touched for months or years. Cold storage such as Amazon S3 Glacier is much cheaper than S3. Together, the three techniques add up:

8Failure handling

Failures are normal in a large system, and an interviewer may ask how each one is handled:

Break the system

Fail components and compare a design with redundancy everywhere (the book’s) to one where each component is a single instance:

Losing a notification server

Why is reconnecting a million clients slow? The surviving servers can only accept new connections (each with a TLS handshake) at a limited rate. If every client retries at once, the flood itself can eat the capacity needed to let anyone in.

9Wrap-up

The design combines strong consistency, low bandwidth and fast sync. It has two flows, managing file metadata and file sync, plus a notification service that uses long polling to keep clients up to date. No design is perfect: every company has its own constraints, and what matters is knowing the trade-offs of each choice. Two to discuss if time remains:

Upload straight to cloud storage?

Clients could upload directly to cloud storage instead of going through block servers. That is faster, because the file is transferred once instead of twice. The book lists two drawbacks: the chunking, compression and encryption logic must be implemented on every platform (iOS, Android, web), which is error-prone and a lot of engineering work, whereas block servers keep it in one place; and clients can easily be hacked or manipulated, so encryption logic on the client is not ideal.

A presence service

Online/offline tracking currently lives in the notification servers. Moving it into a separate presence service lets other services use it too, for example to show who else is viewing a shared folder.

Beyond the book

Points the chapter leaves open, useful for follow-up questions in an interview.

• Where chunking happens decides what delta sync saves. In the book’s flow, the client sends the whole file to the block servers, so delta sync only saves block server → storage traffic. Dropbox’s clients split files into 4 MB blocks and hash them (SHA-256) on the device, send the list of hashes, and upload only the blocks the server is missing. That saves the slow, metered hop: the user’s uplink.
• Fixed-size blocks and insertions. Hash-compared fixed blocks lose almost everything after an insertion. rsync-style rolling checksums or content-defined chunking fix that, at the cost of more complex clients.
• De-duplication scope versus privacy. De-duplicating across all users saves more space, but if uploading a file you don’t have finishes instantly, you have learned that someone else stores it. Per-user encryption keys also make identical files look different, so cross-user dedup needs special schemes (convergent encryption). Account-level dedup, as in the book, avoids both problems.
• Notifications as hints, a change log as the truth. Real sync engines keep a per-namespace change journal, and each client remembers a cursor into it. A notification just says “pull”; the client asks for everything since its cursor (Dropbox’s API pairs list_folder/longpoll with list_folder/continue). A client returning from a week offline does exactly the same thing, so lost notifications or a dead notification server never lose changes.
• Commit only complete versions. The pending → uploaded status is how the book makes sure a version never points at blocks that don’t exist yet. A failed or abandoned upload stays pending and can be cleaned up.
• Sharing. The schema has no sharing table. One clean model, used by Dropbox, makes a shared folder its own namespace mounted into each member’s tree, with an access-control list. A change then has to notify every member’s devices.
• Owning the storage. At sufficient scale, renting object storage becomes the biggest cost: Dropbox moved most of its data off S3 to its own system (Magic Pocket) in 2016.

Interview cheat sheet

Self-check quiz

Glossary