Deduplication of data on disk devices using low-latency random read memory

• US 7,908,436 B1
• Filed: 04/25/2008
• Issued: 03/15/2011
• Est. Priority Date: 04/25/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Srinivasan, Kiran, Voruganti, Kaladhar, Goodson, Garth
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US12/110,193
• Time in Patent Office: 1,054 Days
• Field of Search: None
• US Class Current: 711/114
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Deduplication of data using a low-latency random read memory (LLRRM) is described herein. Upon receiving a block, if a matching block stored on a disk device is found, the received block is deduplicated by producing an index to the address location of the matching block. In some embodiments, a matching block having a predetermined threshold number of associated indexes that reference the matching block is transferred to LLRRM, the threshold number being one or greater. Associated indexes may be modified to reflect the new address location in LLRRM. Deduplication may be performed using a mapping mechanism containing mappings of deduplicated blocks to matching blocks, the mappings being used for performing read requests. Deduplication described herein may reduce read latency as LLRRM has relatively low latency in performing random read requests relative to disk devices.

Claims

1. A storage system for deduplicating blocks of data, the storage system comprising:

a set of one or more disk devices for storing a plurality of blocks;

a set of one or more low-latency random read memory (LLRRM) devices for storing a plurality of blocks, an LLRRM device having lower latency in performing random read requests relative to a disk device; and

a deduplication layer configured for;

receiving a set of blocks;

for each received block, determining whether the received block matches a block stored on a disk device; and

upon determining that a matching stored block is found in a disk device, deduplicating the received block by;

transferring the matching stored block from an original address location on a disk device to a new address location in an LLRRM device; and

producing an index to the matching stored block, the index comprising the new address location of the matching stored block in the LLRRM device.

2. The storage system of claim 1, wherein a matching stored block is transferred to an LLRRM device upon the first instance of the stored block matching a received block.

3. The storage system of claim 1, wherein a received block matches a stored block when the blocks have the same data content or have a high probability of having the same content.

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

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

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

6. The storage system of claim 4, wherein a metadata entry for a stored block comprises a reference count indicating the number of indexes that reference the stored block and a set of pointers to the indexes, a pointer being used to modify an index to reflect the new address location when a stored block is transferred to an LLRRM device.

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

a mapping mechanism for storing mappings of deduplicated received blocks to corresponding matching stored blocks, wherein the deduplication layer is configured for producing indexes to matching stored blocks in the mapping mechanism, 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 deduplicated received blocks, wherein the read request comprises a read of one or more matching stored blocks on an LLRRM device.

8. The storage system of claim 7, wherein:

a received block comprises a block to be written to a disk device using a write log comprising the data of the block and an assigned address location for the block on the disk device; and

the deduplication layer is further configured for deduplicating a received block by deleting the data of the block and the assigned address location for the block in the write log.

9. The storage system of claim 7, wherein:

the received blocks comprise blocks stored on a disk device; and

the deduplication layer is further configured for deduplicating a received block by deleting the received block stored on the disk device.

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

a driver selector layer for receiving an access request that specifies an address location and sending the received request to a disk device driver or an LLRRM driver depending on the value of the address location.

11. The storage system of claim 1, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.

12. A storage system for deduplicating blocks of data, the storage system comprising:

a set of one or more disk devices for storing a plurality of blocks;

a set of one or more low-latency random read memory (LLRRM) devices for storing a plurality of blocks, an LLRRM device having lower latency in performing random read requests relative to a disk device; and

a deduplication layer configured for;

receiving a set of blocks;

for each received block, determining whether the received block matches a block stored on a disk device; and

upon determining that a matching stored block is found in a disk device, deduplicating the received block by;

determining whether a number of associated indexes referencing the matching stored block equals a predetermined threshold number, the threshold number being two or greater;

upon determining that the threshold number of associated indexes reference the matching stored block, transferring the matching stored block from an original address location on a disk device to a new address location in an LLRRM device; and

producing an index to the matching stored block, the index comprising the new address location of the matching stored block in the LLRRM device.

13. The storage system of claim 12, wherein the number of associated indexes indicate a number of received blocks that are deduplicated using the matching stored block.

14. The storage system of claim 12, wherein a received block matches a stored block when the blocks have the same data content or have a high probability of having the same content.

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

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

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

17. The storage system of claim 15, wherein a metadata entry for a stored block comprises a reference count indicating the number of associated indexes that reference the stored block and a set of pointers to the associated indexes, a pointer being used to modify an associated index to reflect the new address location when a stored block is transferred to an LLRRM device.

18. The storage system of claim 12, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.

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 set of one or more low-latency random read memory (LLRRM) devices for storing a plurality of blocks, an LLRRM device having lower latency in performing random read requests relative to a disk device; and

a deduplication layer configured for;

receiving a set of blocks;

determining that 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;

deduplicating the blocks of the THN series using the matching THN sequence;

for at least one received block, determining that the received block matches a block stored on a disk device; and

deduplicating the received block by;

transferring the matching stored block from an original address location on a disk device to a new address location in an LLRRM device; and

producing an index to the matching stored block, the index comprising the new address location of the matching stored block in the LLRRM device.

20. The storage system of claim 19, wherein a sequence of blocks comprises blocks having consecutive address locations.

21. The storage system of claim 19, wherein a matching stored block is transferred to an LLRRM device upon the first instance of the stored block matching a received block.

22. The storage system of claim 19, wherein a received block matches a stored block when the blocks have the same data content or have a high probability of having the same content.

23. The storage system of claim 19, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.