Storage and communication de-duplication

• US 8,799,467 B2
• Filed: 09/09/2011
• Issued: 08/05/2014
• Est. Priority Date: 09/09/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shah, Nilesh R., Barton, Tyler M., Nusca, Gianluigi, Rao, Ravi T.
• Primary Examiner(s): Meky, Moustafa M
• Application Number:
  US13/229,621
• Publication Number:
  US 20130067080A1
• Time in Patent Office: 1,061 Days
• Field of Search: 709200-203, 709217-227, 709/228, 709/229
• US Class Current: 709/225
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0613 in relation to throughput
• 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

Storage and communication de-duplication are described. In one or more implementations, a system comprises one or more modules that are implemented at least partially in hardware, the one or more modules configured to utilize one or more algorithms to calculate hashes of chunks of data, the hashes used to replace the chunks in the data for storage locally in the system as well as to communicate the hashes in response to a request received via a network for the data to avoid communicating at least one of the chunks of the data via the network.

Claims

1. A method implemented by a sending device, the method comprising:

prior to receiving a request to communicate a content item via a network, identifying one or more duplicate chunks of data from the content item by comparing data in the content item to previously stored data, wherein the one or more duplicate chunks of data from the content item are one or more chunks of data from the content item that match data that has been previously stored;

generating one or more identifiers for the one or more duplicate chunks of data, wherein each of the one or more identifiers are associated with respective ones of the one or more duplicate chunks of data;

storing the one or more identifiers;

storing the content item such that each of the stored one or more identifiers replace the respective identified ones of the one or more duplicate chunks of data, whereby each duplicate chunk of data is stored only once at the sending device; and

responsive to the request to communicate the data via a network, forming a communication to communicate via the network, the communication having the stored content item with the one or more identifiers associated with the one or more duplicate chunks of data, the one or more identifiers configured to be usable to identify whether the one or more duplicate chunks are available to a receiving device at least one of the group consisting of;

a local cache and a peer-to-peer network.

2. A method as described in claim 1, further comprising:

replacing the one or more identifiers with the respective ones of the one or more duplicate chunks of data when the data is not available locally to the receiving device; and

sending the one or more duplicate chunks of data to the receiving device.

3. A method as described in claim 1, wherein the one or more identifiers are hashes of the respective ones of the one or more duplicate chunks of data.

4. A method as described in claim 1, wherein at least one of the one or more identifiers included in the communication is usable by the receiving device to identify that a respective one of the one or more duplicate chunks of data is available locally to the receiving device.

5. A method as described in claim 4, wherein the identification is performed such that the respective one of the one or more duplicate chunks of data is not communicated from the sending device to the receiving device via the network.

6. A method as described in claim 1, wherein the network is a wide area network.

7. A method as described in claim 1, wherein at least one of the one or more duplicate chunks of data and the respective associated identifier are usable reconstruct another item of data.

8. A method as described in claim 1, wherein at least one of the one or more duplicate chunks of data is usable to replace communication of the at least one of the one or more chunks of data for another item of data.

9. A method as described in claim 1, further comprising identifying the one or more duplicate chunks of data using an algorithm, wherein the algorithm detects similarities between different items of content stored at the sending device.

10. A method as described in claim 1, further comprising identifying the one or more duplicate chunks of data using a Rabin chunking algorithm.

11. A method implemented by a receiving device, the method comprising:

receiving a communication via a network, the communication having a content item, stored at sender, with one or more identifiers associated with one or more chunks taken from data;

comparing the one or more identifiers from the communication to one or more identifiers of chunks that are available to the receiving device at a local cache;

responsive to a determination that at least one of the identifiers from the communication matches at least one of the identifiers of a corresponding chunk that is available to the receiving device at the local cache, replacing the at least one identifier with the corresponding chunk from the local cache;

responsive to a determination that at least one of the identifiers from the communication does not match at least one of the identifiers of a corresponding chunk that is available to the receiving device at the local cache, comparing the one or more identifiers from the communication to one or more identifiers of chunks that are available to the receiving device via a peer-to-peer network;

responsive to a determination that at least one of the identifiers from the communication matches at least one of the identifiers of a corresponding chunk that is available to the receiving device via a peer-to-peer network, replacing the at least one identifier with the corresponding chunk from the peer-to-peer network; and

responsive to a determination that at least one of the identifiers from the communication does not match at least one of the identifiers of a corresponding chunk that is available to the receiving device at the local cache or the peer-to-peer network, forming a communication to be communicated via the network to a sender of the communication to cause the sender to communicate the corresponding chunk via the network for receipt by the receiving device.

12. A method as described in claim 11, further comprising responsive to a request to access other data locally at the receiving device, replacing a first identifier of the other data with a first chunk that is available locally to the receiving device.

13. A method as described in claim 11, wherein the identifiers are hashes of respective chunks.

14. A method as described in claim 11, wherein the network is a wide area network, and the peer-to-peer network is a local area network.

15. A method as described in claim 11, wherein at least one of the chunks that are available locally to the receiving device is usable to reconstruct another item of data at the receiving device.

16. A method as described in claim 11, wherein at least one of the chunks that are available locally at the receiving device is usable replace communication of the at least one chunk for another item of data.

17. A sending device comprising:

a memory; and

at least one processor coupled to the memory, the at least one processor configured to;

prior to receiving a request to communicate a content item via a network, identify one or more duplicate chunks of data from the content item by comparing data in the content item to previously stored data, wherein the one or more duplicate chunks of data from the content item are one or more chunks of data from the content item that match data that has been previously stored;

generate one or more identifiers for the one or more duplicate chunks of data, wherein each of the one or more identifiers are associated with respective ones of the one or more duplicate chunks of data;

store the one or more identifiers;

store the content item and the one or more identifiers such that each of the one or more identifiers replace the respective ones of the one or more duplicate chunks of data, whereby each duplicate chunk of data is stored only once at the sending device; and

form a communication to communicate via a network, the communication having the stored content item with the one or more identifiers associated with the one or more duplicate chunks of data, the one or more identifiers configured to be usable to identify whether the one or more duplicated chunks are available to a receiving device at at least one of the group consisting of;

a local cache and a peer-to-peer network.

18. The sending device of claim 17, wherein the one or more identifiers are hashes of the respective ones of the one or more duplicate chunks of data.

19. The sending device of claim 17, wherein at least one of the one or more identifiers included in the communication is usable by the receiving device to identify that a respective one of the one or more duplicate chunks of data is available locally to the receiving device.

20. The sending device of claim 19, wherein the identification is performed such that the respective one of the one or more duplicate chunks of data is not communicated from the sending device to the receiving device via the network.