De-duplication in a virtualized storage environment

• US 8,209,506 B2
• Filed: 09/28/2007
• Issued: 06/26/2012
• Est. Priority Date: 09/05/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Yueh, Jedidiah
• Primary Examiner(s): BRADLEY, MATTHEW A
• Application Number:
  US11/864,583
• Publication Number:
  US 20090063795A1
• Time in Patent Office: 1,733 Days
• Field of Search: 711/162, 707/101, 707/664
• US Class Current: 711/162
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• 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/0683 Plurality of storage devices

Abstract

A data de-duplication application de-duplicates redundant data in the pooled storage capacity of a virtualized storage environment. The virtualized storage environment includes a plurality of storage devices and a virtualization or abstraction layer that aggregates all or a portion of the storage capacity of each storage device into a single pool of storage capacity, all or portions of which can be allocated to one or more host systems. For each host system, the virtualization layer presents a representation of at least a portion of the pooled storage capacity wherein the corresponding host system can read and write data. The data de-duplication application identifies redundant data in the pooled storage capacity and replaces it with one or more pointers pointing to a single instance of the data. The de-duplication application can operate on fixed or variable size blocks of data and can de-duplicate data either post-process or in-line.

Claims

1. A method for de-duplicating redundant data in a virtualized storage environment, the method comprising:

pooling storage capacity from a plurality of storage devices into a single storage pool by applying an abstraction layer to the plurality of storage devices, the abstraction layer presenting a representation of a corresponding portion of the pooled storage capacity to each of one or more host systems;

operating the one or more host systems in a computer architecture that includes the plurality of storage devices, each host system configured to write data to and read data from a corresponding portion of the pooled storage capacity; and

operating a data de-duplication application on a host system included in the one or more host systems in the computer architecture to globally de-duplicate data in the pooled storage capacity, wherein the abstraction layer presents a representation at least a portion of the pooled storage capacity to the data de-duplication application and wherein the data de-duplication application performs de-duplication in the portion of the pooled storage capacity.

2. The method of claim 1, wherein the abstraction layer is implemented:

in at least one of the one or more host systems, in at least one of the plurality of storage devices, or in a switch or other appliance of a storage area network to which the plurality of storage devices are coupled.

3. The method of claim 1, wherein de-duplicating data in the pooled storage capacity comprises:

identifying first data in the pooled storage capacity that is identical to second data in the pooled storage capacity;

deleting the second data from the pooled storage capacity; and

replacing the second data with the pointer pointing to the identical first data.

4. The method of claim 3, wherein identifying first data in the pooled storage capacity that is identical to second data in the pooled storage capacity includes performing a hash function on each of the first and second data, comparing the resulting hash values for the first and second data to each other, and determining that the hash values are identical.

5. The method of claim 4, wherein the pointer pointing to the identical first data comprises the hash value of the first or second data.

6. The method of claim 1, wherein the data de-duplication application de-duplicates data written from the one or more host systems to the pooled storage capacity either post-process or in-line.

7. The method of claim 1, wherein the virtualization layer intercepts read and write requests from the one or more host systems and maps virtual storage addresses included in the read and write requests to physical storage addresses in the pooled storage capacity.

8. A method for providing storage virtualization and data de-duplication in a computer environment including a plurality of storage devices, the method comprising:

applying a virtualization layer to a plurality of storage devices to aggregate their storage capacity such that during operation, when a write request comprising a virtual memory address and write data is received, the virtualization layer maps the virtual memory address to a physical memory address within the aggregated storage capacity, wherein the aggregated storage capacity includes previously stored data including a first data block, wherein the aggregated storage capacity is shared by a plurality of hosts;

determining that a second block of data included in the write data is identical to the first block of data using a de-duplication application operating on a host system in the computer environment, wherein the virtualization layer presents a representation of the aggregated storage capacity to the de-duplication application operating on the host system; and

storing a pointer in the aggregated storage capacity at the physical memory address instead of storing the second block of data, the pointer pointing to the first block of data.

9. The method of claim 8, further comprising, in response to receiving a mapped read request from the virtualization layer for the second data including the second block of data stored at the physical memory address, using the pointer to access and return the first block of data that is identical to the second block of data.

10. The method of claim 8, further comprising operating a host system in a computer environment that includes the plurality of storage devices, the host system sending the write request to the virtualization layer.

11. The method of claim 8, wherein determining that the second block of data is identical to the first block of data comprises:

breaking the previously stored data into a first set of one or more blocks, the first set of one or more blocks including the first block of data;

breaking the write data into a second set of one or more blocks, the second set of one or more blocks including the second block of data;

performing a hash function on the first block of data to obtain a first hash value and on the second block of data to obtain a second hash value, wherein the hash function is deterministic and configured to produce probabilistically unique hash values; and

determining that the first hash value is identical to the second hash value by comparing the first hash value to the second hash value.

12. The method of claim 11, wherein the pointer pointing to the first block of data comprises the first hash value or the second hash value.

13. The method of claim 11, wherein the size of the blocks in the first set of one or more blocks and the second set of one or more blocks is either fixed or variable.

14. The method of claim 8, wherein the steps of determining that the second block of data is identical to the first block of data and storing the pointer in the aggregated storage capacity are performed either as the second data is written to the physical storage address or after the second data has already been stored at the physical storage address.

15. A method of pooling storage capacity from a plurality of storage devices and de-duplicating data within the pooled storage capacity, the method comprising:

applying a virtualization layer to a plurality of storage devices to pool storage capacity from the plurality of storage devices, wherein original data is stored in the pooled storage capacity and wherein the pooled storage capacity is shared;

receiving a write request from a first host system, the write request including at least a virtual storage address and write data;

mapping the virtual storage address to a physical storage address within a portion of the pooled storage capacity allocated to the host system;

comparing the write data to the original data to identify a first data block within the original data that is identical to a second data block within the write data with a data de-duplication application operation on a second host system, wherein the virtualization layer presents a representation of the pooled storage capacity to the second host system; and

replacing one of the first data block and the second data block with a pointer that points to a remaining one of the first data block and the second data block in the pooled storage capacity.

16. The method of claim 15, wherein the plurality of storage devices comprise a plurality of heterogeneous storage devices, the abstraction layer presenting a logical representation of the pooled storage capacity to a plurality of host systems including the first host system.

17. The method of claim 15, wherein the virtualization layer is implemented:

in the first host system, in a storage controller of at least one of the plurality of storage devices, or in a switch or other appliance of a storage area network to which the plurality of storage devices are coupled.

18. The method of claim 15, further comprising:

receiving a read request from the first host system, the read request including the same virtual storage address as the write request;

mapping the virtual storage address to the physical storage address;

if the second data block within the write data was replaced with a pointer that points to the first data block within the original data, using the pointer to access and return the first data block in response to the read request; and

if the first data block was replaced with a pointer that points to the second data block, accessing and returning the second data block in response to the read request.

19. The method of claim 15, wherein comparing the write data to the original data to identify at least a first data block within the original data that is identical to a second data block within the write data comprises:

breaking the original data into one or more data blocks including the first data block;

breaking the write data into one or more data blocks including the second data block;

hashing the first data block to produce a first hash and the second data block to produce a second hash; and

comparing the first hash and the second hash.