Cheap paxos

• US 7,249,280 B2
• Filed: 06/18/2004
• Issued: 07/24/2007
• Est. Priority Date: 06/18/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Massa, Michael T., Lamport, Leslie B.
• Primary Examiner(s): Beausoliel; Robert
• Assistant Examiner(s): Ehne; Charles
• Application Number:
  US10/872,338
• Publication Number:
  US 20050283659A1
• Time in Patent Office: 1,131 Days
• Field of Search: 714 4- 8, 714 10- 14, 709220-222
• US Class Current: 714/11
• CPC Class Codes: G06F 11/182 based on mutual exchange of the output between redundant processing components
• CPC Class Codes: G06F 11/187 Voting techniques

Abstract

A distributed computing system can be operated in a fault tolerant manner using a collection of auxiliary computing devices and more main computing devices than the number of faults the system can tolerate. A quorum of all of the main computing devices can be used. In the event of a failure, an alternative quorum from a selected set of quorums, comprising at least one main computing device and some or all of the auxiliary computing devices, can be used to complete pending operations and to select a new set of quorums. Alternatively, another state machine, comprising at least one main computing device and some or all of the auxiliary computing devices, can select a new quorum comprising the currently operating main computing devices, and the new quorum can then complete pending operations and can continue to select proposals using the proposal number assigned by the other state machine.

Claims

1. A method for selecting a value in a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the method comprising the steps of:

proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;

receiving a first set of vote responses from a first quorum, wherein the first quorum comprises at least one operational main computing device; and

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums;

proposing the value to a second quorum from the first set of quorums;

receiving a second set of vote responses from the second quorum; and

determining that the value was selected if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value.

2. The method of claim 1, wherein the second quorum is the first preferred quorum from the first set of quorums.

3. The method of claim 1, wherein, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, the method further comprises the steps of:

proposing the value to a third quorum that is different than the second quorum, the third quorum being in the first set of quorums;

receiving a third set of vote responses from the third quorum; and

determining that the value was selected if any combination of vote responses from the second set of vote responses and the third set of vote responses indicates that every computing device in the third quorum has voted for the value.

4. The method of claim 3, wherein, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, the method further comprises the steps of:

determining one or more faulty computing devices in the second quorum; and

proposing, to the third quorum, a second set of quorums comprising a second preferred quorum comprising all of the operational main computing devices, and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed second set of quorums share at least one computing device, and wherein further the second preferred quorum does not include the one or more faulty computing devices.

5. The method of claim 4, wherein the determining the one or more faulty computing devices comprises the steps of:

perceiving a failure of a target computing device;

entering, by performing a state machine command, an indication of the perceived failure of the target computing device into a data structure, the data structure correlating a perceiving computing device and the target computing device; and

determining that the target computing device is faulty by reference to the data structure.

6. The method of claim 3, wherein the proposing the value to the third quorum comprises sending a hash of the value to one or more auxiliary computing devices in the third quorum.

7. The method of claim 1, wherein, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, the method further comprising the step of:

proposing a no-operation value for every system step between a current system step and a future system step at which the first set of quorums becomes effective, wherein the proposed first set of quorums is a current system step value selected for the current system step.

8. The method of claim 1, wherein, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, the method further comprising the step of:

if the first quorum comprises one or more auxiliary computing devices, informing the one or more auxiliary computing devices that values have been selected for system steps through a future system step at which the first set of quorums becomes effective, thereby enabling the one or more auxiliary computing devices to erase information related to the system steps through the future system step.

9. The method of claim 1, wherein the value is a function to be executed for a system step.

10. The method of claim 1, wherein, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, the method further comprising the step of:

communicating with the at least one operational main computing device to ensure that the at least one operational main computing device has recorded values selected for system steps through a future system step at which the first set of quorums becomes effective.

11. The method of claim 10, wherein the at least one operational main computing device has recorded values selected for system steps through the future system step if it has recorded a checkpoint state at a checkpoint system step and values selected for system steps from the checkpoint system step through the future system step.

12. The method of claim 1, further comprising the steps of:

proposing a proposal number for system steps larger than a last known system step; and

receiving a first set of proposal responses from a first set of computing devices, the first set of proposal responses comprising, for system steps larger than the last known system step, last vote information and prior proposal response information for each computing device in the first set of computing devices.

