Design Google Drive

Do the numbers before the boxes

An interviewer gives a scale, not a load. If we draw before we do the math, we cannot say why any box has its size.

A 45-minute version of this answer is at the end.

We assume about 1.176 million daily users at launch, each saving about 3.67 files a day. 1,176,000 x 3.67 = 4.32 million saves a day.

4,320,000 / 86,400 = 50 saves a second on average. The evening peak is twice that, our assumption: 100.

Later we grow 10 times: 500 saves a second on average, 1,000 at the peak. A save is a file created or changed and committed.

One device is online per daily user at the evening peak, our estimate. A desktop client stays connected whenever the computer is on.

Some daily users have nothing on at the peak; others have a laptop and a phone app in the foreground. So 1.176 million online devices, then 11.76 million.

Each save makes 4 API calls: an upload session, a commit that records the change, and 2 listings where other devices fetch it.

And 2.5 block transfers: 1 up, 1.5 down.

While devices poll for changes every 60 seconds, polls add 196 calls per save: 11,760,000 / 60 / 1,000 = 196.

Out of scope: real-time co-editing of a document, with operational transforms or CRDTs, as in Google Docs. Files here are opaque bytes.

Check in: Close the page and derive the 196 polls per save.

Split files into blocks

A user changes one page of a 1 GB video project. Sending the whole file again is a waste of their upload link, the scarce resource.

The client splits each file into 4 MiB blocks, a step called chunking.

It hashes each block with SHA-256. The content hash names the block by what it holds, so two identical blocks get the same name.

It compresses each block, then asks the server which hashes are missing, and uploads only those.

An edit in place, overwriting bytes as many binary formats do, changes only the blocks it touches.

An insert near the start shifts every later fixed-size block, so the client re-uploads from the insert onwards.

Content-defined chunking sets block boundaries by the content, so later blocks keep their hashes. Most saves are small files of one or two blocks, so fixed blocks are the simple start.

So the average transfer is 256 KiB: most saves are small files, a few KiB to a few hundred KiB. Compression cuts text 2 to 3 times more, our estimate.

Step through the figure to follow one file into blocks.

The trade-off:

Blocks make the client work harder: hashing and compressing. In exchange, an in-place edit moves a block, not the file.

A file in blocks, named by their hash

1. The client splits each file into 4 MiB blocks.
2. Each block is hashed with SHA-256. The hash names the block by what it holds.
3. Overwrite a few bytes in place, and only the touched block's hash changes. The client uploads that block, not the file.
4. Insert near the start, and every later fixed-size block shifts and changes hash. Content-defined chunking would keep the later blocks' hashes.
5. A repeated block is stored once inside a namespace, never across them, so no one learns what others hold.

Check in: A user inserts a paragraph near the start of a large file. What uploads?

Namespaces, dedup and deletion

Blocks repeat, inside one user's files and across a shared folder. Storing them once saves money, if deletion and privacy still work.

A namespace is one user's files, or one shared folder, with its own members and its own change numbering.

Dedup means storing a block once when it repeats. Here it stays inside a namespace, so no one learns that someone else holds a file.

Blocks are keyed by hash prefix, namespace and hash. The prefix spreads writes over S3, and deleting one namespace's block never touches another's.

Two hashes: the SHA-256 of the stored, compressed bytes names the object, and S3 checks it on upload.

The SHA-256 of the plaintext is the dedup hint, checked by a scanner before it counts.

A block is deleted only when its count of references in the namespace reaches zero and no version younger than 30 days lists it.

With dedup, deleting one file rarely frees its blocks. Uploads resume cleanly: after a drop, only the blocks the namespace lacks are sent.

The trade-off:

Per-namespace dedup stores a block twice when two namespaces hold it. In exchange, deletion and privacy never cross a namespace.

Check in: Why keep dedup inside one namespace, not across all users?

Devices poll; block servers carry the bytes

Stage 1 is the simple design at launch: blocks through our own block service to S3, metadata in Aurora, and devices that poll.

API calls: 100 saves x 200 = 20,000 a second. At 1 ms of CPU a call and a 70% target, 29 tasks run, 69.0%.

Statements: 20,000 x 1.02 = 20,400 a second, 19,900 of them reads. A statement takes about 0.5 ms of CPU, our estimate.

Each instance is a db.r6g.xlarge, which has 4 vCPUs. That gives 4 x 1,000 / 0.5 = 8,000 statements a second an instance.

Four readers take the reads at 62.2%; the writer is at 6.3%.

