The 100 problems, solved / Storage and files / 002 · Design a distributed file system (GFS)

Design a distributed file system (GFS)

Petabytes of large files on thousands of cheap machines, with a master that never becomes the bottleneck.

Problem 002 of 100Storage and filesL61 Nov 2026
Concepts this design leans on

01The design, in the six-step framework

1. Requirements

Functional

  • Store very large files (hundreds of MB to many GB) for internal batch jobs: crawlers, indexers, log processors.
  • Operations: create, open, read a byte range, append, delete. Random writes in the middle of a file are rare and may be slow.
  • Many clients append to the same file at once (log collection) and each append must land exactly once, in some order.
  • Out of scope: POSIX semantics, small files, a user-facing sharing model.

Non-functional

  • Tens of petabytes across 10,000 commodity machines; disks and whole machines fail every day and that is normal, not an incident.
  • Throughput over latency: a reader should get a full disk's bandwidth; a 100 ms first-byte latency is fine.
  • No byte is lost when any two machines die at once; the control plane recovers from its own crash in under a minute.
  • The master must never be on the data path.
Back of the envelope

Say 50 PB of data in 64 MB chunks:

50 × 1015 / 64 × 106 ≈ 7.8 × 108 chunks; × 3 replicas = 2.3 × 109 chunk replicas.

Metadata per chunk (id, version, three locations) is about 64 bytes, so 7.8 × 108 × 64 B ≈ 50 GB. That fits in the RAM of one large machine, which is the whole reason the chunk size is 64 MB and not 4 KB: with 4 KB chunks the metadata would be 800 TB.

Failure rate: 10,000 machines × 12 disks, with a 3 percent annual disk failure rate, is about 10 disk failures a day. Re-replicating one lost 12 TB disk at 100 MB/s from a single source takes 33 hours; spreading its chunks' copies across hundreds of sources brings that to minutes.

2. Core entities

  • File: path, ordered list of chunk ids, size, owner, permissions.
  • Chunk: 64-bit id, version number, size, checksum per 64 KB block, replica locations.
  • Chunk server: machine id, capacity, the chunks it holds, last heartbeat.
  • Lease: chunk id, primary replica, expiry time; the primary orders writes for that chunk.

3. API

  • GET /files/{path}/chunks?range= → from the master: the chunk ids and replica locations covering a byte range (cached by the client).
  • READ chunk_id, offset, length → to any chunk server holding a replica; returns bytes with checksums.
  • WRITE chunk_id, data → data is pushed to all replicas first, then the client asks the primary to commit.
  • APPEND file, data → record append: the primary picks the offset and returns it; the client never chooses.
  • POST /files, DELETE /files/{path} → master-only metadata operations; delete is a rename into a hidden name, reclaimed days later.

4. High-level design

ClientsControlDatawhere is chunk?every mutationread / write bytesforward dataforward dataheartbeatBatch job client(library)Master(metadata in RAM)Operation log+ checkpointsShadow mastersChunk server 1Chunk server 2Chunk server 3

A read of 1 GB from a crawler's output file:

  1. The client asks the master which chunks cover bytes 0 to 1 GB. The master answers from memory: 16 chunk ids, each with three replica locations. The client caches this.
  2. The client reads each chunk directly from the nearest replica, several chunks in parallel. The master is not involved again unless a replica fails.
  3. Every 64 KB block carries a checksum; a corrupt block is re-read from another replica and the master is told to re-replicate.

5. Deep dives

How does one master handle 10,000 servers and billions of chunks without being the bottleneck?

By never touching data and by keeping all metadata in RAM. Clients talk to the master only for namespace operations and chunk locations, and they cache locations, so a long sequential read makes one master call per 64 MB. The master persists every namespace mutation to an operation log replicated to shadow machines, and checkpoints its memory image regularly so recovery replays only the tail. Chunk locations are not persisted at all: on restart the master asks every chunk server what it holds, which is the only truth anyway. If one master still cannot keep up (hundreds of millions of files), the namespace is partitioned across several masters by directory subtree, which later systems did.

How do many clients append to one file concurrently and all get a sane result?

With a lease: the master grants one replica of a chunk a 60-second lease to be primary. All appends to that chunk flow data to every replica first (chained, so each machine's network link is used once), then the client asks the primary to commit. The primary assigns the offset, applies the write, and tells the secondaries the order. The guarantee is "appended at least once, atomically, at an offset of the system's choosing"; a failed secondary leaves a duplicate or padding region that readers skip by record checksum. This is weaker than POSIX and exactly what log writers need, and it avoids any distributed lock on the hot path.

Two machines die within a minute. What happens to the data on them?

Heartbeats every few seconds tell the master which servers are alive. When one stops, every chunk it held drops below three replicas; the master queues re-replication, prioritised by how few replicas remain and whether a client is blocked on it. Copies are pulled from the surviving replicas by many different destination servers at once, so a lost 12 TB disk is restored in minutes rather than the 33 hours a single stream would take. Placement spreads the three replicas across racks, so a rack switch failure loses at most one copy. Stale replicas (a server that missed a write while down) are detected by a per-chunk version number the master bumps on each lease grant, and are garbage collected.

Why 64 MB chunks, and what does it cost?

Large chunks keep master metadata small (50 GB for 50 PB), keep client-master chatter low, and let a client hold a TCP connection to one server for a long sequential read. The cost is hot spots: a small file that fits in one chunk and is read by a thousand jobs at once hammers three machines. The fixes are a higher replication factor for hot files and staggering job starts; the honest answer is that the design is tuned for large sequential I/O and small-file workloads should live elsewhere.

How does a client know a replica is stale or corrupt?

Two mechanisms. Each chunk replica stores the version number the master assigned at the last lease grant; a replica that was offline during a write keeps the old version, and the master excludes it from the locations it hands out. Within a replica, each 64 KB block has a 32-bit checksum kept in memory and verified on every read, so a disk that returns wrong bytes is caught before the bytes reach a client, and the client simply reads the same block from another replica. Checksumming on the reader side is cheap compared with the disk and network cost of the read itself.

6. What a strong answer sounds like

  • Open with the workload: huge files, appends and sequential reads, failures as the normal case. The design follows from it.
  • Say the metadata arithmetic out loud (64 MB chunks → 50 GB of RAM) to justify the single master.
  • Draw the data path bypassing the master, and the chained push of data separate from the commit order.
  • Explain leases and version numbers as the way to order writes and detect stale replicas without a lock service on the path.
  • Expect follow-ups on master failover (shadow masters, external lock service for election), snapshots (copy-on-write at chunk granularity), and checksums.
  • Common mistake: offering strong POSIX consistency and then being unable to explain how concurrent appends stay fast.

02Where this question was reported