CN105242979B - It is a kind of that there is the preceding backward recovery fault-tolerance approach to recovery feature - Google Patents

Abstract

The invention discloses a backward recovery fault-tolerant method with forward recovery features. This method uses fault bits to control the sending of messages; if both the sending and receiving processes are faultless, the sending process stores the message and its corresponding logical clock in the message log before sending the message; if the process is in the fault recovery stage, its sending is prohibited message; if the receiving process is faulty, the sending process waits until it recovers before sending a message to this process; thereby achieving the effect of conditional execution of a fault-free process in the system fault recovery phase. When a process fails, under the control of the recovery thread, the replay message and the corresponding logical clock are first obtained from the message log, and then the replay message is reordered according to the logical clock of the message; finally, the sorted message is resent to the faulty process, and the faulty process restarts Receive messages, process messages, so as to realize the replay of messages.

Description

A Fault Tolerant Method for Backward Recovery with Forward Recovery Characteristic

technical field

The invention relates to a fault recovery method of a distributed system based on message reordering message logs.

Background technique

In the research field of backward recovery fault tolerance in distributed systems, according to the type of stored information, rollback recovery protocols can be divided into checkpoint-based rollback recovery protocols and message log-based rollback recovery protocols. Protocols based on message log rollback recovery are subdivided into pessimistic message logs and optimistic message logs.

In the system using pessimistic message log [1], after the process receives the message, it always saves it in the message log first, and then submits it to the application program for processing. This feature ensures that the messages received by the process and their receiving order are completely stored in the message log file, making the recovery of the process easier; but because the message information must be saved to the message log after receiving the message, it seriously affects the performance of the system during normal operation. According to which process saves the message information to the message log, the pessimistic message log protocol is divided into sender-based message log protocol (sender-based)[2][3][4] and receiver-based message log protocol (receiver-based based).

In the receiver-based message log protocol, after a process receives a message, it first stores information such as the receiving order of the message into the message log, and then submits the message to the application program for processing.

In the sender-based message log protocol [2][3][4], the message sending process first saves the message content in the memory buffer before sending a message, and then sends the message to the receiving process. After receiving the message, the receiving process first transmits the receiving sequence of the message to the sending process of the message, and then submits the message to the application process. After the sending process of the message receives the receiving order of the message, the content of the message and the receiving order are uniformly stored in the message log.

In the system using optimistic message log [1], the process submits the message to the application program immediately after receiving the message, and then saves the received message to the message log when the process is idle. This feature enables the system process to have good performance during normal operation; however, when a failure occurs, if there are messages received by the process but not saved in the message log, the receiving order of such messages will inevitably be lost, making the recovery of the process extremely complicated.

The log recovery protocol [5][6] based on message reordering and message number verification uses the message reordering method to better solve the problem of losing the order of message reception caused by process failures in optimistic logs. The sending process under this protocol uses the logical clock to indirectly mark the receiving order of the message when sending the message and saves the message and its logical clock in the local storage of the sending process. After the receiving process receives the message, it first submits the message to the application program for processing, and then saves the message and its receiving order to the message log when the process is idle. When the message receiving process fails, the recovery process first obtains the saved messages and their logical clocks from the message log, and then obtains the messages that have not been saved due to process failure from the local storage of the sending process according to the difference between the number of messages saved by the sending process and the receiving process. Messages and their logical clocks that can be saved to the message log. Messages are then reordered according to their logical clock and replay of messages is realized. When the process under this protocol is running normally, it will immediately submit the message to the application for processing after receiving the message, and only save the message information to the message log when the process is idle. The above characteristics make this recovery protocol still belong to the optimistic message log protocol in essence; under this protocol, the process has good performance when the process is running normally, and its recovery algorithm is relatively simple when a process fails.

The main disadvantage of the log recovery protocol for message reordering and message number verification is that when the program is running normally, the process still needs to save the message to the message log when the process is idle after receiving the message. However, under this protocol, the sending process has saved the content of the message and its logical clock value to the local storage before sending the message, and the message log at the receiving process end is redundant, so the protocol algorithm can be further optimized.

The modified reordering recovery protocol [7] is still based on the basic theory of reordering for algorithm design, but the recovery protocol has been greatly modified, mainly removing the message log at the message receiving process end. In this protocol, the message sending process saves the content of the message and its logical clock to the message log before sending the message. After the message receiving process receives the message, it immediately submits it to the application program for processing, and thereafter no longer saves any message information. Compared with the sender-based message log protocol (sender-based)[2][3][4], the receiving process in the modified reordering recovery protocol does not need to transfer the order of message reception to the sending process after receiving the message, so that The process has good performance during normal execution and ensures that there are no orphan processes in the system during the process failure recovery phase.

The modified reordering recovery protocol [7] completely got rid of the shackles of pessimistic and optimistic protocols, and formed a new fault-tolerant recovery protocol with the advantages of both pessimistic and optimistic protocols. This protocol has the following main features:

1) Before the process sends the message, the content of the message and the logical clock indicating the order of receiving the message are saved to the message log at one time, and then the message is sent to the receiving process. This feature makes the protocol have the characteristics of a pessimistic message log protocol, that is, there is no orphan process in the system at any time.

2) The process does not save any message information after receiving the message, so the process under this protocol has better performance than the process under the optimistic log protocol during normal execution. This feature makes the protocol completely different from the pessimistic and optimistic protocols, and the performance of its system is better than the optimistic protocol in normal execution.

3) When a process fails, the non-faulty process continues to execute conditionally; therefore, in the process recovery phase, the process under the reordering recovery protocol has better recovery performance than the process under the pessimistic log protocol.

4) Any process can independently save its process state (checkpoint) at any time.

The above characteristics of the modified reordering recovery protocol make its performance indicators better than all existing message log protocols. However, the protocol only provides the conditions for the running of a fault-free process (conditions such as restricting a faulty process to send a message to another faulty process), but does not provide a specific implementation method for the conditional execution of a fault-free process, thus limiting the application of the protocol .

Purpose of the present invention and the effect that can be achieved:

