Processing a request to restore deduplicated data

• US 8,904,128 B2
• Filed: 06/08/2011
• Issued: 12/02/2014
• Est. Priority Date: 06/08/2011
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Lillibridge, Mark David
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): DOAN, HAN V
• Application Number:
  US13/155,566
• Publication Number:
  US 20120317359A1
• Time in Patent Office: 1,273 Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache

Abstract

For a restore request, at least a portion of a recipe that refers to chunks is read. Based on the recipe portion, a container having plural chunks is retrieved. From the recipe portion, it is identified which of the plural chunks of the container to save, where some of the chunks identified do not, at a time of the identifying, have to be presently communicated to a requester. The identified chunks are stored in a memory area from which chunks are read for the restore operation.

Claims

1. A method comprising:

receiving, from a requester, a request to restore data stored in a storage subsystem, wherein the data stored in the storage subsystem includes deduplicated data;

in response to the request,

reading at least a portion of a recipe that refers to chunks in the deduplicated data;

based on the recipe portion, retrieving a first container having plural chunks;

identifying, from the recipe portion, which of the plural chunks of the first container to save, wherein some of the identified chunks do not, at a time of the identifying, have to be presently communicated to the requester for a restore operation specified by the request;

determining locations in a memory area to place the identified chunks, wherein the determined locations are based on an order of chunks referred to in the recipe portion;

storing the identified chunks in the determined locations of the memory area from which chunks are read as the restore operation proceeds, wherein storing the identified chunks in the determined locations results in at least one empty chunk spot between at least two of the identified chunks;

retrieving, based on the recipe portion, a second container having plural chunks;

identifying, from the recipe portion, which of the plural chunks of the second container to save to the memory area; and

storing the identified chunks of the second container in the memory area, at least one of the identified chunks of the second container stored in the empty chunk spot.

2. The method of claim 1, wherein the memory area has a predefined size.

3. The method of claim 1, wherein adjacent chunks in the recipe portion have adjacent locations in the memory area.

4. The method of claim 1, wherein the memory area includes a ring buffer, the method further comprising:

shifting a beginning point of the ring buffer as chunks are read out of the ring buffer in the restore operation.

5. The method of claim 1, further comprising:

assigning locations and space in the memory area to chunk references of the recipe portion, wherein some of the chunk references are allocated zero space.

6. The method of claim 1, wherein storing the identified chunks in the memory area comprises storing the identified chunks in a cache, the method further comprising:

using the recipe portion to determine which chunk in the cache to evict to provide space for storing another chunk.

7. The method of claim 6, wherein determining which chunk in the cache to evict is based in part on an order in which each chunk will have to be communicated to the requester by the restore operation.

19. The method of claim 1, wherein the chunks referred to in the recipe portion are chunks from multiple containers, and wherein the retrieved first container is one of the multiple containers selected for retrieval based on the recipe portion.

8. A system comprising:

non-transitory storage media to store a data store including containers containing respective chunks that are part of deduplicated data; and

at least one processor to;

in response to a restore request, received from a requester, specifying a restore operation, read a portion of a recipe that refers to chunks in the data store;

retrieve, based on the recipe portion, a first one of the containers that has plural chunks;

identify, from the recipe portion, which of the plural chunks of the first container to save, wherein some of the identified chunks do not, at a time of the identifying, have to be presently communicated to the requester for the restore operation specified by the restore request;

determine locations in a memory area to place the identified chunks, wherein the determined locations are based on an order of chunks referred to in the recipe portion;

store the identified chunks in the determined locations of the memory area from which chunks are read for the restore operation, wherein storing the identified chunks in the determined locations results in at least one empty chunk spot between at least two of the identified chunks;

retrieve, based on the recipe portion, a second of the containers having plural chunks;

identify, from the recipe portion, which of the plural chunks of the second container to save to the memory area; and

store the identified chunks of the second container in the memory area, at least one of the identified chunks of the second container stored in the empty chunk spot.

9. The system of claim 8, wherein chunk references of the recipe portion are to be allocated locations and space in the memory area according to an order of the chunk references.

10. The system of claim 9, wherein the identified chunks are to be stored at locations in the memory area corresponding to locations allocated for the identified chunks.

11. The system of claim 8, wherein the memory area is a ring buffer having a beginning point, wherein the at least one processor is to write out a beginning portion of contiguous one or multiple chunks adjacent to the beginning point upon the contiguous one or multiple chunks being saved in the memory area.

12. The system of claim 11, wherein the at least one processor is to shift the beginning point of the ring buffer in response to the beginning portion being written out.

13. The system of claim 11, wherein locations and space in the memory area are to be assigned to chunk references of the recipe portion, and wherein some of the chunk references of the recipe portion are allocated zero space.

14. The system of claim 13, wherein the some of the chunks referenced by chunk references allocated zero space are to be written out to the requester without first saving them to the memory area.

15. The system of claim 8, wherein the memory area comprises a cache, and wherein the at least one processor is to evict chunks from the cache based on content of the recipe portion.

16. The system of claim 15, wherein the identified chunks will be used by the requester according to the recipe portion before the evicted chunks.

20. The system of claim 8, wherein the chunks referred to in the recipe portion are chunks from multiple containers of the containers included in the data store, and wherein the at least one processor is to select the first container from among the multiple containers for retrieval, based on the recipe portion.

17. An article comprising at least one non-transitory machine-readable storage medium storing instructions that upon execution cause a system to:

receive, from a requester, a request to restore data stored in a storage subsystem, wherein the data stored in the storage subsystem includes deduplicated data;

in response to the request,

read at least a portion of a recipe that refers to chunks in the deduplicated data, wherein the chunks referred to in the recipe portion are chunks from multiple containers;

based on the recipe portion, select a first one of the multiple containers to retrieve;

retrieve the first container having plural chunks;

identify, from the recipe portion, which of the plural chunks of the first container to save, wherein some of the identified chunks do not, at a time of the identifying, have to be presently communicated to the requester for a restore operation specified by the request;

determine locations in a memory area to place the identified chunks, wherein the determined locations are based on an order of chunks referred to in the recipe portion;

store the identified chunks in the memory area from which chunks are read as the restore operation proceeds, wherein storing the identified chunks in the determined locations results in at least one empty chunk spot between at least two of the identified chunks;

after storing the identified chunks in the memory area, select a second one of the multiple containers based on the recipe portion; and

reiterating the retrieving, the identifying, and the storing for the second container, wherein the storing for the second container comprises storing a data chunk of the second container in the empty chunk spot of the memory area.

18. The article of claim 17,

wherein an order of retrieving containers for processing a response to the request is based on a sequence of the chunks referred to in the recipe portion.