Storage system deduplication

• US 10,417,202 B2
• Filed: 12/21/2016
• Issued: 09/17/2019
• Est. Priority Date: 12/21/2016
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Nazari, Siamak, Wang, Jin, Murthy, Srinivasa D., Tamma, Roopesh Kumar
• Primary Examiner(s): Aspinwall, Evan
• Application Number:
  US15/387,603
• Publication Number:
  US 20180173731A1
• Time in Patent Office: 1,000 Days
• Field of Search: 707692
• CPC Class Codes: G06F 16/215 Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

An example storage system may include storage media and a storage controller. The storage controller may be to establish virtual volumes, private data stores, and a deduplication data store, each being a virtual storage space of the storage media, wherein each of the private data stores is associated with one of the virtual volumes and the deduplication data store is shared among the virtual volumes. The storage controller may, in response to receiving input data that is to be stored in a given one of the virtual volumes, determine a signature for the input data and select between storing the input data in the private data store associated with the given one of the virtual volumes and storing the input data in the deduplication data store. The storage controller may select where to store the input data based on whether a metadata storage location addressed by a first portion of the signature includes valid metadata, and, if so: whether the metadata includes a back-pointer to one of the virtual volumes, and whether a second portion of the signature matches a key included in the metadata.

Claims

1. A storage system comprising:

storage media;

processing circuitry; and

non-transitory machine-readable media storing machine-readable instructions that, when executed by the processing circuitry, cause the processing circuitry to;

establish virtual volumes, private data stores, and a deduplication data store, each being a virtual storage space of the storage media, wherein each of the private data stores is associated with one of the virtual volumes and the deduplication data store is shared among the virtual volumes;

in response to receiving input data that is to be stored in a given virtual volume of the virtual volumes, determine a signature for the input data and;

if a metadata storage location addressed by a first portion of the signature includes valid metadata, select where to store the input data based on;

whether the metadata includes a back-pointer to one of the virtual volumes, and

whether a second portion of the signature matches a key included in the metadata; and

if the metadata storage location does not include valid metadata,

store the second portion of the signature and a back-pointer to the given virtual volume in the metadata storage location, and

store the input data in the private data store associated with the given virtual volume.

2. The storage system of claim 1, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

if the metadata storage location addressed by the first portion of the signature includes valid metadata and if the second portion of the signature does not match the key included in the metadata, store the input data in the private data store associated with the given virtual volume.

3. The storage system of claim 1, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

if the metadata storage location addressed by the first portion of the signature includes valid metadata, if the second portion of the signature matches the key included in the metadata, and if the metadata includes a back-pointer to one of the virtual volumes, store the input data in the deduplication data store.

4. The storage system of claim 1, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

if the metadata storage location addressed by the first portion of the signature includes valid metadata, if the second portion of the signature matches the key included in the metadata, and if the metadata includes a pointer to a storage location in the deduplication data store;

compare the input data to data stored in the storage location pointed to by the pointer.

5. The storage system of claim 4, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

if the input data matches the data stored in the storage location pointed to by the pointer;

refrain from storing the input data and instruct the virtual volume to reference the storage location in the deduplication data store.

6. The storage system of claim 4, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

if the input data does not match the data stored in the storage location pointed to by the pointer;

store the input data in the private data store associated with the virtual volume.

7. The storage system of claim 1, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

in determining the signature for the input data, apply a hash function to a first portion of the input data to obtain a first hash and apply the hash function to a second portion of the input data to obtain a second hash,

wherein the signature comprises the combination of the first hash and the second hash.

8. Non-transitory machine-readable media storing machine-readable instructions that, when executed by processing circuitry of a storage system, cause the processing circuitry to:

establish virtual volumes, private data stores, and a deduplication data store, each being a virtual storage space of storage media of the storage system, wherein each of the private data stores is associated with one of the virtual volumes and the deduplication data store is shared among the virtual volumes; and

