On this page

GFS & HDFS: Distributed File Systems

In October 2003, Sanjay Ghemawat, Howard Gobioff and Shun-Tak Leung published "The Google File System" at SOSP. The paper described a file system that broke several rules people had treated as settled. It had a single master in a world that feared single points of failure. It used 64 MB blocks when local file systems used 4 KB. It gave applications a deliberately weak consistency model and told them to cope. And it ran on cheap machines that the authors expected to fail all the time.

It worked. GFS ran Google's crawling, indexing and MapReduce pipelines for most of a decade. Doug Cutting and Mike Cafarella reimplemented the design in the Nutch project (as NDFS, 2004), which became the Hadoop Distributed File System (HDFS) when Hadoop split out in 2006 — the storage layer of a whole generation of "big data" infrastructure. Then the single master turned out to be the limit both systems eventually hit, and how Google (Colossus) and the Hadoop community (HA, federation, Ozone) moved past it is just as useful to know as the original design.

Sources: the GFS paper (SOSP 2003), the HDFS paper (Shvachko et al., MSST 2010), the Apache Hadoop HDFS documentation, and Google's public descriptions of Colossus; numbers are cited inline.


1. The problem and its constraints

Google in 2001–2002 was running a web crawler, an indexer and a fast-growing set of batch jobs over data that no single machine could hold. Off-the-shelf options were network file systems (NFS, AFS) designed for home directories and small files, or expensive SAN storage. Neither fit. The GFS paper starts by listing the assumptions behind its design (Section 2.1), and nearly every odd design choice follows from one of them:

Assumption from the paperConsequence for the design
Component failures are the norm, not the exception — hundreds or thousands of cheap machines, some of which are always brokenConstant monitoring, replication, fast automatic recovery, checksums on everything
Files are huge — multi-GB files are commonLarge block ("chunk") size, metadata small enough to keep in memory
Most mutations append new data; random overwrites are rareOptimise appends, make record append atomic, don't optimise small random writes
Reads are mostly large streaming reads plus some small random readsOptimise throughput; applications batch and sort small reads
Many clients append to the same file at once (producer–consumer queues, many-way merges)Atomic concurrent append without client-side locking
High sustained bandwidth matters more than low latencyPipelined data transfer, no client-side data caching

Two more constraints were implicit. Google controlled both the file system and its applications, so it could skip POSIX: GFS offers create, delete, open, close, read, write, plus snapshot and record append. And a single master was far simpler to build than distributed metadata — a deliberate simplification.

HDFS inherited the same constraints; its architecture guide lists hardware failure as the norm, streaming access, large data sets, a write-once-read-many coherency model, and "moving computation is cheaper than moving data".


2. Architecture

A GFS cluster has one master, many chunkservers, and many clients. Files are split into fixed-size chunks of 64 MB. The master gives each chunk an immutable, globally unique 64-bit chunk handle when it creates it. Chunkservers store chunks as ordinary Linux files on local disks, and each chunk is replicated on (by default) three chunkservers.

HDFS maps one to one, with new names:

GFSHDFSRole
MasterNameNodeNamespace, file → block map, replica placement
ChunkserverDataNodeStores blocks as local files, serves reads and writes
Chunk (64 MB)Block (128 MB default since Hadoop 2)Unit of replication and placement
Chunk handleBlock ID (plus generation stamp)Global block identifier
Operation log + checkpointEditLog + FsImageDurable metadata
Shadow masterStandby / Observer NameNodeRead-only or failover replica of metadata
Client libraryDFSClientTalks to master for metadata, to servers for data
flowchart LR
    subgraph Clients
        C1["Client app + GFS library"]
        C2["Client app + GFS library"]
    end
    subgraph Master["Master (single process)"]
        NS["Namespace tree<br/>(in memory)"]
        MAP["File to chunk-handle map"]
        LOC["Chunk to replica locations<br/>(not persisted, rebuilt from heartbeats)"]
        OPLOG["Operation log + checkpoints<br/>(replicated to remote disks)"]
    end
    subgraph CS["Chunkservers"]
        S1["Chunkserver 1<br/>chunks as Linux files"]
        S2["Chunkserver 2"]
        S3["Chunkserver 3"]
        S4["Chunkserver N"]
    end
    C1 -->|"1. (file, chunk index)"| Master
    Master -->|"2. (handle, replica locations)"| C1
    C1 ==>|"3. read/write data directly"| S2
    C2 ==>|"data"| S3
    Master -.->|"heartbeats: instructions, lease grants"| S1
    S1 -.->|"heartbeats: chunk list, health"| Master
    S1 <-->|"pipelined data"| S2
    S2 <-->|"pipelined data"| S3

The key idea is separating the control path from the data path. The master handles only metadata: which chunks make up a file and where their replicas live. File data never flows through the master. A client asks the master once, caches the answer, and then talks to chunkservers directly for as long as the cache entry lives. Most of the time a client reading a large file sends one metadata request per few hundred megabytes, which is why one master could serve hundreds of chunkservers and thousands of clients.

What the master stores

The master keeps three kinds of metadata, all in memory:

  1. The file and chunk namespaces — the directory tree.
  2. The mapping from files to chunks — each file is an ordered list of chunk handles.
  3. The locations of each chunk's replicas.

The first two are made durable in an operation log, flushed locally and on remote replicas before the master replies, plus periodic checkpoints (a compact B-tree-like form) so recovery replays only the log tail.

The third kind — chunk locations — is not persisted at all. The master asks every chunkserver which chunks it has when the master starts up and whenever a chunkserver joins, and keeps the picture fresh through regular heartbeats. The paper's reasoning (Section 2.6.2): the chunkserver has the final word on what is on its disks — disks fail, servers get renamed, chunks get corrupted — so a persistent copy on the master would just be a source of sync bugs. HDFS does the same thing with block reports: DataNodes send a full block report at startup and periodically after that (every six hours by default, dfs.blockreport.intervalMsec), plus incremental reports as blocks are added or removed.

