Storage-network de-duplication

• US 8,626,723 B2
• Filed: 10/13/2009
• Issued: 01/07/2014
• 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): Perveen, Rehana
• Assistant Examiner(s): Khong, Alexander
• Application Number:
  US12/578,485
• Publication Number:
  US 20100094817A1
• Time in Patent Office: 1,547 Days
• Field of Search: 707/650, 707/821, 707/692
• US Class Current: 707/692
• 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 system comprising:

one or more processors;

a de-duplicated repository of a storage management system, coupled to the one or more processors; and

a de-duplication logic of the storage management system, coupled to the one or more processors and to the de-duplicated repository, wherein the de-duplicated logic is operable to store files in the de-duplicated repository using a single storage encoding and to;

receive, from a client device over a network, a first request to store a file in the de-duplicated repository, wherein the first request includes an identifier of the file and a set of signatures that respectively identify a set of chunks from the file, wherein the client device is remote from the storage management system;

look up the set of signatures in the de-duplicated repository to determine whether any chunks in the set of chunks are not stored in the de-duplicated repository;

request, from the client device, those chunks from the set of chunks that are not stored in the de-duplicated repository;

for each chunk from the set of chunks that is not stored in the de-duplicated repository, store in the de-duplicated repository using the single storage encoding at least the chunk and a signature, from the set of signatures, that represents the chunk; and

store, in the de-duplicated repository, a file entry that represents the file and that associates the set of signatures with the identifier of the file,

wherein the de-duplicated repository is stored on physical disk blocks that have a fixed size, and wherein the set of chunks are generated using a fingerprinting logic that is configured to generate variable-sized chunks in a manner that is dependent on the fixed size, such that each variable-sized chunk is no larger than the fixed size.

2. The system as recited in claim 1, wherein the de-duplication logic is further operable to:

receive, from the client device over the network, 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 the 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 the client device over the network.

3. The system as recited in claim 2, wherein the de-duplication logic is further operable to:

receive a third request from the client device over the network, wherein the third request includes one or more signatures that respectively identify one or more chunks that are not stored at the client device;

look up the one or more signatures in the de-duplicated repository to determine the one or more chunks identified in the third request; and

send the one or more chunks identified in the third request to the client device over the network.

4. The system as recited in claim 1, wherein the de-duplication logic is further operable to:

increment first one or more reference counts that are respectively associated with those first one or more chunks, from the set of chunks, that were already stored in the de-duplicated repository; and

initialize second one or more reference counts that are respectively associated with those second one or more chunks, from the set of chunks, that were not previously stored in the de-duplicated repository.

5. The system as recited in claim 1, wherein the set of chunks have varying lengths, and wherein the fingerprinting logic determines chunk boundaries based on the content of the file.

6. The system as recited in claim 1, wherein the de-duplicated repository comprises a file system structure and a store structure, wherein the file system structure is configured to store the identifier of the file and the file entry, and wherein the store structure is configured to store the set of signatures and the set of chunks.

7. The system as recited in claim 6, wherein the de-duplication logic is further operable to:

generate one or more metadata chunks for the file by applying the fingerprinting logic to metadata information associated with the file;

compute one or more metadata signatures respectively for the one or more metadata chunks;

store, in the store structure, the one or more metadata chunks and the one or more metadata signatures; and

store, in the file entry that represents the file in the file system structure, data that associates the one or more metadata signatures with the identifier of the file.

8. The system as recited in claim 6, wherein the store structure is organized in a plurality of hierarchical levels, and wherein signatures at each of the hierarchical levels are keyed based on a subset of the signatures'"'"' bits.

9. The system as recited in claim 6, wherein the de-duplication logic further includes a programming interface that is operable to look up signatures directly into the store structure to find corresponding chunks.

10. The system as recited in claim 1, wherein the de-duplication logic is further operable to:

receive a second request from the client device over the network, wherein the second request includes a list of signatures that identify a plurality of chunks that need to be sent to the client device;

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 the order indicated by the sorted list of block identifiers.

11. The system as recited in claim 1, wherein the de-duplication logic is operable to determine whether any chunks in the set of chunks are not stored in the de-duplicated repository by looking up the set of signatures in a negative-cache bitmap.

12. The system as recited in claim 1, wherein the de-duplication logic is further operable to:

receive a new file for storing into the de-duplicated repository;

store the new file in temporary storage;

concurrently with storing the new file in the de-duplicated repository using the single storage encoding, compute on-the-fly a file-level signature from the new file as chunks of the new file are being processed for storing in the de-duplicated repository; and

after the new file is stored in the de-duplicated repository, store the file-level signature in the de-duplicated repository without accessing the new file in the temporary storage.

