Optimizing restoration of deduplicated data

Patent metadata

Field	Value
Publication number	US-9329942-B2
Application number	US-201414334814-A
Country	US
Kind code	B2
Filing date	Jul 18, 2014
Priority date	Sep 12, 2012
Publication date	May 3, 2016
Grant date	May 3, 2016

Abstract

A computer identifies a plurality of data retrieval requests that may be serviced using a plurality of unique data chunks. The computer services the data retrieval requests by utilizing at least one of the unique data chunks. At least one of the unique data chunks is utilized for servicing two or more of the data retrieval requests. The computer determines a servicing sequence for the plurality of data retrieval requests such that the two or more of the data retrieval requests that are serviced utilizing the at least one of the unique data chunks are serviced consecutively. The computer services the plurality of data retrieval requests according to the servicing sequence.

First claim

What is claimed is:

1. A method comprising the steps of:
a first computing device identifying a plurality of data retrieval requests for servicing with a plurality of unique data chunks, wherein each data retrieval request is serviced utilizing at least one of the unique data chunks, and wherein at least a first unique data chunk is utilized for the servicing of both a first data retrieval request and a second data retrieval request;
the first computing device determining a servicing sequence of the plurality of data retrieval requests such that the first and the second data retrieval requests are serviced consecutively; and
the first computing device servicing the plurality of data retrieval requests according to the servicing sequence;
wherein:
determining the servicing sequence is based, at least in part, on determining that the first unique data chunk is common to servicing both the first and the second data retrieval requests;
determining the servicing sequence is based, at least in part, on using a relationship graph, which the relationship graph including nodes and edges connecting the nodes, and which each edge having a weight;
each node of the relationship graph corresponds to a data retrieval request of the plurality of data retrieval requests; and
the weight of an edge connecting two nodes is based, at least in part, on a measure of data common to servicing the data retrieval requests corresponding to the two nodes.

2. The method of claim 1 wherein the measure of data is based, at least in part, on whether and/or how many unique data chunks are common to servicing the data retrieval requests corresponding to the two nodes.

3. The method of claim 1 wherein the measure of data is based, at least in part, on the total size of the unique data chunks common to servicing the data retrieval requests corresponding to the two nodes.

4. The method of claim 1 wherein using the relationship graph includes determining a relationship score for each node in the relationship graph.

5. The method of claim 4 wherein the relationship score for a node is based, at least in part, on total edge weight of all edges of the node.

6. The method of claim 4 wherein:
a node having a relationship score at least as high as any other node in the relationship graph is designated a root node and inserted into the servicing sequence;
the relationship graph is searched in a substantially breadth-first fashion beginning at the root node; and
each node's neighboring node not already in the servicing sequence is inserted into the servicing sequence in descending order of each node's relationship score.

7. A computer program product comprising:
one or more computer-readable hardware storage device(s) and program instructions stored on the one or more computer-readable hardware storage device(s), the program instructions comprising:
program instructions to identify a plurality of data retrieval requests for servicing with a plurality of unique data chunks, wherein each data retrieval request is serviced utilizing at least one of the unique data chunks, and wherein at least a first unique data chunk is utilized for the servicing of both a first data retrieval request and a second data retrieval request;
program instructions to a servicing sequence of the plurality of data retrieval requests such that the first and the second data retrieval requests are serviced consecutively; and
program instructions to service the plurality of data retrieval requests according to the servicing sequence;
wherein:
determining the servicing sequence is based, at least in part, on determining that the first unique data chunk is common to servicing both the first and the second data retrieval requests;
determining the servicing sequence is based, at least in part, on using a relationship graph, which the relationship graph including nodes and edges connecting the nodes, and which each edge having a weight;
each node of the relationship graph corresponds to a data retrieval request of the plurality of data retrieval requests; and
the weight of an edge connecting two nodes is based, at least in part, on a measure of data common to servicing the data retrieval requests corresponding to the two nodes.

8. The product of claim 7 wherein the measure of data is based, at least in part, on whether and/or how many unique data chunks are common to servicing the data retrieval requests corresponding to the two nodes.

9. The product of claim 7 wherein the measure of data is based, at least in part, on the total size of the unique data chunks common to servicing the data retrieval requests corresponding to the two nodes.

10. The product of claim 7 wherein using the relationship graph includes determining a relationship score for each node in the relationship graph.

11. The product of claim 10 wherein the relationship score for a node is based, at least in part, on total edge weight of all edges of the node.

12. The product of claim 10 wherein:
a node having a relationship score at least as high as any other node in the relationship graph is designated a root node and inserted into the servicing sequence;
the relationship graph is searched in a substantially breadth-first fashion beginning at the root node; and
each node's neighboring node not already in the servicing sequence is inserted into the servicing sequence in descending order of each node's relationship score.

13. A computer system comprising:
one or more computer processors;
one or more computer-readable storage media;
program instructions stored on the computer-readable storage media for execution by at least one of the one or more processors, the program instructions comprising:
program instructions to identify a plurality of data retrieval requests for servicing with a plurality of unique data chunks, wherein each data retrieval request is serviced utilizing at least one of the unique data chunks, and wherein at least a first unique data chunk is utilized for the servicing of both a first data retrieval request and a second data retrieval request;
program instructions to a servicing sequence of the plurality of data retrieval requests such that the first and the second data retrieval requests are serviced consecutively; and
program instructions to service the plurality of data retrieval requests according to the servicing sequence;
wherein:
determining the servicing sequence is based, at least in part, on determining that the first unique data chunk is common to servicing both the first and the second data retrieval requests;
determining the servicing sequence is based, at least in part, on using a relationship graph, which the relationship graph including nodes and edges connecting the nodes, and which each edge having a weight;
each node of the relationship graph corresponds to a data retrieval request of the plurality of data retrieval requests; and
the weight of an edge connecting two nodes is based, at least in part, on a measure of data common to servicing the data retrieval requests corresponding to the two nodes.

14. The system of claim 13 wherein the measure of data is based, at least in part, on whether and/or how many unique data chunks are common to servicing the data retrieval requests corresponding to the two nodes.

15. The system of claim 13 wherein the measure of data is based, at least in part, on the total size of the unique data chunks common to servicing the data retrieval requests corresponding to the two nodes.

16. The system of claim 13 wherein using the relationship graph includes determining a relationship score for eac

Assignees

• IBM

Inventors

• Chavda Kavita
• Mandagere Nagapramod S
• Routray Ramani R
• Zhou Pin

Classifications

• G06F17/30194

  Physics · mapped topic

• G06F17/3015

  Physics · mapped topic

• G06F11/1453 Primary

  using de-duplication of the data · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title