13. The method of claim 1, wherein, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums and if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value, the method further comprising the steps of:

indicating, to the second quorum, that subsequent values received directly from one or more clients are to be treated as proposed values having a proposal number equivalent to that used to propose the value; and

indicating, to the second quorum, that responses to the subsequent values are to be sent to the one or more clients;

wherein the second quorum comprises more computing devices than twice a number of tolerable failures.

14. A computer-readable storage medium having computer-executable instructions for selecting a value in a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the computer-executable instructions performing steps comprising:

proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;

receiving a first set of vote responses from a first quorum, wherein the first quorum comprises at least one operational main computing device; and

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums;

proposing the value to a second quorum from the first set of quorums;

receiving a second set of vote responses from the second quorum; and

determining that the value was selected if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value.

15. The computer-readable storage medium of claim 14, wherein the second quorum is the first preferred quorum from the first set of quorums.

16. The computer-readable storage medium of claim 14 having further computer-executable instructions for, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value performing steps comprising:

proposing the value to a third quorum that is different than the second quorum, the third quorum being in the first set of quorums;

receiving a third set of vote responses from the third quorum; and

determining that the value was selected if any combination of vote responses from the second set of vote responses and the third set of vote responses indicates that every computing device in the third quorum has voted for the value.

17. The computer-readable storage medium of claim 16 having further computer-executable instructions for, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, performing steps comprising:

determining one or more faulty computing devices in the second quorum; and

proposing, to the third quorum, a second set of quorums comprising a second preferred quorum comprising all of the operational main computing devices, and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed second set of quorums share at least one computing device, and wherein further the second preferred quorum does not include the one or more faulty computing devices.

18. The computer-readable storage medium of claim 17, wherein the computer-executable instructions for determining the one or more faulty computing devices comprise computer-executable instructions for performing steps comprising:

perceiving a failure of a target computing device;

entering, by performing a state machine command, an indication of the perceived failure of the target computing device into a data structure, the data structure correlating a perceiving computing device and the target computing device; and

determining that the target computing device is faulty by reference to the data structure.

19. The computer-readable storage medium of claim 16, wherein the computer-executable instructions for proposing the value to the third quorum comprise computer-executable instructions for sending a hash of the value to one or more auxiliary computing devices in the third quorum.

20. The computer-readable storage medium of claim 14 having further computer-executable instructions for, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, performing steps comprising:

proposing a no-operation value for every system step between a current system step and a future system step at which the first set of quorums becomes effective, wherein the proposed first set of quorums is a current system step value selected for the current system step.

21. The computer-readable storage medium of claim 14 having further computer-executable instructions for, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, performing steps comprising:

if the first quorum comprises one or more auxiliary computing devices, informing the one or more auxiliary computing devices that values have been selected for system steps through a future system step at which the first set of quorums becomes effective, thereby enabling the one or more auxiliary computing devices to erase information related to the system steps through the future system step.

22. The computer-readable storage medium of claim 14, wherein the value is a function to be executed for a system step.

23. The computer-readable storage medium of claim 22, wherein the function is identified by a unique function identifier.

24. The computer-readable storage medium of claim 14 having further computer-executable instructions for, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, performing steps comprising:

communicating with the at least one operational main computing device to ensure that the at least one operational main computing device has recorded values selected for system steps through a future system step at which the first set of quorums becomes effective.

25. The computer-readable storage medium of claim 24, wherein the at least one operational main computing device has recorded values selected for system steps through the future system step if it has recorded a checkpoint state at a checkpoint system step and values selected for system steps from the checkpoint system step through the future system step.

26. The computer-readable storage medium of claim 14, having further computer-executable instructions for performing steps comprising:

proposing a proposal number for system steps larger than a last known system step; and

receiving a first set of proposal responses from a first set of computing devices, the first set of proposal responses comprising, for system steps larger than the last known system step, last vote information and prior proposal response information for each computing device in the first set of computing devices.

27. The computer-readable storage medium of claim 14 having further computer-executable instructions for, if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums and if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value, performing steps comprising:

indicating, to the second quorum, that subsequent values received directly from one or more clients are to be treated as proposed values having a proposal number equivalent to that used to propose the value; and

