Deduplication of Data on Disk Devices Based on a Threshold Number of Sequential Blocks

• US 20090271402A1
• Filed: 04/25/2008
• Published: 10/29/2009
• Est. Priority Date: 04/25/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Srinivasan, Kiran, Voruganti, Kaladhar, Goodson, Garth
• Granted Patent: US 8,346,730 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Abstract

Deduplication of data on disk devices based on a threshold number (THN) of sequential blocks is described herein, the threshold number being two or greater. Deduplication may be performed when a series of THN or more received blocks (THN series) match a sequence of THN or more stored blocks (THN sequence), whereby a sequence comprises blocks stored on the same track of a disk device. Deduplication may be performed using a block-comparison mechanism comprising metadata entries of stored blocks and a mapping mechanism containing mappings of deduplicated blocks to their matching blocks. The mapping mechanism may be used to perform later read requests received for the deduplicated blocks. The deduplication described herein may reduce the read latency as the number of seeks between tracks may be reduced. Also, when a seek to a different track is performed, the seek time cost is spread over THN or more blocks.

Claims

1. A storage system for deduplicating blocks of data based on a predetermined threshold number (THN) of sequential blocks, the storage system comprising:

a set of one or more disk devices for storing a plurality of blocks, each disk device comprising a set of tracks for storing blocks; and

a deduplication layer configured for;

receiving a set of blocks;

determining whether a series of THN or more received blocks (THN series) matches a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising a series of blocks stored on a same track of a disk device, THN having a value of 2 or greater; and

upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series using the matching THN sequence.

2. The storage system of claim 1, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence.

3. The storage system of claim 1, further comprising:

comparison mechanism for storing metadata entries for a plurality of THN sequences, each metadata entry comprising metadata for a THN sequence and being indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence using the comparison mechanism.

4. The storage system of claim 3, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content.

5. The storage system of claim 3, wherein the comparison mechanism stores metadata entries for full or partial THN sequences, a partial THN sequence comprising a subset of THN or more blocks of a full THN sequence, a set of zero or more partial THN sequences being derived from each full THN sequence, each partial THN sequence in the set having a different combination of block size and offset from the beginning of the full THN sequence.

6. The storage system of claim 1, further comprising:

a mapping mechanism for storing mappings of deduplicated blocks of the THN series to blocks of the matching THN sequence, wherein the deduplication layer is configured for deduplicating the blocks of the THN series by creating indexes to the blocks of the matching THN sequence in the mapping mechanism.

7. The storage system of claim 6, wherein:

the mapping mechanism comprises a set of inodes or a metadata structure; and

the mapping mechanism is used for performing a subsequent read request for the deduplicated blocks of the THN series, wherein the read request comprises a seek operation to the track storing the matching THN sequence and sequential reads of the blocks of the matching THN sequence comprising sequential reads of THN or more blocks.

8. The storage system of claim 6, wherein:

the THN series comprises blocks to be written to a disk device using a write log comprising the data of the blocks and assigned address locations for the blocks; and

the deduplication layer is further configured for deduplicating the blocks of the THN series by deleting the data of the blocks and the assigned address locations for the blocks in the write log.

9. The storage system of claim 6, wherein:

the THN series comprises blocks stored on a disk device; and

the deduplication layer is further configured for deduplicating the blocks of the THN series by deleting the blocks of the THN series stored on the disk device.

10. The storage system of claim 3, wherein:

a set of non-deduplicated blocks comprises received blocks that are not deduplicated, each non-deduplicated block having an assigned address location indicating a location on a disk device for storage;

the deduplication layer is further configured for;

determining a set of zero or more THN sequences of non-deduplicated blocks, a THN sequence of non-deduplicated blocks comprising THN or more non-deduplicated blocks having consecutive assigned address locations; and

for each THN sequence of non-deduplicated blocks, producing a metadata entry in the comparison mechanism.

11. The storage system of claim 1, wherein:

the set of received blocks is received from a first application or a second application;

the deduplication layer is further configured for;

using a first threshold number for the set of received blocks received from the first application and a second threshold number for the set of received blocks received from the second application, the first and second threshold numbers being different in value.

12. A storage system for deduplicating blocks of data for storage based on a predetermined threshold number (THN) of blocks, the storage system comprising:

a set of one or more disk devices for storing a plurality of blocks, each block having an address location; and

a deduplication layer configured for;

receiving a set of blocks;

determining whether a series of THN or more received blocks (THN series) match a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising blocks having consecutive address locations, THN having a value of 2 or greater; and

upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series.

13. The storage system of claim 12, wherein:

an address location comprises a logical block number (LBN); and

a THN sequence comprises a set of THN or more stored blocks having consecutive LBNs.

14. The storage system of claim 12 wherein:

each disk device comprises a set of tracks for storing blocks; and

a sequence of blocks comprises a series of blocks stored on a same track of a disk device.

15. The storage system of claim 12, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence.

16. The storage system of claim 12, further comprising:

comparison mechanism for storing metadata entries for a plurality of THN sequences, each metadata entry comprising metadata for a THN sequence and being indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence using the comparison mechanism.

17. The storage system of claim 16, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content.

18. The storage system of claim 12, further comprising:

a mapping mechanism for storing mappings of deduplicated blocks of the THN series to blocks of the matching THN sequence, wherein the deduplication layer is configured for deduplicating the blocks of the THN series by creating indexes to the blocks of the matching THN sequence in the mapping mechanism.

19. A storage system for deduplicating blocks of data based on a predetermined threshold number (THN) of sequential blocks, the storage system comprising:

a set of one or more disk devices for storing a plurality of blocks, each disk device comprising a set of tracks for storing blocks;

a deduplication layer configured for;

receiving a set of blocks;

using a comparison mechanism, determining whether a series of THN or more received blocks (THN series) matches a sequence of THN or more stored blocks (THN sequence), a series of blocks comprising a set of consecutive blocks and a sequence of blocks comprising a series of blocks stored on a same track of a disk device, THN having a value of 2 or greater; and

upon determining that a matching THN sequence is found, deduplicating the blocks of the THN series using the matching THN sequence; and

the comparison mechanism for storing metadata entries for a plurality of THN sequences comprising full or partial THN sequences, a partial THN sequence comprising a subset of THN or more blocks of a full THN sequence, a set of zero or more partial THN sequences being derived from each full THN sequence, each partial THN sequence in the set having a different combination of block size and offset from the beginning of the full THN sequence.

20. The storage system of claim 19, wherein a THN series matches a THN sequence when the blocks of the THN series have the same data content as or have a high probability of having the same content as the blocks of the THN sequence.

21. The storage system of claim 19, wherein each metadata entry comprises metadata for a THN sequence and is indexed in the comparison mechanism by a content identifier that represents the data contents of the blocks of the THN sequence.

22. The storage system of claim 21, wherein the deduplication layer is configured for determining whether a THN series matches a THN sequence by determining a content identifier for the THN series and determining whether a matching content identifier is found in the comparison mechanism, wherein two sets of blocks having the same content identifier have a high probability of having the same data content.