Storage-network de-duplication

• US 9,558,201 B2
• Filed: 01/07/2014
• Issued: 01/31/2017
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Ben-Shaul, Israel Zvi, Vasetsky, Leonid
• Primary Examiner(s): Hershley, Mark E
• Assistant Examiner(s): Khong, Alexander
• Application Number:
  US14/149,762
• Publication Number:
  US 20140310250A1
• Time in Patent Office: 1,120 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/174 Redundancy elimination performed by the file system management of the data involved in backup or backup restore using de-duplication of the data G06F11/14
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

Techniques are provided for de-duplication of data. In one embodiment, a system comprises de-duplication logic that is coupled to a de-duplication repository. The de-duplication logic is operable to receive, from a client device over a network, a request to store a file in the de-duplicated repository using a single storage encoding. The request includes a file identifier and a set of signatures that identify a set of chunks from the file. The de-duplication logic determines whether any chunks in the set are missing from the de-duplicated repository and requests the missing chunks from the client device. Then, for each missing chunk, the de-duplication logic stores in the de-duplicated repository that chunk and a signature representing that chunk. The de-duplication logic also stores, in the de-duplicated repository, a file entry that represents the file and that associates the set of signatures with the file identifier.

Claims

1. A method comprising:

receiving a request to store a file in a de-duplicated repository of a management system, wherein the de-duplicated repository is stored on physical disk blocks that have a fixed size, and wherein the request includes an identifier of the file and a set of signatures that respectively identify a set of chunks from the file;

identifying a first chunk, from the set of chunks, that is not stored in the de-duplicated repository;

storing the first chunk and a first signature, from the set of signatures, that represents the first chunk in the de-duplicated repository, wherein the first chunk is generated as a variable-sized chunk based on the fixed size of the physical disk blocks such that each variable-sized chunk is no larger than the fixed size of the physical disk blocks; and

storing a second chunk and a second signature, from the set of signatures, that represents the second chunk in the de-duplicated repository, wherein the second chunk is generated such that a combined size of the first chunk and the second chunk is no larger than the fixed size of the physical disk blocks.

2. The method of claim 1, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, an unused portion of a respective physical disk block remains unused.

3. The method of claim 1, wherein the second chunk comprises a plurality of chunks;

and

generating a third signature for an aggregation of the plurality of chunks; and

storing the plurality of chunks and the third signature for the aggregation of the plurality of chunks in the de-duplicated repository.

4. The method of claim 1, further comprising receiving a second request to download the file, wherein the second request includes the identifier of the file;

looking up the identifier of the file in the de-duplicated repository to determine the file entry;

based on the file entry, retrieving a set of signatures that are associated with the identifier of the file, but not data from the file; and

in response to the second request, sending the set of signatures but not the file to a client device over the network.

5. The method of claim 1, further comprising:

receiving a second request to store a second file in the de-duplicated repository of the management system, wherein the second request includes a list of signatures that identify a plurality of chunks;

based on the list of signatures, determine a list of block identifiers of a plurality of physical disk blocks on which the plurality of chunks are stored;

sort the list of block identifiers; and

retrieve the plurality of chunks by accessing the plurality of physical disk blocks in an order indicated by the sorted list of block identifiers.

6. The method of claim 1, further comprising generating the variable-sized chunks in a manner that is further dependent on a predetermined overhead amount for each physical disk block, such that each variable-sized chunk is no larger than the fixed size minus the predetermined overhead amount.

18. The method of claim 1, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, storing a third chunk and a third signature, from the set of signatures, that represents the third chunk in the de-duplicated repository, wherein the third chunk is generated such that a combined size of the first chunk, the second chunk, and the third chunk is no larger than the fixed size of the physical disk blocks.

7. A system comprising:

a de-duplicated repository stored on physical disk blocks that have a fixed size; and

a processor programmed to;

receiving a request to store a file in the de-duplicated repository, the request including an identifier of the file and a set of signatures that respectively identify a set of chunks from the file;

identify a first chunk, from the set of chunks, that is not stored in the de-duplicated repository;

store the first chunk and a first signature, from the set of signatures, that represents the first chunk in the de-duplicated repository, wherein the first chunk is generated as a variable-sized chunk based on the fixed size of the physical disk blocks such that each variable-sized chunk is no larger than the fixed size of the physical disk blocks; and

store a second chunk and a second signature, from the set of signatures, that represents the second chunk in the de-duplicated repository, wherein the second chunk is generated such that a combined size of the first chunk and the second chunk is no larger than the fixed size of the physical disk blocks.

