Fault tolerant virtual machine

• US 20090222815A1
• Filed: 02/29/2008
• Published: 09/03/2009
• Est. Priority Date: 02/29/2008
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Dake, Steven
• Granted Patent: US 8,156,491 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/1443 Transmit or communication errors
• CPC Class Codes: G06F 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/1691 using a quantum
• CPC Class Codes: G06F 11/2041 with more than one idle spare processing component
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines

Abstract

A virtual machine communicates with one or more additional virtual machines to establish membership for a virtual lockstep computing system, wherein each virtual machine is hosted by a node in a network. The virtual machine communicates with the one or more additional virtual machines to determine a membership configuration, wherein a first virtual machine in the membership configuration is an active machine, and all remaining virtual machines in the membership configuration are standby machines. A single step operation is executed by the virtual machine upon obtaining an operational token that includes contents of the single step operation, wherein the operational token is generated by the active machine. The operational token is passed to a next virtual machine in the membership configuration, wherein the operational token is passed between the virtual machine and the additional virtual machines according to the membership configuration.

Claims

1. A computerized method comprising:

communicating by a virtual machine with one or more additional virtual machines to establish membership for a virtual lockstep computing system, wherein each virtual machine is hosted by a node in a network;

communicating by the virtual machine with the one or more additional virtual machines to determine a membership configuration for the virtual lockstep computing system, wherein a first virtual machine in the membership configuration is an active machine, and all remaining virtual machines in the membership configuration are standby machines;

executing a single step operation by the virtual machine upon obtaining an operational token that includes contents of the single step operation, wherein the operational token is generated by the active machine; and

passing the operational token to a next virtual machine in the membership configuration, wherein the operational token is passed between the virtual machine and the additional virtual machines according to the membership configuration.

2. The method of claim 1, further comprising:

detecting a failure of at least one of the one or more additional virtual machines by the virtual machine;

communicating by the virtual machine with the one or more additional virtual machines to reestablish the membership for the virtual lockstep computing system, wherein the reestablished membership excludes all failed virtual machines;

obtaining a last operational token that includes contents of a last single step operation;

executing the last single step operation if the last single step operation was not executed by the virtual machine prior to detecting the failure; and

passing the last operational token to the next virtual machine in the membership configuration.

3. The method of claim 2, further comprising:

if the virtual machine was the first standby machine in the membership configuration and a failed machine was the active machine, becoming a new active machine.

4. The method of claim 2, further comprising:

initiating a timer on the virtual machine; and

detecting the failure if a specified time limit elapses on the timer.

5. The method of claim 2, wherein the reestablished membership includes virtual machines that were not in the original membership, the method further comprising:

replicating the virtual machine;

copying the replicated virtual machine to a new node in the network; and

determining a new membership configuration for the reestablished membership.

6. The method of claim 1, wherein the virtual machine is the active machine, the method further comprising:

generating the operational token;

passing the operational token to a next virtual machine in the membership configuration;

receiving the operational token from the last standby machine in the membership configuration; and

generating a new operational token that includes contents of a next single step operation.

7. The method of claim 1, wherein the contents of the operation include changes in memory values, changes to registers, inputs from ports and outputs to ports.

8. The method of claim 1, wherein the operational token includes a new sequence identifier that has a value that is different than a previous sequence identifier included in a previous operational token, the method further comprising:

upon obtaining the operational token, comparing the new sequence identifier to an operation identifier maintained by the virtual machine;

if the sequence identifier matches an entry in the operation identifier, executing the single step operation whose contents are included in the operational token and adding an entry to the operation identifier that matches the new sequence identifier; and

if the sequence identifier does not mach an entry in the operation identifier, passing the operational token to the next virtual machine in the membership configuration without executing the single step operation.

9. The method of claim 1, wherein establishing the membership includes generating a sorted members list that includes a network address of each virtual machine in the membership, wherein the membership configuration is at least partially dependent upon the members list.

15. The method of claim 1, wherein the virtual machine is the active machine, the virtual machine further comprising:

the execution logic component to generate the operational token, to pass the operational token to a next virtual machine in the membership configuration, to receive the operational token from the last standby machine in the membership configuration, and to generate a new operational token that includes contents of a next single step operation.

10. A computing apparatus comprising:

a virtual machine that operates in lock step with one or more additional virtual machines that run on additional computing apparatuses, the virtual machine comprising;

a membership logic component to determine the one or more additional virtual machines with which the virtual machine operates in lock step and to determine a membership configuration, wherein a first virtual machine in the membership configuration is an active machine and all remaining virtual machines in the membership configuration are standby machines; and

an execution logic component to execute a single step operation upon obtaining an operational token that includes contents of the single step operation, and to pass the operational token to a next virtual machine in the membership configuration, wherein the operational token is passed between the virtual machine and the additional virtual machines according to the membership configuration.

11. The computing apparatus of claim 10, the virtual machine further comprising:

a failure logic component to detect a failure of at least one of the one or more additional virtual machines;

