Efficient storage of encrypted data in a dispersed storage network

• US 9,043,616 B2
• Filed: 07/21/2014
• Issued: 05/26/2015
• 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: Grube, Gary W., Markison, Timothy W., Gladwin, S. Christopher, Abhijeet, Kumar, Dhuse, Greg, Resch, Jason K.
• Primary Examiner(s): Eskandarnia, Arvin
• Application Number:
  US14/336,189
• Publication Number:
  US 20140331104A1
• Time in Patent Office: 309 Days
• Field of Search: 713/193
• US Class Current: 713/193
• 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 obtaining data to store and determining whether substantially similar data to the data is stored. When the substantially similar data is not stored, the method continues with the processing module generating a first encryption key based on the data, encoding the first encryption key into encoded data slices in accordance with an error coding dispersal storage function, and storing the encoded data slices in a dispersed storage network (DSN) memory. The method continues with the processing module encrypting the data using an encryption key of the substantially similar data in accordance with an encryption function to produce encrypted data, compressing the encrypted data in accordance with a compression function to produce compressed data, storing the compressed data when the substantially similar data is stored.

Claims

1. A method for execution by a processing module in a distributed storage (DS) unit, the method comprising:

receiving, via a communication interface of the DS unit, a request to retrieve data from a requesting device;

identifying first unique retrieval matrix that is assigned to the requesting device and that is associated with one or more sets within first plurality of sets of error coded (EC) data slices, wherein first substantially similar data to the data is stored within dispersed storage network (DSN) memory as the first plurality of sets of EC data slices;

determining whether a decode threshold number of EC data slices within at least one set of the one or more sets of the first plurality of sets of EC data slices is available for retrieval based on the first unique retrieval matrix;

when availability of the decode threshold number of EC data slices for retrieval is determined, transmitting, via the communication interface of the DS unit, the first unique retrieval matrix to the requesting device;

when less than the decode threshold number of EC data slices for retrieval is determined to be available;

generating second plurality of sets of EC data slices to store second substantially similar data to the data;

storing the second plurality of sets of EC data slices within the DSN memory;

assigning second unique retrieval matrix of the second plurality of sets of EC data slices to the requesting device, wherein the requesting device can recover a decode threshold number of EC data slices within at least one set of the second plurality of sets of EC data slices based on the second unique retrieval matrix; and

transmitting, via the communication interface of the DS unit, the second unique retrieval matrix to the requesting device.

2. The method of claim 1, wherein the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device.

3. The method of claim 2, wherein the determining whether the decode threshold number of EC data slices within at least one set of the one or more sets of the first plurality of sets of EC data slices is available for retrieval based on the first unique retrieval matrix further comprises:

determining whether a decode threshold number of EC data slices within a first unique pillar combination of a first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval;

when availability of the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the first unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device; and

when less than the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined to be available;

determining whether a second unique pillar combination of the first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval; and

when availability of the second unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the second unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device.

4. The method of claim 1, wherein:

the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device; and

the less than the decode threshold number of EC data slices for retrieval is determined when there an additional decode threshold number of EC data slices within an additional unique pillar combination cannot be identified as available for any other set within the first plurality of sets of EC data slices.

5. The method of claim 1, wherein the generating the second plurality of sets of EC data slices further comprises:

generating the second plurality of sets of EC data slices based on one or more write operational parameters that include at least one write operational parameter that is not included in other one or more write operational parameters by which the second plurality of sets of EC data slices are generated.

6. The method of claim 1, wherein the storing the second plurality of sets of EC data slices within the DSN memory further comprises:

storing the second plurality of sets of EC data slices within first one or more DS units that include at least one DS unit that is not included within second one or more DS units that store the first plurality of sets of EC data slices.

7. The method of claim 1, wherein the first unique retrieval matrix corresponds to one or more read operational parameters for use in recovering the decode threshold number of EC data slices within the at least one set of the one or more sets of the first plurality of sets of EC data slices.

8. The method of claim 7, wherein the one or more read operational parameters is based on one or more of:

an estimation of a number of common requesting devices;

an actual number of common requesting devices;

a subscription level indicator of the requesting device;

a number of sets within the first plurality of sets of EC data slices;

a previous read operational parameter;

a user ID;

the request to store data;

a data object name;

a data size;

a data type;

a data object;

a data object hash;

a priority indicator;

a security indicator;

or

a performance indicator.

9. A distributed storage (DS) processing unit comprises:

a communication interface; and

a processing module configured to;

receive, via the communication interface, a request to retrieve data from a requesting device;

identify first unique retrieval matrix that is assigned to the requesting device and that is associated with one or more sets within first plurality of sets of error coded (EC) data slices, wherein first substantially similar data to the data is stored within dispersed storage network (DSN) memory as the first plurality of sets of EC data slices;

determine whether a decode threshold number of EC data slices within at least one set of the one or more sets of the first plurality of sets of EC data slices is available for retrieval based on the first unique retrieval matrix;

when availability of the decode threshold number of EC data slices for retrieval is determined, transmit, via the communication interface of the DS unit, the first unique retrieval matrix to the requesting device;