Read the four tiles. Here the load buttons count saves a second. In Stages 1 and 2 they also stand for more users, as polls ride on devices.

"First to saturate" notes the Metadata API, at 69%.

A part saturates when it gets more work than it can serve. A card turns red at 90% of its limit; only past 100% does the result name it.

The latency tile shows 153ms: load balancer 1.5 + block service 1 + S3 150 = 152.5 ms, the longest arm.

The 150 ms is a size step on the S3 card. A 256 KiB PUT really takes tens of milliseconds, plus the client's own upload.

The cost tile shows $12k/mo, an average month. The evening peak is twice the average, so charges that grow with traffic bill at half the peak.

The cards stay sized for the peak, and every stage bills this way.

Of that, $5,811 pays for the parts on the canvas. The other $5,865 is egress, data sent out to the internet; data coming in is free.

About two thirds of the bytes going out are block downloads. Nearly all the rest are answers to polls.

Press 50: half the users. Nothing saturates.

Press 200: twice the users. The Metadata database saturates: its readers are the wall, at 32,000 / 199 = 160.8 saves a second.

The tile still shows a plain 153ms. A "≥" before it would mark the number as only a floor, but the database sits on the shorter API arm.

Really, its queries queue until they time out.

The trade-off:

Small, transactional metadata and large, immutable blocks scale on different axes, so they live in different stores.

Stage 1: Devices poll; block servers carry the bytes

• Load: 100 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $12k/mo

Check in: Why not store the files in the database?

One commit, five statements

Two devices edit the same file at once. One edit must win, the other must not vanish, and every device must see every change in order.

A save ends in one commit on the writer: one transaction of 5 statements.

First, the file update, only if the file is still at the version the client started from. Then the version row, with its block list.

Then the block references, one insert however many blocks. Then the namespace row's sequence goes up by one, and the change is written with it.

A sequence number counts a namespace's changes. The journal is the list of changes, one row each, numbered by that sequence.

The number comes from the namespace row, not a database sequence. With a sequence, A takes 10, B takes 11, B commits first, and a device skips A.

If another device committed first, the commit fails. The client keeps both, saving its version as a conflicted copy.

Each commit carries a client-made commit id. A retry after a lost answer finds its own id on a version and is answered as success.

A move within a namespace is one row: files point at a parent folder, so moving 10,000 files changes one row.

A move into a shared folder crosses namespaces: each block is copied to the new keys, then referenced, then deleted. 10,000 files is about 20,000 copies, about $0.10.

Step through the figure to follow one commit.

The trade-off:

The namespace row is locked for one statement and the commit, which caps one namespace at a few hundred commits a second. In exchange, no change is ever skipped.

One commit, five statements

1. A save ends in one transaction on the writer: the file, the version, the block references, the sequence, then the journal row.
2. With a database sequence, numbers follow start order. If B commits first, a device that listed after 11 never sees A.
3. Numbered from the namespace row inside the commit, sequence order is commit order, and no listing skips a change.
4. If another device committed first, the commit fails. Its client saves its edit as a conflicted copy, so nothing is lost.

Check in: Why take the sequence number from the namespace row, not from a database sequence?

The same design, ten times the users

The interviewer asks: We grow ten times. What breaks?

Stage 2 runs Stage 1's design at 1,000 saves a second, with 11.76 million devices polling every 60 seconds.

That is 196,000 polls a second. 99 in 100 find nothing: 2,000 devices a second have a change, against 196,000 asking.

Aurora allows up to 15 readers: 120,000 reads a second. The Metadata database saturates.

Its warning reads "Readers 166% used: 199,002 reads/s against 120,000 across 15 readers".

The tile still shows a plain 153ms: the block arm is longer than the API arm the database sits on.

Really, polls queue at the readers until they time out or the connection pools run out. Without shedding, fewer than 120,000 reads a second finish in time.

The cost tile shows $80k/mo. About a third of the bytes going out are API answers, nearly all to polls. Polling costs bytes as well as reads.

Bigger readers would carry it: 199,002 / (32,000 x 0.7) = 8.9, so 9 readers of 16 vCPUs.

That is about $19,470 a month of instances, to answer "no" 99 times in 100.

A cache of each namespace's latest sequence would spare the database. But the API fleet would still answer 196,000 polls, and changes would still take a minute.

Press 500: half the users. Nothing saturates, but the readers read 83% and warn. The cost tile shows $46k/mo.

The trade-off:

Polling costs in proportion to devices, not to changes.

Stage 2: The same design, ten times the users

• Load: 1,000 req/sec
• First to saturate: Metadata database
• Estimated cost: $80k/mo

