Fault Tolerance in Distributed Systems

1. The Landscape of Fault Tolerance

A fault-tolerant system can continue its intended operation, possibly at a reduced level, rather than failing completely, when some part of the system fails. Achieving this involves a continuous process.

We will examine two fundamental recovery strategies:

1. Replication: Maintaining multiple copies of data or computation to provide high availability.
2. Checkpointing & Logging: Periodically saving the state of a system to allow it to be restored after a crash.

2. Replication: Surviving Failures with Redundancy

The most common strategy for fault tolerance is replication: running multiple copies (replicas) of a service or data store on different machines. If one replica fails, the others can take over.

To begin, let's get a formal introduction to why replication is so crucial in distributed systems.

As the video explains, replication is simple for static, unchanging data. The real challenge emerges when the data needs to be updated. How do we ensure all replicas stay consistent? This is the central problem of data replication.

The Problem of Changing Data

When requests that modify data (writes) are sent to a replicated system, we can encounter issues due to network failures or retries. A simple "increment counter" operation, if retried, could be applied twice.

A key concept for handling this is idempotence. An operation is idempotent if applying it multiple times has the same effect as applying it once.

• Not idempotent: increment(x)
• Idempotent: set(x, 5) or add_element_to_set('a')

Let's watch a segment that illustrates this problem and introduces idempotence as a partial solution.

While idempotence helps with simple retries, it doesn't solve all consistency problems, especially when multiple clients are making concurrent updates. This leads us to specific protocols designed to manage replication.

Replication Protocols: Primary-Backup and Chain Replication

Let's examine two common protocols that provide strong consistency, meaning the system behaves as if there's only one copy of the data. Your engineering background will be useful here, as we'll analyze the performance trade-offs between them in terms of latency and throughput.

1. Primary-Backup Replication (or Leader-Follower): One replica is designated as the primary (or leader). It receives all write requests, forwards them to the backups (followers), waits for their acknowledgements, and then confirms the write to the client. All read requests also go to the primary.

2. Chain Replication: Replicas are organized in a chain. Writes go to the head of the chain, propagate through the middle nodes, and are finally committed at the tail. The tail is responsible for acknowledging the client. Read requests are served exclusively by the tail.

To understand how these work in detail, let's turn to a lecture that explains and compares them.

Let's summarize the trade-offs discussed in the video:

The choice between them depends on the application's needs. If fast writes are critical, Primary-Backup is better. If maximizing throughput for a mixed workload is the goal, Chain Replication might be superior, despite its higher write latency.

3. Checkpointing and Logging: Recovering from a Crash

Replication keeps a system running during a failure. But what if a non-replicated process crashes, or an entire replicated group fails simultaneously? For this, we need a way to recover the state of a process to a point before the failure. The two main techniques are checkpointing and logging.

As the text explains:

• Checkpointing: Periodically saving the entire state of a process to stable storage (like a disk). After a failure, the process can be restarted from its last checkpoint.

  • Pro: Recovery can be fast because the full state is ready to be loaded.
  • Con: Taking a checkpoint can be slow and resource-intensive, especially for large applications. It also means any work done since the last checkpoint is lost.

• Logging: Recording every state-changing event or operation in a log file on stable storage.

  • Pro: Less intrusive than checkpointing during normal operation.
  • Con: Recovery can be very slow if the log is long, as all operations since the beginning (or the last checkpoint) must be replayed.

In practice, these two techniques are almost always used together. A system takes infrequent, full checkpoints and then logs all the changes that occur between checkpoints.

This diagram shows how checkpointing and logging are combined. The system state is recovered by first loading the last checkpoint and then replaying the subsequent log entries. This minimizes data loss while avoiding the need to replay the entire history of operations.

When a failure occurs, the recovery process is:

1. Restore the system to the state of the last checkpoint.
2. Replay the log to reconstruct the work done between the checkpoint and the crash.

This hybrid approach provides a balance: it limits the amount of data lost (only events not yet written to the log) and significantly speeds up recovery time compared to using logs alone.

There are further complexities, such as coordinating checkpoints across multiple interacting processes to avoid inconsistencies (a problem known as finding a consistent recovery line), but the fundamental strategy remains this combination of periodic state dumps and continuous event logging.

Conclusion

In this lesson, we explored two fundamental strategies for building fault-tolerant distributed systems. These concepts are the bedrock of the reliable, "always-on" services we use every day.

Key Takeaways:

• Fault tolerance is a system's ability to operate correctly despite component failures.
• Replication provides high availability by maintaining multiple live copies of data or a service. Different replication protocols (like Primary-Backup and Chain Replication) offer different trade-offs in performance (latency, throughput) and complexity.
• Checkpointing involves periodically saving the entire state of a process, enabling fast but potentially lossy recovery.
• Logging records individual operations, providing durable storage of all changes made to a system.
• Combining infrequent checkpoints with continuous logging is a powerful and widely used pattern that balances recovery speed with minimizing data loss.

In our next lesson, we will look at how these fundamental principles are packaged and delivered by cloud providers. We will compare the major cloud computing service models: Infrastructure as a Service (IaaS), Platform as a Service (PaaS), and Software as a Service (SaaS), and see how they offer different levels of fault tolerance and management abstraction.