CSE Roadmap

Common tier · about 3 hours · 8 parts

Part 5 of 8 · 3 min read

Metadata and data, kept apart

A small, strongly consistent database for names and versions, and a big object store for bytes.

Think of a warehouse and its inventory book. The shelves hold the goods. The book lists what is where, who owns it and which version it is. Losing the book makes the goods hard to find, and losing a shelf loses only part of the goods.

The cloud drive design in the book "System Design Interview" splits the system into two stores with different jobs.

  • The object store holds the chunk bytes. It is huge, cheap and slow to change.
  • The metadata database holds users, devices, namespaces (the root folder of a user), files, file versions and blocks. It is small compared with the data, and needs strong rules.

The book lists the tables in the simplified schema:

Table Holds
User Name, email, profile picture
Device One row per device of a user, with a push address
Namespace The root directory of a user
File The latest state of each file
File_version The history of a file. Rows are read-only, to keep the history intact
Block The pieces of each version, in order

A file of any version can be rebuilt by joining the block rows of that version in order.

The book chooses a relational database for the metadata, since it needs strong consistency: it is unacceptable for a file to look different to different clients at the same time. Relational databases give transactions natively. Caches in front of it must be kept consistent too, by invalidating cache entries whenever the database changes.

A worked example of version history. A file notes.txt is made of blocks A, B, C.

  • Version 1: blocks A, B, C.
  • The user edits the middle. Version 2: blocks A, B2, C. Block B2 is new.
  • Metadata rows: version 1 → [A, B, C]; version 2 → [A, B2, C].
  • Stored chunks: A, B, B2, C. A and C are shared by both versions. Two versions cost 4 chunks, not 6.
  • To restore version 1, the system reads A, B, C.

The upload flow in the book runs two requests in parallel from the client:

  1. Add file metadata. The metadata database records the file with status "pending", and the notification service tells other devices that a file is being added.
  2. Upload the content. The block servers chunk, compress and encrypt the content, and upload the chunks to the object store. When the store finishes, it calls back the API servers, which set the status to "uploaded" and tell the notification service. Other devices then fetch the metadata and download the blocks.

The status "pending" matters: other devices know a file exists but do not try to download it before all blocks have arrived.

When two users change the same file at once, the book's rule is that the version processed first wins. The second gets a conflict, and the user is shown both copies and can merge or override.

A worked example for sizing the metadata. Using the book's assumption of 10 million daily users who each upload 2 files a day:

  • New files per day: 10,000,000 × 2 = 20,000,000.
  • If a file averages 500 KB and chunks are 4 MB, most files are a single chunk, so about 20,000,000 chunk rows a day.
  • At 150 bytes per row for files, versions and chunks together, 3 rows per file: 20,000,000 × 3 × 150 = 9,000,000,000 bytes = 9 GB of metadata per day, 3.3 TB a year.
  • The data per day: 20,000,000 × 500 KB = 10 TB. Metadata is under 0.1 percent of the data (9 GB ÷ 10 TB = 0.09 percent).

So the metadata database is small enough to partition (Level 4) and keep on fast storage, while the data goes to cheap object storage.

For the curious For the curious

The book also covers a notification service: clients that are online are told by a long-lived connection, such as long polling, that something changed. Clients that were offline fetch the changes when they reconnect. Level 6 and Level 11 return to this.

Check yourself:

  • Which table keeps the history of a file, and why are its rows read-only?
  • Why does a version history cost less than a full copy for each version?