Improve the reordering recovery protocol, and propose a backward recovery fault-tolerant method based on reordering theory that is easy to implement in programmer language. This method has the basic features similar to the modified reordering recovery protocol [7], and has the following unique features: 1. The theory and method of conditional operation under the fault state of the fault-free process are further improved; 2. The process fault flag is added , and control the conditional operation of the non-fault process in the system fault recovery phase through the fault bit.

Fundamentals of message reordering

Under the PWD assumption, the message reception event of a process is random, that is, the message reception is uncertain in time and order, but the message sending event is indeed a definite event.

As shown in Figure 1, it is assumed that the distributed system consists of processes p, q and r. Among them, δ _p,0 , δ _{q,0 and} δ _{r,0 represent} the initial state intervals of _p , _q and r respectively; State interval; t _pq and t _rq represent the communication channel delays between processes p and q and between q and r, respectively. Under the optimistic message logging protocol, if process q fails at " _x " before saving the necessary information for messages m1 and _m2 to the log file. After process q fails, processes p, q, and r must be restarted to resend and receive m ₁ and m ₂ . Obviously, the order of process q's replay (replay) messages should be m ₁ , m ₂ , but because the channel delay t _pq and t _rq are not fixed constants, if t _pq >t _rq , the order of process q receiving messages may become m ₂ , m ₁ . The example in Figure 1 shows that although the optimistic message log protocol requires that the faulty process accurately send and receive messages that are not saved to the log file when it is replayed, in some cases (for example, the process channel delay changes, the process in the system is restarted) The time is uneven, etc.) The order in which the actual process sends and receives messages may be inconsistent with that before the failure. However, the final result of the system should be consistent every time it is repeated, which means that under the assumption of PWD, the execution result of the system has nothing to do with the order in which certain messages are received.

Always happens before relationship (always happens before) relationship:

Assuming that the channel of the process is a FIFO reliable channel, e _i and e _j represent the sending or receiving events of messages m _i and m _j respectively. If the occurrence of ei is always prior to the occurrence of e _j in any execution of the system and has nothing to do with factors such as channel delay and CPU speed, then it is said that e _i always occurs prior to e _j , which is recorded as:

In Fig. 2, R(m ₁ ), R(m ₂ ), R(m ₃ ) and R(m ₄ ) denote the reception events of messages m ₁ , m ₂ , m ₃ and m ₄ respectively, and S(m ₁ ), S(m ₂ ), S(m ₃ ) and S(m ₄ ) denote sending events of messages m ₁ , m ₂ , m ₃ and m ₄ , respectively. Under the PWD assumption, since q must send m ₂ after receiving m ₁ , r must send m ₃ after receiving m ₂ , namely therefore R(m ₁ ) always precedes R(m ₃ ), indicating that R(m ₃ ) is logically dependent on R(m ₁ ), and the relationship between R(m ₃ ) and R(m ₁ ) is a Logical dependencies are independent of other factors of the system. Since the receive event of a message is a deterministic event, the Under the assumption of FIFO channels,

In Fig. 2, since the transmissions of m ₃ and m ₄ arrive at process q through different channel delays, R(m ₃ ) may not always occur prior to R(m ₄ ). If the occurrence of event e _i is not necessarily always prior to the occurrence of event e _j , but is related to factors such as channel delay and cpu speed, it is said that e _i does not always occur before ej, denoted as In Figure 2, Therefore, the actual message receiving sequence of process q is m1, m3, m4 or m1, m4, m3.

Message Equivalent Sequence Theorem:

Suppose S is a message sequence of process p, and S' is a new sequence formed by rearranging the messages in S. The elements in S' satisfy: 1. All messages that exist in S still exist in S'; 2. If the receiving events of some messages have a relationship that always occurs first in S, then this relationship is in S' is still maintained. Under the assumption of process channel FIFO and reliable channel, S and S' are equivalent sequences during the replay process of process p (the calculations completed by the processes after receiving the two sequences respectively are the same).

Proof: Under the assumption of the theorem, although some messages in S are reordered in S', the always-before relationship between these messages remains unchanged in S'; therefore, the reception of messages in S' The order is the actual order in which the process might occur in a replay. If S and S' are not equivalent sequences during the replay process of process p, then the execution of the message receiving event in S in process p is not equivalent to the execution of the message receiving event in S' in process p, that is, the same process Each execution of is inconsistent, which contradicts the consistency property of process execution.

For example, in Figure 2, m1, m3 and m4 are equivalent sequences to m1, m4 and m3, that is, the calculations completed by the process p replaying m1, m3 and m4 and replaying m1, m4 and m3 are the same .

Improved Logic Clock:

The improved logical clock LCp of process p is an integer variable used to count the send event and receive event of the message. LCp satisfies:

1. Its initial value is zero;

2. Every time a message is sent, LCp is incremented by one;

3. Every time a message from process q is received, LCp←max(LCp+1,LCq+1), where LCp and LCq represent process p respectively

and the logic clock of q, max means to take the maximum value among LCp+1 and LCq+1.

As shown in FIG. 3 , LCp=1 after p sends m ₁ , and LCp=2 after sending m ₄ . q After receiving and storing m ₁ , LCq=2, after sending m ₂ , LCq=3, after receiving and storing m ₃ , LCq=6, after receiving and storing m ₄ , LCq=7.

For ease of expression, the improved logical clock is abbreviated as logical clock.

Message reordering logic clock theorem:

If the segmentation is determined assuming that PWD holds and Then LCp(S(mi))<LCq(S(mj)). Among them, R(mi) and R(mj) represent the receiving events of messages mi and mj of process k respectively. LCp(S(mi)) represents the logical clock after process p sends message mi, and LCq(S(mj)) represents The logical clock after process q sends message mj.

