Scalable consensus protocol

• US 7,937,482 B1
• Filed: 03/27/2008
• Issued: 05/03/2011
• Est. Priority Date: 03/27/2008
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vermeulen, Allan H., Sivasubramanian, Swaminathan
• Primary Examiner(s): Phan; Man
• Assistant Examiner(s): Mansoury; Nourali
• Application Number:
  US12/056,597
• Time in Patent Office: 1,132 Days
• Field of Search: 370/254, 370/401, 370/390, 370/252, 709/229, 709/226, 707/100, 707/204, 707/202, 707/203, 714/11, 714/4, 714/10, 714/12
• US Class Current: 709/229
• CPC Class Codes: G06F 11/1425 by reconfiguration of node membership
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data

Abstract

In one embodiment, a system comprises a plurality of nodes coupled to a network. At least a subset of the nodes are configured to maintain a replica of a state machine. The nodes are classified into a plurality of non-overlapping classes. A first class comprises at least one node that is a current participant in a consensus protocol to control transitions of the state machine. A second class comprises nodes that are not current participants in the consensus protocol but which are reclassifiable into the first class. The node(s) in the first class are configured to act on a proposal for a transition of the state machine according to the consensus protocol.

Claims

1. A system, comprising:

a plurality of nodes coupled to a network, wherein at least a subset of the plurality of nodes are each configured to maintain a replica of a state machine; and

the plurality of nodes are classified into a plurality of non-overlapping classes, and a first class of the plurality of non-overlapping classes comprises multiple nodes that are each a current participant in a consensus protocol for controlling transitions of the state machine such that respective state machine replicas maintained by at least one node in the first class and one or more nodes in a second class of the plurality of non-overlapping classes are transitioned to a state upon at least some of the multiple nodes of the first class accepting a proposal to change the state of said state machine according to the consensus protocol, the second class comprising nodes that are not current participants in the consensus protocol but which are reclassifiable into the first class; and

the multiple nodes in the first class are each configured to act on the proposal for a transition of the state machine in order to collectively accept or deny that proposal according to the consensus protocol.

2. The system as recited in claim 1 wherein the plurality of non-overlapping classes further comprise a third class that comprises nodes which are not permitted to participate in the consensus protocol.

3. The system as recited in claim 2 wherein the at least one node in the first class is configured to communicate accepted state transitions to one or more nodes in the third class.

4. The system as recited in claim 1, wherein the nodes in the first class are each assigned nodes in the second class and are configured to transmit an indication of an accepted state transition to their respective assigned nodes in the second class.

5. The system as recited in claim 1 wherein a second node of the plurality of nodes is classified as a master node having additional responsibilities according to the consensus protocol.

6. The system as recited in claim 5 wherein the additional responsibilities include periodically transmitting a communication to other ones of the plurality of nodes.

7. The system as recited in claim 6 wherein the communication includes data identifying a current state of the state machine on the master node wherein each of the plurality of nodes that maintain a respective replica of the state machine are configured to detect one or more missing state transitions responsive to the communication and are configured to request a state update responsive to detecting the one or more missing state transitions.

8. The system as recited in claim 1 wherein a second node of the plurality of nodes is configured to generate the proposal, and wherein the second node is configured to transmit the proposal only to nodes in the first class.

9. The system as recited in claim 1 wherein a second node of the plurality of nodes is configured to detect that a number of nodes in the first class is less than a desired number, and wherein the second node is configured to propose that one of the plurality of nodes in the second class be added to the first class responsive to the detecting.

10. The system as recited in claim 1 wherein at least one node in the first class is configured to communicate accepted state transitions resulting from the consensus protocol to nodes in other classes of the plurality of non-overlapping classes.

11. A non-transitory computer accessible storage medium storing a plurality of instructions which, when executed on a first node of a plurality of nodes:

maintain a first replica of a state machine on the first node, wherein one or more other nodes of the plurality of nodes also maintain replicas of the state machine, and wherein the plurality of nodes are classified into a plurality of non-overlapping classes including a first class that comprises multiple nodes that are each a current participant in a consensus protocol for controlling transitions of the state machine such that respective state machine replicas maintained by at least one node in the first class and one or more nodes in a second class of the plurality of non-overlapping classes are transitioned to a state upon at least some of the multiple nodes of the first class accepting a proposal to change the state of said state machine according to the consensus protocol, the second class comprising nodes that are not current participants in the consensus protocol but which are reclassifiable into the first class; and

responsive to the first node being in the first class, act on the proposal for a transition of the state machine in coordination with one or more other nodes of the first class in order to collectively accept or deny that proposal according to the consensus protocol.

12. The non-transitory computer accessible storage medium as recited in claim 11 wherein the plurality of non-overlapping classes further comprise a third class, wherein nodes in the third class are not permitted to become a participant in the consensus protocol.

13. The non-transitory computer accessible storage medium as recited in claim 12 wherein the plurality of instructions, when executed, transmit accepted state transitions to one or more nodes in the third class that are assigned to the first node.

