Leadership lease protocol for data replication groups

• US 10,565,227 B1
• Filed: 08/31/2016
• Issued: 02/18/2020
• Est. Priority Date: 08/31/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Chen, Tao, Brooker, Marc John, Jain, Divya Ashok Kumar, Kusters, Norbert Paul, Ping, Fan, Pallikila, Lakshmi N.
• Primary Examiner(s): Le, Debbie M
• Application Number:
  US15/253,677
• Time in Patent Office: 1,266 Days
• Field of Search: None
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• 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: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064

Abstract

Data replication groups may be used to store data in a distributed computing environment. A data replication group may include a set of nodes executing a consensus protocol to maintain data durably. In order to increase efficiency and performance of the data replication, a particular node of the data replication group may be assigned the role of master node. The role of master node may be lease in accordance with a consensus protocol. If the lease is not renewed within an interval of time election/selection of a new master node may be commenced.

Claims

1. A computer-implemented method, comprising:

determining a particular node of a plurality of nodes of a data replication group has been elected as a master node and setting a current state to a leased state, the plurality of nodes implementing a consensus protocol for replicating data across the plurality of nodes;

transmitting, by the master node, heartbeat messages to individual nodes of the plurality of nodes;

on a condition that responses to the heartbeat messages are not received by the master node from a quorum of the plurality of nodes within a heartbeat interval, suspending transmission of further heartbeat messages;

on a condition that responses to the heartbeat messages are not received by the master node from a quorum of the plurality of nodes within a wait period, the wait interval being a period during which the master node waits to receive responses to pending heartbeat messages, the wait interval being greater than the heartbeat interval, setting the current state to an expiring state; and

after expiration of a safety interval, the safety interval being greater than the wait interval, commencing election of a new master node.

2. The computer-implemented method of claim 1, wherein the master node no longer transmits heartbeat messages after the expiration of the heartbeat interval during a wait interval, where the wait interval indicates an interval of time before election of the new master node may commence during which the particular node may renew the leased state.

3. The computer-implemented method of claim 2, wherein the computer-implemented method further comprises:

receiving a response to a heartbeat message transmitted to the particular node of the set of nodes; and

resetting the current state to the leased state.

4. The computer-implemented method of claim 1, wherein transmitting the heartbeat messages further comprises ensuring the heartbeat messages are transmitted by only one node of the set of nodes of the data replication group.

5. A system, comprising:

one or more processors; and

memory that includes instructions that, as a result of being executed by the one or more processors, cause the system to;

during a first interval, transmit a set of heartbeat messages to individual nodes of a plurality of nodes of a data replication group, the plurality of nodes implementing a consensus protocol, where a current state corresponds to a role of master node being leased; and

in response to a failure to receive a set of responses to the set of heartbeat messages from a quorum of the plurality of nodes during a second interval;

modify the current state such that the current state indicates that the role of master node is expiring and no longer transmits heartbeat messages;

transmit, after a third interval, a set of election requests to the plurality of nodes.

6. The system of claim 5, wherein the instructions that cause the system to transmit the set of messages further include instructions that, as a result of being executed by the one or more processors, cause the system to transmit the set of messages based at least in part on a particular node of the plurality of nodes assigned the role of master node transmitting a message indicating the particular node has resigned the role of master node.

7. The system of claim 5, wherein each heartbeat message of the set of heartbeat messages includes at least a lease identification number and a ballot number, the lease identification number indicates a particular lease of the role of master node and the ballot number indicates a particular message.

8. The system of claim 5, wherein the instructions that cause the system to transmit the set of election requests further include instructions that, as a result of being executed by the one or more processors, cause the system to transmit the set of election requests in accordance with an election algorithm.

9. The system of claim 5, wherein the memory further includes instructions that, as a result of being executed by the one or more processors, cause the system to:

receive a response to a particular heartbeat message of the set of heartbeat messages during the second interval;

receive the set of responses from the quorum of nodes of the plurality of nodes; and

renew the lease of the role of master node.

10. The system of claim 5, wherein the memory further includes instructions that, as a result of being executed by the one or more processors, cause the system to transmit an election request to the plurality of nodes based at least in part on the expiration of a third interval.

11. The system of claim 10, wherein transmitting the election request further includes transmitting the election request as a result of the number of responses to the set of messages indicates that the quorum of nodes of the plurality of nodes share the current state indicating that the role of master node is expiring.

12. The system of claim 11, wherein the first interval is less than the second interval and the second interval is less than the third interval.

13. A set of one or more non-transitory computer-readable storage media having stored thereon executable instructions that, as a result of being executed by one or more processors of a computer system, cause the computer system to:

transmit a set of messages to a plurality of nodes of a data replication group, the plurality of nodes implementing a consensus protocol including at least one node having a role of master node of the data replication group, wherein receipt of a response from a quorum of the plurality of nodes during a first interval results in a renewal of a lease;

after not receiving a set of responses to the set of messages from a quorum of the plurality of nodes within a second interval, indicate that the lease of the role of master node is expiring; and

at the expiration of a third interval, select a node of the plurality of nodes to obtain the role of master node.

14. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the consensus protocol further comprises a Paxos consensus protocol.

15. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions that cause the computer system to transmit the set of messages further include instructions that cause the computer system to transmit the set of messages not in accordance with the consensus protocol.

16. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions that cause the computer system to transmit the set of messages further include instructions that cause the computer system to include a lease identification number in the set of messages.

17. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to generate a new lease identification number associated with the node of the plurality of nodes selected to obtain the role of master node.

18. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions that cause the computer system to select the node of the plurality of nodes to obtain the role of master node further include instructions that cause the computer system to select the node of the plurality of nodes based at least in part on a master node election algorithm.

19. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions that cause the computer system to select the node of the plurality of nodes to obtain the role of master node further include instructions that cause the computer system to select the node based at least in part on a quorum of the nodes indicating that the role of master node is expiring.

20. The set of one or more non-transitory computer-readable storage media of claim 13, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to receive a response to a particular message of the set of message messages during the second interval and causing the role of the master node to be renewed.