Independent checkpointing method using a memory checkpoint on a distributed system

[0002] The present invention relates to an independent checkpointing method, which recovers problems in running a distributed system and reduces work time. In the method in accordance with an embodiment of the present invention, transmitting processes send messages with a self checkpoint number, and receiving processes determine whether memory checkpoint is to be performed in reference to the transmitting processes' checkpoint number, current process checkpoint number, memory checkpoint flag, and message transmission flag before processing the received message. In performing periodical checkpointings, the method makes reference to the result of the memory checkpoint for checkpointing.

[0003] Checkpointing technology stores status information of each process and recovers errors by using the stored information when errors occur in running distributed system environments.

[0004] Several studies have been done in the area of checkpointing technology. An adaptive checkpointing algorithm was proposed by Jian Xu et al. at Proceedings of Fifth IEEE Symposium on Parallel and Distributed Processing in 1993. The adaptive checkpointing algorithm performs checkpointing by checking whether zigzag cycles made by an input message exist. If input messages make zigzag cycles, the adaptive checkpointing algorithm is based upon the fact that a domino effect may be caused. Therefore, if input messages make zigzag cycles, the adaptive checkpointing algorithm performs checkpointing to remove zigzag cycles before the processing of messages.

[0005] A lazy checkpointing algorithm was proposed by Wang et al. at Technical report CRHC-92-27. In the lazy checkpointing algorithm, message transmission processes attach a self checkpointing number to messages to be transmitted, and the message receiving processes compare the checkpointing number of the transmitted messages with their checkpoint number before processing the transmitted messages. If the checkpoint number of the transmission process is larger, checkpointing is performed before the message is processed. At the moment, the checkpoint numbers of the two processes become identical.

[0006] However, when the amount of message transmission and execution speed difference increases, these checkpointing methods may cause a large number of checkpoints and increase job completion time.

[0007] The number of checkpoints is directly related with job completion time in the error-free environment and the roll back distance is directly related with job completion time in the environment with errors. Therefore, a large number of checkpoints and an increase in roll back distance causes delayed job completion time.

[0008] An independent checkpointing method using memory checkpoint on a distributed system is provided.

[0009] The independent checkpointing method in accordance with an embodiment of the present invention includes a message transmission routine, a message processing routine, and a periodical checkpoint routine. The message transmission routine adds a self checkpoint number to a message to be transmitted when a current process tries to send a message to another process. The message processing routine performs a memory checkpoint and processes a message in reference to a checkpoint number of a transmission process, a checkpoint number of the current process, a memory checkpoint flag, and a message transmission flag when a message is received from a process. The periodical checkpoint routine performs a checkpoint that records a necessary state information for recovery against faults periodically in reference to the memory checkpoint flag.

[0010] Preferably, the message transmission routine includes the following steps. A step is to generate a message to be transmitted. Another step is to add the checkpoint number of the current process to the message to be transmitted. A further step is to set the message transmission flag true for preparing cases in which an orphan message occurs. An additional step is to transmit the message.

[0011] Preferably, the message processing routine includes the following steps. A first step is to receive the message from the process and compare the checkpoint number of the transmission process with the checkpoint number of the current process. Another step is to process the received message if the checkpoint number of the transmission process is smaller than or equal to the checkpoint number of the current process. A further step is to check the memory checkpoint flag if the checkpoint number of the transmission process is larger than the checkpoint number of the current process. Another step is to replace the checkpoint number of the current process with the checkpoint number of the message transmission process and process the received message if the checked memory checkpoint flag is true. A further step is to check the message transmission flag if the checked memory checkpoint flag is false. An additional step is to record the state information of the current process into a memory, set the checkpoint number of the current process as the checkpoint number of message transmission process, set the memory checkpoint flag true, set the message transmission flag false, and process the received message if the checked message transmission flag is true. Another additional step is to replace the checkpoint number of the current process with the checkpoint number of the transmission process and process the received if the checked message transmission flag is false.

[0012] Preferably, the periodical checkpoint routine includes the following steps. An initial step is to check the memory checkpoint flag on a periodical checkpoint time. Another step is to record the state information stored at the memory to a disk if the checked memory checkpoint flag is true or recording the state information to a disk and increasing the checkpoint number by one if the checked memory checkpoint flag is false. A further step is to calculate a next periodical checkpoint time. An additional step is to set the memory checkpoint flag and the message transmission flag false.

[0013] The embodiments of the present invention will be explained with reference to the accompanying drawings, in which:

[0014] FIG. 1 is a diagram illustrating a process in a distributed system in accordance with an embodiment of the present invention;

[0015] FIG. 2 is a flow diagram illustrating a message transmission routine in accordance with an embodiment of the present invention;

[0016] FIG. 3 is a flow diagram illustrating a message processing routine in accordance with an embodiment of the present invention; and

