GFS Fault Recovery

The Foundation: High Availability by Design

GFS achieves high availability through two primary strategies: fast recovery and replication.

• Fast Recovery: Both master and chunkserver processes are designed to restart their state and become operational within seconds, regardless of whether they terminated cleanly or crashed. The system treats a crash-and-restart as a routine event.
• Replication: As we've discussed, data is made durable through replication. Chunks are replicated across multiple chunkservers, and the master's critical state is also replicated.

This philosophy of expecting failure permeates every aspect of the system's design. Let's now dissect how GFS applies these principles to handle specific failure scenarios.

Recovering from Chunkserver Failures

Chunkserver failures are the most common type of failure in a GFS cluster. They can manifest as a temporary network partition, a process crash, or a permanent hardware failure.

Detection and Re-replication

The master detects a chunkserver failure when it stops receiving the periodic HeartBeat messages from that server. When this happens, the master assumes the chunkserver is dead and all the replicas it holds are unavailable. This has an immediate consequence: the replication factor for many chunks suddenly drops below the desired goal (typically three).

The master's response is swift and automatic:

1. It scans its in-memory metadata to identify all chunks that are now under-replicated.
2. It prioritizes the re-replication tasks. For example, a chunk that has lost two replicas (and is down to its last copy) is given a much higher priority than a chunk that has lost only one.
3. For each high-priority task, the master selects an existing, valid replica and instructs a healthy chunkserver to "clone" it. This data transfer happens directly between the two chunkservers, minimizing the load on the master.
4. The placement of the new replica follows the same rack-aware policy as initial creation to maximize fault tolerance.

The entire process is carefully throttled to prevent re-replication traffic from overwhelming the network and impacting active client operations. The GFS paper reports that after a chunkserver with 600 GB of data failed, all its chunks were restored to full replication in just over 23 minutes.

Data Corruption

A more insidious failure is silent data corruption on disk, often called "bit rot." A chunk replica might appear to be available, but its content has been altered. GFS guards against this using checksums.

Each 64 MB chunk is divided into 64 KB blocks, and each block has a 32-bit checksum. These checksums are stored in memory and persisted separately from the data.

When a chunkserver receives a read request, it first verifies the checksums for the data blocks being read before returning data to the client. If a checksum mismatch is found, the recovery process is triggered.

The steps are as follows:

1. The chunkserver detects the mismatch and returns an error to the requester (a client or another chunkserver).
2. It also reports the corruption to the master.
3. The requester, upon receiving the error, simply asks the master for chunk locations again and retries the read from a different replica.
4. The master, now aware of the corrupt replica, treats it as it would a failed replica. It initiates a cloning operation to create a new, valid replica from a good one.
5. Once the new replica is in place, the master instructs the chunkserver with the corrupted data to delete its replica.

This mechanism ensures that data corruption is not propagated through the system and that the file system automatically heals itself.

Recovering from a Master Failure

While chunkserver failures are common, a master failure is more critical because it is a single point of control. GFS employs a robust strategy to ensure the master can recover quickly and its state is not lost.

Master State Persistence

As we've learned, the master stores all file system metadata in memory for fast access. To make this state durable, GFS uses two familiar mechanisms from database design: an operation log (also known as a write-ahead log or WAL) and checkpoints.

• Operation Log: Every operation that changes the file system's metadata (e.g., creating a file, changing permissions, granting a lease) is first written as a record to an append-only log on disk.
• Log Replication: This operation log is the master's source of truth. To protect it, the log is synchronously replicated to a set of remote machines. A metadata mutation is only considered "committed" after its log record has been successfully flushed to disk on both the primary master and all its log replicas.
• Checkpoints: To avoid replaying an ever-growing log on startup, the master periodically creates a checkpoint—a compact, B-tree representation of its entire in-memory state—and writes it to disk.

When a master process crashes and restarts, it recovers its state by loading the most recent checkpoint from disk and then replaying only the operation log records that have occurred since that checkpoint. This makes the recovery process extremely fast.

If the master's entire machine fails, an external monitoring system starts a new master process on a different machine. This new master recovers its state using a replicated copy of the checkpoint and operation log. The clients, which connect to the master via a DNS alias (e.g., gfs-production), are seamlessly redirected to the new master once the alias is updated.

Rebuilding Chunk Locations

An elegant simplification in the master's design is that it does not persist chunk location information. Storing this volatile information would be complex, as chunkservers constantly join and leave the cluster.

Instead, the master treats the chunkservers themselves as the source of truth for replica locations. When a master starts up, it polls every live chunkserver and asks for an inventory of the chunks it holds. It uses these responses to build its in-memory map of chunk locations. This information is then kept up-to-date via the regular HeartBeat messages. This design avoids potential inconsistencies between persisted state on the master and the actual state on the chunkservers.

Shadow Masters for Read Availability

To further mitigate the impact of a master outage, GFS can run "shadow" masters. These are read-only replicas of the master that asynchronously apply the same operation log as the primary. They may lag the primary by a fraction of a second, but they can satisfy read requests for metadata (e.g., file lookups) if the primary master is temporarily unavailable. This enhances read availability, especially for applications that are not actively mutating files.

Clean-Up: Lazy Garbage Collection

The final piece of the fault tolerance puzzle is how GFS reclaims storage space from deleted files and orphaned replicas. Instead of immediate, synchronous deletion—which would be complex and error-prone in a distributed system—GFS uses a lazy garbage collection mechanism.

• When a file is deleted, the master simply logs the deletion and renames the file to a hidden name that includes a timestamp. The file is not immediately removed.
• During a regular background scan, the master permanently removes any hidden files that are older than a configurable interval (e.g., three days). This provides a safety net against accidental deletion.
• Once a file's metadata is removed, its constituent chunks become "orphaned."
• In a separate background scan of the chunk namespace, the master identifies these orphaned chunks.
• During the next HeartBeat message exchange with a chunkserver, the master includes a list of orphaned chunks that the chunkserver is free to delete.

This approach is simple, reliable, and amortizes the cost of storage reclamation. It reliably cleans up replicas that might have been created but never recorded by the master due to a failure, or replicas left behind by a failed chunkserver.

Conclusion

In this lesson, we have analyzed the critical fault tolerance mechanisms that make GFS a resilient storage platform capable of running on unreliable hardware. You can now articulate how GFS handles both the common and the critical failure modes.

The key takeaways are:

• Chunkserver Failures: Detected via missed heartbeats. Recovery is handled by the master orchestrating re-replication, with data copied directly between chunkservers.
• Data Corruption: Detected via checksums on every read. The system isolates the bad replica and automatically heals by creating a new, correct copy.
• Stale Replicas: Detected using chunk version numbers, ensuring clients are not served old data from a recovered-but-out-of-sync chunkserver.
• Master Failures: The master's state is protected by a synchronously replicated operation log and periodic checkpoints. This allows for fast recovery. If the master machine fails, a new instance can be started elsewhere and clients are redirected via DNS.
• Read Availability: Shadow masters can serve read-only metadata requests during a primary master outage, enhancing overall system availability.

We have now completed our deep dive into the original GFS architecture. We've examined its components, its read and write paths, its consistency model, and its robust fault tolerance. However, GFS was just the beginning. In our next lesson, we will describe the evolution from GFS to Colossus, its successor, and analyze the key architectural improvements made to overcome the limitations of the original design, particularly the single master bottleneck.