when less than the decode threshold number of EC data slices for retrieval is determined to be available;

generate second plurality of sets of EC data slices to store second substantially similar data to the data;

store the second plurality of sets of EC data slices within the DSN memory;

assign second unique retrieval matrix of the second plurality of sets of EC data slices to the requesting device, wherein the requesting device can recover a decode threshold number of EC data slices within at least one set of the second plurality of sets of EC data slices based on the second unique retrieval matrix; and

transmit, via the communication interface of the DS unit, the second unique retrieval matrix to the requesting device.

10. The DS processing unit of claim 9, wherein the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device.

11. The DS processing unit of claim 10, wherein the processing module is further configured to:

determining whether a decode threshold number of EC data slices within a first unique pillar combination of a first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval;

when availability of the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the first unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device; and

when less than the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined to be available;

determining whether a second unique pillar combination of the first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval; and

when availability of the second unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the second unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device.

12. The DS processing unit of claim 9, wherein:

the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device; and

the less than the decode threshold number of EC data slices for retrieval is determined when there an additional decode threshold number of EC data slices within an additional unique pillar combination cannot be identified as available for any other set within the first plurality of sets of EC data slices.

13. The DS processing unit of claim 9, wherein the processing module is further configured to:

generate the second plurality of sets of EC data slices based on one or more write operational parameters that include at least one write operational parameter that is not included in other one or more write operational parameters by which the second plurality of sets of EC data slices are generated.

14. The DS processing unit of claim 9, wherein the processing module is further configured to:

store the second plurality of sets of EC data slices within first one or more DS units that include at least one DS unit that is not included within second one or more DS units that store the first plurality of sets of EC data slices.

15. The DS processing unit of claim 9, wherein the first unique retrieval matrix corresponds to one or more read operational parameters for use in recovering the decode threshold number of EC data slices within the at least one set of the one or more sets of the first plurality of sets of EC data slices.

16. A non-transitory computer readable medium having instructions causing a processing module in a distributed storage (DS) unit to execute a method comprising:

receiving, via a communication interface of the DS unit, a request to retrieve data from a requesting device;

identifying first unique retrieval matrix that is assigned to the requesting device and that is associated with one or more sets within first plurality of sets of error coded (EC) data slices, wherein first substantially similar data to the data is stored within dispersed storage network (DSN) memory as the first plurality of sets of EC data slices;

determining whether a decode threshold number of EC data slices within at least one set of the one or more sets of the first plurality of sets of EC data slices is available for retrieval based on the first unique retrieval matrix;

when availability of the decode threshold number of EC data slices for retrieval is determined, transmitting, via the communication interface of the DS unit, the first unique retrieval matrix to the requesting device;

when less than the decode threshold number of EC data slices for retrieval is determined to be available;

generating second plurality of sets of EC data slices to store second substantially similar data to the data;

storing the second plurality of sets of EC data slices within the DSN memory;

assigning second unique retrieval matrix of the second plurality of sets of EC data slices to the requesting device, wherein the requesting device can recover a decode threshold number of EC data slices within at least one set of the second plurality of sets of EC data slices based on the second unique retrieval matrix; and

transmitting, via the communication interface of the DS unit, the second unique retrieval matrix to the requesting device.

17. The non-transitory computer readable medium having instructions causing the processing module to execute the method of claim 16, wherein the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device.

18. The non-transitory computer readable medium having instructions causing the processing module to execute the method of claim 17, wherein the determining whether the decode threshold number of EC data slices within at least one set of the one or more sets of the first plurality of sets of EC data slices is available for retrieval based on the first unique retrieval matrix further comprises:

determining whether a decode threshold number of EC data slices within a first unique pillar combination of a first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval;

when availability of the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the first unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device; and

when less than the decode threshold number of EC data slices within the first unique pillar combination for retrieval is determined to be available;

determining whether a second unique pillar combination of the first set within the first plurality of sets of EC data slices that is assigned to the requesting device is available for retrieval; and

when availability of the second unique pillar combination for retrieval is determined, transmitting, via the communication interface of the DS unit, the second unique pillar combination of the first set within the first plurality of sets of EC data slices to the requesting device.

19. The non-transitory computer readable medium having instructions causing the processing module to execute the method of claim 16, wherein:

the first unique retrieval matrix identifies one or more unique pillar combinations of the one or more sets within the first plurality of sets of EC data slices that are assigned to the requesting device; and

the less than the decode threshold number of EC data slices for retrieval is determined when there an additional decode threshold number of EC data slices within an additional unique pillar combination cannot be identified as available for any other set within the first plurality of sets of EC data slices.

20. The non-transitory computer readable medium having instructions causing the processing module to execute the method of claim 16, wherein:

the generating the second plurality of sets of EC data slices further comprises generating the second plurality of sets of EC data slices based on one or more write operational parameters that include at least one write operational parameter that is not included in other one or more write operational parameters by which the second plurality of sets of EC data slices are generated; and

the storing the second plurality of sets of EC data slices within the DSN memory further comprises storing the second plurality of sets of EC data slices within first one or more DS units that include at least one DS unit that is not included within second one or more DS units that store the first plurality of sets of EC data slices.