Multi-stage slice recovery in a dispersed storage network

• US 10,318,380 B2
• Filed: 07/10/2018
• Issued: 06/11/2019
• Est. Priority Date: 06/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Resch, Jason K.
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US16/031,488
• Publication Number:
  US 20180322009A1
• Time in Patent Office: 336 Days
• 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/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2471 Distributed queries
• 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 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/33 Synchronisation based on error coding or decoding
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

Abstract

A method and computing device for use in a dispersed storage network (DSN) to recover corrupt encoded data slices. In response to a request to storage units of the DSN for encoded data slices corresponding to a data segment, the computing device of a receives at least a decode threshold number of encoded data slices and at least one integrity error message that provides an indication of a corrupt encoded data slice, such that less than a decoded threshold number of valid slices is received. Utilizing at least one correction approach involving stored integrity data, the computing device then corrects the corrupt slice(s) to produce a decode threshold number of encoded data slices in order to decode the corresponding data segment. A variety of correction approaches may be employed, including a multi-stage approach that utilizes data from both valid and invalid slices.

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:

in response to a request for encoded data slices of an encoded portion of a corresponding data segment, receiving at least a decode threshold number of encoded data slices from a set of storage units of the DSN in which the encoded data slices are stored, the encoded data slices including at least one encoded data slice identified as corrupt by a storage unit of the set of storage units (“

at least one corrupt encoded data slice”

) and less than a decoded threshold number of encoded data slices identified as valid by the set of storage units;

applying stored integrity information corresponding to the at least one encoded data slice identified as corrupt to determine if the at least one encoded data slice is valid; and

in response to determining that the at least one encoded data slice is not valid, correcting the at least one corrupt encoded data slice utilizing stored additional integrity information and at least one correction approach to produce the decode threshold number of encoded data slices.

2. The method of claim 1, further comprising:

decoding the decode threshold number of encoded data slices to generate the corresponding data segment.

3. The method of claim 1, wherein correcting the at least one corrupt encoded data slice includes:

selecting a first correction approach based on available additional integrity information;

attempting to correct the at least one corrupt encoded data slice using the first correction approach;

in response to determining that the first correction approach was not successful, selecting a second correction approach based on the available additional integrity information; and

correcting the at least one corrupt encoded data slice using the second correction approach.

4. The method of claim 1, the at least one correction approach utilizing slice substitution and available additional integrity information corresponding to a pre-encoded version of the corresponding data segment.

5. The method of claim 1, wherein the at least one correction approach includes byte-by-byte recovery of the at least one corrupt encoded data slice utilizing valid bytes, in a common byte position, from a decode threshold number of encoded data slices.

6. The method of claim 1, the at least one correction approach utilizing integrity information regarding the corresponding data segment.

7. The method of claim 1, the at least one correction approach utilizing integrity information generated by a dispersed storage error encoding process during encoding of the encoded data slices.