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

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

СКАЧАТЬ is taken by P1 after it has received m0, therefore, the dependency on P0 is captured by C1. Similarly, the dependency of P2 on P1 is also preserved by the checkpoint C2 taken by P2. Such a global state is an example of consistent global state. Of course, the execution after the checkpoints, such as the sending and receiving of m2 and m3, will be lost upon recovery.

      The scenario described in Figure 2.2(c) is the most subtle one. In this scenario, P0 takes a checkpoint after it has sent message m0 while P1 takes a checkpoint before it receives m0 but after it has sent m1, and P2 takes a checkpoint before it receives m1. This means that the checkpoint C0 reflects the state change resulting from sending m0 whereas C1 does not incorporate the state change caused by the receiving of m0. Consequently, this set of checkpoints cannot be used to recover the system after a failure because m0 and m1 would have been lost. However, the global state reconstructed by using such a set of checkpoints would still be qualified as a consistent global state because it is one such that it could have happened, i.e., messages m0 and m1 are still in transit to their destinations. To accommodate this scenario, an additional type of states, referred to as channel state, is introduced as part of the distributed system state [5].

      To define the channel state properly, it is necessary to provide a more rigorous (and abstract) definition of a distributed system. A distributed system consists of two types of components [5]:

       ◾ A set of N processes. Each process, in turn, consists of a set of states and a set of events. One of the states is the initial state when the process is started. Only an event could trigger the change of the state of a process.

       ◾ A set of channels. Each channel is a uni-directional reliable communication channel between two processes. The state of a channel is the set of messages that are still in transit along the channel (i.e., they have not yet been received by the target process). A TCP connection between two processes can be considered as two channels, one in each direction.

      Using this revised definition, the channel states in the third scenario would consist of the two in-transit messages m0 and m1. If the channel states can be properly recorded in addition to the checkpoints in this scenario, the recovery can be made possible (i.e., m0 will be delivered to P1 and m1 will be delivered to P2 during recovery).

      2.1.3 Piecewise Deterministic Assumption

      Checkpoint-based protocols only ensure to recover the system up to the most recent consistent global state that has been recorded and all executions happened afterwards, if any, are lost. Logging can be used to recover the system to the state right before the failure, provided that all events (that could potentially change the state of the processes) are logged and the log is available upon recovery. This is what is referred to as the piecewise deterministic assumption [21]. According to this assumption, all nondeterministic events can be identified and sufficient information (referred to as a determinant [1]) must be logged for each event. The most obvious example of nondeterministic events is the receiving of a message. Other examples include system calls, timeouts, and the receipt of interrupts. In this chapter, we typically assume that the only nondeterministic events are the receiving of a message. Note that the sending of a message is not a deterministic event, i.e., it is determined by a nondeterministic event or the initial state of the process [7].

      2.1.4 Output Commit

      2.1.5 Stable Storage

      An essential requirement for logging and checkpointing protocols is the availability of stable storage. Stable storage can survive process failures in that upon recovery, the information stored in the stable storage is readily available to the recovering process. As such, all checkpoints and messages logged must be stored in stable storage.

      There are various forms of stable storage. To tolerate only process failures, it is sufficient to use local disks as stable storage. To tolerate disk failures, redundant disks (such as RAID-1 or RAID-5 [14]) could be used as stable storage. Replicated file systems, such as the Google File Systems [9], can be used as more robust stable storage.

      Checkpoint-based protocols do not rely on the piecewise deterministic assumption, hence, they are simpler to implement and less restrictive (because the developers do not have to identify all forms of nondeterministic events and log them properly). However, a tradeoff is that the distributed systems that choose to use checkpoint-based protocols must be willing to tolerate loss of execution unless a checkpoint is taken prior to every event, which is normally not realistic.

      2.2.1 Uncoordinated Checkpointing

      Uncoordinated checkpointing, where each process in the distributed system enjoys full autonomy and can decide when to checkpoints, even though appears to be attractive, is not recommended for two primary reasons.

      EXAMPLE 2.2

Schematic illustration of an example of the domino effect in recovery with uncoordinated checkpointing.

       ◾ The most recent checkpoint СКАЧАТЬ