GFS and HDFS

A search company stores the crawled web, logs and the intermediate results of large computations. Files are enormous, often many gigabytes, and the total is petabytes. The machines are cheap, so some of them are always broken. Workloads mostly read huge files sequentially and append to the end of files, and rarely overwrite data in the middle. Throughput matters far more than the latency of a single operation. The Google File System (GFS) was designed around exactly these facts, and the open source Hadoop Distributed File System (HDFS) follows the same blueprint.

• Failure is the norm. With thousands of machines, disks and servers fail every day, so the system must detect, tolerate and recover automatically.
• Files are huge, so optimize for large streaming reads and large appends, not for millions of tiny files.
• Writes are mostly appends, and once written, files are mostly read, so random in-place writes can be unsupported or slow.
• Many clients append to the same file at once, such as many workers writing results, so appending must be atomic and cheap.
• High sustained bandwidth is more valuable than low latency.

A cluster has three kinds of participants.

• A single master keeps all metadata: the namespace (the file and directory tree), the mapping from each file to its chunks, and where each chunk's replicas live.
• Many chunkservers store the actual data, as ordinary files on local disks.
• Clients are the applications, using a library.

Files are split into fixed size chunks of 64 MB, each identified by a unique 64-bit chunk handle. Each chunk is replicated, by default on three chunkservers.

The crucial design point: data never flows through the master. The master answers questions about where, and the client then talks directly to chunkservers for the data. This keeps the single master from becoming a bottleneck.

A single master makes the design simple: it has a global view, so it can make good placement and replication decisions without coordination protocols. The danger is overloading it. Three choices prevent that.

• The metadata is kept entirely in memory, so master operations are fast.
• The master is involved in metadata only, and clients cache chunk locations.
• Chunks are large. Large chunks mean less metadata: about 64 bytes per chunk. A petabyte of data is 2 to the 50 bytes divided by 2 to the 26, about 16 million chunks, so roughly 1 GB of metadata. That fits comfortably in one machine's memory. Large chunks also mean a client reading sequentially needs to contact the master rarely, and can keep a long-lived connection to one chunkserver.

The cost of big chunks is that a small file occupies a single chunk, and if many clients read it at once, that chunk's servers become hot. This is handled by raising the replication of hot files.

The master holds three kinds of metadata: namespaces, file-to-chunk mapping, and chunk locations. The first two are made persistent through an operation log, a write-ahead record of every change, stored on the master's disk and replicated on remote machines. The master periodically writes checkpoints of its state, so recovery loads the latest checkpoint and replays the short log after it.

The third kind, chunk locations, is not persisted. The master simply asks each chunkserver what chunks it holds when it starts, and keeps current through regular heartbeat messages. This removes the problem of keeping the master and chunkservers in agreement, because the chunkserver is always the authority on what it has. If the master fails, an external monitor starts a new one from the log, and read-only shadow masters can serve reads in the meantime.

1. The client converts a file name and byte offset into a chunk index, and asks the master for the chunk handle and the replica locations.
2. The master replies, and the client caches the answer.
3. The client sends a read request to one replica, usually the closest, and reads the data directly.

Later reads of the same chunk skip the master entirely.

Writes must reach all replicas in the same order. Instead of making the master order every write, GFS delegates that to one replica through a lease.

1. The master picks one replica of the chunk as the primary, granting it a lease for about 60 seconds, renewable. The others are secondaries.
2. The client asks the master which replica is primary, and caches it.
3. The client pushes the data to all replicas. It sends data along a chain, each server forwarding to the nearest one that has not yet received it, so the client's network bandwidth is used once and each machine's outbound bandwidth is used fully. Data is buffered but not yet applied.
4. The client sends a write request to the primary. The primary assigns it a serial number, applies it, and forwards the same order to all secondaries.
5. Secondaries apply and acknowledge. The primary replies to the client.

Separating data flow from control flow is the key idea: data travels along a network-efficient chain, while ordering is decided by one primary.

Appending is the most common write, so GFS gives it a special atomic operation. The client provides only the data, and the system chooses the offset. The primary appends the data at the end of the chunk, and returns the offset used. If the data would exceed the chunk size, the primary pads the chunk and tells the client to retry on the next chunk. Many clients can append concurrently without locks.

The guarantee is at least once: if an append fails on some replicas and is retried, a record may appear more than once, and chunks may contain padding. Applications handle this by writing checksums and unique ids in records, so readers can skip junk and discard duplicates.

GFS relaxes consistency to keep the system simple and fast. After a mutation, a region of a file is either consistent (all replicas show the same data) or not, and defined (consistent and showing exactly what one write wrote) or not. A successful serial write leaves the region defined. Concurrent successful writes leave it consistent but possibly undefined, a mixture of fragments. A failed write leaves it inconsistent. Applications live with this by favoring appends, using checksums, and writing self-validating records.

• Snapshots are made with copy-on-write: the master revokes leases, records the snapshot as new metadata pointing to the same chunks, and only copies a chunk when someone first writes to it. A snapshot is near instant.
• Placement: replicas are spread across racks, so a rack failure or switch loss does not destroy all copies, and reads can use the bandwidth of several racks.
• Re-replication: when a chunkserver dies, the master notices missing replicas and orders new copies, prioritizing chunks with the fewest remaining.
• Garbage collection: deleting a file only renames it to a hidden name. Space is reclaimed lazily in the background, which is simple and safe even when messages are lost.
• Stale replicas: each chunk has a version number, raised when a new lease is granted. A replica that missed a mutation has an old version and is detected and discarded.
• Data integrity: each chunkserver divides chunks into 64 KB blocks with a checksum, verified on every read, so disk corruption is caught instead of returned.

HDFS, part of Hadoop, applies the same ideas with different names and some simplifications.

• The NameNode corresponds to the master. It keeps the namespace and the block map in memory, with an edit log and an fsimage checkpoint.
• DataNodes correspond to chunkservers, storing blocks, 128 MB by default, and sending heartbeats and block reports.
• The replication factor is 3 by default, with rack-aware placement: the first replica on the writer's node, the second on a node in a different rack, and the third on another node in that same remote rack. This survives a rack failure while limiting cross-rack traffic.

HDFS write: the client asks the NameNode to create a file and receives a list of DataNodes for each block. It writes to the first DataNode, which forwards to the second, which forwards to the third, forming a pipeline. Data is sent as small packets and acknowledgements travel back up the pipeline. HDFS read: the NameNode returns, for each block, the DataNodes sorted by closeness, and the client reads directly from the nearest.

• HDFS files have a single writer and support append, but not concurrent record append from many clients.
• HDFS blocks are larger by default.
• HDFS added high availability to the NameNode: an active and a standby NameNode share the edit log through a quorum of JournalNodes, and a failover controller using ZooKeeper promotes the standby automatically.
• Federation splits the namespace across several NameNodes, so the memory of one NameNode is no longer the limit.
• For cold data, erasure coding stores data with parity blocks, for example 6 data plus 3 parity, so the overhead is 1.5 times instead of 3 times, at the cost of more work to read and repair.

• Small files are a weakness: each file and block costs memory on the single master, so millions of tiny files exhaust it. Pack them into larger files.
• Low latency random access is not the goal.
• The single master and relaxed consistency are deliberate tradeoffs: simplicity and throughput over generality.
• A repeating principle: keep the control plane small and central, and let the data plane scale out, with components that can always be rebuilt from the cluster's state.