8. The system of claim 7, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, an unused portion of a respective physical disk block remains unused.

9. The system of claim 7, wherein the one or more second chunks comprises a plurality of chunks, and wherein the processor is further programmed to:

generate a third signature from the set of signatures for an aggregation of the plurality of chunks; and

store the plurality of chunks and the third signature for the aggregation of the plurality of chunks in the de-duplicated repository.

10. The system of claim 7, wherein the processor is further programmed to:

receive a second request to download the file, wherein the second request includes the identifier of the file;

look up the identifier of the file in the de-duplicated repository to determine the file entry;

based on the file entry, retrieve set of signatures that are associated with the identifier of the file, but not data from the file; and

in response to the second request, sending the set of signatures but not the file to a client device over the network.

11. The system of claim 7, wherein the processor is further programmed to:

receive a second request to store a second file in the de-duplicated repository of the management system, wherein the second request includes a list of signatures that identify a plurality of chunks;

based on the list of signatures, determine a list of block identifiers of a plurality of physical disk blocks on which the plurality of chunks are stored;

sort the list of block identifiers; and

retrieve the plurality of chunks by accessing the plurality of physical disk blocks in an order indicated by the sorted list of block identifiers.

19. The system of claim 7, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, store a third chunk and a third signature, from the set of signatures, that represents the third chunk in the de-duplicated repository, wherein the third chunk is generated such that a combined size of the first chunk, the second chunk, and the third chunk is no larger than the fixed size of the physical disk blocks.

12. One or more non-transitory storage media storing instructions that when executed by one or more processors, cause the one or more processors to:

receive a request to store a file in a de-duplicated repository of a management system, wherein the de-duplicated repository is stored on physical disk blocks that have a fixed size, and wherein the request includes an identifier of the file and a set of signatures that respectively identify a set of chunks from the file;

identify a first chunk, from the set of chunks, that is not stored in the de-duplicated repository;

store the first chunk and a first signature, from the set of signatures, that represents the first chunk in the de-duplicated repository, wherein the first chunk is generated as a variable-sized chunk based on the fixed size of the physical disk blocks such that each variable-sized chunk is no larger than the fixed size of the physical disk blocks; and

store a second chunk and a second signature, from the set of signatures, that represents the second chunk in the de-duplicated repository, wherein the second chunk is generated such that a combined size of the first chunk and the second chunk is no larger than the fixed size of the physical disk blocks.

13. The one or more non-transitory storage media of claim 12, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, an unused portion of a respective physical disk block remains unused.

14. The one or more non-transitory storage media of claim 12, wherein the one or more second chunks comprises a plurality of chunks;

and

generating a third signature from the set of signatures for an aggregation of the plurality of chunks; and

storing the plurality of chunks and the third signature for the aggregation of the plurality of chunks in the de-duplicated repository.

15. The one or more non-transitory storage media of claim 12, wherein the instructions further cause the one or more processors to:

receive a second request to download the file, wherein the second request includes the identifier of the file;

look up the identifier of the file in the de-duplicated repository to determine the file entry;

based on the file entry, retrieve a set of signatures that are associated with the identifier of the file, but not data from the file; and

in response to the second request, send the set of signatures but not the file to a client device over the network.

16. The one or more non-transitory storage media of claim 12, wherein the instructions further cause the one or more processors to:

receiving a second request to store a second file in the de-duplicated repository of the management system, wherein the second request includes a list of signatures that identify a plurality of chunks;

based on the list of signatures, determine a list of block identifiers of a plurality of physical disk blocks on which the plurality of chunks are stored;

sort the list of block identifiers; and

retrieve the plurality of chunks by accessing the plurality of physical disk blocks in an order indicated by the sorted list of block identifiers.

17. The one or more non-transitory storage media of claim 12, wherein the instructions further cause the one or more processors to generate the variable-sized chunks in a manner that is further dependent on a predetermined overhead amount for each physical disk block, such that each variable-sized chunk is no larger than the fixed size minus the predetermined overhead amount.

20. The one or more non-transitory storage media of claim 12, wherein if the combined size of the first chunk and the second chunk is smaller than the fixed size, store a third chunk and a third signature, from the set of signatures, that represents the third chunk in the de-duplicated repository, wherein the third chunk is generated such that a combined size of the first chunk, the second chunk, and the third chunk is no larger than the fixed size of the physical disk blocks.