Multi-stage slice recovery in a dispersed storage network

• US 10,025,665 B2
• Filed: 06/16/2016
• Issued: 07/17/2018
• 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:
  US15/184,614
• Publication Number:
  US 20170004041A1
• Time in Patent Office: 761 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 for use by a computing device 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 less than a decode threshold number of valid encoded data slices and at least one integrity error message that provides an indication of a corrupt encoded data slice. The computing device requests and receives at least one corrupt encoded data slice corresponding to the integrity error message(s). 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, receiving less than a decode threshold number of encoded data slices and at least one integrity error message from a set of storage units of the DSN in which the encoded data slices are stored, wherein each of the encoded data slices is an encoded portion of a corresponding data segment, and the at least one integrity error message provides an indication of a corrupt encoded data slice;

requesting at least one corrupt encoded data slice from the set of storage units;

receiving the at least one corrupt encoded data slice; and

correcting the at least one corrupt encoded data slice, utilizing at least one correction approach, to produce at least 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 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 available integrity information; and

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

4. The method of claim 1, wherein the at least one correction approach includes applying stored integrity information corresponding to the at least one corrupt encoded data slice to determine if the data of the encoded data slice is valid.

5. The method of claim 1, the at least one correction approach utilizing slice substitution and a stored integrity value corresponding to a pre-encoded version of the data segment.

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

7. The method of claim 1, the at least one correction approach utilizing at least one of:

stored integrity information regarding the data segment, stored integrity information generated by a dispersed storage error encoding process during encoding of the encoded data slices, or stored integrity information regarding individual ones of the encoded data slices generated prior to storage of the encoded data slices in the set of storage units.