Reliably recovering stored data in a dispersed storage network

• US 10,152,601 B2
• Filed: 03/31/2015
• Issued: 12/11/2018
• Est. Priority Date: 06/05/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Volvovski, Ilya, Cabral, Bruno Hennig, Motwani, Manish, Cocagne, Thomas Darrel, Markison, Timothy W., Grube, Gary W., Leggette, Wesley, Resch, Jason K., Storm, Michael Colin, Dhuse, Greg, Vedpathak, Yogesh Ramesh, Khadiwala, Ravi
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US14/675,360
• Publication Number:
  US 20150355980A1
• Time in Patent Office: 1,351 Days
• Field of Search: 707674
• 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/1464 for networked environments
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• 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/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• 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
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB

Abstract

A method begins by storage units of a dispersed storage network (DSN) receiving a retrieval request for a data object, where each storage unit stores a unique group of encoded data slices of the data object and a local set of encoded recovery data slices. The method continues with some storage units sending the unique group of encoded data slices to a requesting computing device and with one storage unit sending an encoded recovery data slice to the requesting computing device. The method continues with the requesting computing device identifying an errant unique group encoded data slice, correcting the errant encoded data slice based on received data slices to produce an updated unique group of encoded data slices, and dispersed storage error decoding the updated unique group of encoded data slices and the unique groups of encoded data slices from other storage units to recover the data object.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

sending, to a set of storage units of a dispersed storage network (DSN), a retrieval request for a data object, wherein the data object includes a plurality of data segments, wherein the plurality of data segments is dispersed storage error encoded to create a plurality of sets of encoded data slices, wherein each storage unit of the set of storage units stores a unique group of encoded data slices of the plurality of sets of encoded data slices, and wherein one or more storage units of the set of storage units dispersed storage error encodes at least one encoded data slice of the unique group of encoded data slices to produce a local set of encoded recovery data slices;

receiving, from each storage unit of a decode threshold number of storage units of the set of storage units, the unique group of encoded data slices;

receiving, from one or more of the decode threshold number of storage units, at least one encoded recovery data slice of the local set of encoded recovery data slices;

identifying an errant encoded data slice of the unique group of encoded data slices received from the one of the decode threshold number of storage units;

correcting the errant encoded data slice based on encoded data slices of the unique group of encoded data slices that are not errant encoded data slices from the one of the decode threshold number of storage units and the at least one encoded recovery data slices received from the one of the decode threshold number of storage units to produce an updated unique group of encoded data slices; and

dispersed storage error decoding the updated unique group of encoded data slices to recover the data object.

2. The method of claim 1, wherein

each storage unit of the decode threshold number of storage units determines whether the respective unique group of encoded data slices includes an encoded data slice requiring rebuilding and further wherein

the one of the decode threshold number of storage units identifies the encoded data slice requiring rebuilding in the unique group of encoded data slices of the one of the decode threshold number of storage units.

3. The method of claim 1 further comprises:

receiving, from one of the decode threshold number of storage units, a unique encoded recovery data slice of the local set of encoded recovery data slices for each of multiple encoded data slices that require rebuilding, wherein

the one of the decode threshold number of storage units provides information sufficient to identify multiple encoded data slices in the unique group of encoded data slices of the one of the decode threshold number of storage units that require rebuilding.

4. The method of claim 1 further comprises:

receiving, from a second one of the decode threshold number of storage units, at least one encoded recovery data slice of the local set of encoded recovery data slices of the second one of the decode threshold number of storage units, wherein

each storage unit of the decode threshold number of storage units determines whether the respective unique group of encoded data slices includes an encoded data slice requiring rebuilding and wherein

a second one of the decode threshold number of storage units provides information sufficient to identify the encoded data slice requiring rebuilding in the unique group of encoded data slices of the second one of the decode threshold number of storage units.

5. The method of claim 1 further comprises:

receiving, from each storage unit of the decode threshold number of storage units, at least one encoded recovery data slice of a respective local set of encoded recovery data.

6. The method of claim 1, wherein the identifying the errant encoded data slice comprises at least one of:

receiving an indication from the one of the decode threshold number of storage units;

performing an integrity check on the errant encoded data slice; and

identifying the errant encoded data slice from a rebuild list.

7. The method of claim 1 further comprises:

creating a rebuilt encoded data slice from the at least one encoded recovery data slice and remaining encoded data slices of the unique group of encoded data slices; and

replacing the errant encoded data slice with the rebuilt encoded data slice to produce the updated unique group of encoded data slices.

8. The method of claim 1 further comprises:

selecting the decode threshold number of storage units based on one or more of;

identifying the decode threshold number of storage units based on reliability of the storage units in the decode threshold number of storage units;

