Data de-duplication in a dispersed storage network utilizing data characterization

• US 8,458,233 B2
• Filed: 09/17/2010
• Issued: 06/04/2013
• Est. Priority Date: 11/25/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Gladwin, S. Christopher, Abhijeet, Kumar, Dhuse, Greg, Resch, Jason K., Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US12/885,244
• Publication Number:
  US 20110125771A1
• Time in Patent Office: 991 Days
• Field of Search: 707/758, 707/812, 707/827, 707/959, 709/219
• US Class Current: 707/812
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• 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]
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

A method begins with a processing module receiving, from a requesting device, a data storage request that includes data for storage. The method continues with the processing module determining whether substantially identical data is currently stored in a dispersed storage network (DSN) memory. The method continues with the processing module encoding at least a portion of the data using an error coding dispersal storage function to produce a set of encoded data slices, sending the set of encoded data slices to the DSN memory for storage therein, and generating a unique retrieval matrix for the requesting device, wherein the unique retrieval matrix identifies a sub-set of encoded data slices of the set of encoded data slices for subsequent retrieval of the at least a portion of the data, when the substantially identical data is not stored in the DSN memory.

Claims

1. A computer implemented method comprises:

receiving, from a requesting device, a data storage request that includes data for storage;

determining whether substantially identical data is currently stored in a dispersed storage network (DSN) memory; and

when the substantially identical data is not stored in the DSN memory;

encoding at least a portion of the data using an error coding dispersal storage function to produce a set of encoded data slices;

sending the set of encoded data slices to the DSN memory for storage therein; and

generating a unique retrieval matrix for the requesting device, wherein the unique retrieval matrix identifies a sub-set of encoded data slices of the set of encoded data slices for subsequent retrieval of the at least a portion of the data; and

when the substantially identical data is stored in the DSN memory;

generating a second unique retrieval matrix for the requesting device, wherein the second unique retrieval matrix identifies a second sub-set of encoded data slices of the set of encoded data slices for subsequent retrieval of the at least a portion of the data.

2. The method of claim 1, wherein the determining whether the substantially identical data is currently stored in the DSN memory further comprises at least one of:

determining whether a data identifier associated with the data substantially matches a data identifier associated with the substantially identical data;

determining whether a calculated hash of the data substantially matches a stored hash of the substantially identical data; and

comparing the data to the substantially identical data.

3. The method of claim 1, wherein generating the unique retrieval matrix further comprises at least one of:

determining the unique retrieval matrix from a data identifier associated with the data;

determining the unique retrieval matrix based on a group identification code that identifies a group of requesting devices, which includes the requesting device;

determining the unique retrieval matrix based on an individual identification code of the requesting device; and

determining the unique retrieval matrix based on a matrix generating function.

4. The method of claim 1, wherein the unique retrieval matrix comprises at least one of:

a pillars list;

a segmenting protocol;

a pre-slice data manipulation function;

a forward error correction encoding function;

a slicing pillar width;

a post-slice data manipulation function;

a write threshold; and

a read threshold.

5. The method of claim 1, wherein the unique retrieval matrix comprises one of:

identity of a single unique sub-set of the encoded data slices, wherein a number of encoded data slices in the single unique sub-set of the encoded data slices is in a range including and between a read threshold of the error coding dispersal storage function and a pillar width of the error coding dispersal storage function; and

identity of a group of unique sub-sets of the encoded data slices, wherein one of the group of unique sub-sets of the encoded data slices is selected to be used as the sub-set of encoded data slices.

6. The method of claim 1 further comprises at least one of:

storing the unique retrieval matrix; and

sending the unique retrieval matrix to the requesting device.

7. A computer implemented method comprises:

receiving, from a requesting device, a read request for data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

obtaining a unique retrieval matrix based on an identity of the requesting device;

identifying a sub-set of encoded data slices for a set of the plurality of sets of the encoded data slices based on the unique retrieval matrix; and

when the sub-set of encoded data slices has been retrieved from the DSN memory;

sending the sub-set of encoded data slices to the requesting device;

or

decoding the sub-set of the encoded data slices to produce a decoded data segment and sending the decoded data segment to the requesting device;

when the sub-set of encoded data slices has not been retrieved from the DSN memory in a given time frame;

identifying a second sub-set of encoded data slices for the set of the plurality of sets of the encoded data slices based on the unique retrieval matrix; and

when the second sub-set of encoded data slices has been retrieved from the DSN memory;

sending the second sub-set of encoded data slices to the requesting device;

or

decoding the second sub-set of the encoded data slices to produce the decoded data segment and sending the decoded data segment to the requesting device.