the membership logic component to communicate with the one or more additional virtual machines to reestablish the membership for the virtual lockstep computing system, wherein the reestablished membership excludes all failed virtual machines;

the execution logic component to obtain a last operational token that includes contents of a last single step operation, to execute the last single step operation if the last single step operation was not executed by the virtual machine prior to detecting the failure, and to pass the last operational token to the next virtual machine in the membership configuration.

12. The computing apparatus of claim 11, wherein the virtual machine is configured to become a new active machine if the virtual machine was the first standby machine in the membership configuration and a failed machine was the active machine.

13. The computing apparatus of claim 11, wherein the failure logic component is configured to detect the failure if a specified time limit elapses on a timer.

14. The computing apparatus of claim 11, wherein the reestablished membership includes virtual machines that were not in the original membership, the virtual machine further comprising:

a replicator to replicate the virtual machine and to copy the replicated virtual machine to a new node in the network;

the membership logic component to determine a new membership configuration for the reestablished membership.

16. A computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:

communicating by a virtual machine with one or more additional virtual machines to establish membership for a virtual lockstep computing system, wherein each virtual machine is hosted by a node in a network;

communicating by the virtual machine with the one or more additional virtual machines to determine a membership configuration, wherein a first virtual machine in the membership configuration is an active machine, and all remaining virtual machines in the membership configuration are standby machines;

executing a single step operation by the virtual machine upon obtaining an operational token that includes contents of the single step operation, wherein the operational token is generated by the active machine; and

passing the operational token to a next virtual machine in the membership configuration, wherein the operational token is passed between the virtual machine and the additional virtual machines according to the membership configuration.

17. The computer readable storage medium of claim 16, the method further comprising:

detecting a failure of at least one of the one or more additional virtual machines by the virtual machine;

communicating by the virtual machine with the one or more additional virtual machines to reestablish the membership for the virtual lockstep computing system, wherein the reestablished membership excludes all failed virtual machines;

obtaining a last operational token that includes contents of a last single step operation;

executing the last single step operation if the last single step operation was not executed by the virtual machine prior to detecting the failure; and

passing the last operational token to the next virtual machine in the membership configuration.

18. The computer readable storage medium of claim 17, the method further comprising:

if the virtual machine was the first standby machine in the membership configuration and a failed machine was the active machine, becoming a new active machine.

19. The computer readable storage medium of claim 17, the method further comprising:

initiating a timer on the virtual machine; and

detecting the failure if a specified time limit elapses on the timer.

20. The computer readable storage medium of claim 17, wherein the reestablished membership includes virtual machines that were not in the original membership, the method further comprising:

replicating the virtual machine;

copying the replicated virtual machine to a new node in the network; and

determining a new membership configuration for the reestablished membership.

21. The computer readable storage medium of claim 16, wherein the virtual machine is the active machine, the method further comprising:

generating the operational token;

passing the operational token to a next virtual machine in the membership configuration;

receiving the operational token from the last standby machine in the membership configuration; and

generating a new operational token that includes contents of a next single step operation.

22. The computer readable storage medium of claim 16, wherein the operational token includes a new sequence identifier that has a value that is different than a previous sequence identifier included in a previous operational token, the method further comprising:

upon obtaining the operational token, comparing the new sequence identifier to an operation identifier maintained by the virtual machine;

if the sequence identifier matches an entry in the operation identifier, executing the single step operation whose contents are included in the operational token and adding an entry to the operation identifier that matches the new sequence identifier; and

if the sequence identifier does not mach an entry in the operation identifier, passing the operational token to the next virtual machine in the membership configuration without executing the single step operation.

23. A computerized method comprising:

establishing membership for a virtual lockstep computing system from a plurality of nodes in a network, wherein the membership includes a plurality of virtual machines, each of which is hosted by one of the plurality of nodes;

determining a membership configuration for the plurality of virtual machines, wherein a first virtual machine in the membership configuration is an active machine, and all remaining virtual machines in the membership configuration are standby machines; and

executing single step operations by each of the plurality of virtual machines in strict order according to the membership configuration, wherein the active machine executes each single step operation first, and a last standby machine in the membership configuration executes each single step operation last.

24. The method of claim 23, further comprising:

initiating a timer on each of the plurality of virtual machines;

detecting a failure of one or more of the plurality of virtual machines if a time limit elapses on the timer;

reestablishing the membership for the virtual lockstep computing system, wherein the reestablished membership excludes the failed one or more of the plurality of virtual machines;

setting a first standby machine in the membership configuration as a new active machine if the failed one or more of the plurality of virtual machines was the active machine; and

executing a last single step operation by those of the plurality of virtual machines in the reestablished membership that were unable to execute the last single step operation before the failure was detected.

25. The method of claim 23, further comprising:

after executing each single step operation by the active machine, generating an operational token that includes the contents of the single step operation; and

passing the operational token in strict order among the plurality of virtual machines such that each of the plurality of virtual machines passes the operational token to a next virtual machine in the membership configuration and the last standby machine passes the operational token to the active machine, wherein each of the standby machines executes the single step operation upon first receiving the operational token.