identifying the decode threshold number of storage units based on decoding efficiency of the unique groups of encoded data slices stored by the storage units in the decode threshold number of storage units; and

identifying the decode threshold number of storage units based on availability of the storage units in the decode threshold number of storage units.

9. The method of claim 1 further comprises:

determining that a data segment of the plurality of data segments is unrecoverable due to a corresponding set of encoded data slices including less than a decode threshold number of uncorrupted encoded data slices;

sending a request for the local set of encoded recovery data slices from each of the storage units of the decode threshold number of storage units; and

utilizing the local set of encoded recovery data slices from each of the storage units of the decode threshold number of storage units and the unique group of encoded data slices from the decode threshold number of storage units to recover the data segment.

10. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), causes the one or more computing devices to;

send, to a set of storage units of the DSN, a retrieval request for a data object, wherein the data object includes a plurality of data segments, wherein the plurality of data segments is dispersed storage error encoded to create a plurality of sets of encoded data slices, wherein each storage unit of the set of storage units stores a unique group of encoded data slices of the plurality of sets of encoded data slices, and wherein one or more storage units of the set of storage units dispersed storage error encodes at least one encoded data slice of the unique group of encoded data slices to produce a local set of encoded recovery data slices;

send, by each storage unit of a decode threshold number of storage units of the set of storage units, the unique group of encoded data slices to a requesting computing device;

receive, from one of the decode threshold number of storage units, at least one encoded recovery data slice of the local set of encoded recovery data slices;

identify an errant encoded data slice of the unique group of encoded data slices from the one of the decode threshold number of storage units;

correct the errant encoded data slice based on encoded data slices of the unique group of encoded data slices that are not errant encoded data slices from the one of the decode threshold number of storage units and at least one encoded recovery data slice received from the one of the decode threshold number of storage units to produce an updated unique group of encoded data slices; and

dispersed storage error decoding the updated unique group of encoded data slices to recover the data object.

11. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

receive from the one of the decode threshold number of storage units, the encoded data slice requiring rebuilding in the unique group of encoded data slices of the one of the decode threshold number of storage units, wherein each storage unit of the decode threshold number of storage units determines whether the respective unique group of encoded data slices includes an encoded data slice requiring rebuilding.

12. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

receive, from one of the decode threshold number of storage units, a unique encoded recovery data slice of the local set of encoded recovery data slices for each of multiple encoded data slices that require rebuilding, wherein

the one of the decode threshold number of storage units provides information sufficient to identify multiple encoded data slices in the unique group of encoded data slices of the one of the decode threshold number of storage units that require rebuilding.

13. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

receive, from a second one of the decode threshold number of storage units, at least one encoded recovery data slice of the local set of encoded recovery data slices of the second one of the decode threshold number of storage units to the requesting computing device, wherein

each storage unit of the decode threshold number of storage units determines whether the respective unique group of encoded data slices includes an encoded data slice requiring rebuilding and wherein

a second one of the decode threshold number of storage units provides information sufficient to identify the encoded data slice requiring rebuilding in the unique group of encoded data slices of the second one of the decode threshold number of storage units.

14. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

receive, from each storage unit of the decode threshold number of storage units, at least one encoded recovery data slice of a respective local set of encoded recovery data.

15. The non-transitory computer readable storage medium of claim 10, wherein the one or more processing modules functions to execute operational instructions stored by at least one memory section to cause the one or more computing devices of the DSN to identify the errant encoded data slice by at least one of:

receiving an indication from the one of the decode threshold number of storage units;

performing an integrity check on the errant encoded data slice; and

identifying the errant encoded data slice from a rebuild list.

16. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

create a rebuilt encoded data slice from the at least one encoded recovery data slice and remaining encoded data slices of the unique group of encoded data slices; and

replace the errant encoded data slice with the rebuilt encoded data slice to produce the updated unique group of encoded data slices.

17. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

select the decode threshold number of storage units based on one or more of;

identifying the decode threshold number of storage units based on reliability of the storage units in the decode threshold number of storage units;

identifying the decode threshold number of storage units based on decoding efficiency of the unique groups of encoded data slices stored by the storage units in the decode threshold number of storage units; and

identifying the decode threshold number of storage units based on availability of the storage units in the decode threshold number of storage units.

18. The non-transitory computer readable storage medium of claim 10 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

determine that a data segment of the plurality of data segments is unrecoverable due to a corresponding set of encoded data slices including less than a decode threshold number of uncorrupted encoded data slices;

send a request for the local set of encoded recovery data slices from each of the storage units of the decode threshold number of storage units; and

utilize the local set of encoded recovery data slices from each of the storage units of the decode threshold number of storage units and the unique group of encoded data slices from the decode threshold number of storage units to recover the data segment.