Prioritized leadership for data replication groups

• US 10,521,311 B1
• Filed: 06/30/2016
• Issued: 12/31/2019
• Est. Priority Date: 06/30/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Greenwood, Christopher Magee, Jain, Divya Ashok Kumar
• Primary Examiner(s): Le, Uyen T
• Application Number:
  US15/199,635
• Time in Patent Office: 1,279 Days
• Field of Search: None
• CPC Class Codes: G06F 11/0757 by exceeding a time limit, i.e. time-out, e.g. watchdogs
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2028 eliminating a faulty processor or activating a spare
• CPC Class Codes: G06F 11/2035 without idle spare hardware
• CPC Class Codes: G06F 11/2048 where the redundant components share neither address space nor persistent storage
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/24578 using ranking
• 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

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 group leadership and/or fitness information may be determined for each node of the set of nodes executing the consensus protocol. The fitness information may be based at least in part on information associated with computing resource in the distributed computing environment and one or more constraints on assignment of a role of master node in the data replication group. The master node may be responsible for advancing the data replication group.

Claims

1. A computer-implemented method, comprising:

obtaining host configuration information for a set of computing resources in a distributed computing environment, the set of computing resources containing at least one storage resource; and

generating a data replication group associated with the at least one storage resource by at least;

identifying a subset of computing resources of the set of computing resources for placement of a set of nodes of the data replication group;

determining a plurality of fitness scores based at least in part on the subset of computing resources and the host configuration information, the plurality of fitness scores comprising individual fitness scores for each node of the set of nodes of the data replication group;

causing the subset of computing resources to implement the set of nodes; and

providing the plurality of fitness scores to the set of nodes to cause the set of nodes to select a master node from the set of nodes in accordance with a consensus protocol such that an individual node of the set of nodes delays submitting a request to become the master node based at least in part on an individual fitness score of the individual node.

2. The computer-implemented method of claim 1, wherein the plurality of fitness scores form a ranking of the set of nodes of the data replication group, the ranking indicating a particular node to be selected as the master node prior to at least one other node of the set of nodes.

3. The computer-implemented method of claim 1, wherein the plurality of fitness scores comprises a value generated as a result of a fitness function to optimize a location of the master node among the subset of computing resources.

4. The computer-implemented method of claim 1, further comprising:

determining the master node is inaccessible based at least in part on an expiration of an interval of time without receiving a heartbeat message; and

causing the set of nodes to select a new master node based at least in part on the plurality of fitness scores.

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;

receive a request for a data replication group, the data replication group to be associated with a storage resource in a distributed environment;

determine a group of computer resources within a distributed computing environment to host a plurality of nodes of the data replication group;

determine fitness information for the plurality of nodes based at least in part on information associated with the group of computer resources and one or more constraints on assignment of a role of master node in the data replication group;

provision the plurality of nodes of the data replication group such that the role of master node is assigned to a particular node of the plurality of nodes based at least in part on the fitness information, wherein an individual node of the plurality of nodes delays submitting a request to become the master node based at least in part on respective fitness information of the individual node; and

fulfill the request by at least indicating the data replication group is ready.

6. 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 request for additional fitness information for at least a portion of the nodes of the plurality of nodes as a result of the particular nodes assigned the role of master node being inaccessible to at least one other node of the plurality of nodes.

7. The system of claim 6, wherein the memory further includes instructions that, as a result of being executed by the one or more processors, cause the system to determine the additional fitness information based at least in part on the portion of the nodes.

8. 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:

detect modification to the storage resource; and

determine additional fitness information based at least in part on the modification to the storage resource.

9. The system of claim 8, wherein the memory further includes instructions that, as a result of being executed by the one or more processors, cause the system to cause the plurality of nodes to assign a new node of the plurality of nodes the role of master node based at least in part on the additional fitness information.

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

determine an expected performance increase between the fitness information and the additional fitness information; and

wherein causing the plurality of nodes to assign the new node of the plurality of nodes the role of master node comprises assigning the new node of the plurality of nodes the role of master node if the expected performance is above a threshold.

11. 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 obtain information indicating a location of at least a portion of the computing resources of the group of computer resources in the distributed computing environment.

12. The system of claim 5, wherein the group of computer resources comprises at least one of:

a server, a rack of servers, a router, a switch, a networking device, a virtual computer system, a power source, or a data center.

13. A non-transitory computer-readable storage medium 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 at least:

determine one or more computing resources to implement a plurality of nodes of a data replication group, wherein the data replication group include metadata associated with storage resources;

determine fitness information for the plurality of nodes based at least in part on host configuration information, the host configuration information including information associated with the one or more computing resources and the fitness information indicating an optimization of a selection of a master node of the data replication group; and

cause, at least in part by providing the fitness information to the plurality of nodes, the plurality of nodes to select a leader node from the plurality of nodes in accordance with a consensus protocol such that an individual node of the plurality of nodes delays submitting a request to become the leader node based at least in part on individual fitness information of the individual node.

14. The non-transitory computer-readable storage medium 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 determine a threshold required to select a new master node.

15. The non-transitory computer-readable storage medium 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:

detect a modification to the host configuration information;

determine additional fitness information based at least in part on the modification to the host configuration information; and

provide the additional fitness information to the plurality of nodes.

16. The non-transitory computer-readable storage medium of claim 15, wherein the instructions further comprise instructions that, as a result of being executed by the one or more processors, cause the computer system to cause the plurality of nodes to elect a new master node based at least in part on the additional fitness information.

17. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine fitness information for the plurality of nodes further include instructions that cause the computer system to determine the optimization of the selection of the master node of the data replication group such that the master node is the shortest network distance to a particular computing resource of the one or more computing resources.

18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine fitness information for the plurality of nodes further include instructions that cause the computer system to determine the optimization of the selection of the master node of the data replication group such that the master node is within the same fault zone as a quorum of nodes of the plurality of nodes.

19. The non-transitory computer-readable storage medium 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, as a result of providing the fitness information, cause the plurality of nodes to select the master node.

20. The non-transitory computer-readable storage medium of claim 13, wherein the instructions that cause the computer system to determine fitness information for the plurality of nodes further include instructions that cause the computer system to determine an order in which each node of the plurality of nodes will attempt to elect itself as the master node.