[0017] FIG. 4 is a flow diagram illustrating a periodical checkpointing routine in accordance with an embodiment of the present invention.

[0018] The method in accordance with an embodiment of the present invention may be applied to a distributed system, which includes a number of local machines connected through LANs (local area network).

[0019] FIG. 1 is a diagram illustrating a process in a distributed system in accordance with an embodiment of the present invention. As shown in FIG. 1, a local machine includes local memory and a local disk. A local machine executes a process allocated to a job. Each process includes message transmission routine, message processing routine, and periodical checkpoint routine for recovery against faults. Each process sends information to other processes through messages.

[0020] FIG. 2 is a flow diagram illustrating a message transmission routine in accordance with an embodiment of the present invention. As shown in FIG. 2, the independent checkpointing method includes four steps. A first step is to generate a message to be transmitted. A second step is to attach checkpoint number of current process to the message. A third step is to set transmission flag true for processing orphan messages. A fourth step is to transmit the message.

[0021] When the current process is running and a new message needs to be transmitted to a different process running in a different local machine, a message that needs to be transmitted earlier is generated at step S10.

[0022] Then, a checkpoint number of the current process is added to the generated message to be transmitted at step S11.

[0023] Executing a periodical checkpoint routine that is to be described later may increase the checkpoint number of the current process. When a message arrives from other processes, the checkpoint number of the current process may be replaced by the checkpoint number of the transmission process.

[0024] After the checkpoint number is added to the message to be transmitted, the message transmission flag is set true for notifying that the current process has sent a message to another process and then the message is transmitted at step S12 and S13.

[0025] The message transmission flag is important because it is necessary to reduce the number of the memory checkpoint when orphan messages are generated. Orphan messages are the messages transmitted after the checkpoint of the message transmission processes and received before the checkpoint of the message receiving processes. When errors occur in the message transmission processes, orphan messages bring back the message receiving processes to the point before the checkpoints. Therefore, in order to avoid generating orphan messages, checkpointing is performed after the message transmission processes send a message.

[0026] The method in accordance with an embodiment of the present invention employs message transmission flags to reduce the number of memory checkpoints in overall execution of each process and to prevent orphan messages. That is, memory checkpoint is performed only if the checkpoint number of the message transmission process is larger than checkpoint number of the message receiving process and the current message transmission flag of the message receiving process is true.

[0027] FIG. 3 is a flow diagram illustrating a message processing routine in accordance with an embodiment of the present invention.

[0028] As shown in FIG. 3, the message processing routine includes the following seven steps. A first step is to receive a message from a process and compare a checkpoint number of the message transmission process with a checkpoint number of the current process. A second step is to process the received message if the checkpoint number of the message transmission process is smaller than or equal to the checkpoint number of the current process. A third step is to check a memory checkpoint flag if the checkpoint number of the message transmission process is larger than the checkpoint number of the current process. A fourth step is to replace the checkpoint number of the current process with the checkpoint number of the message transmission process and process the received message if the memory checkpoint flag checked is true. A fifth step is to check the message transmission flag if the memory checkpoint flag checked is false. A sixth step is to record state information of the current process into memory, set the checkpoint number of the current process as a checkpoint number of message transmission process, set the memory checkpoint flag true, set the message transmission flag false, and process the received message if the message transmission flag checked is true. A seventh step is to replace the checkpoint number of the current process with a checkpoint number of the message transmission process and process the received message if the message transmission flag checked is false.

[0029] When a message is received from other processes, the message processing routine compares the checkpoint number of the current process with the checkpoint number of the message transmission process that is added to the message before processing the received message at step S21 and S22.

[0030] If the checkpoint number of the message transmission process is smaller than or equal to the checkpoint number of the current process, it means that the processing speed of the message transmission process is slower than or equal to the processing speed of the current process. In such cases, since the memory checkpoint of the current process is not necessary, the current process treats the received message without performing the memory checkpoint at step S25.

[0031] However, if the checkpoint number of the message transmission process is larger than the checkpoint number of the current process, it means that the processing speed of the message transmission process is faster than the processing speed of the current process. That is, the current process determines whether the memory checkpoint is to be performed before processing the received message.

[0032] The memory checkpoint is performed only if the checkpoint number of the message transmission process is larger than the checkpoint number of the current process, the memory checkpoint has not been performed, and the memory checkpoint after transmitting a message to other processes and periodical checkpoint have not been performed. It reduces number of checkpoints by preventing repetition of memory checkpoints and therefore reduces job completion time, even if a number of messages are received from other processes before the periodical checkpoint is performed.

[0033] For this purpose, the memory checkpoint flag is checked to see whether the memory checkpoint has been performed before at step S23.