Proof: due to R(mj) logic depends on R(mi), S(mj) is a definite event, so Otherwise, assume that R(mi) does not always happen-before S(mj), which means that R(mi) and S(mj) can happen in any order, or that R(mi) happens-before S(mj) , or S(mj) happens-before R(mi). If S(mj) precedes R(mi), since S(mj) always precedes R(mj), S(mj) can only indirectly precede R(mi). As shown in Figure 4, there must be at least one message mk located between mj and mi, so that S(mj)→S(mk), S(mk)→R(mk), R(mk)→S(mi), S(mi)→R(mi), where “→” indicates the occurrence-before relationship. In this case, mj and mi must arrive at process k through different transmission channels, and the transmission of mj and mi may have different channel delays, so R(mi) cannot always happen before R(mj), This contradicts the assumption of the theorem, so According to the definition of improved logic clock, LCp(R(mi)) must be smaller than LCq(S(mj)), that is, LCp(R(mi)<LCq(S(mj)). And because So LCp(S(mi))<LCp(R(mi)). From this, LCp(S(mi))<LCp(R(mi))<LCq(S(mj)), LCp(S(mi))<LCq(S(mj)) can be obtained.

For example, in Figure 3, LCp(S(m1))=1, LCr(S(m3))=5, LCp(S(m1))<LCr(S(m3)).

The above theorem shows that the order of receiving messages in the message receiving sequence of any process can be determined by the logical clock of the message sending process. If the sending process of the message saves the logical clock related to the message and the content of the message to the stable storage or the message log while sending the message; after the receiving process of the message fails, the recovery process can save the pre-saved message according to its logic The clocks are reordered and thus the desired sequence of replayed messages is obtained. For example, in Fig. 3, p process saves <m1, LCp=1> after sending m1, saves <m4, LCp=2> after p process sends m4; r saves after sending m3 <m3, LCr=5>; if Process p fails at "X", process p replays the sequence of messages according to the logical clocks in the tuples <m1,LCp=1>, <m3,LCr=5> and <m4,LCp=2> for m1, m4 and m3. In Fig. 3, although the message sequence received by process q in the fault recovery phase is: m1, m4 and m3, which is different from the original message receiving sequence m1, m3 and m4; but the message sequence m1, m4 and m3 are indeed system runtime One of the actual message reception sequences for process q. Since the functions realized by a system (except the random system) are deterministic, the calculations completed by q in Fig. 3 after receiving the above two different message sequences are the same.

Conditions for continuation of process execution without failure during the recovery phase

Before the introduction of reordering theory, in the process recovery phase, the fault-free process under any protocol either fell back to eliminate the orphan process existing in the system (optimistic message log protocol), or stopped in its current state to wait for the recovery of the faulty process (pessimistic message log).

Example In Fig. 5, let p, q and r denote processes in the system respectively; C _{x, y} denote the yth checkpoint of process x, x=p, q, r; y=0, 1; process q and r fails at 'x' respectively. Under the pessimistic logging protocol, the maximum recoverable state of the system [1] is shown by the dotted line in the figure. In the recovery phase of the system, process q needs to retreat to checkpoint C _q,0 and replay messages m2, m4 and m6, process r needs to retreat to checkpoint C _r,1 and replay messages m3 and m5, process p stops at its current The state waits for other processes to recover from their failed state.

As another example in Fig. 6, let q, p and r represent processes in the system respectively; C _{x, y} represent the yth checkpoint of process x, x=p, q, r; y=0, 1; process r Failure at 'x' before receiving m5 but saving m5 to message log. Under the optimistic logging protocol, the maximum recovery state of the system is shown by the dotted line in the figure. In the system recovery phase, the process r must fall back to the checkpoint C _r,1 . Since the states of the processes q and p depend on or indirectly depend on the receiving event of the message m5, in order to avoid the occurrence of orphan processes, the processes q and p must respectively Fall back to its checkpoints C _q,0 and C _p,1 .

The execution of a process in a traditional message log protocol can be divided into two phases [7], the normal execution phase and the failure recovery phase. In the normal execution stage, after the process receives the message, it either saves the message information to the message log and then submits it to the application program for processing, or directly submits it to the application program for processing. In the fault recovery phase, the faulty process can only receive the replay message [7] (replay message) sent by the faulty recovery process, otherwise the faulty process may receive the same message repeatedly; for the messages sent by the faulty process, because such messages have been Other processes receive and process, so such messages must be shielded, or discarded after being received by the receiving process, or the communication system prohibits the transfer of such messages [7].

The maximum recoverable state of a system refers to the state that the system can recover to when a process failure occurs, more precisely, it refers to the maximum globally consistent state that the system can achieve during the process recovery phase.

In the traditional pessimistic message log protocol, because the system must eventually recover to a maximum globally consistent state during the recovery phase, the fault-free process must be suspended at its maximum recovery state during the recovery phase to ensure that the system recovers from a consistent state after the recovery phase. The global state of the execution continues. Otherwise, if the non-faulty process continues to execute during the fault recovery phase, especially after the process sends and receives new messages, the state it is in may be inconsistent with the state after the faulty process is recovered. For example, in Figure 5, assuming that processes q and r fail, if process p continues to execute and sends messages to process q or r, the sending and receiving of such messages will inevitably change the message receiving sequence of process q or r, This leaves the system in a wrong global state.

However, under certain conditions, the continuation of the fault-free process in the fault recovery phase does not affect the recovery of the faulty process and the final achievement of the system's consistent global state.

Example In Fig. 7, let p, q, r and s represent processes in the system respectively; C _{x, y} represents the yth checkpoint of process x, x=p, q, r, s; y=0, 1 ; Processes q and r each failed at 'x'. Under the pessimistic log protocol, after the process q and r fails, the process p and s stop executing to wait for the recovery of the failed process. The maximum recoverable state of the system is shown in the figure maximum recoverable state. Assume that in the recovery phase of process q and r, if process p continues to execute and sends message m8 to process s, and process q and r recovers to the maximum recoverable state and no longer sends any messages, then the system reaches a The new global state, as shown in Figure New maximum recoverable state. Since no orphan processes are included in the New maximum recoverable state state, this state is a globally consistent state. However, if the faulty process is restored to the maximum recoverable state and then sends messages to other processes, the message sent by the continued execution of the non-faulty process may produce messages sent by the faulty process and messages sent by the faulty process after recovery Inconsistencies in the order of receipt. In Figure 8, in the fault recovery phase, if process p is suspended and waits for the faulty process to recover, process s will receive message m9 and then m8 after system recovery; if process p continues to execute and send m8, process r will send message m8 after the faulty process recovers. m9, the process s first receives m8 and then m9 (as shown by the dotted line in the figure). Obviously, the order in which process s receives messages m8 and m9 may be inconsistent under the above circumstances; however, this inconsistency is an objective existence in the actual execution of the system. In fact, messages m8 and m9 are transmitted through different process channels. When the delay of the process channel changes, both messages are possible for process s. As a deterministic system, the calculations completed by the system cannot be changed due to changes in system parameters, so after receiving messages in two different orders, the calculations completed by the process s and the entire system are the same.

In summary, the following conclusions are drawn:

Assume that the distributed system is a loosely coupled system, that is, there is no shared memory between processes, and the information of messages sent by any process during normal operation, including message content and message receiving order, have been saved to stable storage.

Faultless process conditional execution theorem:

In the process failure recovery phase, assume that no faulty process continues to execute; if the following conditions are met, the system is in a consistent global state after the recovery phase.

1. Disable the sending of messages sent by the faulty process.

2. Forbid other processes to send messages to it during the recovery phase of the faulty process, that is, the faulty process only receives replay messages sent by the faulty recovery process.

3. The non-faulty process continues to execute and send and receive messages, but when sending a message to the faulty process, it must stop waiting until the faulty process is recovered.

prove:

According to the conditions of the problem, since the fault-free process and the faulty process are completely isolated during the process fault recovery phase, the messages sent by the fault-free process must be transmitted between the fault-free processes, and the number of messages sent by the fault-free process must be greater than or equal to The number of such messages received [7] (there may be interim messages), so it is impossible to have orphan messages and orphan processes at any moment. Therefore, if the fault-free process is conditionally executed in the fault recovery phase, the system must be in a globally consistent state after the faulty process is recovered.

According to the above theorem, under the conditions set by the theorem, the non-faulty process continues to run in the fault recovery stage of other processes, and its final calculation is the same as the calculation completed by the system without faults.

The present invention designs a fault recovery protocol according to the theorem's problem setting conditions. This protocol has some characteristics of forward recovery. When some processes fail, only the faulty process is recovered. No faulty processes are conditionally executed, and the system does not stop until Complete the required calculations.

Contents of the invention

The purpose of the present invention is to solve the problem of low system operation efficiency caused by the process of normal execution caused by the message receiving process saving the message receiving order in the pessimistic message log and the problem of low system operation efficiency caused by the non-faulty process stopping and waiting in the fault recovery stage, so as to improve the normal execution of the process phase and failure recovery phase for the purpose of system performance. The invention uses logical clocks to indirectly mark the receiving order of messages, and the process saves the message content and corresponding logical clocks to the message log before sending messages. When the message receiving process fails, the recovery process first obtains all the messages and corresponding logical clocks received since the receiving process saved the checkpoint from the message log, and reorders the messages according to the corresponding logical clocks of the messages, and finally sorts the sorted messages Resend to the failed process. The recovery fault-tolerant protocol of the present invention allows multiple processes to fail; in the fault recovery phase, no faulty process is executed conditionally, and the faulty process is recovered independently, so that the protocol has the feature of forward recovery.

To achieve the above object, the present invention adopts the following technical solutions:

The distributed system consists of ordinary process Pi, i=1, 2...n, state control process Control i, i=1, 2...n, Recover-manager fault recovery management process and message log system, as shown in Figure 9.

The system defines the following data structures respectively:

1. Vector Ti, Ti=[T _i1 , T _i1 , . . . T _in ], where T _ik represents the number of messages received by process Pi and sent by Pk. In order to facilitate the access to the Ti vector under faulty and non-faulty conditions, the Control-i process and the ordinary process Pi define and use the same Ti vector, which is stored in the shared memory space of the two processes (or the local hard disk). For ordinary processes, the Ti vector is write-only; for Control-i processes, the Ti vector is read-only.

2. _{Fault vector} F, _{F =} [F ₁ , F ₂ , . Similar to the above reasons, the Control-i process and the common process Pi use the same F vector and save it in the shared memory space (or the local hard disk) of the Control-i process and the common process Pi. For normal processes, the F vector is read-only; for Control-i processes, the F vector is write-only.

3. The improved logical clock, LCi (abbreviated as the logical clock variable, whose definition is as mentioned above), this variable is stored in the memory space of the common process Pi.

The working principle of each component of the system:

1. The Recover-manager process is responsible for fault detection and fault recovery of common processes in the system, and is mainly composed of the main thread and the fault recovery thread. The main thread periodically sends heartbeat information to the process Pi, i=1,...n, through a reliable channel (eg tcp channel), and receives Pi's response message.

If the main thread does not receive the response message from the Pi process, it means that Pi has failed (assuming that the cpu of the machine where Pi is located satisfies the fail-stop assumption [8]), then kill the Pi process through the state control process Control-i, and start from the Pi process. A permanent checkpoint restarts the Pi. Then restore the Pi through the fault recovery thread of Recover-manager. The fault recovery thread first obtains the replay messages from the message log Mlog, reorders the replay messages, and finally sends the sorted messages to the Pi process.

If the main thread receives the response message from Pi and the scheduled time has come, it sends a control message to the state control process Control-i, and the Control-i process saves the temporary checkpoint of Pi after receiving the control message and persists it (saved as permanent checkpoint).

2. The state control process Control-i, i=1,...n, is deployed in the same machine as the process Pi, and is responsible for controlling the process state of Pi, including: saving the current state of Pi as a temporary checkpoint, and saving the current state of Pi as a temporary checkpoint. Transition from temporary checkpoint to permanent checkpoint, kill Pi process, restart Pi process from permanent checkpoint.

3. The ordinary process Pi is responsible for the transmission of application messages in the system, and submits the application messages to the application programs of the system.

4. In order to reduce the bottleneck of system communication, the log files in the message log system adopt a distributed deployment method, that is, one system deploys multiple message log files Mlog; each Mlog file is responsible for the storage of message information sent by different processes. Each Mlog consists of several records, and is a sequential file that saves the message information sent by the process. Each record is a four-tuple: <i, j, LCi, m>, where i and j represent the process IDs of the sending and receiving processes respectively, LCi represents the logical clock after the process Pi sends message m, and m represents the content of the message . Each log file is maintained by a daemon process, and multiple log daemons jointly complete operations such as accessing message information in Mlog and calculating U _ij . U _ij is a variable indicating the number of messages sent by the Pi process and received by the Pj process. The initial value of U _ij is zero; every time the daemon process receives a message <i, j, LCi, m>, the value of U _ij is increased by one. All the daemon processes of the log system maintain a total of (n-1)×(n-1) U _ij variables, where i=1,2...n,j=1,2...n, i≠j,n means the system The number of common processes in . All U _ij variables constitute a system U matrix [7], and the U matrix records the number of messages sent by any process in the system to other processes.

When the system is running normally, the message transmission between processes Pi and Pj is shown in Figure 10. Before process Pi sends message m, it first stores <i, j, LCi, m> into Mlog through the log daemon, then Pi sends message <i, j, LCi, m> to receiving process Pj, and Pj submits it immediately after receiving m Give the application APP processing.

When a process Pi fails, as shown in Figure 11, the recovery process of Pi is as follows.

1. Recover-manager sends Pi failure message (Fi=1) to Control-i process; Control-i process kills Pi after receiving the message and restarts Pi from Pi's permanent checkpoint.

2. The Control-i process sends the Ti vector (as described above) to the Recover-manager. Since the Ti vector is allocated in the shared memory space of the Control-i process and the ordinary process Pi, after Pi restarts from the permanent checkpoint, the Ti vector is restored to the value before saving the checkpoint, which is the value of the Pi process before saving the permanent checkpoint The number of messages received, sent by other processes.

3. The Recover-manager access log daemon obtains the vector {U _1i , U _2i ... U _ni }. Calculate the number of messages U _ki -T _ik sent by the Pk process (k=1,2...n,k≠i) to the Pi process, and obtain U _ki -T _ik from Mlog through the corresponding log daemon process in order from back to front Pk are sent to Pi process messages (replay messages), k=1, 2,...n, k≠i.

4. Reorder all the replay messages according to their logical clock LCi, and send the sorted messages to the Pi process in turn.

Detailed processing flow:

A backward recovery fault-tolerant method with forward recovery features, its steps are:

The normal process Pi message receiving thread and the running flow of sending and receiving functions are shown in Figure 12.

The normal process Pi receiving thread operation flow is as follows:

1. For k is an integer variable, k=1, 2...n, initialize Tik and LCi to 0, Tik indicates the number of messages received by process Pk by process Pi, and LCi indicates the logical clock variable of process Pi.

2. If a message is received from Pj, go to 3; otherwise, go to 4.

3. Call the ReadM(j,i,LCj,m) function to read the message from the system message receiving buffer, where j and i represent the sending and receiving process of the message respectively, and LCj represents the logical clock corresponding to the message m.

4. Submit the message read in step 3 to the application program for processing, and then turn to step 5.

5. If the heartbeat message sent by the main thread of Recover-manager is received, go to 6; otherwise, go to 2.

6. Send a response message to the main thread of Recover-manager, and then go to 2.

Assuming that the computer in the system satisfies the fail-stop failure downtime model, because Pi fails, it is impossible for Pi to receive the heartbeat message sent by the main thread of Recover-manager, let alone send a reply message to the Recover process, so the execution of step 6 means that Pi The process is not faulted. The main thread of Recover-manager can judge whether Pi is in a normal operating state according to whether it receives the response from Pi.

The operation flow of the common process Pi sending function SendM(i,j,LCi,m) is as follows:

1. If Fi=0, it indicates that the message sending process Pi has no fault, then go to 2; otherwise, it shows that Fi=1, Pi has a fault, and go to 4.

2. If Fj=0, it indicates that the message receiving process Pj is not faulty, and then go to 3; otherwise, Fj=1, it shows that Pj has a fault, and then go to 2, and wait for Pj to recover from the faulty state.

3. When both the sending and receiving processes have no faults, add one to the logical clock of the sending process: LCi←LCi+1; add message information <i, j, LCi, m> to the end of the message log file. Among them, i and j represent the sending and receiving process respectively, LCi represents the logic clock variable of the Pi process, and m represents the load of the message (payload). Go to 5.

4. Add one to the logical clock of the sending process: LCi←LCi+1; end the message sending process.

5. Send the application message AM<i,j,LCi,m> to the receiving process Pj, and end the message sending process.

Step 4 corresponds to the failure of the Pi process. When Pi fails, Pi does not send the message AM<i,j,LCi,m>, but only updates the LCi variable.

In order to ensure that the process does not send any messages in the fault state, the fault flag bits Fi and Fj are used in the sending function to indicate the fault state of the sending and receiving process. If the fault bit is 1, it means that the process is faulty, otherwise it means that the process is not faulty. In order to realize the above fault identification mechanism, each common process Pk, k=1, 2,...n, maintains a fault vector F, F={F1, F2,...Fn}. The fault vector F used by the process Pk is defined in the shared memory of the Control k process and the ordinary thread Pk, and is maintained and updated by the Control k process. When a process fails, Control k sets the corresponding bit in the fault vector to 1, and when a certain process recovers from the fault, Control k sets the corresponding bit in the fault vector to 0.

The operation flow of the ordinary process Pi receiving function ReadM(j,i,LCj,m) is as follows:

1. Receive application message AM<j,i,LCj,m> from process Pj.

2. Add one to the Tij variable: Tij←Tij+1; Tij represents the number of messages received by the Pi process from the Pj process.

3. Add one to the LCi variable: LCi←LCi+1; LCi represents the logic clock of Pi.

4. If LCi is greater than or equal to AM.LCj+1, turn to end; otherwise, turn to 5. AM.LCj represents the component LCj in the quaternion <j,i,LCj,m>, that is, the logical clock of the sending process Pj.

5. LCi←AM.LCj+1, the steering is over.

The above steps 3, 4 and 5 are actually calculating the logical clock LCi of Pi after receiving the message, that is, adding one to the larger of the logical clocks of Pi and Pj as the logical clock LCi of Pi.

Figure 13 shows the running process of the main thread, message receiving thread and fault recovery thread Recover(k) of the Recover-manager process.

The main thread operation flow is as follows:

1. Initialize memory variables, Fi←0, i=1, 2...n, num←0. Wherein, Fi is a fault flag, which is used to mark the fault state of the process Pi, Fi=0 indicates that Pi has no fault, and Fi=1 indicates that Pi has a fault; num is a loop control variable.

2. If num is greater than COUNT, transfer to 3, otherwise transfer to 5.

COUNT is a constant, which can be set according to the time interval for saving temporary checkpoints. The time interval for saving checkpoints is: COUNT×DELAY seconds, for example, if COUNT=60, DELAY=2, save a temporary checkpoint every 120 seconds.

3. If Fi=0, indicating that Pi is not faulty, then send a message to notify the Control-i process to save the Pi temporary checkpoint, Newck[i]←1. Newck[i] is a flag bit, and Newck[i]=1 indicates that Pi has a temporary checkpoint.

4. num←0, reassign 0 to the num variable.

5. num←num+1, the value of the num variable is increased by one; the delay is DELAY seconds, and DELAY is a constant.

6. k←0, k is assigned 0, and k is a variable.

7. If k is greater than n, transfer to 2, otherwise transfer to 8; n represents the number of all common processes Pi in the system.

8. k←k+1, the value of variable k is incremented by one.

9. If Fk=0, it means that the Pk process is not faulty, and then go to 10; otherwise, Fk=1, it means that Pk is faulty and has been restored, and then go to 7.

10. Send a heartbeat message to Pk through a reliable channel.

11. If the response message of the Pk process to the heartbeat message is received, it means that Pk has no failure, and then proceed to 13; otherwise, the response message of the Pk process to the heartbeat message is not received, indicating that there is a fault in Pk, and then proceed to 12.

12. Send a message to notify Control-k to delete the temporary checkpoint; Newck[k]←0; start the thread Recover(k) to restore Pk; Fk is assigned a value of 1, so as to control the heartbeat message no longer sent to Pk in the next cycle, and turn to 7 .

13. If Newck[k]=1, it means that there is a Pk temporary checkpoint, and go to 14; otherwise, it means that there is no Pk temporary checkpoint, and go to 7.

14. Send a message to notify the Control-k process to convert the temporary checkpoint of the process Pk into a permanent checkpoint; Newck[k]←0, Newck[k] is set to zero, and transfers to 7.

The fault recovery Recover(k) thread operation process is as follows:

1. Send Fk=1 message to Control-i,i=1,2,...n through a reliable channel to notify other processes that Pk process has failed.

2. If the Tk vector sent by Control-k is received, go to 3; otherwise, go to 2 and wait to receive the Tk vector.

Note: After the Recover (k) thread sends the message of Fi=1 through step 1, the process Control-k process corresponding to the faulty process Pk will kill Pk after receiving it and restart Pk from its permanent checkpoint, and then send the Tk vector to Recover (k) Threads.

3. Save the received Tk vector to memory.

4. Access daemon to get Uik.

5. The access log daemon process obtains Uik-Tki messages sent from Pi to Pk from the log file in the order from back to front.

6. Sort all the messages according to the value of the LCk variable from small to large.

7. Send the sorted message to Pk, that is, replay the message.

8. Send a message of Fk=0 to Control-i,i=1,2,...n through a reliable channel; it indicates that the Pk process has recovered from the failure. Fk←0, Fk is set to zero, and the steering is over.

Figure 14 shows the running process of the Control-i process.

The operation process of Contril-i is as follows:

1. If the message of saving the temporary checkpoint is received, go to 2, otherwise go to 3.

2. Save the new temporary checkpoint and delete the old temporary checkpoint.

3. If the message of saving the permanent checkpoint is received, go to 4, otherwise go to 5.

4. Delete the original permanent checkpoint and convert the Pi temporary checkpoint into a permanent checkpoint.

5. If the message of Fk=0 is not received, go to 7; otherwise, go to 6.

6. Fk←0.

Fk is set to zero, indicating that the Pk process has resumed.

7. If the message of Fk=1 is not received, go to 1; otherwise, go to 8.

8. Fk←1. Fk is set to 1, indicating that the Pk process fails.

9. If i is not equal to k, it means that the Pi process has not failed, and turn to 1; otherwise, i is equal to k, indicating that the Pi process has failed, and turn to 10.

10. Kill the faulty process Pi; then restart the Pi from the Pi permanent checkpoint.

11. Send the Ti vector to Recover(k), go to 1.

Note: Thereafter, Pk, ie Pi(i=k), will be recovered by the Recover(k) thread.

Proof of the correctness of recovery thread Recover(i) recovery algorithm:

Firstly, explain the recoverability principle of the process state interval: a process state interval is recoverable, if any failure occurs in the process in the future, the re-execution of the process can always reach this interval.

Theorem 1 assumes that the non-faulty process is suspended when the faulty process is restored, and if one or more processes fail, the faulty process will be restored to the state before the fault under the recovery process of Recovery (i).

Proof: Since a process saves the message information (determinant) in the message log file before sending a message, the process is recoverable according to the above-mentioned process state interval recoverability principle. The following two cases are respectively proved in detail.

1. Assume that only one process Pk fails, k=1, 2...n. After the failure is detected, the failed process Pk is killed and started from its permanent checkpoint. After the recovery thread Reconver(k) obtains the Tk variable of the Pk process through the Contril-k process and the Uik variable through the log daemon process, all replay messages can be obtained through the log daemon process according to the difference Uik-Tki. These messages are sorted according to their logical clocks, and sent to Pk in turn, and the Pk process receives and processes the messages again, and eventually it will reach the state interval before the process fails, that is, the Pk process is recoverable.

2. If multiple processes fail, since each faulty process is recovered individually by the recovery thread, and each faulty process is prohibited from sending messages, when multiple processes fail, these faulty processes can be recovered separately by the recovery thread.

Theorem 1 proves that when one or more processes fail, each process can be restored to the traditional maximum recoverable state, but the above recovery protocol allows the non-faulty process to continue execution conditionally during the fault recovery, and the faulty process is recovered The consistency of the final state with the state of the non-faulty process will ultimately determine the correctness of the above recovery method.

Theorem 2 Under the action of the recovery thread, if the non-faulty process continues to execute conditionally, then the global state of the system after all the faulty processes are restored is a consistent global state.

Proof: As described in the algorithm for recovering threads, if one or more processes fail, if the non-faulty process sends a message to the faulty process, it will stop waiting for the faulty process to recover, otherwise continue to execute.

Case 1. If a non-faulty process sends a message to a non-faulty process, after the faulty process recovers, the number of messages sent by the non-faulty process to the faulty process must not change, and there cannot be orphan messages among these processes.

Case 2. If the non-faulty process stops at the event of sending a message to the faulty process, after the faulty process recovers, the number of messages sent by the non-faulty process to the faulty process must not change, and there cannot be orphan messages among these processes.

Combining the two cases, according to the meaning of global state consistency, the global state of the system after the recovery of the faulty process is a consistent global state.

However, when all the faulty processes are recovered, there may be a situation that multiple surviving faulty processes send messages to a recovered faulty process. In fact, since multiple sending processes send messages to the recovered process through different channels, there is no always-before relationship between the receiving events of these messages for the receiving process [7], and these events can be arranged according to any Execute in sequence.

Compared with existing message log recovery methods:

Different message log recovery protocols have different performance evaluation indicators. We use the following six indicators to evaluate the performance of a recovery protocol:

1. N.ckpts, all processes save the number of checkpoints.

2. INFOR.add, the amount of additional information carried by an application message.

3. DIS.rol, process rollback distance.

4. N.roll, the number of processes that need to be rolled back during recovery after k processes fail.

5. Rollback, whether the fault-free process is rolled back.

6. type, protocol type.

In the backward recovery fault-tolerant protocol of the forward recovery feature (referred to as the forward feature recovery protocol), since the temporary checkpoint is deleted after the next heartbeat message, each process only needs to save one permanent checkpoint. The data carried by each application message are i, j and LCj; so INFOR.add is 3. After a process fails, the faulty process only needs to roll back to its permanent checkpoint, so the process rollback distance DIS.rol is 1. When k processes fail, no faulty processes need to roll back, only k processes need to roll back, so N.roll is k. Because the process saves the message information before sending the message, there is no orphan process in the system at any time, so this protocol has the advantage of a simple pessimistic protocol recovery algorithm; and because the message receiving process does not save any information to the message log after receiving the message, so the protocol Compared with the optimistic protocol, it has better system uptime performance. Same as the existing protocol [7], in the fault recovery phase, the fault-free process does not roll back or stop waiting, but continues to execute. This feature is similar to the forward recovery algorithm, which makes the process in the system have higher operating efficiency.

In the message log recovery protocol based on message number checksum and message reordering (MNCMR)[5][6], each process only needs to save a checkpoint asynchronously, so N.ckpts is equal to n. The data carried by each application message is j and LCj, so INFOR.add is 2. When one or more processes fail, only the failed process rolls back to its checkpoint, DIS.ro is 1. The number of processes N.roll to be rolled back during recovery is equal to the total number of failed processes.

Compared with the backward recovery fault-tolerant protocol with forward recovery characteristics, the MNCMR protocol needs to save the message information to the local storage before the process sends the message, and also needs to save the message information to the message log after the process receives the message, which will inevitably lead to information loss. Repeated storage; the backward recovery fault-tolerant protocol with forward recovery feature only saves the message information before the message is sent, which not only saves storage space but also improves the performance of the system during normal execution.

Since the 1980s, a large number of message log recovery protocols have been published in domestic and foreign journals, and several typical protocols are selected below for comparison with the MNCMR protocol. Sistla and Welch [1] proposed two optimistic log recovery protocols based on messages. In one protocol, the sent message carries the transitive dependency vector (represented by Prasad.1), and the application message sent by the other protocol only carries the sending process Current state interval value (in Prasad.2 for this protocol). In the Prasad.1 protocol, the amount of additional information required for each application message is o(n), and for each fault, o(n2) system messages need to be exchanged. In the Prasad.2 protocol, the amount of additional information required for each application message is o(1), and for each fault, o(n3) system messages need to be exchanged. In the optimistic message logging protocol of Strom and Yemini [2], each application message sent carries a transitive dependency vector, which has n components, and n is the number of processes in the system. Each process needs to periodically broadcast this transitive dependency vector or attach it to the message it sends when the process executes without failure.

Table 1 shows the comparison results between the protocol of the present invention and the protocol mentioned above.

Table 1

Compared with other non-message log recovery protocols (such as coordinated checkpoint recovery protocols), the main disadvantage of backward recovery fault-tolerant protocols with forward recovery features is that the protocol needs to intervene in the sending and receiving of ordinary process messages, and the algorithm is not transparent. Compared with other message log protocols, forward signature recovery protocol has both the advantages of pessimistic and optimistic protocols, while abandoning their disadvantages. The results of the comparison are shown in Table 2.

Table 2

Main contribution of the present invention:

Precisely control the sending and receiving of process application messages through the fault flag bit, and realize the conditional continuation of the fault-free process in the process fault recovery stage, making the system have forward recovery characteristics, and making the message log recovery protocol algorithm reach the current level The most ideal realm so far.

Description of drawings:

Fig. 1 is an example diagram illustrating the randomness of the message receiving sequence; Fig. 2 is an example diagram illustrating the relationship between message sending and receiving events that always occurs first; Fig. 3 is an example diagram calculating its value according to the definition of a logical clock; Fig. 4 is an explanatory diagram illustrating that the message sending event S(mj) indirectly precedes the message receiving event R(mi); Figure 5 is an example of process rollback when a failure occurs under the pessimistic log protocol; Figure 6 is a failure under the optimistic log protocol Figure 7 is an example diagram of conditional execution of no faulty process and no longer sending messages after the faulty process is restored; Figure 8 is an example diagram of conditional execution of no faulty process and sending of messages after the faulty process is restored; Fig. 9 is a technical solution diagram of the present invention; Fig. 10 is an explanatory diagram of process sending and receiving messages when the system is in normal operation; Fig. 11 is an explanatory diagram of faulty process recovery process; Fig. 12 is a flow chart of ordinary process operation; Fig. 13 is recovery management Process flow chart; FIG. 14 is a flow chart of the state control process Control-i.

[1]Elnozahy E N, Alvisi L, Wang Yimin, et al. "A Survey of Rollback recovery Protocols in Message passing Systems," ACM Computing Surveys, 2002, 34(3): 375-408.

[2] A. Bouteiller, F. Cappello, T. Hérault, G. Krawezik, P. Lemarinier and F. Magniette. MPICH-V2: "a Fault Tolerant MPI for Volatile Nodes based on Pessimistic Sender Based Message Logging," In Proc.of the 15th International Conference on High Performance Networking and Computing (SC2003), November 2003.

[3] D.B.Johnson and W.Zwaenpoel. "Sender-Based Message Logging," InDigest of Papers: 17th International Symposium on Fault-Tolerant Computing, pp.14-19, 1987.

[4]J.Xu,R.B.Netzer and M.Mackey.Sender-based message logging forreducing rollback propagation.In Proc.of the 7th International Symposium on Parallel and Distributed Processing,pp.602-609,1995.

[5] Gao Shengfa, Cai Jing, Feng Zhen. "Message log recovery method based on message reordering and message number inspection," People's Republic of China Invention Patent, Patent No.: 201210239710.0, 2012.

[6] Jing cai, Shengfa gao. "Message Rearrange Theory in Message Recovery Protocol," 2013 5th International Conference on Computer Science and Information Technology (CSIT), pp.293-297, 2013.

[7] Shengfa gao. "Message Number Check and Message Rearranging Theory and Protocols", LAP LAMBERT Academic Publishing house, 2014 (monograph).

[8] SCHLICHTING, R.D. AND SCHNEIDER, F.B. 1983. "Fail-stop processors: An approach to designing fault-tolerant computing systems," ACMTrans.Comput.Syst.1,3,222–238,1983.

Claims (2)

1. A backward recovery fault-tolerant method with forward recovery characteristic is characterized in that a message reordering method is adopted, the effect of conditional execution of a fault-free process when other processes have faults is achieved by sending fault bit control messages, and messages and corresponding logic clocks are stored in a message log at one time and then sent before sending and receiving processes send messages without fault sending processes; when a process fails, acquiring replay messages and corresponding logic clocks from a message log under the control of a recovery thread, and then reordering the replay messages according to the logic clocks of the messages; finally, the sequenced messages are sent to the fault process again, and the fault process receives and processes the messages again, so that the replay of the messages is realized;

the method requires a common process P_iSendM (i, j, LC) function_iM) the working steps are as follows:

step 1, if F_i0, indicates the message sending process P_iIf no fault exists, the step 2 is carried out; otherwise F_i1 indicates P_iIf the fault exists, the step 4 is carried out; wherein F_iIs a component of a fault vector F representing a process P_iFault state of (D), F_i0 denotes the message sending process P_iNo failure, F_i1 represents P_iA fault exists;

step 2, if F_jIf the value is 0, the step 3 is carried out; otherwise F_jStep 2 is carried out when the process P is received_jRecovery from a fault condition, P_jThe failure of (1) is recovered by the Recover (j) thread; wherein F_jIs a component of a fault vector F representing a message receiving process P_jFault state of (D), F_j0 represents P_jNo failure, F_j1 represents P_jA fault exists;

step 3, adding one to the logic clock of the sending process under the condition that both the sending process and the receiving process have no fault: LC (liquid Crystal)_i←LC_i+ 1; adding message information<i,j,LC_i,m>When the message log file is at the end, turning to the step 5; wherein i and j respectively represent a sending process P_iAnd receiving the process P_jProcess number, LC_iRepresents P_iA logical clock variable of the process, m represents the load of the message;

step 4, adding one to the logic clock of the sending process: LC (liquid Crystal)_i←LC_i+ 1; ending the message sending process;

step 5, sending application message AM<i,j,LC_i,m>To receiving process P_jAnd the message sending process is ended.

2. Backward with forward recovery as in claim 1Recovering fault tolerance method, marking the failed common process as P_kK 1,2, 3 … n, failover recovery (k) thread recovery P_kThe steps are as follows:

step 1, sending F with reliable channel_k1 message to each of the state Control processes Control-1, Control-2_kIf the fault occurs, switching to the step 2; wherein the state Control process Control-i is responsible for the normal process P_iState control of (1), including saving P_iTemporary and permanent checkpoint of, killing P_iAnd restarting P from a persistent checkpoint_i，i＝1,2,...n；

Step 2, if T sent by Control-k is received_kVector, go to step 3; otherwise, go to step 2 to wait for T reception_kVector quantity; wherein, the vector T_k＝[T_k1,T_k2,...T_kn],T_kiRepresenting a process P_kReceived, process P_iThe number of messages sent, i ≠ k, i ═ 1, 2.. n;

step 3, receiving T_kSaving the vector to a memory, and turning to the step 4;

step 4, accessing daemon process to obtain U_1k，U_2k，...U_(k-1)k,U_(k+1)k,...U_nkTurning to step 5; wherein U is_ikRepresenting a process P_iSent to process P_jThe number of messages, i ≠ k, i ═ 1, 2.. n;

step 5, accessing the log daemon process, and obtaining the U from the log file according to the sequence from back to front_ik-T_kiA P_iTo P_kStep 6, i ≠ k, i ≠ 1, 2.. n; wherein U is_ik-T_kiThe value of the subtraction expression of (a) represents the process P_kShould be received from process P after restart_iThe number of messages;

step 6, pressing all messages to LC_kSorting the variable values from small to large, and turning to step 7;

step 7, sending the sequenced message to P_kI.e. replay message, go to step 8;

step 8, sending F by reliable channel_kA message of 0 to Control-1, Control-2_kThe process has recovered from the failure; f_k←0，F_kAnd setting zero and finishing steering.