How small is this metadata? The GFS paper says the master keeps less than 64 bytes of metadata per 64 MB chunk and, thanks to prefix compression of file names, less than 64 bytes per file in the namespace. A petabyte of data in 64 MB chunks is about 16 million chunks, so roughly 1 GB of chunk metadata — easy to fit in RAM on 2003 hardware. That arithmetic is the whole justification for the single master, and it is also exactly the arithmetic that breaks once files get small (see the small-files problem below).

Why 64 MB chunks (and 128 MB blocks)

The GFS paper gives three reasons for a large chunk size (Section 2.5):

  • Fewer master interactions. Reads and writes within one chunk need one location lookup. A client streaming a large file talks to the master rarely.
  • Persistent TCP connections. A client doing many operations on the same chunk can keep one connection to the chunkserver open, which cuts network overhead.
  • Smaller metadata. Fewer chunks means the master can keep everything in memory.

And one cost: hot spots. A small file is one chunk on three chunkservers, and if many clients read it at once those three servers get hammered. The paper describes exactly this: an executable stored in GFS and launched on hundreds of machines at once overloaded the chunkservers holding it. The fix was a higher replication factor for such files and staggered start times. HDFS has a direct equivalent: the MapReduce job JAR gets a higher replication factor (mapreduce.client.submit.file.replication, default 10).

HDFS started at 64 MB blocks and moved the default to 128 MB (dfs.blocksize = 134217728) in Hadoop 2. Many large deployments use 256 MB. Larger blocks mean fewer NameNode objects and longer sequential reads per map task, at the cost of fewer parallel tasks for medium-sized files.

Replica placement

GFS spreads chunk replicas across racks, not only across machines (Section 4.2). That protects against a rack switch or power failure and lets reads use the aggregate bandwidth of several racks. The trade-off is that writes must cross rack boundaries.

HDFS made the policy explicit. For the default replication factor of three, the HDFS architecture guide describes it this way: put one replica on the writer's own node if the writer runs on a DataNode (otherwise on a random DataNode, ideally in the writer's rack), the second replica on a node in a different rack, and the third on a different node in that same remote rack. That design cuts cross-rack write traffic (only one inter-rack transfer per block) while still surviving the loss of a whole rack, because two racks hold copies.

flowchart TB
    subgraph R1["Rack 1"]
        W["Writer (on DataNode A)"]
        DA["DataNode A<br/>replica 1"]
        DB["DataNode B"]
    end
    subgraph R2["Rack 2"]
        DC["DataNode C<br/>replica 2"]
        DD["DataNode D<br/>replica 3"]
    end
    W --> DA
    DA -->|"one cross-rack hop"| DC
    DC -->|"in-rack hop"| DD

Namespace and locking

GFS does not have per-directory data structures listing files, and it does not support hard links or symbolic links. The namespace is a lookup table from full pathnames to metadata, held in memory with prefix compression. Each node in that tree — file or directory — has a read-write lock. An operation on /d1/d2/.../dn/leaf takes read locks on every ancestor directory name (/d1, /d1/d2, …) and a read or write lock on the full path itself.

The paper's example: creating /home/user/foo read-locks /home and /home/user and write-locks /home/user/foo, while snapshotting /home/user write-locks /home/user, so the two serialise. Two creates in the same directory don't conflict, because neither write-locks the directory. Locks are taken in a consistent total order (by level in the tree, then lexicographically) to avoid deadlock.

HDFS instead used one global read-write lock (the FSNamesystem lock) for most of its history — simple and correct, but a hard ceiling on NameNode write throughput.


3. Data model