• Metadata database: Readers 166% used: 199,002 reads/s against 120,000 across 15 readers (the writer takes no reads while readers exist).

Check in: What fraction of polls find anything?

Tell devices instead of letting them ask

The server knows when something changed. The device does not. So the server should speak first.

Long polling and WebSockets both hold one connection a device. A long poll answers when something changes or after a timeout, and the client asks again.

A WebSocket stays open, and the server pushes. Dropbox's client long-polls; either beats 60-second polling, as the database is not asked in between.

Here each online device holds a WebSocket to a notification service.

After each commit, the API publishes "namespace changed, sequence n" to a change bus that runs pub/sub.

Pub/sub sends each message to whoever subscribed to its channel, here one channel a namespace. The servers holding those devices push it.

The device then lists the changes after its last sequence number, so it catches up whatever it missed.

Pub/sub delivers at most once. So the commit also sets a latest-sequence key per namespace on the bus.

A server that resubscribes reads those keys and pushes where they moved, and a check every 10 minutes bounds anything else.

A journal tailer re-sets the keys every few seconds, so a crash between commit and announcement delays a push by seconds, not forever.

Step through the figure to compare polling with push.

The trade-off:

The cost moves from answering questions to holding connections: millions of them, nearly idle.

Asking every minute, or being told

1. Polling: every device asks every 60 seconds. 196,000 polls a second, and 99 in 100 find nothing.
2. Push: each device holds one connection. A commit publishes one message, and the servers holding that namespace's devices push it.
3. The push carries the new sequence number. The device lists every change after its last one, so it misses nothing.
4. Pub/sub can drop a message. A resubscribing server reads each namespace's latest sequence and pushes where it moved.

Check in: A notification server loses its bus subscription while its devices stay connected. How do they catch up?

The server tells devices about changes

Stage 3 replaces polling with push at 1,000 saves a second.

API calls: 1,000 x 4 = 4,000, so 6 tasks, 66.7%. Statements: 4,000 x 2.0 = 8,000: 3,000 reads and 5,000 writes.

The writer takes the 5,000 writes at 62.5% of its 8,000. The API fleet adds tasks with load; the writer cannot, as a cluster has one.

Two readers serve listings and failover, at 18.8% on the canvas.

Devices also reconnect about hourly and list again: about 4,900 more reads a second, not on the canvas. With those, the readers run at 49.4%.

The change bus carries 1,000 messages a second, 2,000 pushes. The notification service runs 354 tasks, sized by connections, nearly idle on CPU.

"First to saturate" notes the Metadata API, at 67%. The latency tile shows 153ms.

The cost tile shows $56k/mo, against Stage 2's $80k that could not carry the load. The connections' load balancer adds about $524, by hand.

Press 500, the average hour. Nothing saturates.

Press 1,900: exam season, the same users saving 1.9 times as often. The Metadata database saturates: its writer is out of capacity.

The tile still shows 153ms. Really, commits queue on the writer until they time out, and saves fail.

The writer is the first wall, at 8,000 / 5 = 1,600 saves a second.

The trade-off:

Push trades 196 calls a save for one message and a held connection. The writer, not the readers, is now the wall.

Stage 3: The server tells devices about changes

• Load: 1,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $56k/mo

Check in: What sizes the notification fleet?

The whole design on one screen

Skip on a first read; come back before the interview. Every number on Stage 3 comes from the one before it, at the 1,000 peak.

The dollars bill the 500 average, as on the tile.

Saves: 11.76 million users x about 3.67 saves / 86,400, then x 2 at the peak: 1,000 a second.

API calls: 1,000 x 4 = 4,000; 6 tasks at the peak, 3 billed at the average, $106.64.

API load balancer at the average: 2,000 calls x 0.6 / 25 = 48 LCU, $292.68.

Statements: 4,000 x 2.0 = 8,000, 3,000 reads and 5,000 writes; writer 62.5%, $1,460.16.

Change messages: 1,000, 2 pushes each; bus $252.29.

Connections: 11,760,000 / (50,000 x 2/3) = 352.8, so 354 servers, $12,583.43.

Block transfers: 1,000 x 2.5 = 2,500; 4 tasks at the peak, 2 billed, $71.09.

Block bytes at the average: 1,250 x 256 KiB = 312.5 MiB a second, $6,344.33 at the load balancer.

Store requests at the average: $7,257.60.

Egress at the average: 750 block downloads a second x 256 KiB, plus 2,000 API answers of 1 KiB: $27,863.86.

Total: about $56,232 a month, the average month, the tile's $56k.

