De-duplication in a virtualized storage environment

• US 8,935,497 B1
• Filed: 08/16/2013
• Issued: 01/13/2015
• 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:
  US13/969,191
• Time in Patent Office: 515 Days
• Field of Search: 711/162
• 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

In one example, a method for de-duplicating redundant data in a virtualized storage environment includes, in response to receipt of a write request that includes write data and a virtual memory address of the write data, mapping the virtual memory address to a physical memory address within a pooled storage capacity that includes a virtualization of a plurality of storage devices. Next, a determination is made that a second block of data included in the write data of the write request is identical to a first block of data that is stored in the pooled storage capacity. Finally, a pointer, rather than the second block of data, is stored in the pooled storage capacity at the physical memory address. The pointer points to the first block of data.

Claims

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

in response to receipt of a write request that includes write data and a virtual memory address of the write data;

mapping the virtual memory address to a physical memory address within a pooled storage capacity that comprises a virtualization of a plurality of storage devices;

determining that a second block of data included in the write data of the write request is identical to a first block of data already residing in the pooled storage capacity; and

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

2. The method of claim 1, further comprising using the pointer to access and return the first block of data that is identical to the second block of data.

3. The method of claim 1, further comprising creating the pooled storage capacity by performing one of:

a host-based virtualization of the plurality of storage devices;

a storage-based virtualization of the plurality of storage devices;

or, a network-based virtualization of the plurality of storage devices.

4. The method of claim 1, 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.

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

6. The method of claim 4, 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.

7. A non-transitory computer medium having stored therein computer-executable instructions which, when executed by one or more processing devices, perform de-duplication of redundant data, wherein performing de-duplication of redundant data includes:

in response to receipt of a write request that includes write data and a virtual memory address of the write data;

mapping the virtual memory address to a physical memory address within a pooled storage capacity that comprises a virtualization of a plurality of storage devices;

determining that a second block of data included in the write data of the write request is identical to a first block of data that is stored in the pooled storage capacity; and

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

8. The non-transitory computer medium of claim 7, wherein performing de-duplication of redundant data further comprises creating the pooled storage capacity by performing one of:

a host-based virtualization of the plurality of storage devices;

a storage-based virtualization of the plurality of storage devices;

or, a network-based virtualization of the plurality of storage devices.

9. The non-transitory computer medium of claim 7, 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.

10. A host system, comprising:

an operating system operable to manage sharing of host system resources among applications running on the host system; and

a physical storage device having stored therein a data de-duplication application running on the host system and including computer-executable instructions which, when executed by one or more processing devices, perform de-duplication of redundant data, wherein performing de-duplication of redundant data includes;

in response to receipt of a write request that includes write data and a virtual memory address of the write data;

mapping the virtual memory address to a physical memory address within a pooled storage capacity that comprises a virtualization of a plurality of storage devices;

determining that a second block of data included in the write data of the write request is identical to a first block of data that is stored in the pooled storage capacity; and

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

11. The host system as recited in claim 10, further comprising a virtualization agent operable to create the pooled storage capacity.

12. The host system as recited in claim 10, wherein the host system comprises a server implemented in the form of a computer.

13. A method of de-duplicating data within a pooled storage capacity, the method comprising:

comparing write data of a write request that includes the write data and a virtual storage address to original data to identify a first data block within the original data that is identical to a second data block within the write data, the original data residing in a pooled storage capacity that comprises a virtualization of a plurality of storage devices; 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, such that both the pointer and the data block to which it points reside in the pooled storage capacity and the data block not pointed to by the pointer does not reside in the pooled storage capacity.

14. The method as recited in claim 13, further comprising mapping the virtual storage address to a physical storage address within a portion of the pooled storage capacity allocated to the host system.

15. The method as recited in claim 13, 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.

16. The method of claim 13, further comprising creating the pooled storage capacity by performing one of:

a host-based virtualization of the plurality of storage devices;

a storage-based virtualization of the plurality of storage devices;

or,

a network-based virtualization of the plurality of storage devices.

17. A non-transitory computer medium having stored therein computer-executable instructions which, when executed by one or more processing devices, perform de-duplication of redundant data, wherein performing de-duplication of redundant data includes:

comparing write data of a write request that includes the write data and a virtual storage address to original data to identify a first data block within the original data that is identical to a second data block within the write data, the original data residing in a pooled storage capacity that comprises a virtualization of a plurality of storage devices; 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, such that both the pointer and the data block to which it points reside in the pooled storage capacity and the data block not pointed to by the pointer does not reside in the pooled storage capacity.

18. The non-transitory computer medium as recited in claim 17, wherein performing de-duplication of redundant data further comprises mapping the virtual storage address to a physical storage address within a portion of the pooled storage capacity allocated to the host system.

19. The non-transitory computer medium as recited in claim 17, 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.

20. The non-transitory computer medium as recited in claim 17, wherein performing de-duplication of redundant data further comprises creating the pooled storage capacity by performing one of:

a host-based virtualization of the plurality of storage devices;

a storage-based virtualization of the plurality of storage devices;

or, a network-based virtualization of the plurality of storage devices.

21. A host system, comprising:

an operating system operable to manage sharing of host system resources among applications running on the host system; and

a physical storage device having stored therein a data de-duplication application running on the host system and including computer-executable instructions which, when executed by one or more processing devices, perform de-duplication of redundant data, wherein performing de-duplication of redundant data includes;

comparing write data of a write request that includes the write data and a virtual storage address to original data to identify a first data block within the original data that is identical to a second data block within the write data, the original data residing in a pooled storage capacity that comprises a virtualization of a plurality of storage devices; 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, such that both the pointer and the data block to which it points reside in the pooled storage capacity and the data block not pointed to by the pointer does not reside in the pooled storage capacity.

22. The host system as recited in claim 21, further comprising a virtualization agent operable to create the pooled storage capacity.

23. The host system as recited in claim 22, wherein the host system comprises a server implemented in the form of a computer.