Efficient read/write algorithms and associated mapping for block-level data reduction processes

• US 8,140,821 B1
• Filed: 12/18/2009
• Issued: 03/20/2012
• Est. Priority Date: 12/18/2009
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Raizen, Helen S., Bappe, Michael E., Ruef, Richard, Owen, Karl M., Nikolaevich, Agarkov Vadim, Biester, William Carl
• Primary Examiner(s): Portka, Gary
• Application Number:
  US12/642,071
• Time in Patent Office: 823 Days
• Field of Search: None
• US Class Current: 711/202
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 2206/1004 Defragmentation
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

A system configured to optimize access to stored chunks of data is provided. The system comprises a vLUN layer, a mapped LUN layer, and a mapping layer disposed between the vLUN and the mapped LUN. The vLUN provides a plurality of logical chunk addresses (LCAs) and the mapped LUN provides a plurality of physical chunk addresses (PCAs), where each LCA or PCA stores a respective chunk of data. The mapping layer defines a layout of the mapped LUN that facilitates efficient read and write access to the mapped LUN.

Claims

1. A system configured to optimize access to stored chunks of data content, the system comprising:

a virtual logic unit (vLUN) layer that corresponds to one of a plurality of layers in an input/output (I/O) path of a computer system, the vLUN providing a plurality of logical chunk addresses (LCAs) to layers disposed above it in the I/O path, such that the LCAs in the vLUN are the only LCAs visible to layers above the vLUN;

a mapped logical unit (mapped LUN) layer disposed below the vLUN in the I/O path and being in operable communication with the vLUN, the mapped LUN associated with a plurality of physical chunk addresses (PCAs), each PCA configured to provide physical storage for a respective chunk of data;

a mapping layer disposed between and in operable communication with the vLUN and the mapped LUN layers, the mapping layer defining a layout of the mapped LUN that helps improve the efficiency of read and write access to the mapped LUN, the layout comprising;

a first region comprising a set of first PCAs, each first PCA being allotted to provide physical storage for a respective first chunk of data stored at a single first corresponding LCA in the vLUN, where the first region is reserved for use only by the corresponding LCAs in the vLUN, such that, during a write operation, the first chunk of data is written directly to the first region without requiring location of or allocation of a free PCA to store the first chunk of data;

a second region comprising a set of second PCAs, each second PCA being allotted to provide physical storage for a respective second chunk of data, where the second chunk of data corresponds to data that is associated with at least two LCAs; and

a metadata region, the metadata region including a first portion indicating, for each LCA in the vLUN, whether the corresponding PCA is located in the first region or the second region of the mapped LUN, and a second portion providing, if the first portion indicates that the corresponding PCA is in the second region of the mapped LUN, mapping information for the LCA to the corresponding PCA in the second region, wherein at least the first portion of the metadata is available in a media that is sufficiently fast, such that, during a read operation, the overhead required to access a chunk of data stored in the first region is zero and the maximum overhead required to access a chunk of data stored in the second region corresponds only to the overhead required to read the mapping information stored in the second portion of the metadata region.

2. The system of claim 1, further comprising a data reduction engine in operable communication with the mapping layer, the data reduction engine configured to:

perform a data reduction process on a first chunk of data stored in a first LCA on the vLUN so as to determine that the first chunk of data stored at the first LCA is a first unneeded chunk;

remap the first LCA of the first unneeded chunk from the first PCA in the first region to a second PCA in the second region of the mapped LUN, where the remapping of the first LCA results in the physical storage associated with the first PCA no longer being required to be used to store data associated with the first LCA; and

provide information to the first portion of the metadata region indicating that the corresponding PCA for the first unneeded chunk has changed from the first PCA in the first region to the second PCA in the second region.

3. The system of claim 1, wherein data reduction engine is further operable to deallocate the first PCA associated with the first unneeded chunk, the deallocation freeing the first PCA and its associated physical storage chunk for re-use by another LCA in the vLUN.

4. The system of claim 1, further comprising an input/output (I/O) filter driver in operable communication with the mapped LUN, the mapping layer, and the vLUN, the I/O filter driver operable to map read and writes to LCAs in the vLUN to the corresponding first or second region in the mapped LUN.

5. The system of claim 2, further comprising a garbage collection engine in operable communication with the mapped LUN, the mapping layer, the vLUN and the data reduction engine, the garbage collection operable to:

check, for each respective LCA in the vLUN, whether the information in the mapping layer associated with the respective LCA is correct;

check whether an LCA indicated as remapped to the second region is no longer an unneeded chunk; and

correct the remapping if an LCA is remapped incorrectly.

6. The system of claim 5, where the garbage collection engine is further operable to move data associated with a PCA in the first region to a PCA in the second region, if the chunk that was stored in the second region is no longer an unneeded chunk.

7. The system of claim 1, wherein the data reduction engine is a deduplication engine.

8. The system of claim 7, wherein, in the mapping layer:

the first region is a direct region and corresponds to a set of PCAs associated with direct chunks of data, wherein the set of direct chunks of data are chunks of data that are not shared and have not undergone deduplication;

the second region is a shared region and corresponds to a set of shared PCAs (sPCAs) associated with shared chunks of data, where the shared chunks of data correspond to data chunks that have undergone deduplication, such that a shared chunk of data is associated with more than one LCA;

the first portion of the metadata region comprises, for each LCA, a shared bit indicating whether or not a given chunk has undergone deduplication and is a shared chunk; and

