Automated data recovery from remote data object replicas

Patent metadata

Field	Value
Publication number	US-10216581-B2
Application number	US-201514964073-A
Country	US
Kind code	B2
Filing date	Dec 9, 2015
Priority date	Oct 21, 2013
Publication date	Feb 26, 2019
Grant date	Feb 26, 2019

Abstract

Machines, systems and methods for recovering data objects in a distributed data storage system, the method comprising storing one or more replicas of a first data object on one or more clusters in one or more data centers connected over a data communications network; recording health information about said one or more replicas, wherein the health information comprises data about availability of a replica to participate in a restoration process; calculating a query-priority for the first data object; querying, based on the calculated query-priority, the health information for the one or more replicas to determine which of the one or more replicas is available for restoration of the object data; calculating a restoration-priority for the first data object based on the health information for the one or more replicas; and restoring the first data object from the one or more of the available replicas, based on the calculated restoration-priority.

First claim

What is claimed is:

1. A method for recovering data objects in a distributed data storage system, the method comprising:
storing one or more replicas of a first data object on one or more clusters in one or more data centers connected over a data communications network, wherein a first data center of the one or more data centers includes a first cluster of the one or more clusters and the first cluster includes a plurality of compute nodes, the first cluster further includes a database that stores metadata concerning a replica of each data object of each of the plurality of compute nodes of the first cluster, a first compute node of the plurality of compute nodes includes the first data object, and wherein an availability status of the one or more replicas is maintained in the database at the first cluster per replica, and wherein the availability status is not maintained at the first compute node;
recording health information metadata about said one or more replicas within the database, wherein the health information comprises data about availability of a replica to participate in a restoration process;
determining that the first data object is faulty when at least one replica of the first data object is determined to be lost or damaged;
in response to determining that the first data object is faulty, determining that the first data object is to be recovered when a number of replicas of the first data object that are damaged or lost exceeds a threshold number of replicas;
in response to determining that the first data object is to be recovered, calculating a query-priority for the first data object;
querying, based on the calculated query-priority, the health information metadata within the database for the one or more replicas to determine which of the one or more replicas is available for restoration of the first data object;
calculating a restoration-priority for the first data object based on the health information metadata for the one or more replicas; and
restoring the first data object from the one or more of the available replicas, based on the calculated restoration-priority and based on the availability status, wherein the restoration-priority is calculated based on a priority function P(D)=Func(N(D),C(D),n), where:
D represents a data object with multiple replicas in multiple clusters;
N(D) represents number of remote replicas for which H(D) i is available;
C(D) represents cost of losing N replicas of D;
P(D) represents priority given by the system for the restoration operation of D; and
Func( )represents some function.

2. The method of claim 1 , wherein the query-priority is calculated based on a second function with parameters that represent at least one of:
number of replicas of the first data object in the distributed data storage system,
projected costs associated with losing N replicas of the first data object in the distributed data storage system, or
risk of loss associated with delaying recovery of the first data object over a second data object, wherein the risk of loss is calculated based on the number of replicas or the costs of loss associated with the first and second data objects.

3. The method of claim 1 , wherein the one or more data centers are located remotely from the location in which the first data object is being recovered.

4. The method of claim 1 , wherein the health information comprises availability and location data about the one or more replicas.

5. The method of claim 1 , wherein querying the health information of a plurality of data objects from a location is optimized by aggregating queries for at least a subset of the plurality of the data objects in a single query.

6. The method of claim 5 , wherein data objects in the subset of the plurality of the data objects in the single query are associated with the same query-priority.

7. The method of claim 1 , wherein the restoration of a plurality of data objects is optimized by restoring at least a subset of the plurality of the data objects from a location where a maximum collective number of the plurality of data objects have replicas, using a single restoration request.

8. The method of claim 7 , wherein data objects in the subset of the plurality of the data objects restored using a single restoration request are associated with the same restoration-priority.

9. The method of claim 1 , wherein the query-priority is calculated based on a second priority function P(D)=Func(R(D),C(D),n), where:
D represents a data object with multiple replicas in multiple clusters;
R(D i , i=1 . . n, where “i” and “n” are natural numbers, with a remote replica indexed i of D out of n remote replicas;
C(D) represents cost of losing N replicas of D;
P(D) represents priority given by the system for the query operation of D; and
Func( )represents some function.

10. The method of claim 1 , wherein the health information for the one or more replicas is recorded by a first cluster in a database accessible by a recovery module of the first cluster.

11. The method of claim 1 , wherein a first priority queue is used in the one or more clusters to record and prioritize one or more tasks for restoring one or more data objects such that:
a first task associated with priority set to be the first data object query-priority is inserted into the first priority queue to query the health information for the one or more replicas of the first data object from one or more locations, in response to determining that the first data object is to be recovered, and
a second task with priority set to be the first data object restoration-priority is inserted into the first priority queue to restore the first data object from the one or more available replicas in the one or more locations, in response to determining the restoration-priority for the first data object;
wherein the one or more tasks are extracted from the first priority queue and executed, such that a task with higher priority is executed before a task with lower priority.

12. The method of claim 11 , wherein given a first plurality of data objects with health information that is to be queried from the same location or have the same query-priority, optimizing the querying such that a first task for querying health information for a subset of one or more of the first plurality of data objects is inserted as a single task in the first priority queue.

13. The method of claim 11 , wherein given a second plurality of data objects that are to be restored from the same location or have the same restoration-priority, optimizing the restoring such that a second task for restoring a subset of one or more of the second plurality of data objects is inserted as a single task in the first priority queue.

Assignees

• IBM

Inventors

• Factor Michael E
• Hadas David
• Kolodner Elliot K

Classifications

• G06F11/1451 Primary

  by selection of backup contents · CPC title

• G06F3/0619

  in relation to data integrity, e.g. data losses, bit errors · CPC title

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F3/0647

  Migration mechanisms · CPC title

• G06F11/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 title