13. The system as recited in claim 1, wherein the de-duplication logic is further operable to, prior to receiving the first request to store the file:

receive, from the client device, the identifier of the file and a file-level signature that identifies the file;

look up the file-level signature in the de-duplicated repository;

if a match for the file-level signature is found, then store the file entry that represents the file in the de-duplicated repository, wherein the file entry associates the file-level signature with the identifier of the file; and

if a match for the file-level signature is not found, then send a request to the client device requesting that the client device send the first request.

14. The system as recited in claim 1, wherein the de-duplication logic is further operable to:

receive, from the client device over the network, 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 file-level signature that is associated with the identifier of the file, but not data from the file; and

in response to the second request, send the file-level signature but not the file to the client device over the network,

wherein the download of the file is completed if the client device finds a match for the file-level signature in a local repository that stores file-level signatures and associates the file-level signatures with files stored on the client device.

33. The system of claim 1, wherein the fingerprinting logic is configured 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.

15. One or more non-transitory storage media storing instructions executable by one or more computing devices, the instructions comprising:

instructions that cause the one or more computing devices to receive, from a client device over a network, a first request to store a file in a de-duplicated repository of a storage management system, using a single storage encoding, wherein the first request includes an identifier of the file and a set of signatures that respectively identify a set of chunks from the file, wherein the client device is remote from the storage management system;

instructions that cause the one or more computing devices to look up the set of signatures in the de-duplicated repository to determine whether any chunks in the set of chunks are not stored in the de-duplicated repository;

instructions that cause the one or more computing devices to request, from the client device, those chunks from the set of chunks that are not stored in the de-duplicated repository;

for each chunk from the set of chunks that is not stored in the de-duplicated repository, instructions that cause the one or more computing devices to store in the de-duplicated repository using the single storage encoding at least the chunk and a signature, from the set of signatures, that represents the chunk; and

instructions that cause the one or more computing devices to store, in the de-duplicated repository, a file entry that represents the file and that associates the set of signatures with the identifier of the file,

wherein the de-duplicated repository is stored on physical disk blocks that have a fixed size, and wherein the set of chunks are generated using a fingerprinting logic that is configured to generate variable-sized chunks in a manner that is dependent on the fixed size, such that each variable-sized chunk is no larger than the fixed size.

16. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise:

instructions that cause the one or more computing devices to receive, from the client device over the network, a second request to download the file, wherein the second request includes the identifier of the file;

instructions that cause the one or more computing devices to look up the identifier of the file in the de-duplicated repository to determine the file entry;

instructions that cause the one or more computing devices to retrieve, based on the file entry, the set of signatures that are associated with the identifier of the file, but not data from the file; and

instructions that cause the one or more computing devices to send, in response to the second request, the set of signatures but not the file to the client device over the network.

17. The one or more non-transitory storage media as recited in claim 16, wherein the instructions further comprise:

instructions that cause the one or more computing devices to receive a third request from the client device over the network, wherein the third request includes one or more signatures that respectively identify one or more chunks that are not stored at the client device;

instructions that cause the one or more computing devices to look up the one or more signatures in the de-duplicated repository to determine the one or more chunks identified in the third request; and

instructions that cause the one or more computing devices to send the one or more chunks identified in the third request to the client device over the network.

18. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise:

instructions that cause the one or more computing devices to increment first one or more reference counts that are respectively associated with those first one or more chunks, from the set of chunks, that were already stored in the de-duplicated repository; and

instructions that cause the one or more computing devices to initialize second one or more reference counts that are respectively associated with those second one or more chunks, from the set of chunks, that were not previously stored in the de-duplicated repository.

19. The one or more non-transitory storage media as recited in claim 15, wherein the set of chunks have varying lengths, and wherein the fingerprinting logic determines chunk boundaries based on the content of the file.

20. The one or more non-transitory storage media as recited in claim 15, wherein the de-duplicated repository comprises a file system structure and a store structure, wherein the file system structure is configured to store the identifier of the file and the file entry, and wherein the store structure is configured to store the set of signatures and the set of chunks.

21. The one or more non-transitory storage media as recited in claim 20, wherein the instructions further comprise:

instructions that cause the one or more computing devices to generate one or more metadata chunks for the file by applying the fingerprinting logic to metadata information associated with the file;

instructions that cause the one or more computing devices to compute one or more metadata signatures respectively for the one or more metadata chunks;

instructions that cause the one or more computing devices to store, in the store structure, the one or more metadata chunks and the one or more metadata signatures; and

instructions that cause the one or more computing devices to store, in the file entry that represents the file in the file system structure, data that associates the one or more metadata signatures with the identifier of the file.

22. The one or more non-transitory storage media as recited in claim 20, wherein the store structure is organized in a plurality of hierarchical levels, and wherein signatures at each of the hierarchical levels are keyed based on a subset of the signatures'"'"' bits.

