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

• US 8,762,346 B2
• Filed: 06/03/2013
• Issued: 06/24/2014
• Est. Priority Date: 11/25/2009
• Status: Active Grant

• 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, Markison, Timothy W.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/908,516
• Publication Number:
  US 20130262854A1
• Time in Patent Office: 386 Days
• Field of Search: 707/758, 707/812, 707/827, 707/959, 707/664, 707/678, 707/691, 707/692, 707/697, 707/831, 709/219, 711/153, 711/161, 711/162
• US Class Current: 707/678
• 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 computing device includes a processing module and an interface. The processing module is operable to receive, from a requesting device via the interface, a data storage request that includes data for storage. The processing module then determines whether substantially identical data is currently stored in a dispersed storage network (DSN) memory. When the substantially identical data is stored in the DSN memory, the processing module generates, for the requesting device, a second unique retrieval matrix of a plurality of sets of encoded data slices corresponding to the already stored substantially identical data, wherein the requesting device can recover at least a portion of the data based on the second unique retrieval matrix of the plurality of sets of encoded data slices.

Claims

1. A method for execution by a processing module of a computing device, the method comprises:

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

determining, by the processing module, whether substantially identical data is currently stored in a dispersed storage network (DSN) memory as a plurality of sets of encoded data slices, wherein the identical data was encoded in accordance with a dispersed storage error encoding function to produce the plurality of sets of encoded data slices, and wherein the substantially identical data is recoverable based on a unique retrieval matrix of the plurality of sets of encoded data slices; and

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

generating, for the requesting device, a second unique retrieval matrix of the plurality of sets of encoded data slices, wherein the requesting device can recover at least a portion of the data based on the second unique retrieval matrix of the plurality of sets of encoded data slices, wherein;

the unique retrieval matrix including;

for a first set of encoded data slices of the plurality of sets of encoded data slices, identity of a first sub-set of encoded data slices of the first set of encoded data slices; and

for a second set of encoded data slices of the plurality of sets of encoded data slices, identity of a first sub-set of encoded data slices of the second set of encoded data slices; and

the second unique retrieval matrix including;

for the first set of encoded data slices of the plurality of sets of encoded data slices, identity of a second sub-set of encoded data slices of the first set of encoded data slices; and

for the second set of encoded data slices of the plurality of sets of encoded data slices, identity of a second sub-set of encoded data slices of the second set of encoded data slices, wherein each sub-set of encoded data slices includes a least a decode threshold number of encoded data slices.

2. The method of claim 1 further comprises:

the first sub-set of encoded data slices of the first set of encoded data slices including at least some encoded data slices having different pillar numbers than encoded data slices of the first sub-set of encoded data slices of the second set of encoded data slices; and

the second sub-set of encoded data slices of the first set of encoded data slices including at least some encoded data slices having different pillar numbers than encoded data slices of the second sub-set of encoded data slices of the second set of encoded data slices.

3. 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.

4. The method of claim 1 further comprises:

generating, using a key generating function, an encryption key based on the data; and

comparing the encryption key with a stored encryption key of the substantially identical data, wherein the stored encryption key was generated, using the key generating function, based on the substantially identical data; and

when the encryption key compares favorably with the stored encryption key, indicating that the substantially identical data is currently stored.

5. The method of claim 4, wherein the key generating function comprises at least one of:

setting the encryption key to be substantially equal to the data; and

generating a representation of the data and setting the encryption key to be substantially equal to the representation of the data, wherein the representation of the data is generated by a reversible transformation such equivalency, adding a constant, subtracting a constant, or inverting one or more bits.

6. The method of claim 4 further comprises:

generating a key reference based on the encryption key; and

comparing the encryption key with a stored encryption key by comparing the key reference with a stored key reference of the stored encryption key.

7. The method of claim 6, wherein the generating the key reference comprises at least one of:

transforming the encryption key;

performing a hash function on the encryption key;

equating the key reference to a distributed stored network (DSN) address at which the encryption key is stored;

equating the key reference to information regarding the data, wherein the information includes one or more of;

data object name, a data size, a hash of the data object, and indicators regarding the data.

8. A computing device 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 as a plurality of sets of encoded data slices, wherein the identical data was encoded in accordance with a dispersed storage error encoding function to produce the plurality of sets of encoded data slices, and wherein the substantially identical data is recoverable based on a unique retrieval matrix of the plurality of sets of encoded data slices; and

when the substantially identical data is stored in the DSN memory, generate, for the requesting device, a second unique retrieval matrix of the plurality of sets of encoded data slices, wherein the requesting device can recover at least a portion of the data based on the second unique retrieval matrix of the plurality of sets of encoded data slices, wherein;

the unique retrieval matrix including;

for a first set of encoded data slices of the plurality of sets of encoded data slices, identity of a first sub-set of encoded data slices of the first set of encoded data slices; and

for a second set of encoded data slices of the plurality of sets of encoded data slices, identity of a first sub-set of encoded data slices of the second set of encoded data slices; and

the second unique retrieval matrix including;

for the first set of encoded data slices of the plurality of sets of encoded data slices, identity of a second sub-set of encoded data slices of the first set of encoded data slices; and

for the second set of encoded data slices of the plurality of sets of encoded data slices, identity of a second sub-set of encoded data slices of the second set of encoded data slices, wherein each sub-set of encoded data slices includes a least a decode threshold number of encoded data slices.

9. The computing device of claim 8 further comprises:

the first sub-set of encoded data slices of the first set of encoded data slices including at least some encoded data slices having different pillar numbers than encoded data slices of the first sub-set of encoded data slices of the second set of encoded data slices; and

the second sub-set of encoded data slices of the first set of encoded data slices including at least some encoded data slices having different pillar numbers than encoded data slices of the second sub-set of encoded data slices of the second set of encoded data slices.

10. The computing device of claim 8, wherein the processing module is further operable 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 computing device of claim 8, wherein the processing module is further operable to:

generate, using a key generating function, an encryption key based on the data; and

compare the encryption key with a stored encryption key of the substantially identical data, wherein the stored encryption key was generated, using the key generating function, based on the substantially identical data; and

when the encryption key compares favorably with the stored encryption key, indicate that the substantially identical data is currently stored.

12. The computing device of claim 11, wherein the key generating function comprises at least one of:

setting the encryption key to be substantially equal to the data; and

generating a representation of the data and setting the encryption key to be substantially equal to the representation of the data, wherein the representation of the data is generated by a reversible transformation such equivalency, adding a constant, subtracting a constant, or inverting one or more bits.

13. The computing device of claim 11, wherein the processing module is further operable to:

generate a key reference based on the encryption key; and

compare the encryption key with the stored encryption key by comparing the key reference with a stored key reference of the stored encryption key.

14. The computing device of claim 13, wherein the processing module is further operable to generate the key reference by at least one of:

transforming the encryption key;

performing a hash function on the encryption key;

equating the key reference to a distributed stored network (DSN) address at which the encryption key is stored;

equating the key reference to information regarding the data, wherein the information includes one or more of;

data object name, a data size, a hash of the data object, and indicators regarding the data.