Courses › System Design › Question Breakdowns

Design a Distributed File System

GFS/HDFS: a metadata master, large replicated chunks, leases, record append and re-replication.

Design a distributed file system like GFS or HDFS: store petabytes of large files across thousands of commodity machines, survive frequent disk and machine failures, and deliver high throughput to batch jobs that read and append huge files. It's a question about separating metadata from data, chunking and replication, failure detection and re-replication, and consistency for appends.

Requirements

Functional

  • Clients can create, read, write, append to and delete files in a hierarchical namespace (/logs/2026/10/11/part-0001)
  • Files can be very large (GBs to TBs)
  • Many clients can append to the same file concurrently (e.g. log collection)
  • Clients can list directories and get file metadata

Out of scope: POSIX compliance (random small writes, locks, hard links), small-file optimization, a user-facing sync product (that's Dropbox).

Non-functional

  • Scale: ~10 PB, ~100M files, thousands of storage servers
  • Durability: no data loss despite constant hardware failure (at this size, disks die daily)
  • Throughput over latency: large sequential reads and appends at many GB/s aggregate
  • Availability of the namespace; a single metadata node is acceptable only if it fails over quickly

[!TIP] Workload shapes the design GFS was designed around a specific workload: huge files, mostly sequential reads and appends, rare overwrites, and failures as the norm. Stating those assumptions is what justifies big chunks (64–128 MB), a single metadata master and relaxed consistency.

Capacity estimates

The metadata fits in one machine's RAM, which is why a single master is viable.

Core Entities

  • File / directory — path, owner, permissions, list of chunk handles
  • Chunk — 64-bit handle, version number, size (up to 128 MB), replica locations
  • Chunk server — ID, disks, free space, the chunks it holds, last heartbeat

API

create(path) / delete(path) / list(dir)
open(path) → handle
read(handle, offset, length) → bytes
write(handle, offset, bytes)
append(handle, bytes) → offset the system chose

Applications use a client library, not raw RPC: it caches metadata and talks to chunk servers directly.

High-Level Design

c = client "Client Library" @0,1
m = service "Master\n(namespace + chunk map)" @1,0
sh = service "Shadow Master\n(standby)" @2,0
log = store "Operation Log\n(replicated)" @3,0
cs1 = store "Chunk Server 1" @1.5,2
cs2 = store "Chunk Server 2" @2.5,2
cs3 = store "Chunk Server 3" @3.5,2
c -> m : 1. which chunks / where?
c -> cs1 : 2. read / write data
cs1 -> cs2 : pipeline
cs2 -> cs3 : pipeline
m -> log
log -> sh
cs1 --> m : heartbeat + chunk list
cs2 --> m
cs3 --> m
  • The master stores the namespace and the file → chunk mapping, and knows which chunk servers hold each chunk. It never carries file data.
  • A client asks the master for chunk locations (and caches them), then reads and writes directly with chunk servers.
  • Chunk servers store chunks as local files, heartbeat to the master and report the chunks they hold.
  • Every metadata change is written to a replicated operation log before it's applied, so a standby master can take over.

Deep Dives

1. Why a single master works (and its limits)

All metadata lives in master RAM, so lookups are microseconds. The master is off the data path, and clients cache locations, so it handles only small requests.

  • Durability: an operation log replicated to other machines + periodic checkpoints (B-tree snapshots) for fast restart.
  • Availability: a shadow master replays the log and can take over in seconds-to-minutes; reads can be served by shadows (slightly stale).
  • Limits: at ~1B files the namespace no longer fits one machine. Then federate the namespace (HDFS Federation: different masters own different directory subtrees) or move metadata into a distributed store (Colossus keeps it in Bigtable).

2. Chunk size

Large chunks are the standard answer for this workload. Hot small files (e.g. a binary every job reads) get a higher replication factor.

3. Writes and leases

For each chunk, the master grants a lease (e.g. 60s, renewable) to one replica: the primary. The primary decides the order of mutations, so all replicas apply them identically.

Client -> [Primary replica] -> [Secondary 1] -> [Secondary 2]
Client -> [Master]
  • Data flow is pipelined along a chain of chunk servers (each forwards to the next nearest), using every link's full bandwidth.
  • Control flow: once all replicas have the data buffered, the client asks the primary to commit; the primary assigns a serial number, applies it and tells secondaries to apply in the same order.
  • If any replica fails, the client retries; the result may leave inconsistent regions on some replicas, which readers skip using checksums and record IDs.

4. Record append

Many writers appending to one log file would need a lock if they chose offsets themselves. Instead the system chooses the offset: the primary appends the record at the end of the chunk and tells the client where it went. Semantics are at-least-once: a retried append may leave a duplicate, so records carry unique IDs and readers dedup. This is the trade that makes concurrent appends fast.

5. Detecting failures and re-replicating

  • A chunk server that misses heartbeats for ~1 minute is considered dead; the master finds every chunk that dropped below its replication factor and schedules copies, most-endangered first (chunks down to one replica before those down to two).
  • Stale replicas: each chunk has a version number bumped on every new lease. A server that was down during a mutation returns with an old version, and the master ignores and garbage-collects it.
  • Silent corruption: chunk servers keep a checksum per 64 KB block and verify on read; a bad block is reported and re-copied from a good replica.

[!NOTE] Replica placement Put replicas on different racks (e.g. one local, two on another rack) so a rack switch or power failure doesn't take out every copy. It costs cross-rack write bandwidth; it buys survival of correlated failures.

6. Erasure coding for cold data

Three replicas cost 200% overhead. For cold files, Reed-Solomon (6 data + 3 parity) cuts overhead to 50% with similar durability, at the cost of slower reconstruction. Hot data stays replicated; files are converted after they cool.

7. Deletion and garbage collection

Delete just renames the file to a hidden name with a timestamp. A background scan removes hidden files older than a few days, and chunk servers drop chunks the master no longer references (discovered via heartbeats). Simple, robust, and it gives an undo window.

What's expected at each level

  • Mid-level: split files into replicated chunks, a metadata service that maps files to chunks, clients reading data directly from storage nodes.
  • Senior: chunk size reasoning, heartbeats and re-replication, leases and a primary for write ordering, rack-aware placement, checksums.
  • Staff: record-append semantics and their consequences, master durability/failover and namespace federation, version numbers for stale replicas, erasure coding economics.