Check in: Close the page and rebuild the chain from 1,000 saves to the writer's load.

Holding 11.76 million connections

The notification fleet looks idle on its card. Its real limit is not CPU but open connections, which no card draws.

About 50,000 connections a server. Losing one of 3 zones leaves two thirds: 11,760,000 / (50,000 x 2/3) = 352.8.

That rounds up to 118 servers in each of 3 zones: 354, not 353. After a zone loss each holds about 49,800, under the load balancer's 55,000 a target.

With TLS ended on the servers, the Network Load Balancer costs about $524 a month. Ending TLS on it costs about $16,950; an ALB about $22,600.

Each server has 2 GB for 50,000 connections, about 40 KB each, and TLS state alone is about 30 KB, our estimate. Measure it.

Past about 35 KB, use 4 GB tasks, about $2,266 a month more.

Each device pings every 30 seconds: 1,107 pings a second a task. A ping costs about 0.05 ms, one small frame: 5.5% of a vCPU.

The card's 0.5 ms is for a push, which builds and sends a message. Devices reconnect about hourly, about 4,900 listings a second.

Losing a zone sends about 3.92 million devices to reconnect: about 16,600 TLS handshakes on each remaining server, about 17 seconds of CPU each.

If every device listed, that would be 5.9 million listings, about 6 minutes of the readers.

So devices reconnect with jittered backoff over a few minutes, and list only where the namespace's latest sequence has moved past theirs.

The trade-off:

Connections are cheap to hold and expensive to lose all at once. Every reconnect is a listing on the readers.

Check in: Why 354 servers, not 236?

Photos and video, still through our servers

The interviewer asks: Photo and video sync launches. What breaks?

The same 1,000 saves a second, but the average block moved grows from 256 KiB to 2 MiB. That is mostly photos; a video is many 4 MiB blocks.

Stage 4 has no load buttons, as the photo mix is a fixed twist.

The block service's CPU grows 8 times, to 8 ms a transfer. It needs 2,500 / (125 x 0.7) = 28.6 tasks, against a 12-task cost guard.

The Block service saturates. Its warning reads "Scaled to the 12-task ceiling and 100% used at 2500 RPS"; here that is block transfers.

The tile shows "≥ 184ms", a floor: 1.5 + 8 ms x 4 + 150. The extra 24 ms is the card's queueing curve.

Really, nothing sheds the excess: transfers queue on every task without bound, and the load balancer times some out.

Busy tasks fail health checks. At least 1,000 transfers a second, 40%, cannot be served; in practice more fail as queued transfers time out.

The cost tile shows $264k/mo. The block load balancer alone is about $50,600, eight times Stage 3's, because it bills every byte it carries.

About $194,000 of the tile is egress, nearly all of it blocks going out to devices.

The network is worse than the canvas shows: about 4.9 GiB a second in, and the same out, through the fleet.

The trade-off:

Bytes through our servers cost CPU, network and a load balancer that bills per gigabyte. None of it is work only we can do.

Stage 4: Photos and video, still through our servers

• Load: 1,000 req/sec
• First to saturate: Block service
• Estimated cost: $264k/mo

• Latency past saturation is a lower bound, not an estimate. Block service is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• Block service: Scaled to the 12-task ceiling and 100% used at 2500 RPS.

Check in: Why not just raise the block service's ceiling?

Signed URLs: the client talks to S3

Our servers decide who may move which bytes. They do not need to move the bytes themselves.

A presigned URL is a short-lived link that lets one request do one thing on S3, signed with our credentials.

The upload session returns one per new block, for this namespace's key, with the block's size and SHA-256 signed in.

The client PUTs straight to S3, and S3 rejects a body that does not match. Listings return signed GET links for downloads.

A signed URL proves permission, not arrival. Each S3 upload event sets an arrival key on the change bus, kept for an hour.

The commit accepts a block only if it arrived or is already referenced. If the arrival record is late, the commit checks with one HEAD on the object.

The request path never carries the bytes: clients upload and download straight to S3.

One background scanner reads each new object once, for malware and to verify the plaintext-hash hint: about $4,300 a month, sign-ups included.

Unsharing stops pushes at once, but signed URLs already issued stay valid until they expire, within minutes.

Step through the figure to compare the two paths.

The trade-off:

The checks move to the client, S3 and a scanner. In exchange, the request path never carries the bytes.

Bytes through our servers, or straight to S3