the second portion of the metadata region comprises a shared map, wherein if the shared bit indicates that a given chunk at a given LCA is a shared chunk, the shared map includes an entry showing a corresponding sPCA for the given LCA.

9. The system of claim 7, wherein the metadata region further comprises a digest, the digest storing a hash of each respective shared chunk, the hash being usable by the deduplication engine during a determination as to whether a first chunk is a duplicate of a second chunk.

10. The system of claim 8, wherein the deduplication engine is configured to perform block-level deduplication on a logical chunk of data stored in the vLUN at a first LCA by:

computing a first hash of a first chunk of data stored at a first LCA in the direct region of the vLUN; and

comparing the first hash to a second hash stored in the digest, the second hash associated with a second chunk located in the shared region at a second shared physical chunk address (sPCA);

wherein if the first hash and the second hash are identical, the deduplication engine updates the shared region such that the LCA of the first chunk points to the second sPCA of the second chunk and sets the shared bit to indicate that first chunk at the first LCA is now a shared chunk.

11. The system of claim 8, wherein the deduplication engine is configured to perform block level deduplication on first and second logical chunks of data stored in the vLUN at respective first and second LCAs, the configuring including:

computing first and second hashes of the first and second respective logical chunks of data stored in the vLUN;

if a comparison of the first and second hashes indicates that the first and second hashes are the same, locating an unused chunk in the shared region, the unused chunk having an unused direct physical chunk address (dPCA);

copying one of the first and second logical chunks to the unused chunk in the shared region;

updating the shared region so that the first LCA and the second LCA point to the unused dPCA in the shared region;

setting the shared bit for the first chunk and the shared identifier for the second chunk each to indicate that each respective first and second chunk is now a shared chunk.

12. The system of claim 1 wherein the data reduction engine comprises a compression engine, wherein the unneeded chunk comprises a compressed chunk, and wherein the information enabling retrieval of data associated with the compressed chunk comprises information indicating the physical location where the shared chunk is stored, the size of the compressed chunk, and the format of the compression used to compress the compressed chunk.

13. The system of claim 12, wherein in the mapping layer:

the first region is an uncompressed region and corresponds to a set of uncompressed chunks of data, wherein the set of uncompressed chunks of data are chunks of data that have not undergone compression, wherein the uncompressed region comprises, for each respective uncompressed chunk of data, a corresponding direct physical chunk address (dPCA) that maps to the location in the mapped LUN where the respective uncompressed chunk of data is physically stored;

the second region is a compressed region and comprises a data structure defining, for each LCA that the compressed identifier indicates corresponds to a compressed chunk, a corresponding pointer to a shared physical chunk address (SPCA) that maps to the location in the mapped LUN where the respective compressed chunk of data is physically stored; and

the metadata region comprises a compression state bit that indicates whether or not a given chunk has undergone compression and is a compressed chunk.

14. The system of claim 1, wherein the vLUN, mapped LUN and mapping layer are implemented as part of a computer system.

15. The system of claim 1, wherein the vLUN, mapped LUN, and mapping layer are implemented as part of a storage appliance.

16. The system of claim 1, wherein the vLUN, mapped LUN, and mapping layer are implemented as part of a network switch.

17. A computer program product, comprising a computer-usable storage medium having a computer-readable program code stored therein, the computer-readable program code containing instructions that when executed by a processor of a computer system implement a method for reducing the storage required to store data content, the method comprising:

implementing a virtual logic unit (vLUN) layer that corresponds to one of a plurality of layers in an input/output (I/O) path of a computer system, the vLUN providing a plurality of logical chunk addresses (LCAs) to layers disposed above it in the I/O path, such that the LCAs in the vLUN are the only LCAs visible to layers above the vLUN;

implementing a mapped logical unit (mapped LUN) layer disposed below the vLUN in the I/O path and being in operable communication with the vLUN, the mapped LUN associated with a plurality of physical chunk addresses (PCAs), each PCA configured to provide physical storage for a respective chunk of data; and

configuring a mapping layer disposed between and in operable communication with the vLUN and the mapped LUN layers, the mapping layer defining a layout of the mapped LUN that helps improve the efficiency of read and write access to the mapped LUN, the layout comprising;

a first region comprising a set of first PCAs, each first PCA being allotted to provide physical storage for a respective first chunk of data stored at a single first corresponding LCA in the vLUN, where the first region is reserved for use only by the corresponding LCAs in the vLUN, such that, during a write operation, the first chunk of data is written directly to the first region without requiring location of or allocation of a free PCA to store the first chunk of data;

a second region comprising a set of second PCAs, each second PCA being allotted to provide physical storage for a respective second chunk of data, where the second chunk of data corresponds to data that is associated with at least two LCAs; and

a metadata region, the metadata region including a first portion indicating, for each LCA in the vLUN, whether the corresponding PCA is located in the first region or the second region of the mapped LUN, and a second portion providing, if the first portion indicates that the corresponding PCA is in the second region of the mapped LUN, mapping information for the LCA to the corresponding PCA in the second region, wherein at least the first portion of the metadata is available in a media that is sufficiently fast, such that, during a read operation, the overhead required to access a chunk of data stored in the first region is zero and the maximum overhead required to access a chunk of data stored in the second region corresponds only to the overhead required to read the mapping information stored in the second portion of the metadata region.