14. The non-transitory computer accessible storage medium as recited in claim 12 wherein a second node of the plurality of nodes is classified as a master node having additional responsibilities according to the consensus protocol.

15. The non-transitory computer accessible storage medium as recited in claim 14 wherein the additional responsibilities include periodically transmitting a communication to other ones of the plurality of nodes.

16. The non-transitory computer accessible medium as recited in claim 15 wherein the communication includes data identifying a current state of the state machine on the master node, and wherein the plurality of instructions, when executed, detect one or more state missing transitions responsive to the communication and request a state update responsive to detecting the one or more state missing transitions.

17. The non-transitory computer accessible storage medium as recited in claim 11 wherein the plurality of instructions, when executed, generate the proposal and transmit the proposal only to nodes in the first class.

18. The non-transitory computer accessible storage medium as recited in claim 11 wherein the plurality of instructions, when executed, communicate accepted state transitions resulting from the consensus protocol to nodes in other classes of the plurality of non-overlapping classes.

19. The non-transitory computer accessible storage medium as recited in claim 11 wherein the plurality of instructions, when executed, detect that a number of nodes in the first class is less than a desired number;

and propose that one of the plurality of nodes in the second class be added to the first class responsive to the detecting.

20. A non-transitory computer accessible storage medium storing a plurality of instructions which, when executed on a first node of a plurality of nodes:

maintain a first replica of a state machine on the first node, wherein one or more other nodes of the plurality of nodes also maintain replicas of the state machine, and wherein the plurality of nodes are classified into a plurality of non-overlapping classes including a first class that comprises multiple nodes that are each a current participant in a consensus protocol for controlling transitions of the state machine such that respective state machine replicas maintained by at least one node in the first class and one or more nodes in a second class of the plurality of non-overlapping classes are transitioned to a state upon at least some of the multiple nodes of the first class accepting a proposal to change the state of said state machine according to the consensus protocol, the second class comprising nodes that are not current participants in the consensus protocol but which are reclassifiable into the first class;

transmit the proposal for a transition of the state machine to cause the proposal to be evaluated according to the consensus protocol by the multiple nodes in the first class and not by nodes in the second class.

21. The non-transitory computer accessible storage medium as recited in claim 20 wherein the plurality of instructions, when executed responsive to the first node being in the first class, act on the proposal in coordination with one or more other nodes of the first class in order to collectively accept or deny that proposal according to the consensus protocol.

22. The non-transitory computer accessible storage medium as recited in claim 21 wherein the plurality of instructions, when executed on the first node in the first class, communicate accepted state transitions resulting from the consensus protocol to one or more nodes in the second class that are assigned to the first node.

23. The non-transitory computer accessible storage medium as recited in claim 20 wherein the plurality of non-overlapping classes further comprise a third class that comprises one or more nodes which are not permitted to participate in the consensus protocol.

24. The non-transitory computer accessible storage medium as recited in claim 23 wherein the plurality of instructions, when executed, do not transmit the proposal to one or more nodes in the third class.

25. The non-transitory computer accessible storage medium as recited in claim 20 wherein the plurality of instructions, when executed, communicate accepted state transitions resulting from the consensus protocol to nodes in other classes of the plurality of non-overlapping classes.

26. The non-transitory computer accessible storage medium as recited in claim 20 wherein the plurality of instructions, when executed, detect that a number of nodes in the first class is less than a desired number;

and propose that one of the plurality of nodes in the second class be added to the first class responsive to the detecting.

27. A method, comprising:

for a plurality of nodes that comprises at least a subset of nodes that each maintain a respective replica of a state machine, classifying the plurality of nodes into a plurality of non-overlapping classes including a first class that comprises multiple nodes that are each a current participant in a consensus protocol for controlling transitions of a state machine such that respective state machine replicas maintained by at least one node in the first class and one or more nodes in a second class of the plurality of non-overlapping classes are transitioned to a state upon at least some of the multiple nodes of the first class accepting a proposal to change the state of said state machine according to the consensus protocol, the second class comprising nodes that are not current participants in the consensus protocol but which are reclassifiable into the first class; and

one of the plurality of nodes detecting that a number of nodes in the first class is less than a desired number; and

the one of the plurality of nodes generating the proposal to propose that a selected one of the plurality of nodes in the second class be added to the first class responsive to the detecting.

28. The method as recited in claim 27 further comprising, responsive to a first node being in the first class, the first node acting on the proposal for a transition of the state machine according to the consensus protocol.

29. The method as recited in claim 27 wherein the plurality of non-overlapping classes further comprise a third class, wherein nodes in the third class are not permitted to become a participant in the consensus protocol.

30. The method as recited in claim 27 further comprising classifying a second node of the plurality of nodes as a master node having additional responsibilities according to the consensus protocol.

31. The method as recited in claim 30 wherein the additional responsibilities include periodically transmitting a communication to other ones of the plurality of nodes.

32. The method as recited in claim 31 wherein the communication includes data identifying a current state of the state machine on the master node, and wherein the method further comprises detecting one or more missing transitions responsive to the communication and requesting a state update responsive to detecting the one or more missing transitions.