The data model is intentionally plain:

  • A namespace of directories and files identified by pathname.
  • A file is an ordered sequence of chunks (blocks). All chunks except the last are full-sized.
  • A chunk is a byte array of up to 64 MB with a handle, a version number, and a set of replica locations.
  • Each replica is a plain Linux file on a chunkserver, extended lazily (so a small last chunk doesn't use 64 MB of disk).

What the data model does not contain is just as important: no records, no keys, no indexes, no in-place structure. Applications put their own structure on top — Bigtable's SSTables, MapReduce's record files, and log files with self-describing records. That's also why the consistency model can be weak: GFS doesn't know where a "record" begins or ends, except in record append.

Chunk version numbers

The master keeps a version number for every chunk. Each time it grants a new lease on a chunk (see below), it increments the version and tells the up-to-date replicas the new number before any client is told about the lease. Both master and chunkservers persist the version. If a chunkserver was down when a mutation happened, its replica keeps the old version. When it comes back and reports its chunks, the master sees the stale version and treats that replica as garbage. If the master ever sees a version higher than its own, it assumes it failed while granting a lease and takes the higher number as current.

HDFS uses the same mechanism under the name generation stamp. Every block has a block ID and a generation stamp, and the NameNode bumps the stamp during pipeline recovery or lease recovery so that replicas that missed the update can be recognised and deleted.

Checksums

Every chunkserver checks the integrity of its own data. A chunk is divided into 64 KB blocks, each with a 32-bit checksum (GFS Section 5.2). Checksums are kept in memory and logged persistently, separately from the data. Reads verify the overlapping blocks first; a mismatch returns an error and the master clones a good replica over the bad one. Idle chunks are scanned in the background. Each server checks its own copy because replicas are not guaranteed to be byte-identical (record append can leave different padding and duplicates), so comparing replicas would flag legitimate differences.

HDFS computes a CRC32C checksum for every 512 bytes (dfs.bytes-per-checksum) and stores them in a separate .meta file next to each block file. The client verifies checksums on read, and a DataNode block scanner verifies blocks periodically in the background.


4. Read path and write path

Read path

sequenceDiagram
    autonumber
    participant App as Application
    participant Lib as GFS client library
    participant M as Master
    participant CS as Nearest chunkserver
    App->>Lib: read(file, byte offset, length)
    Lib->>Lib: chunk index = offset / 64 MB
    alt location not in cache
        Lib->>M: (file name, chunk index, plus a few following indexes)
        M-->>Lib: chunk handles + replica locations
        Lib->>Lib: cache by (file name, chunk index)
    end
    Lib->>CS: read(chunk handle, byte range)
    CS->>CS: verify 64 KB block checksums
    CS-->>Lib: data
    Lib-->>App: data

Three details matter:

  1. The client turns a byte offset into a chunk index itself, because the chunk size is fixed. The master only needs to answer "which handle is chunk i of this file, and where is it?"
  2. The client asks for several chunks at once. The master returns locations for the requested chunk and the next few, so a sequential reader avoids extra round trips at almost no cost.
  3. The client picks the closest replica. GFS infers "closest" from IP addresses. HDFS uses rack awareness: the NameNode sorts replica locations by network distance from the reader, and the client tries them in order, moving to the next on failure or checksum error.

HDFS adds two important read optimisations. Short-circuit local reads let a client on the same machine as a DataNode read the block file directly through a Unix domain socket and a passed file descriptor, skipping the DataNode's TCP path entirely. Centralized cache management lets operators pin hot files in DataNode off-heap memory. Both exist because the pure "stream through the DataNode" path wastes CPU for co-located compute like Impala or HBase.

Write path: leases and mutation order

Writes are where GFS is interesting. A mutation (a write or a record append) must be applied to all replicas of a chunk, and if two clients write concurrently, every replica must apply the mutations in the same order. GFS gets that order without running consensus on each write by using a lease:

  • The master grants a chunk lease to one replica, which becomes the primary.
  • The primary picks a serial order for all mutations to that chunk. All replicas apply mutations in that order.
  • So the global order of mutations on a chunk is: first by the order in which the master grants leases, then, within a lease, by the serial numbers the primary assigns.

A lease has an initial timeout of 60 seconds. While the chunk is being written, the primary can ask for extensions, and those requests and grants are piggybacked on the regular heartbeat messages. The master can revoke a lease early (for example to rename a file or take a snapshot). If the master loses contact with a primary, it can safely grant a new lease to another replica after the old lease expires — the lease timeout is what prevents two primaries at once. This is the same safety argument as any lease-based leader election: correctness depends on bounded clock drift between master and chunkserver, but not on synchronised absolute clocks.

The paper describes the write flow in seven numbered steps (Section 3.1, Figure 2). Here it is as a sequence diagram:

sequenceDiagram
    autonumber
    participant C as Client
    participant M as Master
    participant P as Primary replica
    participant S1 as Secondary A
    participant S2 as Secondary B
    C->>M: who holds the lease for chunk X, and where are the replicas
    M->>M: if no lease, grant one and bump chunk version
    M-->>C: primary = P, secondaries = A, B
    Note over C,S2: Data flow — pushed along a chain, pipelined, in any order
    C->>S1: push data (closest replica first)
    S1->>P: forward while still receiving
    P->>S2: forward while still receiving
    Note over P,S2: each replica holds the data in an LRU buffer, not yet applied
    Note over C,S2: Control flow — only after every replica has the data
    C->>P: write request (references the pushed data)
    P->>P: assign serial number, apply to local chunk
    P->>S1: apply mutation with serial number n
    P->>S2: apply mutation with serial number n
    S1-->>P: done
    S2-->>P: done
    P-->>C: success, or the errors from any replica

Some details that are easy to miss:

  • Data flow and control flow are decoupled. Step 3 pushes the bytes; step 4 tells the primary to apply them. The data is pushed linearly along a chain of chunkservers, each forwarding to the next-closest machine that hasn't received it yet, and forwarding starts as soon as bytes arrive (pipelining). The paper gives the ideal time to push bytes to replicas as , where is network throughput and the per-hop latency. On their 100 Mbps network with well under 1 ms, 1 MB could be distributed in about 80 ms. A tree or a star would split each machine's outbound bandwidth; a chain uses each link's full bandwidth.
  • The order in which replicas receive data doesn't matter. Ordering comes only from the primary's serial numbers in the control flow.
  • A write that spans a chunk boundary is split by the client library into several operations, one per chunk. Each part is atomic for its chunk, but the whole write is not.
  • Failure leaves replicas different. If the primary succeeds and one secondary fails, the client gets an error, and the modified region is now inconsistent: some replicas have the data, some don't. The client library retries steps 3–7 a few times, then falls back to retrying from the beginning. Nothing rolls back the replicas that succeeded.

HDFS's write path is the same idea with stricter rules: a file has one writer at a time (enforced by a NameNode lease), and data is only ever appended to the end of the file. That rules out concurrent writes to the same region altogether, and with it most of GFS's "undefined" states.

sequenceDiagram
    autonumber
    participant C as DFSClient
    participant NN as NameNode
    participant D1 as DataNode 1
    participant D2 as DataNode 2
    participant D3 as DataNode 3
    C->>NN: create(path) — takes the single-writer lease
    NN-->>C: ok, file under construction
    C->>NN: addBlock(path)
    NN-->>C: block ID + generation stamp + pipeline D1, D2, D3
    C->>D1: open pipeline
    D1->>D2: open pipeline
    D2->>D3: open pipeline
    loop for each 64 KB packet
        C->>D1: packet with checksums
        D1->>D2: forward packet
        D2->>D3: forward packet
        D3-->>D2: ack
        D2-->>D1: ack
        D1-->>C: ack, packet leaves the ack queue
    end
    C->>NN: complete(path) once the minimum replicas are reported
    NN-->>C: file closed, lease released

The HDFS client splits the stream into packets (64 KB by default), keeps unacknowledged packets in an ack queue, and removes a packet only after every DataNode in the pipeline has acknowledged it. If a DataNode fails mid-block, the client closes the pipeline, moves the unacknowledged packets back to the front of the data queue, gets a new generation stamp for the block from the NameNode (so the failed node's partial replica will be recognised as stale), and continues with the remaining DataNodes. The NameNode notices the block is under-replicated and schedules another copy later.

The writer's lease has a soft limit (one minute by default) during which the writer has exclusive access and must renew it, and a hard limit (one hour) after which the NameNode assumes the client is dead and runs lease recovery: it picks a primary DataNode to agree on the final length of the last block among the replicas, then closes the file. HBase triggers the same recovery when it takes over a dead RegionServer's write-ahead log.

HDFS also makes durability levels explicit: hflush() guarantees every pipeline DataNode has the data (in memory) and new readers see it, hsync() additionally fsyncs, and close() finalises the length.

Record append

Record append is the operation GFS invented for its many-producer workloads. The client gives GFS only the data; GFS chooses the offset, appends the record atomically at least once, and returns the offset to the client. It is like O_APPEND in Unix, but safe with many concurrent writers on different machines and without a distributed lock.

The mechanism (Section 3.3) rides on the normal write path with one extra check at the primary:

  1. The client pushes the data to all replicas of the last chunk of the file.
  2. The primary checks whether the record fits in the current chunk. If appending would exceed 64 MB, it pads the chunk to its maximum size, tells the secondaries to do the same, and tells the client to retry on the next chunk. Records are limited to one quarter of the chunk size to keep the worst-case padding waste bounded.
  3. If it fits, the primary appends at its current end-of-chunk offset, tells the secondaries to write at exactly that offset, and replies success.

If any replica fails, the client retries. The retry may land at a new offset. Meanwhile some replicas already wrote the first attempt. So after a failed-then-retried append, replicas of the same chunk can contain different bytes, including complete or partial duplicates of the record. What GFS guarantees is narrower than "the replicas are identical": it guarantees that the data is written at least once as an atomic unit, and that on success the record is at the same offset on every replica, because the retry only succeeds once every replica has written it at one common offset (padding the others up to that point if needed).

flowchart LR
    subgraph R1["Replica 1"]
        a1["rec A"] --> b1["rec B (try 1)"] --> c1["rec B (try 2)"] --> d1["rec C"]
    end
    subgraph R2["Replica 2"]
        a2["rec A"] --> b2["(failed — garbage/pad)"] --> c2["rec B (try 2)"] --> d2["rec C"]
    end
    subgraph R3["Replica 3"]
        a3["rec A"] --> b3["rec B (try 1)"] --> c3["rec B (try 2)"] --> d3["rec C"]
    end

In the figure, the region holding "rec B (try 1)" is inconsistent — replica 2 differs. The region holding "rec B (try 2)" is defined: the same bytes at the same offset on all three. The application reading this file will see rec B twice on replicas 1 and 3, so it must deal with duplicates and with garbage. Which brings us to the consistency model.

HDFS never implemented record append. Its single-writer rule means concurrent producers have to write to separate files (or go through something like Kafka or Flume), which is the main semantic difference between the two systems.

Snapshot

GFS also supports cheap snapshot using copy-on-write (Section 3.4): the master revokes outstanding leases on the affected chunks, logs the operation, duplicates the metadata so the new file points at the same chunks, and bumps each chunk's reference count. The first later write to a shared chunk makes each chunkserver copy it locally first. HDFS added read-only directory snapshots in Hadoop 2.


5. Consistency guarantees

GFS's consistency model is the part of the paper most worth reading closely, because it's precise about what it doesn't guarantee. The paper (Section 2.7) separates namespace operations from data mutations.

Namespace mutations: atomic and totally ordered

File creation, deletion and renaming are handled entirely by the master, under the namespace locks described above, and the master's operation log defines a global total order of these operations. They are atomic and correct. If you rename a file, every client sees either the old name or the new one.

File regions: three states

For file data, the paper defines two properties of a file region after a mutation:

  • Consistent: all clients will always see the same data, no matter which replica they read from.
  • Defined: consistent, and clients see what the mutation wrote in its entirety.

That yields three possible states for any region: defined, consistent but undefined, and inconsistent (which is also undefined). The paper's Table 1 shows which operation leads to which:

Write (at an offset the client chooses)Record append (offset GFS chooses)
Serial successdefineddefined, interspersed with inconsistent
Concurrent successesconsistent but undefineddefined, interspersed with inconsistent
Failureinconsistentinconsistent

Unpacking each cell:

  • Serial write success → defined. One writer, no interference, every replica applied the same bytes in the same order. Everyone reads what was written.
  • Concurrent write successes → consistent but undefined. Each write is atomic per chunk and applied in the same serial order on all replicas, so all replicas agree. But a large write gets split into chunk-sized pieces, and pieces from two writers can interleave. If clients A and B both write 100 MB to the same offset range, the result could be A's bytes in chunk 1 and B's bytes in chunk 2. Every reader sees the same mingled result (consistent), but it isn't what any single writer wrote (undefined).
  • Failure → inconsistent. Some replicas applied the mutation and some didn't. Different readers can see different data depending on the replica they read.
  • Record append success → defined, interspersed with inconsistent. The successfully appended record is defined at the offset GFS returned. Around it there may be padding and the remains of failed attempts — regions that are inconsistent.

How GFS makes a region defined after successful mutations

The paper's guarantee is: after a sequence of successful mutations, the mutated file region is guaranteed to be defined and contain the data written by the last mutation. It gets there by two means:

  1. Applying mutations to a chunk in the same order on all replicas (the primary's serial order).
  2. Using chunk version numbers to detect stale replicas — replicas that missed mutations because their chunkserver was down. Stale replicas are never handed out to clients and are garbage-collected soon after.

The caveats the paper itself states

Read the following carefully; these are the parts that surprise people.

  1. Clients cache chunk locations, so they can read from a stale replica. The window is limited by the cache entry's timeout and by the next open of the file (which purges cached locations). The paper notes that because most files are append-only, a stale replica usually returns a premature end of chunk rather than outdated data, and a reader retrying will contact the master and get fresh locations. But it is a window, not a guarantee.
  2. Failed mutations don't roll back. Inconsistent regions stay in the file. GFS doesn't repair them; applications must skip them.
  3. Duplicates are possible. Record append is at-least-once. A record can appear more than once.
  4. Component failures can still corrupt or destroy data. GFS identifies failed chunkservers by handshakes and detects corruption with checksums, and restores from valid replicas "as soon as possible". A chunk is lost irreversibly only if all its replicas are lost before GFS can react — typically within minutes. Even then the result is unavailability, not silent corruption: applications get clear errors.

What applications must do

GFS pushes part of the consistency burden onto applications, and the paper is explicit about the techniques Google's applications used (Section 2.7.2):

  • Prefer appends to overwrites. A writer generates a file from beginning to end and then atomically renames it to a permanent name, or it periodically checkpoints how much has been successfully written. Readers process only up to the last checkpoint, which is known to be defined.
  • Write self-validating, self-identifying records. Each record carries a checksum so a reader can detect and skip padding and fragments, and a unique identifier so a reader can drop duplicates. If an application can't tolerate duplicates (for example, a non-idempotent operation), it filters them using those IDs.
  • Google provided this as a shared library, so application authors didn't each reinvent record framing.
# A reader for a GFS-style record-append file: length-prefixed, checksummed,
# uniquely identified records. Garbage and padding are skipped by resyncing on a
# magic marker; duplicates from retried appends are dropped by record id.
import struct, zlib

MAGIC = b"\xfa\xce\xb0\x0c"
HEADER = struct.Struct(">4sI16sI")  # magic, length, 16-byte record id, crc32

def read_records(buf: bytes):
    seen = set()
    i = 0
    while i + HEADER.size <= len(buf):
        magic, length, rid, crc = HEADER.unpack_from(buf, i)
        end = i + HEADER.size + length
        if magic != MAGIC or end > len(buf):
            nxt = buf.find(MAGIC, i + 1)          # resync past padding / torn record
            if nxt < 0:
                return
            i = nxt
            continue
        payload = buf[i + HEADER.size:end]
        if zlib.crc32(payload) != crc:
            nxt = buf.find(MAGIC, i + 1)          # inconsistent region — skip it
            if nxt < 0:
                return
            i = nxt
            continue
        if rid not in seen:                        # drop at-least-once duplicates
            seen.add(rid)
            yield payload
        i = end

def frame(rid: bytes, payload: bytes) -> bytes:
    return HEADER.pack(MAGIC, len(payload), rid, zlib.crc32(payload)) + payload

if __name__ == "__main__":
    a, b = frame(b"A" * 16, b"alpha"), frame(b"B" * 16, b"bravo")
    # rec B duplicated by a retried append, with padding between
    data = a + b"\x00" * 37 + b + b
    assert list(read_records(data)) == [b"alpha", b"bravo"]
    print("ok")

That is the essence of GFS's bargain: the file system stays simple and fast because applications agree to frame their records.

HDFS's model

HDFS has a stricter model because it gave up concurrent writers: one writer per file, appends only, and data visible to new readers after hflush() (readers may see a stale last-block length until close()). In GFS terms, HDFS files are almost always defined: a single writer with serial appends. The one remaining source of inconsistency, a pipeline failure, is handled by pipeline recovery with generation stamps, so stale partial replicas are recognised and discarded rather than served.


6. Fault tolerance and recovery

GFS's high availability rests on two ideas from the paper (Section 5.1): fast recovery and replication.

Fast recovery

Both the master and the chunkservers restore their state and start in seconds, however they stopped; the paper says servers are routinely shut down by killing the process, and clients simply time out, reconnect and retry.

Chunk re-replication

The master re-replicates a chunk as soon as the number of available replicas falls below the target. Not all re-replications are equal, so the master prioritises (Section 4.3):

  1. How far the chunk is from its replication goal. A chunk that has lost two replicas is more urgent than one that has lost one.
  2. Live files before recently-deleted files.
  3. Chunks blocking client progress, to minimise the effect of failures on running applications.

The master limits the number of active clone operations, both cluster-wide and per chunkserver, so that recovery traffic doesn't swamp client traffic. Each chunkserver also throttles the bandwidth it spends on cloning. The master also rebalances replicas periodically, gradually filling a new chunkserver rather than flooding it with new chunks (which would also make it a write hot spot, because new chunks are where writes go).

The real numbers from the paper (Section 6.2.5) show this working: in a cluster, they killed one chunkserver holding about 15,000 chunks / 600 GB. With cloning limited to 91 concurrent clones (40% of the number of chunkservers) and each clone limited to 6.25 MB/s, all chunks were restored in 23.2 minutes, an effective replication rate of 440 MB/s. In a second experiment they killed two chunkservers, each with about 16,000 chunks and 660 GB, which left 266 chunks with a single replica. Those were cloned at higher priority and all brought back to at least two replicas within 2 minutes.

HDFS does the same through the NameNode's BlockManager. A DataNode sends a heartbeat every 3 seconds by default. A DataNode is considered dead after 2 × dfs.namenode.heartbeat.recheck-interval + 10 × dfs.heartbeat.interval, which with defaults (5 minutes and 3 seconds) is 10 minutes 30 seconds. The long timeout is deliberate: re-replicating a 10 TB node is expensive, and you don't want to start it because a DataNode had a long GC pause or a rolling restart. HDFS also has "stale" DataNode detection (30 seconds by default) so readers and writers avoid a node that's slow to heartbeat well before it's declared dead.

Garbage collection instead of eager deletion

When a file is deleted, the GFS master logs the deletion but does not reclaim storage immediately. It renames the file to a hidden name that includes the deletion time. During its regular namespace scan, the master removes hidden files older than three days (configurable). Until then, the file can be read under the hidden name and undeleted by renaming it back. In a similar regular scan of the chunk namespace, the master identifies orphaned chunks (not reachable from any file) and, in heartbeat exchanges, tells chunkservers which of their reported chunks no longer exist in its metadata. The chunkservers delete those.

The paper's argument: lazy collection is simple and reliable when chunk creation can fail halfway and deletion messages get lost, it batches work into idle time, and the delay is a safety net against accidental deletion. The cost is that space isn't freed immediately. HDFS has the same idea as an optional trash directory (fs.trash.interval) for shell deletes.

Master replication

The master's operation log and checkpoints are replicated on multiple machines, and a mutation is committed only after its log record has been flushed to disk locally and on all master replicas. One master process remains in charge of all mutations and of background activities like garbage collection. If it fails, it can restart almost instantly. If the machine or disk fails, monitoring infrastructure outside GFS starts a new master process elsewhere with the replicated operation log. Clients find the master by a DNS alias, which is changed to point at the new machine.

GFS also has shadow masters, which provide read-only access to the file system even when the primary master is down. They are shadows, not mirrors: they lag the primary slightly, typically fractions of a second, by reading a replica of the growing operation log and applying the same sequence of changes. They poll chunkservers at startup and exchange handshakes with them to keep replica locations fresh. For files that aren't being actively mutated, or for applications that can tolerate slightly stale results, shadow masters improve read availability.

So GFS had no automatic failover of the primary master, only fast restart, external restart elsewhere, and read-only shadows. That's the gap HDFS later filled with HA.

HDFS NameNode: from SPOF to HA

Early HDFS (Hadoop 1.x) had a single NameNode and a badly-named Secondary NameNode. The Secondary NameNode is not a standby: it periodically downloads the FsImage and EditLog, merges them into a new checkpoint, and uploads it back, so that the edit log doesn't grow forever and restarts don't take hours. If the NameNode died, the cluster was down until an operator restarted it, and a restart on a large cluster could take a long time (loading the image, replaying edits, then waiting for DataNodes to send block reports so it could leave safe mode).

Hadoop 2.0 added NameNode High Availability. The design (described in the HDFS HA documentation) is:

  • Two (and since Hadoop 3, optionally more) NameNodes: one Active, the rest Standby.
  • The Active writes every edit to a shared edit log. The recommended implementation is the Quorum Journal Manager (QJM): a group of JournalNodes (at least three, an odd number), and an edit is durable once a majority of JournalNodes have it. With N JournalNodes the system survives (N − 1) / 2 failures.
  • Standbys tail the edit log from the JournalNodes and apply edits to their own in-memory namespace, so they're always nearly current.
  • DataNodes send block reports and heartbeats to all NameNodes, so a Standby already knows block locations when it takes over. This is what makes failover take seconds instead of the long cold-start.
  • ZKFailoverController (ZKFC) processes, one per NameNode, use ZooKeeper for health monitoring and leader election: each ZKFC holds a session, and the one that holds an ephemeral lock znode makes its NameNode Active.
  • Fencing prevents split brain. The JournalNodes only accept writes from one writer at a time, tracked by an epoch number: a new Active gets a higher epoch, and JournalNodes reject edits from any NameNode with a lower one. This is the fencing token pattern applied to an edit log. Operators can also configure extra fencing methods (SSH to kill the old process, or a shell script that cuts power).
flowchart TB
    ZK["ZooKeeper ensemble<br/>(lock znode for active NN)"]
    subgraph NNs["NameNodes"]
        A["Active NameNode"]
        S["Standby NameNode"]
    end
    ZA["ZKFC"] --- A
    ZS["ZKFC"] --- S
    ZA <-->|"session + ephemeral lock"| ZK
    ZS <-->|"session, watches lock"| ZK
    subgraph QJM["JournalNodes (quorum)"]
        J1["JN 1"]
        J2["JN 2"]
        J3["JN 3"]
    end
    A -->|"write edits (epoch n), majority ack"| QJM
    QJM -->|"tail edits"| S
    DN["DataNodes"] -->|"heartbeats + block reports"| A
    DN -->|"heartbeats + block reports"| S

Hadoop 3.3 added the Observer NameNode (HDFS-12943): a read-only standby that serves read RPCs. Clients track the last transaction ID they've seen from the Active (a "state ID"), and an Observer delays a read until it has applied edits up to that ID, giving read-your-writes consistency while moving read load off the Active. Large deployments use this because read RPCs (getBlockLocations, getFileInfo, listStatus) dominate NameNode traffic.

HDFS Federation

HA fixed availability but not scale. One NameNode still held the whole namespace in one JVM heap behind one lock. Federation (also Hadoop 2.0) splits the namespace across multiple independent NameNodes:

  • Each NameNode manages one namespace volume and its block pool — the set of blocks belonging to that namespace. NameNodes don't talk to each other.
  • Every DataNode stores blocks for all block pools and registers with every NameNode, so storage is shared while metadata is partitioned.
  • Clients see a unified view through ViewFs, a client-side mount table (like /user → NameNode 1, /data → NameNode 2), or through Router-based Federation (Hadoop 2.9/3.0), where stateless routers hold the mount table in a state store and proxy RPCs to the right NameNode, so clients don't need the mount table.

Federation is coarse-grained partitioning: a whole subtree lives on one NameNode, and moving data between namespaces is a copy, not a metadata operation. Operators manage it by hand; it is not automatic metadata sharding.


7. Performance numbers from the paper

The GFS paper reports both micro-benchmarks and production measurements. The numbers are from 2003 hardware; what matters is the shape.

Micro-benchmarks (GFS Section 6.1)

The test cluster had 1 master, 2 master replicas, 16 chunkservers and 16 clients. Each machine had dual 1.4 GHz PIII processors, 2 GB of memory, two 80 GB 5400 rpm disks, and a 100 Mbps full-duplex Ethernet connection to an HP 2524 switch. The 19 GFS servers were on one switch and the 16 clients on another, with a 1 Gbps link between them.

BenchmarkResultNotes from the paper
Reads, 16 clients each reading 4 MB regions of a 320 GB file set94 MB/s aggregateAbout 75% of the 125 MB/s limit of the 1 Gbps inter-switch link; per-client 6 MB/s, about 80% of the 12.5 MB/s NIC limit
Writes, 16 clients each writing 1 GB to new files35 MB/s aggregateAbout half the 67 MB/s limit (each byte goes to 3 of 16 chunkservers); ~6.3 MB/s for one client
Record append, N clients to one file6.0 MB/s for one client, 4.8 MB/s for 16Bound by the chunkservers holding the last chunk; in practice many files are appended at once

GFS was not fast for writes, and didn't need to be: its workloads cared about aggregate bandwidth across many files, not per-write latency.

Production clusters (GFS Section 6.2)

Cluster A (R&D)Cluster B (production)
Chunkservers342227
Available disk72 TB180 TB
Used disk55 TB155 TB
Number of files735 k737 k
Number of dead files22 k232 k
Number of chunks992 k1,550 k
Metadata at chunkservers13 GB21 GB
Metadata at master48 MB60 MB
Read rate (last minute)583 MB/s380 MB/s
Write rate (last minute)1 MB/s101 MB/s
Master ops325 ops/s533 ops/s

Look at the "metadata at master" row: 48–60 MB of master memory for over 150 TB of data. That's the single-master argument in one number. The paper says the master could keep up with 200–500 operations per second easily, and that an earlier bottleneck — linear scans of large directories — was fixed by changing the data structures to allow efficient binary search through the namespace, after which it could handle many thousands of file accesses per second.


8. What it got right, what it got wrong, and what came next

What GFS got right

  • Separating metadata from data. Every large-scale storage system since (HDFS, Colossus, Ceph, S3's internal architecture, object stores generally) keeps a metadata service separate from the data servers that actually stream bytes.
  • Designing for failure as a normal event. Checksums on every block, fast restarts, background scrubbing, version numbers, automatic re-replication with priorities.
  • Leases to order writes cheaply. The master is involved once per lease (60 seconds), not once per write. The primary gives a total order without per-write consensus.
  • Pipelined chain replication of data. Using full link bandwidth for each hop is still how HDFS, Ceph and most chunk stores push replicas.
  • Co-designing with applications. Weak semantics plus a record-framing library was a much simpler system than strong semantics, and it fit the workloads.
  • Lazy garbage collection. Simpler and safer than eager distributed deletion.

What it got wrong (by its own authors' later account)

In 2009, ACM Queue published "GFS: Evolution on Fast-forward", an interview between Kirk McKusick and Sean Quinlan, who had been GFS tech lead. It's the most candid source on GFS's limits:

  • The single master didn't scale for the workloads that arrived later. The number of files, not their size, was the problem. As clusters grew to many petabytes and applications created many more files, master memory and master CPU became bottlenecks. Google's workaround was to run multiple GFS cells per data center and multiple masters over shared chunkservers, with applications partitioning their data across them — essentially manual federation, the same thing HDFS did later.
  • 64 MB chunks were wrong for many newer applications. Gmail and similar services wanted small files and low latency. Much smaller chunks would have multiplied master metadata, which the single master couldn't afford.
  • Latency-sensitive applications suffered. GFS was designed for batch throughput. When a chunkserver was slow or failed during a write, recovery of the write pipeline could stall a client for seconds, or for a minute in the case of master failover.
  • Record append's semantics were too weak. Quinlan said in the interview that the at-least-once, possibly-duplicated, possibly-padded semantics caused real pain for application developers, and that a single-writer model with stronger guarantees (essentially what HDFS chose) would have been better.

Colossus

Google replaced GFS with Colossus around 2010. Google hasn't published a Colossus paper; most of what is public comes from talks and a 2021 Google Cloud blog post ("A peek behind Colossus, Google's file system"). The public description is:

  • Distributed metadata. The single master is gone. Metadata is stored in a scalable database — Bigtable originally, with the 2021 post describing Colossus metadata stored in Bigtable — which lets one Colossus file system scale to exabytes and billions of files. Stateless curators handle control-plane operations such as file creation and talk to that metadata store.
  • D file servers. Data lives on "D" servers, which are simple network-attached disk servers; clients talk to them directly.
  • Custodians perform background storage management — durability, rebalancing, recovery, disk-space balancing.
  • Client-side encoding. The client library does the replication or Reed-Solomon erasure coding, which lets applications choose the encoding per file instead of everything paying 3× replication.
  • Mixing of hardware and data. The system places hot and cold data across flash and disk to make good use of the I/O of every device.

In other words, Colossus inverted GFS's main shortcut: metadata is now a sharded, replicated database (Bigtable, which itself stored its files on GFS — Colossus effectively uses a smaller Colossus to bootstrap the metadata layer). The data path kept GFS's ideas: direct client-to-server streaming, checksums, and background repair.

How HDFS evolved

Problem in GFS-style designHDFS response
Master is a single point of failureNameNode HA with QJM + ZKFC (Hadoop 2.0), multiple standbys (Hadoop 3)
Master is a scalability ceilingFederation + ViewFs (Hadoop 2.0), Router-based Federation (Hadoop 2.9/3.0)
Read RPCs overload the active masterObserver NameNode with consistent reads (Hadoop 3.3)
3× replication is expensive for cold dataErasure coding, e.g. RS(6,3) — 1.5× overhead tolerating 3 lost blocks (Hadoop 3.0)
Weak append semanticsSingle writer; hflush/hsync; append support with careful lease recovery
Small files exhaust master memoryHAR files, SequenceFiles, compaction jobs; ultimately Apache Ozone, an object store with scalable metadata in RocksDB-backed, Raft-replicated Ozone Managers
Cost and elasticity of on-prem clustersMany organisations moved to cloud object stores (S3, GCS, ADLS) with table formats like Iceberg and Delta on top

The small-files problem

The single-master design hard-codes an assumption: metadata per byte of data is tiny. That's true when files are gigabytes. It breaks when they're kilobytes.

The widely cited rule of thumb (from Cloudera's guidance, derived from NameNode internals) is that every file, directory and block is an object in NameNode memory costing roughly 150 bytes. Take 100 million small files, each one block:

And the data volume might be small — 100 million 10 KB files is only 1 TB. The NameNode is now a 30+ GB JVM, its GC pauses get long, restarts get slower (loading the image, processing block reports), and every MapReduce or Spark job over that data creates one task per file, so scheduling overhead dominates.

The same ratio is why the GFS paper's "less than 64 bytes per 64 MB chunk" was so effective: 64 bytes per 64 MB is one millionth. A 10 KB file carries the same per-object overhead for one six-thousandth of the data.

Mitigations, from least to most invasive: don't create small files (batch writes, size outputs to the block size, coalesce in Spark); compact after the fact (Iceberg, Delta and Hudi have it built in); pack records into container formats (SequenceFile, Parquet, Hadoop Archives); federate; or move small objects to HBase, Ozone or an object store.


9. Lessons for system design interviews

GFS is the reference design behind many interview questions — "design a distributed file system", "design Dropbox's storage layer", "design S3", "design a log storage service". The lessons that transfer best:

  1. Separate metadata from data and make the data path bypass the coordinator. A coordinator that only handles small, cacheable metadata requests can serve a huge cluster.
  2. Do the metadata arithmetic. Bytes of metadata per object × number of objects = coordinator memory. If the interviewer's numbers make that more than a big server's RAM, you need partitioned metadata (federation, or a sharded metadata database like Colossus).
  3. Order writes with a lease, not with consensus on every write. A primary holding a time-bounded lease from a coordinator gives a total order cheaply. Know the safety requirement: the coordinator must wait for the old lease to expire before granting a new one, and clock drift must be bounded.
  4. Decouple data flow from control flow. Push data along a pipeline/chain first, then commit with a small control message. This keeps the primary from becoming a bandwidth bottleneck.
  5. State the consistency model precisely. "Eventually consistent" is not an answer. Say which operations are atomic, what readers can see after a failure, and what the application must do about it (checksums, unique IDs, idempotent processing).
  6. Recovery is a scheduling problem. Re-replication needs priorities (fewest remaining replicas first) and throttles, or recovery traffic will hurt user traffic. Mention failure-detection timeouts and why they're long for storage nodes (re-replicating a big node is expensive).
  7. Make single points of failure into fast-failover pairs with fencing. The HDFS HA design — shared quorum log, standby that tails it, ZooKeeper for election, epoch numbers for fencing — is a reusable template for any single-leader metadata service.

10. Interview questions

1. Why doesn't file data flow through the GFS master? What would break if it did?

Aggregate throughput would be capped at one machine's NIC (about 12.5 MB/s on the paper's network) instead of scaling with hundreds of chunkservers. Handling only small, cacheable metadata requests — roughly one per 64 MB chunk — keeps master load proportional to chunk lookups, not bytes.

2. Walk through what happens when a GFS primary crashes in the middle of a write.

Some secondaries may have applied the mutation and some not; the client gets an error or timeout, the region is inconsistent, and the client retries. The master notices the primary is gone (missed heartbeats), waits until the lease expires (up to 60 s, which is what prevents two primaries), then grants a new lease to another up-to-date replica and bumps the chunk version. Any replica that missed mutations is now stale by version number and is garbage-collected and replaced by re-replication. Nothing rolls back the partial write, which is why applications use checksums and checkpoints.

3. Explain "consistent but undefined" with a concrete example.

Two clients concurrently write 128 MB to the same offset of a file. Each write is split into two chunk-sized operations. For chunk 1, the primary orders A then B, so B's data wins in chunk 1. For chunk 2, a different primary orders B then A, so A's data wins in chunk 2. All replicas of each chunk agree (consistent), so every reader sees the same bytes. But what they see — B's first half and A's second half — isn't what either client wrote (undefined).

4. Why does record append limit records to a quarter of the chunk size?

When a record doesn't fit in the remaining space of the current chunk, the primary pads the chunk to 64 MB and the client retries in the next chunk. The padding is wasted space. Capping records at 16 MB bounds worst-case waste per chunk to under a quarter of it, and in practice records are much smaller, so waste is small.

5. Your HDFS NameNode has a 120 GB heap and GC pauses of 30 seconds. What's going on and what do you do?

Almost certainly too many namespace objects — usually small files. At ~150 bytes per file/block object, 120 GB is several hundred million objects. Short term: find the directories with the most files (fsimage analysis with the Offline Image Viewer), compact small files into larger ones, tune GC (G1 or a modern low-pause collector), and add an Observer NameNode to offload reads. Medium term: federate — split the namespace across NameNodes with Router-based Federation. Long term: move small-object workloads to HBase, Ozone or an object store.

6. How does HDFS HA prevent two Active NameNodes (split brain)?

Two layers. First, ZKFC uses a ZooKeeper ephemeral lock znode: only one ZKFC holds it, and it makes its NameNode Active. If its session expires, the lock disappears and the other ZKFC takes over. But a paused old Active might not know it lost the lock. So second, the JournalNodes enforce an epoch: a new Active obtains a higher epoch from a majority of JournalNodes, and they reject any edit with a lower epoch. The old Active cannot commit edits even if it wakes up and tries. Optional fencing scripts (SSH kill, power off) add a third layer.

7. Design question — you have 10 billion 50 KB images. Would you store them in HDFS? If not, what?

No, not as individual files: 10 billion files plus 10 billion blocks at ~150 bytes each is about 3 TB of NameNode metadata — impossible for a single NameNode and impractical even with heavy federation. Options: an object store (S3/GCS) designed for many small objects with partitioned metadata; packing images into large container files (like Facebook's Haystack design: append images to large volume files and keep a compact in-memory index of offset and size per image); or HBase/Bigtable keyed by image ID, which stores small values inside large SSTable/HFiles on HDFS/Colossus.

8. What did Colossus change compared to GFS, and why?

It replaced the single in-memory master with metadata stored in a scalable distributed database (Bigtable), with stateless curators for control operations, so the namespace scales to billions of files and exabytes. It moved replication and erasure coding into the client library so encoding is per-file, and added custodians for background repair and rebalancing. The motivation is exactly GFS's later pain points: master memory, file count, and latency-sensitive workloads like Gmail and Bigtable serving that needed smaller files and faster recovery.


Further reading

  • Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System. SOSP 2003.
  • Konstantin Shvachko, Hairong Kuang, Sanjay Radia, Robert Chansler. The Hadoop Distributed File System. IEEE MSST 2010.
  • Apache Hadoop documentation: HDFS Architecture, HDFS High Availability Using the Quorum Journal Manager, HDFS Federation, HDFS Router-based Federation, Consistent Reads from HDFS Observer NameNode, HDFS Erasure Coding.
  • Marshall Kirk McKusick, Sean Quinlan. GFS: Evolution on Fast-forward. ACM Queue, 2009.
  • Dean Hildebrand, Denis Serenyi. A peek behind Colossus, Google's file system. Google Cloud Blog, 2021.
  • Related on Archon: Replication, Consistency Models, Leader Election, Distributed Locking, Blob Storage, Bigtable & HBase, ZooKeeper, MapReduce & Spark.