1. Through our servers, every byte crosses a load balancer that bills per gigabyte and a fleet that burns CPU on it.
2. Instead, the API returns a signed URL per new block, with the block's size and checksum signed in.
3. The client uploads straight to S3, which checks the checksum. An S3 event sets an arrival key on the change bus; if it is late, the commit checks with one HEAD.
4. One background scanner reads each new object once, for malware and the dedup hint. The request path never carries the bytes.

Check in: Why must the commit check an arrival record, not just the signed URL?

Blocks go straight to the store with signed URLs

Stage 5 runs Stage 4's photo mix with signed URLs. The block load balancer and the block service leave the canvas.

The client sends blocks straight to S3, which takes 2,500 requests a second without strain. Arrival records live on the change bus, so the database is unchanged.

Nothing saturates; the note names the Metadata API, at 67%. The latency tile shows 150ms, the client to S3.

The cost tile shows $216k/mo, about $48,000 less than Stage 4 for the same bytes.

About $194,000 of it is egress: the downloads still go out to devices. Signed URLs take the bytes off our servers, not off the bill.

Press 500, the average hour. Nothing saturates.

The trade-off:

Keep bytes off your servers. Your servers decide who may move which bytes; the store moves them.

Stage 5: Blocks go straight to the store with signed URLs

• Load: 1,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $216k/mo

Check in: What still costs money for the bytes?

Storage and egress are the real bill

Skip on a first read; come back before the interview. The parts on the canvas are a small share of what this system costs.

After growth we store about 60 million GiB. All of it in S3 Standard would be about $1.26 million a month.

So blocks older than 30 days move to S3 Glacier Instant Retrieval, at $0.004 a GiB-month against about $0.021, with a 90-day minimum.

Lifecycle rules move blocks by age, not use, so files people still open move too. Each read of an old block then pays $0.03 a GB.

S3 Intelligent-Tiering moves objects by access instead, for a monitoring fee per object: about $50,000 a month at 20 billion objects, which packing shrinks.

Most of the stock arrives with new users, about 2 GiB each: about 2 million GiB a month from sign-ups, more than saves add.

Tiered, with sign-ups, Stage 5's storage is about $317,600 a month. Lifecycle moves add about $38,000.

Egress at Stage 5 is about $194,000 a month, on the tile, or about $111,700 through CloudFront.

The CloudFront saving is its lower price per GB and the free transfer from S3. It is not cache hits: each block is fetched by only about 1.5 devices.

Every line of the Stage 5 bill, at the average month: the tile's $215,930, which is $21,953 of parts and $193,977 of egress.

Then $524 connections, $317,594 storage, $37,967 transitions, $3,012 sign-up uploads and $4,303 scanning: about $579,300.

The parts on the canvas are about 3.8% of it. Through CloudFront, the whole bill is about $497,100.

There are about 18 to 20 billion objects. Real systems pack blocks into larger objects, because per-object fees and minimums add up.

The trade-off:

Storage and egress dwarf the servers. Tiering, packing and a CDN are where the money is.

Check in: What are the two largest lines in the real bill, and what shrinks each?

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a user see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

A notification server dies: its devices reconnect elsewhere and list from their last sequence. A zone fails: the other 236 servers take them.

A reader is behind: a device that was told sequence n reads from the writer instead.

The writer fails: commits fail for about 30 seconds while a reader is promoted, and retries with the same commit id succeed.

An upload drops: the session lists the blocks already stored, and only the rest are sent.

A hot shared folder with 10,000 online members turns one save into 10,000 pushes. Coalesce them to one a second, and jitter the fetches.

Backgrounded phones hold no connection. They get a visible push for new shares only, and fetch on open.

Long term, shard the metadata by namespace, so a commit stays a single-shard transaction.

Say it out loud: "Blocks named by hash, and a 5-statement commit numbered per namespace. Push over held connections, and signed URLs so bytes skip our servers."

Minutes 0 to 5: requirements. Sync delay, durability, isolation, conflicts.

Minutes 5 to 10: the numbers. Saves, devices, calls per save, blocks per save.

Minutes 10 to 17: Stage 1. Chunking, hashing, metadata against blocks, the 5-statement commit.

Minutes 17 to 25: Stages 2 and 3. Polling against push, connections, sequence numbers and lost messages.

Minutes 25 to 32: Stages 4 and 5. Bytes off the servers, signed URLs and what they cost the design.

Minutes 32 to 38: storage tiers, packing and egress.

Minutes 38 to 45: conflicts, versions, sharing and hot folders, sharding by namespace.

The trade-off:

Each answer has a price. A journal, a bus and held connections are more to run than polling, and they cost less than answering "no" all day.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.