Distributed File System

The problem

"Design a distributed file system." It keeps files of many gigabytes on thousands of ordinary machines for big batch jobs: web crawls, logs, results. Files are written once, mostly by adding records to the end (appends), then read many times from start to end. One metadata server knows every file's name and where its pieces are. Google's GFS and Hadoop's HDFS are the classic examples.

This practice problem reuses Design Dropbox's chunks, kept apart from the names, and the Key-Value Store's 3 copies on different racks. Leave out what this workload never needs: syncing devices, conflicted copies, and overwriting bytes in the middle of a file.

The numbers

From the interviewer: 10 PB of files before copies, on about 3,000 machines. With 3 copies that is 30 PB, about 10 TB on each machine. A PB is a billion MB, so 10 PB is 10 billion MB.

The metadata server keeps one entry per chunk, listing its 3 machines; say an entry takes about 100 bytes. With Dropbox's 4 MB chunks, 10 PB is 2.5 billion chunks and a map of about 250 GB.

Big chunks: 64 MB

Say the metadata server can spare about 100 GB of memory. At 64 MB a chunk, 10 PB is about 160 million chunks, 16× fewer, and the map is about 16 GB: it fits, with room to grow. A job also asks where chunks are 16× less often, and reads each chunk as one long stream from one machine.

Small chunks paid off in Dropbox because people edit a few bytes of big files. Batch jobs don't. Bigger still isn't better: with 1 GB chunks a 10 GB file is only 10 chunks, so at most 10 workers could split its reading, against about 160 at 64 MB. A short file doesn't waste 64 MB: each chunk is a plain file on its machine's disk, only as big as what was written.

Off the data path

who                 says
job                 where are the chunks of /crawl/day1?
metadata server     c1: A, E, I    c2: B, F, G    …
job → machine E     read c1

A job reading a 10 GB file, about 160 chunks, first asks the metadata server where they are. The answer is a few machine names per chunk; then the job reads each chunk straight from the nearest of its 3 machines.

If the metadata server fetched the chunks and sent them on, every byte would cross one network of about 1 GB a second: a thousand jobs reading 10 GB each, 10 TB, would take almost 3 hours. Read directly, the 3,000 chunk machines send about 3,000 GB a second together.

Appends follow the same rule. The job asks for the 3 machines of the file's last chunk. In a common design one of them, the primary, decides the order of the appends; the job sends its bytes along a chain of the 3 machines, and the primary confirms once all 3 have them. A full chunk is closed, and the metadata server picks 3 machines on different racks for the next.

When a chunk machine dies

With 3,000 machines, say one dies every few days. Every machine sends the metadata server a heartbeat every few seconds, listing the chunks it holds. When machine B goes silent, re-replication runs on its own:

1. B stops sending heartbeats.
2. After about 10 minutes of silence, the metadata server marks B dead. Waiting means a restart doesn't cost a full copy.
3. It finds every chunk that had a copy on B, now down to 2. A chunk with one copy left goes first.
4. For each, it tells a machine with a copy to send it to a rack with none.
5. The new machine reports the chunk, and the map shows 3 copies again.

A full machine holds about 10 TB, about 160,000 chunks, whose other copies are spread all over the cluster. So hundreds of machines share the copying: minutes, not the almost 3 hours one machine would need.

When the metadata server dies

Every change, such as "c6 added to /crawl/day1", is written to a log on disk and copied to other machines before the job hears OK. A standby replays the log as it grows, so it can take over quickly, and a snapshot of the map now and then keeps the log short. A lock service decides which of the two is active.

Where each chunk lives isn't logged: the chunk machines report what they hold. But they can't rebuild the rest, because a machine knows only chunk ids, not which file a chunk belongs to or in what order. Splitting the map over 10 servers by file name fixes a map too big for one memory, not a dead server: each part still lives only in memory.

Same pattern as Dropbox and the Key-Value Store

From Dropbox: a file is a list of chunks, with the names apart from the bytes. From the Key-Value Store: every chunk on 3 machines on different racks. What doesn't carry over: chunks named by their hash, sync, conflicts, and the ring. The metadata server places each chunk, so it can choose by rack and free space. A common variation puts two of the three copies on one other rack: one rack can still fail, and a write crosses racks once instead of twice.

Summary

• Scope: huge files, written once by appending, read many times; no sync, no overwrites.
• Data: names → chunks → machines, one map in the metadata server's memory.
• API and busy path: ask where the chunks are, then read or append at the chunk machines.
• Numbers: 10 PB in about 160 million chunks of 64 MB, a 16 GB map.
• Dead machines: missing heartbeats, then re-replication back to 3 copies on 3 racks.
• Dead metadata server: a log copied to other machines, and a standby replaying it.