for input data that is to be stored in one of the virtual volumes;

determine a signature for the input data;

read a metadata storage location that is addressed by a first portion of the signature;

when the metadata storage location does not include valid metadata, store a second portion of the signature and a back-pointer to the virtual volume in the metadata storage location and store the input data in the private data store associated with the virtual volume; and

when the entry includes valid metadata, determine whether to store the input data in the private data store associated with the virtual volume or in the deduplication data store based on;

whether the metadata includes a back-pointer to one of the virtual volumes, and whether a second portion of the signature matches a key included in the metadata.

9. The non-transitory machine-readable media of claim 8, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

when the metadata storage location includes valid metadata and when the second portion of the signature does not match the key included in the metadata, store the input data in the private data store associated with the virtual volume.

10. The non-transitory machine-readable media of claim 8, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

when the metadata storage location includes valid metadata, when the second portion of the signature matches the key included in the metadata, and when the metadata includes a back-pointer to one of the virtual volumes, store the input data in the deduplication data store.

11. The non-transitory machine-readable media of claim 8, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

when the metadata storage location includes valid metadata, when the second portion of the signature matches the key included in the metadata, and when the metadata includes a pointer to a storage location in the deduplication data store;

compare the input data to data stored in the storage location pointed to by the pointer.

12. The non-transitory machine-readable media of claim 11, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

when the metadata storage location includes valid metadata, when the second portion of the signature matches the key included in the metadata, when the metadata includes a pointer to storage location in the deduplication data store, and when the input data does not match the data stored in the storage location pointed to by the pointer;

store the input data in the private data store associated with the virtual volume.

13. The non-transitory machine-readable media of claim 8, wherein the machine-readable instructions, when executed, further cause the processing circuitry to:

in determining the signature for the input data, apply a hash function to a first portion of the input data to obtain a first hash and apply the hash function to a second portion of the input data to obtain a second hash,

wherein the signature comprises the combination of the first hash and the second hash.

15. The method of claim 13, further comprising:

responsive to determining that the metadata storage location addressed by the first portion of the signature does not include valid metadata, storing the second portion of the signature and a back-pointer to the virtual volume in the metadata storage location and storing the input data in the private data store associated with the virtual volume.

14. A method of controlling a storage system comprising virtual volumes, private data stores associated respectively with the virtual volumes, and a deduplication data store shared among the virtual volumes, the method comprising:

determining a signature for input data that is to be written to one of the virtual volumes by applying a hash function to a first portion of the input data to obtain a first hash and applying the hash function to a second portion of the input data to obtain a second hash wherein the signature comprises the combination of the first hash and the second hash;

determining whether to store the input data in the private data store associated with the virtual volume or in the deduplication data store based on;

whether a metadata storage location addressed by a first portion of the signature includes valid metadata, and, when so;

whether the metadata includes a back-pointer to one of the virtual volumes, and

whether a second portion of the signature matches a key included in the metadata; and

storing the input data in the private data store associated with the virtual volume or in the deduplication data store.

16. The method of claim 14, further comprising:

responsive to determining that the metadata storage location addressed by the first portion of the signature includes valid metadata and that the second portion of the signature does not match the key included in the metadata, storing the input data in the private data store associated with the virtual volume.

17. The method of claim 14, further comprising:

responsive to determining that the metadata storage location addressed by the first portion of the signature includes valid metadata, that the second portion of the signature matches the key included in the metadata, and that the metadata includes a back-pointer to one of the virtual volumes, storing the input data in the deduplication data store.

18. The method of claim 14, further comprising:

responsive to determining that the metadata storage location addressed by the first portion of the signature includes valid metadata, that the second portion of the signature matches the key included in the metadata, and that the metadata includes a pointer to storage location in the deduplication data store;

comparing the input data to data stored in the storage location pointed to by the pointer and determining whether to store the input data in the private data store associated with the virtual volume or in the deduplication data store based on the comparison.