indicating, to the second quorum, that responses to the subsequent values are to be sent to the one or more clients;

wherein the second quorum comprises more computing devices than twice a number of tolerable failures.

28. A main computing device operating as part of a distributed computing system comprising one or more main computing devices and one or more auxiliary computing devices, the main computing device comprising:

a processing unit performing steps comprising;

proposing a first set of quorums comprising a first preferred quorum comprising all of the operational main computing devices and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed first set of quorums share at least one computing device;

if a first set of vote responses indicate that every computing device in a first quorum has voted for the proposed set of quorums, proposing the value to a second quorum from the first set of quorums; and

if a second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value, determining that the value was selected; and

a network interface performing steps comprising;

receiving the first set of vote responses from the first quorum, wherein the first quorum comprises at least one operational main computing device; and

receiving a second set of vote responses from the second quorum.

29. The main computing device of claim 28, wherein the second quorum is the first preferred quorum from the first set of quorums.

30. The main computing device of claim 28, wherein the processing unit, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, performs additional steps comprising:

proposing the value to a third quorum that is different than the second quorum, the third quorum being in the first set of quorums and determining that the value was selected if any combination of vote responses from the second set of vote responses and a third set of vote responses from the third quorum indicates that every computing device in the third quorum has voted for the value; and

wherein further the network interface, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, performs additional steps comprising;

receiving the third set of vote responses from the third quorum.

31. The main computing device of claim 28, wherein the processing unit, if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has not voted for the value, performs additional steps comprising:

determining one or more faulty computing devices in the second quorum; and

proposing, to the third quorum, a second set of quorums comprising a second preferred quorum comprising all of the operational main computing devices, and one or more additional quorums comprising one or more of the one or more main computing devices and one or more of the one or more auxiliary computing devices so that any two quorums in the proposed second set of quorums share at least one computing device, and wherein further the second preferred quorum does not include the one or more faulty computing devices.

32. The main computing device of claim 31, wherein the determining the one or more faulty computing devices comprises:

perceiving a failure of a target computing device;

entering, by performing a state machine command, an indication of the perceived failure of the target computing device into a data structure, the data structure correlating a perceiving computing device and the target computing device; and

determining that the target computing device is faulty by reference to the data structure.

33. The main computing device of claim 30, wherein the proposing the value to the third quorum comprises utilizing the network interface to send a hash of the value to one or more auxiliary computing devices in the third quorum.

34. The main computing device of claim 28, wherein the processing unit performs additional steps comprising:

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, proposing a no-operation value for every system step between a current system step and a future system step at which the first set of quorums becomes effective, wherein the proposed first set of quorums is a current system step value selected for the current system step.

35. The main computing device of claim 28, wherein the network interface performs additional steps comprising:

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums and if the first quorum comprises one or more auxiliary computing devices, transmitting to the one or more auxiliary computing devices an indication that values have been selected for system steps through a future system step at which the first set of quorums becomes effective, thereby enabling the one or more auxiliary computing devices to erase information related to the system steps through the future system step.

36. The main computing device of claim 28, wherein the value is a function to be executed for a system step.

37. The main computing device of claim 28, wherein the processing unit performs additional steps comprising:

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums, utilizing the network interface to communicate with the at least one operational main computing device to ensure that the at least one operational main computing device has recorded values selected for system steps through a future system step at which the first set of quorums becomes effective.

38. The main computing device of claim 28, wherein the processing unit performs additional steps comprising:

proposing a proposal number for system steps larger than a last known system step; and

wherein further the network interface performs additional steps comprising;

receiving a first set of proposal responses from a first set of computing devices, the first set of proposal responses comprising, for system steps larger than the last known system step, last vote information and prior proposal response information for each computing device in the first set of computing devices.

39. The main computing device of claim 28, wherein the processing unit performs additional steps comprising:

if the first set of vote responses indicate that every computing device in the first quorum has voted for the proposed set of quorums and if the second set of vote responses from the second quorum indicate that every computing device in the second quorum has voted for the value, utilizing the network interface to indicate to the second quorum that subsequent values received directly from one or more clients are to be treated as proposed values having a proposal number equivalent to that used to propose the value and that responses to the subsequent values are to be sent to the one or more clients, wherein the second quorum comprises more computing devices than twice a number of tolerable failures.