Virtually synchronous Paxos

• US 7,849,223 B2
• Filed: 12/07/2007
• Issued: 12/07/2010
• Est. Priority Date: 12/07/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Lidong, Malkhi, Dahlia, Lamport, Leslie B.
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): HENRY, MARIEGEORGES A
• Application Number:
  US11/952,133
• Publication Number:
  US 20090150566A1
• Time in Patent Office: 1,096 Days
• Field of Search: 709/248, 714/12, 714/13, 714/25, 714/39, 714/49
• US Class Current: 709/248
• CPC Class Codes: H04L 67/34 involving the movement of software or configuration parameters network booting or remote initial program loading [RIPL] G06F9/4416

Abstract

A variant of Paxos is referred to as Virtually Synchronous Paxos (VS Paxos). VS Paxos is a self-reconfigurable protocol that allows for delay only for reconfiguration decisions, without placing an artificial limit on regular decisions. In an implementation of VS Paxos, subject to any restriction on reconfiguration decisions, a leader may activate an unbounded number of consensus instances ahead. A VS Paxos technique permits unlimited progress during stability periods, in that a leader may initiate commands at any number of consensus instances without bound. VS Paxos waits for command completion only when configuration-changing commands occur.

Claims

1. A method for updating a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:

a leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, where the first data state update comprises a first ballot number;

the leader proposing the first data state update to the plurality of computing devices;

the leader generating a second data state updates for the state machine resulting from a second requests from a second client operating on the state machine, the second data state update comprising a second ballot number;

the leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements from the plurality of computing devices for the first data state update;

the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update; and

the state machine implementing the second data state update, if a quorum of acknowledgements is received from the plurality of computing devices for the second data state update.

2. The method of claim 1, the leader comprising a leader of a plurality of servers using a synod protocol.

3. The method of claim 1, comprising determining an ordering of the first data state update and the second data state update using the ballot numbers associated with respective updates.

4. The method of claim 3, the ordering used for one or more of:

an ordering of the data state update proposals to the plurality of computing devices; and

an ordering of the implementation of the data state updates on the state machine.

5. The method of claim 1, the computing devices comprising a plurality of servers in a data storage network implementing a Paxos-based consensus protocol.

6. The method of claim 1, comprising the leader sending a message to the plurality of computing devices comprising a leader ballot number chosen from a set of ballot numbers for the leader.

7. The method of claim 6, comprising receiving from a first computing device of the plurality of computing devices a message to the leader comprising a value of a highest ballot number received by the first computing device prior to receiving the message from the leader.

8. The method of claim 6, comprising receiving from a first computing device of the plurality of computing devices a message to the leader comprising a default ballot number value, if the first computing device has not received a message comprising a ballot number prior to receiving the leader'"'"'s message.

9. The method of claim 6, comprising receiving from a first computing device of the plurality of computing devices a message to the leader comprising an indication that the first computing device is ignoring the message from the leader, if the first computing device has received a message comprising a ballot number higher than the leader ballot.

10. The method of claim 9, if the leader is configured to remain the leader of the plurality of computing devices, comprising one or more of:

the leader responding with a message comprising a higher ballot number than the ballot number received by the first computing device; and

the leader responding with a message comprising a higher message instance value than the ballot number received by the first computing device.

11. The method of claim 1, after the leader receives a quorum of acknowledgments from the plurality of computing devices, comprising:

the leader sending a message to the plurality of computing devices comprising a proposed value to be learned by the state machine, comprising one of;

a result of a function comprising at least one ballot tuple comprising a highest ballot tuple from one or more messages received from the plurality of computing devices, if at least one ballot tuple is received by the leader; and

a value proposed by the leader; and

one or more of the plurality of computing devices sending a message to the other of the plurality of computing devices, the message comprising a ballot number greater than a current active ballot number, and receiving information about the state of the other computing devices in return.

12. A method for reconfiguring a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:

a first leader of the plurality of computing devices sending a message to the plurality of computing devices, the message comprising a state machine configuration update and a ballot number higher than a current ballot number used by a second leader for the state machine;

one or more of the plurality of computing devices disabling the second leader by refusing messages comprising a ballot number lower than the first leader'"'"'s;

after receiving a quorum of acknowledgements from the plurality of computing devices, the first leader;

generating a plurality of data state updates for the state machine resulting from a plurality of requests from one or more clients operating on the state machine, the respective plurality of data state updates comprising different ballot numbers; and

proposing the plurality of data state updates to the plurality of computing devices without regard to receiving a quorum of acknowledgements for the respective plurality of data state updates; and

the state machine implementing the one or more plurality of data state updates, if the quorum of acknowledgements is received for the respective plurality of data state updates.

13. The method of claim 12, disabling the second leader comprising refusing messages having a lower ballot number than a ballot number received by a computing device from the one or more of the other plurality of computing devices.

14. The method of claim 12, comprising the first leader collecting information on a state of remaining computing devices from the plurality of computing devices after proposing the configuration update.

15. The method of claim 14, comprising the remaining computing devices sending information on a previous command from the second leader, comprising a ballot number.

16. The method of claim 12, comprising the first leader determining a current configuration of the state machine utilizing a consensus decision based on a quorum set for the plurality of computing devices.

17. The method of claim 16, comprising the first leader:

choosing a ballot number higher than the current ballot number determined from the current configuration state; and

sending a message to the plurality of computing devices, the message comprising the chosen ballot number.

18. The method of claim 16, upon learning of the current configuration of the state machine the first leader proposing a new configuration of the state machine, where the proposal comprises a ballot number higher than a ballot number used in the current configuration.

19. The method of claim 12, the fault tolerant state machine comprising a data operations state machine and a quorum configuration state machine, the method comprising:

the data operations state machine generating a plurality of decisions orthogonal to a plurality of decisions generated by the quorum configuration state machine, so that the data operations state machine continues operating when a reconfiguration decision is made by the quorum configuration state machine.

20. A method for updating and reconfiguring a fault tolerant state machine comprising a plurality of computing devices using a fault tolerant, quorum-based consensus protocol, comprising:

a first leader of the plurality of computing devices generating a first data state update for the state machine resulting from a first request from a first client operating on the state machine, the first data state update comprising a first ballot number;

the first leader proposing the first data state update to the plurality of computing devices;

the first leader generating a second data state update for the state machine resulting from a second request from a second client operating on the state machine, the second data state update comprising a second ballot number;

the first leader proposing the second data state update to the plurality of computing devices prior to receiving a quorum of acknowledgements for the first data state update;

the state machine implementing the first data state update, if the quorum of acknowledgements is received for the first data state update;

the state machine implementing the second data state update, if the quorum of acknowledgements is received for the second data state update;

a second leader of the plurality of computing devices sending a message to the plurality of computing devices, the message comprising a state machine configuration update and a ballot number higher than a current ballot number used by the first leader for the state machine;

one or more of the plurality of computing devices disabling the first leader by refusing messages comprising a ballot number lower than the second leader'"'"'s ballot number.