8. The method of claim 7, wherein the obtaining the unique retrieval matrix further comprises one of:

receiving the unique retrieval matrix from the requesting device;

retrieving the unique retrieval matrix from the DSN memory based on the identity of the requesting device; and

generating the unique retrieval matrix based on one or more of;

the identity of the requesting device;

an error coding dispersal storage function;

a data identifier;

a unique retrieval matrix associated with at least one other requesting device of a plurality of requesting devices; and

a unique retrieval matrix functionality indicator.

9. A computer comprises:

an interface; and

a processing module operable to;

receive, from a requesting device via the interface, a data storage request that includes data for storage;

determine whether substantially identical data is currently stored in a dispersed storage network (DSN) memory; and

when the substantially identical data is not stored in the DSN memory;

encode at least a portion of the data using an error coding dispersal storage function to produce a set of encoded data slices;

send, via the interface, the set of encoded data slices to the DSN memory for storage therein; and

generate a unique retrieval matrix for the requesting device, wherein the unique retrieval matrix identifies a sub-set of encoded data slices of the set of encoded data slices for subsequent retrieval of the at least a portion of the data and

when the substantially identical data is stored in the DSN memory;

generate a second unique retrieval matrix for the requesting device, wherein the second unique retrieval matrix identifies a second sub-set of encoded data slices of the set of encoded data slices for subsequent retrieval of the at least a portion of the data.

10. The computer of claim 9, wherein the processing module further functions to determine whether the substantially identical data is currently stored in the DSN memory by at least one of:

determining whether a data identifier associated with the data substantially matches a data identifier associated with the substantially identical data;

determining whether a calculated hash of the data substantially matches a stored hash of the substantially identical data; and

comparing the data to the substantially identical data.

11. The computer of claim 9, wherein the processing module further functions to generate the unique retrieval matrix by at least one of:

determining the unique retrieval matrix from a data identifier associated with the data;

determining the unique retrieval matrix based on a group identification code that identifies a group of requesting devices, which includes the requesting device;

determining the unique retrieval matrix based on an individual identification code of the requesting device; and

determining the unique retrieval matrix based on a matrix generating function.

12. The computer of claim 9, wherein the unique retrieval matrix comprises at least one of:

a pillars list;

a segmenting protocol;

a pre-slice data manipulation function;

a forward error correction encoding function;

a slicing pillar width;

a post-slice data manipulation function;

a write threshold; and

a read threshold.

13. The computer of claim 9, wherein the unique retrieval matrix comprises one of:

identity of a single unique sub-set of the encoded data slices, wherein a number of encoded data slices in the single unique sub-set of the encoded data slices is in a range including and between a read threshold of the error coding dispersal storage function and a pillar width of the error coding dispersal storage function; and

identity of a group of unique sub-sets of the encoded data slices, wherein one of the group of unique sub-sets of the encoded data slices is selected to be used as the sub-set of encoded data slices.

14. The computer of claim 9, wherein the processing module further functions to perform at least one of:

controlling storage of the unique retrieval matrix; and

sending, via the interface, the unique retrieval matrix to the requesting device.

15. A computer comprises:

an interface; and

a processing module operable to;

receive, from a requesting device via the interface, a read request for data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

obtain a unique retrieval matrix based on an identity of the requesting device;

identify a sub-set of encoded data slices for a set of the plurality of sets of the encoded data slices based on the unique retrieval matrix; and

when the sub-set of encoded data slices has been retrieved from the DSN memory;

send, via the interface, the sub-set of encoded data slices to the requesting device;

or decode the sub-set of the encoded data slices to produce a decoded data segment and send, via the interface, the decoded data segment to the requesting device

when the sub-set of encoded data slices has not been retrieved from the DSN memory in a given time frame;

identify a second sub-set of encoded data slices for the set of the plurality of sets of the encoded data slices based on the unique retrieval matrix; and

when the second sub-set of encoded data slices has been retrieved from the DSN memory;

send, via the interface, the second sub-set of encoded data slices to the requesting device;

or

decode the second sub-set of the encoded data slices to produce the decoded data segment and send, via the interface, the decoded data segment to the requesting device.

16. The computer of claim 15, wherein the processing module further functions to obtain the unique retrieval matrix by one of:

receiving, via the interface, the unique retrieval matrix from the requesting device;

retrieving, via the interface, the unique retrieval matrix from the DSN memory based on the identity of the requesting device; and

generating the unique retrieval matrix based on one or more of;

the identity of the requesting device;

an error coding dispersal storage function;

a data identifier;

a unique retrieval matrix associated with at least one other requesting device of a plurality of requesting devices; and

a unique retrieval matrix functionality indicator.