Deduplication of Data on Disk Devices Using Low-Latency Random Read Memory

• US 20110131390A1
• Filed: 02/07/2011
• Published: 06/02/2011
• 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,145,843 B2
• Time in Patent Office: Days
• US Class Current: 711/209
• 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 method for deduplicating blocks of data, the method comprising:

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

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

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 method 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 method 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 method of claim 1, further comprising:

providing a 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; and

determining whether a received block matches a stored block by using the comparison mechanism.

5. The method of claim 4, wherein determining whether a received block matches a stored block comprises 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 method 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 LLRRIVI device.

7. The method of claim 1, further comprising:

providing a mapping mechanism for storing mappings of deduplicated received blocks to corresponding matching stored blocks; and

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 method 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, the method further comprising:

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 method of claim 7, wherein the received blocks comprise blocks stored on a disk device, the method further comprising:

deduplicating a received block by deleting the received block stored on the disk device.

10. The method of claim 1, further comprising:

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 method of claim 1, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.

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

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

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

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 method 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 method 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 method of claim 12, further comprising:

providing a 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; and

determining whether a received block matches a stored block using the comparison mechanism.

16. The method of claim 15, wherein determining whether a received block matches a stored block comprises 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 method 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 method of claim 12, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.

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

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

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

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 method of claim 19, wherein an LLRRM device comprises a flash memory, Magnetic Random Access Memory (MRAM), or Phase Change RAM (PRAM) device.