DYNAMIC REPLICA FAILURE DETECTION AND HEALING

• US 20160292249A1
• Filed: 04/04/2016
• Published: 10/06/2016
• Est. Priority Date: 06/13/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: HUNTER, BARRY BAILEY Jr., WANG, JIAN, VASANTH, JAI, MUNISWAMY-REDDY, KIRAN-KUMAR, LUTZ, DAVID ALAN, MACCANTI, MAXIMILIANO
• Granted Patent: US 9,971,823 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/006 Identification G06F11/2289 takes precedence
• CPC Class Codes: G06F 11/07 Responding to the occurrence of a fault, e.g. fault tolerance
• 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/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 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/86 Event-based monitoring
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

Detecting replica faults within a replica group and dynamically scheduling replica healing operations are described. Status metadata for one or more replica groups may be accessed. Based, at least in part, the status data a number of available replicas for at least one replica group may be determined to incompliant with a healthy state definition for the replica group. One or more healing operations to restore the number of available replicas for the at least one replica group to the respective healthy state definition may be dynamically scheduled. In some embodiments, one or more resource constraints for performing healing operations and one or more resource requirements for each of the one or more healing operations may be used to order the one or more healing operations.

Claims

1. A system, comprising:

a plurality of computing nodes, each comprising at least one processor and memory, wherein the plurality of computing nodes are configured to implement a data storage service,

wherein the data storage service comprises;

one or more replica groups stored among the plurality of computing nodes, wherein each of the one or more replica groups maintains one or more replicas of data on behalf of one or more storage service clients, wherein each replica group of the one or more replica groups includes a healthy state definition for the replica group;

a replica group status sweeper, configured to identify replica groups with a number of available replicas not compliant with the healthy state definition for the respective replica group, wherein said identification is based, at least in part, on status metadata for the respective replica group; and

a dynamic heal scheduler, configured to schedule one or more replica healing operations to restore the number of available replicas for the identified replica groups to the respective healthy state definition for the identified replica groups based, at least in part, on one or more resource constraints for performing healing operations

2. The system of claim 1, wherein the replica group status sweeper is further configured to:

update the status metadata within a table storing availability information for replicas of the one or more replica groups, wherein the table is stored on one or more of the computing nodes within the data storage service.

3. The system of claim 1, wherein to schedule one or more replica healing operations to restore the number of available replicas for the identified replica groups to their respective specified number of replicas, the dynamic heal scheduler is configured to:

identify the one or more resource constraints of the data storage service;

determine one or more resource requirements for each of the one or more replica healing operations; and

order the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations.

4. A method, comprising:

performing, by a plurality of computing devices;

accessing status metadata for one or more replica groups, wherein each of the one or more replica groups maintains one or more replicas of data, wherein each replica group of the one or more replica groups includes a healthy state definition for the replica group;

determining, based at least in part on the status metadata, that a number of available replicas for at least one replica group of the one or more replica groups is not compliant with the healthy state definition for the respective replica group; and

dynamically scheduling one or more replica healing operations to restore the number of available replicas for the at least one replica group to the respective healthy state definition for the at least one replica group based, at least in part, on one or more resource constraints for performing healing operations.

5. The method of claim 4, wherein each replica of a replica group of the one or more replica groups is stored on different ones of a plurality of compute nodes, and wherein the method further comprises:

receiving from one or more of the different ones of the plurality of computes nodes status information for the compute node; and

in response to receiving the status information for the compute node, updating the status metadata to reflect the received status information.

6. The method of claim 5, wherein the one or more of the different ones of the plurality of computes nodes is a master node of the different ones of the plurality of compute nodes, and wherein the status information is received periodically or aperiodically.

7. The method of claim 4, wherein each replica of a replica group of the one or more replica groups is stored on different ones of a plurality of compute nodes, and wherein said determining, based at least in part on the status metadata, that a number of available replicas for at least one replica group of the one or more replica groups is below the specified number of replicas for the respective replica group, comprises:

analyzing the status metadata to identify one or more compute nodes for status confirmation; and

requesting status information from the identified one or more compute nodes storing the given replica to confirm the status of the identified one or more compute nodes.

8. The method of claim 4, wherein said dynamically scheduling the one or more replica healing operations to restore the number of available replicas for the at least one replica group to the respective specified number of replicas, comprises:

identifying the one or more resource constraints for performing healing operations;

determining one or more resource requirements for each of the one or more replica healing operations; and

ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations.

9. The method of claim 8, wherein said ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations, comprises ordering the one or more replica healing operations according to replica access frequency of the one or more replica groups.

10. The method of claim 8,

wherein said determining the one or more resource requirements of each of the one or more replica healing operations comprises identifying a heal source and heal destination for the one or more replica healing operations;

wherein said ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations, comprises ordering the one or more replica healing operations based, at least in part, on the identified heal sources and the identified heal destinations for the one or more replica healing operations such that the ordering of the one or more replica healing operations does not exceed a healing conflict restraint.

11. The method of claim 8,

wherein said identifying the one or more resource constraints for performing healing operations comprises determining expected network traffic directed toward the one or more replica groups;

wherein said ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations, comprises ordering the one or more replica healing operations according to the expected network traffic directed toward the one or more replica groups.

12. A non-transitory, computer-readable storage medium, storing program instructions that when executed by a plurality of computing devices implement a data storage service that implements:

accessing status metadata for one or more replica groups, wherein each of the one or more replica groups maintains one or more replicas of data stored among a plurality of compute nodes implemented by the plurality of computing devices on behalf of one or more storage service clients, wherein each replica group of the one or more replica groups includes a healthy state definition for the respective replica group;

determining, based at least in part on the status metadata, that a number of available replicas for at least one replica group of the one or more replica groups is not compliant with the healthy state definition for the respective replica group; and

dynamically scheduling one or more replica healing operations to restore the number of available replicas for the at least one replica group to the respective healthy state definition for the at least one replica group based, at least in part, on one or more resource constraints for performing healing operations.

13. The non-transitory, computer-readable storage medium of claim 12, wherein the data storage service further implements:

automatically performing the scheduled one or more replica healing operations to restore the number of available replicas for the at least one replica group to the respective healthy state definition for the at least one replica group.

14. The non-transitory, computer-readable storage medium of claim 13, wherein said accessing, said determining, said dynamically scheduling, and said automatically performing are performed as part of a background process.

15. The non-transitory, computer-readable storage medium of claim 12, wherein different ones of the one or more replica groups include a different healthy state definition from other ones of the one or more replica groups.

16. The non-transitory, computer-readable storage medium of claim 12, wherein the healthy state definition included with the one or more replica groups comprises:

a specified number of replicas;

or

one or more specified compute node locations each including a respective specified number of replicas.

17. The non-transitory, computer-readable storage medium of claim 12, wherein the data storage service further implements:

receiving from one or more of the different ones of the plurality of computes nodes status information for the compute node; and

in response to receiving the status information for the compute node, updating the status metadata within a table storing availability information for replicas of the one or more replica groups.

18. The non-transitory, computer-readable storage medium of claim 12, wherein in said dynamically scheduling one or more replica healing operations to restore the number of available replicas for the at least one replica group to the respective specified number of replicas, the data storage service implements:

identifying the one or more resource constraints for performing healing operations;

determining one or more resource requirements for each of the one or more replica healing operations; and

ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations.

19. The non-transitory, computer-readable storage medium of claim 17, wherein in said ordering the one or more replica healing operations to be performed without exceeding the one or more resource constraints based, at least in part, on the one or more resource requirements for each of the one or more replica healing operations, the data storage service implements ordering the one or more replica healing operations according a load balancing scheme to distribute the one or more replica healing operations among the plurality of compute nodes.

20. The non-transitory, computer-readable storage medium of claim 19, wherein the one or more resource constraints comprise computational requirements, network bandwidth, storage requirements, or a quantity of parallel processes.

21. (canceled)