Systems
Storage Engines

Distributed File System

Chunked, replicated storage with a metadata master: range-partitioned chunks, a master that stays out of the data path, chunk replication and heartbeat-driven re-replication, lease-based write ordering, and master high-availability over an operation log.

~30 min · senior

Problem & Requirements

Store files far larger than any single machine's disk, on a fleet of commodity servers that fail routinely, and serve high-bandwidth sequential reads and large writes. The defining assumptions, taken straight from GFS: files are big (gigabytes to terabytes), the dominant access pattern is large streaming reads and appends rather than small random writes, and component failure is the normal case, not an exception. A design that treats a dead disk or a dead server as routine, and that optimizes for throughput over per-operation latency, is the goal.

Those assumptions produce the architecture. A file is split into large fixed-size chunks by byte range — range partitioning of the file's address space — so a file's size is unbounded by any one disk and a byte offset maps deterministically to a chunk. Each chunk is replicated across several servers and failure domains for redundancy, so a lost server costs nothing but a re-replication. A single master holds all the metadata (which chunks make up a file, where each chunk's replicas live) and hands clients the chunk locations, deliberately staying out of the data path so it isn't a bandwidth bottleneck. Concurrent writes to a chunk are serialized by a lease the master grants to one replica, which keeps the master out of the write path while still ordering mutations. And because the master is a single point, its metadata is made durable and recoverable through an operation log replicated to standbys — leader-follower applied to the metadata service. Those four principles are the prototype.

Functional

  • create, read(path, offset, length), and append(path, data) over files larger than one disk.
  • A chunk survives the loss of any single server (and ideally any single rack) without data loss.
  • Concurrent appends to the same file produce a consistent, ordered result.

Non-functional (back-of-envelope, commodity fleet)

QuantityTargetWhat it forces
File sizeGB–TBFiles must span machines → chunking and a metadata index
Chunk size64 MB (GFS) / 128 MB (HDFS)Large, to cut metadata volume and client↔master chatter
Replication factor3, across racksSurvive disk, server, and rack loss; drives re-replication work
Metadata in master RAMall of it~64 B/chunk keeps millions of chunks in a few GB; master RAM caps the namespace
Read/write pathclient ↔ chunkserver directMaster returns locations only; never relays data, or it becomes the bottleneck
Failure rateconstantHeartbeats + automatic re-replication are steady-state work, not recovery

The RAM row is the quiet constraint that shapes everything else. Because the master keeps all metadata in memory to answer location queries fast, the chunk size is deliberately large (fewer chunks, less metadata) and the master must avoid storing anything it can cheaply reconstruct. That second point is the design decision worth internalizing early: chunk locations are not authoritative state the master persists — they're rebuilt from chunkserver heartbeats, which is why losing the master loses no data and why the operation log only needs to carry namespace changes.

Design

Five components, each tied to its principle:

  1. Chunking — a file is a sequence of fixed-size chunks, each with a globally unique handle. Byte offset o lives in chunk o // chunk_size, the range partition of the file's byte space. Large chunks mean few of them, which keeps master metadata small.
  2. Master — holds the namespace (path → ordered list of chunk handles) and the chunk-to-locations map, grants leases, and persists namespace changes to an operation log. It answers "where is this chunk" and then steps out; it never touches file data.
  3. Chunkservers — store chunks as ordinary local files, serve reads and writes directly to clients, and heartbeat their chunk inventory to the master.
  4. Replication and re-replication — each chunk is placed on several chunkservers across failure domains for redundancy. The master watches heartbeats, notices when a chunk drops below its replication target, and re-replicates to restore it. Placement and repair are the master's continuous background job.
  5. Leases and master HA — for a write, the master grants a time-bounded lease to one replica (the primary) that serializes mutations to that chunk; data flows to all replicas out of band, and the primary assigns the order. The master itself is made durable through leader-follower replication of its operation log to standbys, with periodic checkpoints to bound recovery.

The reference systems agree on the shape and differ in the details. GFS pairs a single master with read-only shadow masters and recovers via an operation log plus checkpoints; its 64 MB chunks and lease-ordered record appends are exactly the model here. HDFS renames the pieces (NameNode for the master, DataNodes for chunkservers, 128 MB blocks) and hardens master failover with a Standby NameNode reading a shared edit log over JournalNodes, with ZooKeeper-driven automatic failover. GFS shows the original append-optimized design; HDFS shows what hot master failover takes in production.

Build it

1

The starting point writes whole files to one machine's disk. It's a filesystem, and it stops being useful the moment a file is bigger than the disk or the machine dies — there's no way to grow past one node and no protection against losing it. Both limits trace to the same thing: the file is one indivisible object on one server. Splitting it is the first move.

2

Split each file into fixed-size chunks and record, in a central master, which chunk handles make up which file. A byte offset maps to a chunk by offset // CHUNK — the range partition of the file's address space — so a read resolves to a single chunk and the chunkserver holding it. The master returns the location and the client reads the chunkserver directly; the master never carries the data, which is what keeps it from becoming a bandwidth bottleneck. Chunks are large so the master's per-chunk metadata stays small.

3

A chunk on one server is lost when that server dies. Place every chunk on several chunkservers, spread across failure domains (different racks), and let a read pick any live replica. The master assigns the replica set at allocation time and tracks it. This is redundancy: the replication factor is how many simultaneous failures a chunk can survive, and reads gain a free benefit — they can spread across replicas. The placement here is naive; real placement balances disk usage and rack diversity.

4

Failure is constant, so maintaining the replication factor is steady-state work, not recovery. Chunkservers heartbeat their chunk inventory to the master, which is how the master learns chunk locations in the first place — they're soft state, reconstructed from heartbeats, never persisted. A missed heartbeat marks a server dead; any chunk that drops below its target gets re-replicated to a fresh server. This is the repair loop that makes redundancy durable over time rather than a one-time placement.

5

Multiple clients may write the same chunk at once, and the master must not be in the data path to referee it — that would make the master the write bottleneck. Instead the master grants a time-bounded lease to one replica, the primary, which becomes the single authority on mutation order for that chunk for the lease duration. Clients push data to all replicas out of band, then ask the primary to commit; the primary picks a serial order, tells the secondaries to apply it, and acks once they all do. The lease bounds the primary's authority, so if it dies the master can safely grant a new lease after expiry without two primaries ever coexisting.

6

The master is a single point whose loss would strand the cluster, so its state has to survive and recover. Every namespace mutation (create, append-extends-file, delete) is appended to an operation log, made durable, and shipped to standby masters — leader-follower replication of the metadata. Periodic checkpoints bound how much log a recovering master must replay. The elegant part falls out of the earlier design choice: chunk locations are not logged, because they're soft state a promoted standby relearns from the next round of heartbeats, so the log stays small and recovery stays fast.

Tradeoffs

DecisionWhat it buysWhat it costs
Large range-partitioned chunksLittle metadata; few client↔master round trips; streaming-friendlySmall files waste a chunk; a hot small file concentrates on its replicas
Master out of the data pathMaster isn't a bandwidth bottleneck; clients get full fleet throughputExtra round trip to locate; clients cache locations and must handle staleness
Chunk locations as soft stateSmall op log; master loss = no data loss; fast recoveryBrief post-failover window where locations are still being relearned
3× redundancy + re-replicationSurvives disk/server/rack loss as routine3× storage; background repair traffic competes with foreground I/O
Lease-ordered writesConcurrent mutations serialized without the master in the pathLease timeout delays failover of a dead primary; clients see ordering, not arbitrary writes
Leader-follower masterDurable, recoverable metadata serviceFailover latency; single-master write throughput caps namespace ops

Scaling it up

The toy omits the parts that make GFS and HDFS production systems. The notable gaps:

The single master eventually limits the namespace. All metadata in one master's RAM caps the number of files and chunks, and all namespace mutations through one log caps metadata write throughput. The successor designs partition the namespace itself: Colossus (GFS's replacement) moved metadata into a distributed store, and HDFS Federation runs multiple NameNodes each owning a namespace subtree — a range partition of the directory tree rather than of one file. The single master is the part that ages first.

