Combining Hash-Based Duplication with Sub-Block Differencing to Deduplicate Data

• US 20110238635A1
• Filed: 03/25/2010
• Published: 09/29/2011
• Est. Priority Date: 03/25/2010
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Leppard, Andrew C.
• Granted Patent: US 8,442,942 B2
• Time in Patent Office: Days
• US Class Current: 707/693
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

In one embodiment, a method includes accessing data; partitioning the data into sub-blocks; determining whether a first one of the sub-blocks is identical to another one of the sub-blocks or similar to another one of the sub-blocks; if the first one of the sub-blocks is identical to another one of the sub-blocks, applying by the one or more computer systems hash-based deduplication to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks; and, if the first one of the sub-blocks is similar to another one of the sub-blocks, applying by the one or more computer systems sub-block differencing to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks.

Claims

1. A method comprising, by one or more computer systems:

accessing data;

partitioning the data into a plurality of sub-blocks;

determining whether a first one of the sub-blocks is identical to another one of the sub-blocks or similar to another one of the sub-blocks;

if the first one of the sub-blocks is identical to another one of the sub-blocks, applying hash-based deduplication to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks; and

if the first one of the sub-blocks is similar to another one of the sub-blocks, applying sub-block differencing to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks.

2. The method of claim 1, further comprising, by the one or more computer systems, storing the first one of the sub-blocks.

3. The method of claim 2, wherein applying sub-block differencing to storage of the first one of the sub-blocks if the first one of the sub-blocks is similar to another one of the sub-blocks comprises:

determining a difference between the first one of the sub-blocks and the other one of the sub-blocks;

storing the difference so that the first one of the sub-blocks can be reconstructed from the other one of the-blocks and the difference.

4. The method of claim 3, wherein the difference comprises one or more block segments that are in both the first one of the sub-blocks and the other one of the sub-blocks.

5. The method of claim 1, further comprising, by the one or more computer systems:

determining whether the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks; and

if the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks, applying sub-block differencing to storage of the first one of the sub-blocks with respect to the set of two or more other ones of the sub-blocks.

6. The method of claim 1, wherein:

the sub-blocks comprise sub-block data; and

determining whether the first one of the sub-blocks is identical to another one of the sub-blocks comprises;

using a strong hash function to calculate hash values representing the sub-block data; and

comparing the hash value representing the sub-block data in the first one of the sub-block with the hash values representing the sub-block data in other ones of the sub-blocks.

7. The method of claim 1, wherein determining whether the first one of the sub-blocks is similar to another one of the sub-blocks comprises:

determining interesting locations in the first one of the sub-blocks and one or more other ones of the sub-blocks;

calculating fingerprints of the data at the interesting locations using a hash function; and

comparing the fingerprints with each other.

8. One or more computer-readable storage media embodying instructions that are operable when executed by one or more computer systems to:

access data;

partition the data into a plurality of sub-blocks;

determine whether a first one of the sub-blocks is identical to another one of the sub-blocks or similar to another one of the sub-blocks;

if the first one of the sub-blocks is identical to another one of the sub-blocks, apply hash-based deduplication to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks; and

if the first one of the sub-blocks is similar to another one of the sub-blocks, apply sub-block differencing to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks.

9. The media of claim 8, wherein the instructions are further operable to store the first one of the sub-blocks.

10. The media of claim 9, wherein applying sub-block differencing to storage of the first one of the sub-blocks if the first one of the sub-blocks is similar to another one of the sub-blocks comprises:

determining a difference between the first one of the sub-blocks and the other one of the sub-blocks;

storing the difference so that the first one of the sub-blocks can be reconstructed from the other one of the-blocks and the difference.

11. The media of claim 10, wherein the difference comprises one or more block segments that are in both the first one of the sub-blocks and the other one of the sub-blocks.

12. The media of claim 8, wherein the instructions are further operable to:

determine whether the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks; and

if the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks, apply sub-block differencing to storage of the first one of the sub-blocks with respect to the set of two or more other ones of the sub-blocks

13. The media of claim 8, wherein:

the sub-blocks comprise sub-block data; and

determining whether the first one of the sub-blocks is identical to another one of the sub-blocks comprises;

using a strong hash function to calculate hash values representing the sub-block data; and

comparing the hash value representing the sub-block data in the first one of the sub-block with the hash values representing the sub-block data in other ones of the sub-blocks.

14. The media of claim 8, wherein determining whether the first one of the sub-blocks is similar to another one of the sub-blocks comprises:

determining interesting locations in the first one of the sub-blocks and one or more other ones of the sub-blocks;

calculating fingerprints of the data at the interesting locations using a hash function; and

comparing the fingerprints with each other.

15. A method comprising:

accessing by one or more computer systems a deduplicated version of data; and

re-creating by the one or more computer systems the data from the deduplicated version using;

results of hash-based deduplication applied to storage of sub-blocks of the data that are identical to other sub-blocks of the data; and

results of sub-block differencing applied to storage of sub-blocks of the data that are similar to other ones of the sub-blocks.

16. One or more computer-readable storage media embodying instructions that are operable when executed by one or more computer systems to:

access a deduplicated version of data; and

re-create the data from the deduplicated version using;

results of hash-based deduplication applied to storage of sub-blocks of the data that are identical to other sub-blocks of the data; and

results of sub-block differencing applied to storage of sub-blocks of the data that are similar to other ones of the sub-blocks.

17. One or more computer-readable storage media embodying data that was stored on the media at least in part by:

accessing the data by one or more computer systems;

partitioning by the one or more computer systems the data into a plurality of sub-blocks;

determining by the one or more computer systems whether a first one of the sub-blocks is identical to another one of the sub-blocks or similar to another one of the sub-blocks;

if the first one of the sub-blocks is identical to another one of the sub-blocks, applying by the one or more computer systems hash-based deduplication to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks; and

if the first one of the sub-blocks is similar to another one of the sub-blocks, applying by the one or more computer systems sub-block differencing to storage of the first one of the sub-blocks with respect to the other one of the sub-blocks.

18. The media of claim 17, wherein applying sub-block differencing to storage of the first one of the sub-blocks if the first one of the sub-blocks is similar to another one of the sub-blocks comprised:

determining a difference between the first one of the sub-blocks and the other one of the sub-blocks;

storing the difference so that the first one of the sub-blocks can be reconstructed from the other one of the-blocks and the difference.

19. The media of claim 18, wherein the difference comprises one or more block segments that were in both the first one of the sub-blocks and the other one of the sub-blocks.

20. The media of claim 17, where the data was stored on the media at least in further part by:

determining by the one or more computer systems whether the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks; and

if the first one of the sub-blocks is similar to a set of two or more other ones of the sub-blocks, applying by the one or more computer systems sub-block differencing to storage of the first one of the sub-blocks with respect to the set of two or more other ones of the sub-blocks.

21. The media of claim 17, wherein:

the sub-blocks comprised sub-block data; and

determining whether the first one of the sub-blocks is identical to another one of the sub-blocks comprised;

using a strong hash function to calculate hash values representing the sub-block data; and

comparing the hash value representing the sub-block data in the first one of the sub-block with the hash values representing the sub-block data in other ones of the sub-blocks.

22. The media of claim 17, wherein determining whether the first one of the sub-blocks is similar to another one of the sub-blocks comprised:

determining interesting locations in the first one of the sub-blocks and one or more other ones of the sub-blocks;

calculating fingerprints of the data at the interesting locations using a hash function; and

comparing the fingerprints with each other.