23. The one or more non-transitory storage media as recited in claim 20, wherein the instructions further comprise instructions that cause the one or more computing devices to provide a programming interface that is operable to look up signatures directly into the store structure to find corresponding chunks.

24. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise:

instructions that cause the one or more computing devices to receive a second request from the client device over the network, wherein the second request includes a list of signatures that identify a plurality of chunks that need to be sent to the client device;

instructions that cause the one or more computing devices to determine, based on the list of signatures, a list of block identifiers of a plurality of physical disk blocks on which the plurality of chunks are stored;

instructions that cause the one or more computing devices to sort the list of block identifiers; and

instructions that cause the one or more computing devices to retrieve the plurality of chunks by accessing the plurality of physical disk blocks in the order indicated by the sorted list of block identifiers.

25. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise instructions that cause the one or more computing devices to determine whether any chunks in the set of chunks are not stored in the de-duplicated repository by looking up the set of signatures in a negative-cache bitmap.

26. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise:

instructions that cause the one or more computing devices to receive a new file for storing into the de-duplicated repository;

instructions that cause the one or more computing devices to store the new file in temporary storage;

concurrently with storing the new file in the de-duplicated repository using the single storage encoding, instructions that cause the one or more computing devices to compute on-the-fly a file-level signature from the new file as chunks of the new file are being processed for storing in the de-duplicated repository; and

after the new file is stored in the de-duplicated repository, instructions that cause the one or more computing devices to store the file-level signature in the de-duplicated repository without accessing the new file in the temporary storage.

27. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise, prior to receiving the first request to store the file:

instructions that cause the one or more computing devices to receive, from the client device, the identifier of the file and a file-level signature that identifies the file;

instructions that cause the one or more computing devices to look up the file-level signature in the de-duplicated repository;

if a match for the file-level signature is found, instructions that cause the one or more computing devices to store the file entry that represents the file in the de-duplicated repository, wherein the file entry associates the file-level signature with the identifier of the file; and

if a match for the file-level signature is not found, instructions that cause the one or more computing devices to send a request to the client device requesting that the client device send the first request.

28. The one or more non-transitory storage media as recited in claim 15, wherein the instructions further comprise:

instructions that cause the one or more computing devices to receive, from the client device over the network, a second request to download the file, wherein the second request includes the identifier of the file;

instructions that cause the one or more computing devices to look up the identifier of the file in the de-duplicated repository to determine the file entry;

instructions that cause the one or more computing devices to retrieve, based on the file entry, a file-level signature that is associated with the identifier of the file, but not data from the file; and

instructions that cause the one or more computing devices to send, in response to the second request, the file-level signature but not the file to the client device over the network,

wherein the download of the file is completed if the client device finds a match for the file-level signature in a local repository that stores file-level signatures and associates the file-level signatures with files stored on the client device.

29. A method comprising:

receiving, from a client device over a network, a first request to store a file in a de-duplicated repository of a storage management system, using a single storage encoding, wherein the first request includes an identifier of the file and a set of signatures that respectively identify a set of chunks from the file, and wherein the client device is remote from the storage management system;

looking up the set of signatures in the de-duplicated repository to determine whether any chunks in the set of chunks are not stored in the de-duplicated repository;

requesting, from the client device, those chunks from the set of chunks that are not stored in the de-duplicated repository;

for each chunk from the set of chunks that is not stored in the de-duplicated repository, storing in the de-duplicated repository using the single storage encoding at least the chunk and a signature, from the set of signatures, that represents the chunk; and

storing, in the de-duplicated repository, a file entry that represents the file and that associates the set of signatures with the identifier of the file,

wherein the de-duplicated repository is stored on physical disk blocks that have a fixed size, and wherein the set of chunks are generated using a fingerprinting logic that is configured to generate variable-sized chunks in a manner that is dependent on the fixed size, such that each variable-sized chunk is no larger than the fixed size.

30. The method of claim 29, further comprising:

receiving, from the client device over the network, 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 the 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 the client device over the network.

31. The method of claim 30, further comprising:

receiving a third request from the client device over the network, wherein the third request includes one or more signatures that respectively identify one or more chunks that are not stored at the client device;

looking up the one or more signatures in the de-duplicated repository to determine the one or more chunks identified in the third request; and

sending the one or more chunks identified in the third request to the client device over the network.

32. The method of claim 29, further comprising:

incrementing first one or more reference counts that are respectively associated with those first one or more chunks, from the set of chunks, that were already stored in the de-duplicated repository; and

initializing second one or more reference counts that are respectively associated with those second one or more chunks, from the set of chunks, that were not previously stored in the de-duplicated repository.