Automated data recovery from remote data object replicas

Patent metadata

Field	Value
Publication number	US-10169159-B2
Application number	US-201514964050-A
Country	US
Kind code	B2
Filing date	Dec 9, 2015
Priority date	Oct 21, 2013
Publication date	Jan 1, 2019
Grant date	Jan 1, 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 one or more clusters and each cluster of the one or more clusters includes a respective plurality of compute nodes and the each cluster further includes a respective database that stores metadata specifying list of candidate clusters from which the one or more replicas can be recovered;
recording health information metadata that is within the database about said one or more replicas, wherein the health information comprises data about availability of a replica to participate in a restoration process;
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 that is 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 that is within the database for the one or more replicas; and
restoring the first data object from the one or more of the available replicas, based on querying the list of candidate clusters and further based on the calculated restoration-priority, wherein the query-priority is calculated based on a 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.

2. The method of claim 1 , wherein the restoration-priority is calculated based on a second function with parameters that represent at least one of:
number of replicas available for restoring the first data object in the distributed data storage system,
projected costs associated with losing M 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 restoration-priority is calculated based on a second priority function P(D)=Func(N(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;
H(D) i represents health of R(D) i at the time a recovery query is run, wherein ad-hoc information provided by a remote cluster may indicate that a replica is “Available” or “Unavailable”, for example;
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.

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

• H04L67/1097 Primary

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• G06F3/0647

  Migration mechanisms · CPC title

• G06F2201/85

  Active fault masking without idle spares · CPC title

• G06F3/067

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F11/2069

  Management of state, configuration or failover · CPC title