# US 2018/0322009 A1 · Multi-stage slice recovery in a dispersed storage network

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0322009 A1
- Document ID: US20180322009A1
- Status: Published application
- Kind: A1
- Application number: 16/031,488
- Filed: 2018-07-10
- Published: 2018-11-08
- Earliest claimed: 2015-06-30
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Jason K. Resch
- Web page: https://patentgrep.com/patent/US20180322009A1

## CPC

- G06F 11/1076: {Parity data used in redundant arrays of independent storages, e.g. in RAID systems}
- G06F 3/0619: {in relation to data integrity, e.g. data losses, bit errors}
- G06F 3/064: {Management of blocks}
- G06F 3/065: {Replication mechanisms}
- G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]}
- 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)}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/24578: {using ranking}
- G06F 16/2471: {Distributed queries}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F 16/273: {Asynchronous replication or reconciliation}
- H03M 13/33: Synchronisation based on error coding or decoding
- 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}
- 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)
- H04L 67/06: specially adapted for file transfer, e.g. file transfer protocol [FTP]
- H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
- 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]
- H04L 67/51: Discovery or management thereof, e.g. service location protocol [SLP] or web services
- G06F 2201/805: Real-time
- H03M 13/1515: {Reed-Solomon codes}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
decoding the decode threshold number of encoded data slices to generate the corresponding data segment.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 1)

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.

### Claim 8

A computing device of a group of computing devices of a dispersed storage network (DSN), the computing device comprises:
an interface;
a local memory; and
a processing module operably coupled to the interface and the local memory, wherein the processing module is configured to:
transmit to a set of storage units of the DSN, via the interface, a request for encoded data slices, wherein each of the encoded data slices is an encoded portion of a corresponding data segment;
receive, via the interface, at least a decode threshold number of requested encoded data slices from the set of storage units of the DSN, 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;
apply stored integrity information corresponding to the at least one corrupt encoded data slice to determine if the at least one corrupt encoded data slice is instead valid; and
in response to determining that the at least one corrupt encoded data slice is not valid, correct 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.

### Claim 9 (depends on 8)

The computing device of claim 8, wherein the processing module is further configured to:
decode the decode threshold number of encoded data slices to generate the corresponding data segment.

### Claim 10 (depends on 8)

The computing device of claim 8, wherein correction of 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 integrity information; and
correcting the at least one corrupt encoded data slice using the second correction approach.

### Claim 11 (depends on 8)

The computing device of claim 8, wherein the at least one correction approach utilizes slice substitution and available additional integrity information corresponding to a pre-encoded version of the corresponding data segment.

### Claim 12 (depends on 8)

The computing device of claim 8, wherein the local memory includes additional integrity information corresponding to a pre-encoded version of the corresponding data segment, wherein the at least one correction approach includes applying the additional integrity information to determine if the encoded data slice is valid.

### Claim 13 (depends on 8)

The computing device of claim 8, 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.

### Claim 14 (depends on 8)

The computing device of claim 8, wherein the at least one correction approach utilizes integrity information regarding the corresponding data segment.

### Claim 15 (depends on 8)

The computing device of claim 8, wherein the at least one correction approach utilizes integrity information generated by a dispersed storage error encoding process during encoding of the encoded data slices.

### Claim 16 (depends on 8)

The computing device of claim 8, wherein the at least one correction approach utilizes 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.