[0034] If the flag is true, which means the memory checkpoint was performed after the periodical checkpoint is performed, the memory checkpoint is not to be performed. Instead, the checkpoint number of the current process is replaced by a checkpoint number of the message transmission process and then a next message is processed at steps S24 and S25.

[0035] If the flag is false at step S23, the message transmission flag is confirmed at step S26.

[0036] The message transmission flag is a flag describing if the current process has sent any messages to other processes. The message transmission flag is set as true by the message transmission routine and as false after the memory checkpoint or periodical checkpoint is performed.

[0037] Therefore, if the message transmission flag is true, which means that the result of the step S26 is true, that is, memory checkpoint or periodical checkpoint is not performed yet, the memory checkpoint that stores the state information of the current process into the memory is performed. Checkpoint numbers become identical by replacing checkpoint number by checkpoint number of message transmission process at step S27.

[0038] Then, the memory checkpoint flag is set true and the message transmission flag value is set false at steps S28 and S25 before the next message is processed.

[0039] FIG. 4 is a flow diagram illustrating a periodical checkpointing routine in accordance with an embodiment of the present invention. As shown in FIG. 4, the periodical checkpointing routine includes the following steps. A first step is to check the memory checkpoint flag on periodical checkpoint time. A second step is to record process state information stored at memory to disk if the memory checkpoint flag checked is true or recording process state information to disk and increasing the checkpoint number by one if the memory checkpoint flag checked is false. A third step is to calculate a next periodical checkpoint time. A fourth step is to set the memory checkpoint flag and the message transmission flag false.

[0040] The periodical checkpoint routine checks whether the memory checkpoint flag is true or false before writing current state information of the process with a certain period at steps S31 and S32.

[0041] The memory checkpoint flag is a flag indicating the memory checkpoint has been performed in the message processing routine. If the memory checkpoint flag is true, which means the memory checkpoint has been performed recently, the process state information stored in memory is written to the disk without increasing the checkpoint number at step S32.

[0042] If the memory checkpoint flag is false, which means the memory checkpoint has not been performed recently, the process state information is written on the disk while increasing the checkpoint number by 1 at step S33.

[0043] Then, the amount of time for executing the periodical checkpoint is calculated and the memory checkpoint flag and message transmission flag are set as false at steps S34 through S36.

[0044] When the amount of message transmission and execution speed difference increase, conventional checkpointing methods cause a large number of checkpoints, which increases delay caused by checkpoints and eventually causes increased job completion time.

[0045] However, the method in accordance with an embodiment of the present invention only performs checkpoint on the memory when a message is initially received from a process with a larger checkpoint number. Later, the method increases only the checkpoint number without performing any checkpoints. As shown in FIG. 4, process state information stored in the memory is recorded to disks in periodical checkpoints.

[0046] That is, process state information is recorded to disks with a certain period. Even though memory checkpoint is caused in every period, the time for memory checkpoint is substantially smaller than the time for the disk checkpoint, which means that actual job delay time is trivial.

[0047] On the contrary, to the conventional checkpoint methods, the method in accordance with an embodiment of the present invention performs only one disk checkpoint with a certain period.

[0048] In addition, as shown in FIG. 3, the method in accordance with an embodiment of the present invention removes dependent relations between processes that are usually caused by message transmissions by comparing checkpoint numbers. That is, when a process receives a message with a larger checkpoint number than the process, the process performs the memory checkpoint before processing the message and identifies a checkpoint number with the transmission process. This procedure virtually removes difference of execution speeds and reduces dependent relations between processes. As a result, the method in accordance with an embodiment of the present invention has a short roll back distance when errors occur.

[0049] As described above, the method of the present invention adds a checkpoint number in transmitting messages between processes. When a checkpoint number of message transmission process is larger than a checkpoint number of a current process, the method of the present invention performs the memory checkpoint in reference to a memory checkpoint flag and message transmission flag, replaces the checkpoint number of the current process with a checkpoint number of the message transmission process. In addition, the method of the present invention uses the result of the memory checkpoint in performing a periodical checkpoint.

[0050] Therefore, when a number of processes perform the same jobs in a distributed system environment, the method in accordance of an embodiment of the present invention has minimum number of checkpoints regardless of the amount of message transmission and execution speed difference. Also, the method removes dependent relations between processes that are usually caused by message transmissions by comparing checkpoint numbers. The method in accordance with an embodiment of the present invention has a short roll back distance when errors occur. Consequently, the method is effective for completing jobs in a minimum amount of time in a distributed system environment with errors or in a distributed system environment without errors.

[0051] Although representative embodiments of the present invention have been disclosed for illustrative purpose, those who are skilled in the art will appreciate that various modifications, additions and substitutions are possible without departing from the scope and spirit of the present invention as defined in the accompanying claims and in equivalents thereof.