From Traditional Fault Tolerance to Blockchain. Wenbing Zhao
Чтение книги онлайн.

Читать онлайн книгу From Traditional Fault Tolerance to Blockchain - Wenbing Zhao страница 19

СКАЧАТЬ and logging are the most essential techniques to achieve dependability in distributed systems [7]. By themselves, they provide a form of fault tolerance that is relatively easy to implement and incurs low runtime overhead. Although some information could be lost (if only checkpointing is used) when a fault occurs and the recovery time after a fault is typically larger than that of more sophisticated fault tolerance approaches, it may be sufficient for many applications. Furthermore, they are used in all levels of dependability mechanisms.

      A checkpoint of a distributed system refers to a copy of the system state [7]. If the checkpoint is available after the system fails, it can be used to recover the system to the state when the checkpoint was taken. Checkpointing refers to the action of taking a copy of the system state (periodically) and saving the checkpoint to a stable storage that can survive the faults tolerated.

      Checkpointing and logging provide a form of rollback recovery [7] because they can recover the system to a state prior to the failure. In contrast, there exist other approaches that accomplish roll-forward recovery, that is, a failed process can be recovered to the current state by incorporating process redundancy into the system. However, roll-forward recovery protocols typically incur significantly higher runtime overhead and demand more physical resources.

Schematic illustration of an example distributed system.

      In such a distributed system, a failure could occur at a process. However, it is assumed that when a process fails, it simply stops execution and loses all its volatile state (i.e., the fail-stop model [18] is used). In addition, it is assumed that any two processes can establish a reliable connection (such as a TCP connection) for communication. Even though the network may lose messages, the reliable channel can effectively mask such losses. Naturally, the reliable connection ensures the first-in first-out (FIFO) property between the two endpoints of the reliable connection. This assumption also implies that the network does not partition, i.e., it does not prevent two or more processes in the system from interacting with each other for extended period of time.

      2.1.2 Process State and Global State

      The state of an individual process is defined by its entire address space in an operating system. A generic checkpointing library (such as Condor [23]) normally saves the entire address space as a checkpoint of the process. Of course, not everything in the address space is interesting based on the application semantics. As such, the checkpoint of a process can be potentially made much smaller by exploiting application semantics.

Schematic illustration of consistent and inconsistent global state examples.

      EXAMPLE 2.1

      To understand the problem better, consider the following example. Assume that P0 and P1 represent two bank accounts, A and B respectively. The purpose of m0 is to deposite $100 to account B after P0 has debited account A. P0 takes a checkpoint C0 before the debit operation, and P1 takes a checkpoint C1 after it has received and processed the deposit request (i.e., m0), as illustrated in Figure 2.2(a). If P0 crashes after sending the deposit request (m0), and P1 crashes after taking the checkpoint C1, upon recovery, P1’s state would reflect a deposit of $100 (from account A) while P0’s state would not reflect the corresponding debit operation. Consequently, $100 would appear to have come from nowhere, which obviously is not what had happened. In essence, the global state constructed using the wrong set of checkpoints does not correspond to a state that could have happened since the initial state of the distributed system. Such a global state is referred to as an inconsistent global state.