Consistency of concurrent appends is subtle. GFS's record-append guarantees that a record appears at least once, atomically, but allows duplicates and padding between records, which pushes deduplication onto the application. That relaxed model is a deliberate trade for append throughput under concurrency; a stricter guarantee would cost coordination the design avoids. Knowing exactly what the write path promises matters more than the path itself.

Failover is a real protocol. "Promote a standby" hides leader election, fencing the old master so it can't keep acting (the split-brain problem the lease model also guards against at the chunk level), and ensuring the new master has the latest log. HDFS spends JournalNodes and ZooKeeper precisely on making this automatic and safe, because a half-failed master is more dangerous than a dead one.

Placement and re-replication are optimization problems. Naive "first N servers" placement ignores rack topology, disk fullness, and the thundering-herd risk of re-replicating many chunks off one failed server at once. Real masters throttle re-replication, prioritize chunks that have fallen to a single replica, and balance new placement across racks and disk utilization — a continuous background optimization, not a fixed rule.

Reads cache stale locations. Clients cache chunk locations to avoid hitting the master per read, so they must tolerate a replica that moved or died — retrying against another replica and refetching from the master on a miss. The master and client share a soft contract that locations are hints, not guarantees, which is what lets the master keep them as cheap soft state.

This is a storage-engine prototype that sits beneath the others: the key-value store, document database, and time-series engine all ultimately persist to something file-system-shaped, and a distributed one is what lets them scale past a single disk. The natural next steps are a dedicated consensus / leader-election prototype (the fencing and failover this lesson waved at, the foundation HDFS builds on with ZooKeeper), a namespace-partitioning prototype that removes the single-master limit, and a replication / repair scheduler prototype around the placement and throttling problems above. Each extends this foundation set without re-covering the chunked-storage core settled here.

References