PARTIAL REBUILDING TECHNIQUES IN A DISPERSED STORAGE UNIT

• US 20180107554A1
• Filed: 12/19/2017
• Published: 04/19/2018
• Est. Priority Date: 10/29/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg R., Vossberg, Trevor J., Resch, Jason K.
• Granted Patent: US 10,095,582 B2
• Time in Patent Office: 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• 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/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: H03M 13/118 Parity check matrix structured for simplifying encoding, e.g. by having a triangular or an approximate triangular structure H03M13/1165 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• 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 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]

Abstract

Methods for use in a dispersed storage network (DSN) to rebuild data. In various examples, at least one data segment of a data object is dispersed storage error encoded to produce a set of encoded data slices that includes an information dispersal algorithm (IDA) width number of encoded data slices, wherein the IDA width number is at least twice the number of storage units of a set of storage units utilized to store the data object. At least two encoded data slices are stored in each of the storage units. In response to detecting a storage error indicating an error slice, a partial threshold number of partial encoded data slices (generated by performing a partial encoding function on stored encoded data slices) are generated. The partial threshold number of partial encoded data slice responses are combined to produce a rebuilt encoded data slice corresponding to the error slice.

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:

receiving a data object for storage in a set of storage units of the DSN;

dispersed storage error encoding at least one data segment of the data object to produce a set of encoded data slices that includes an information dispersal algorithm (IDA) width number of encoded data slices, wherein the IDA width number is at least twice the number of storage units in the set of storage units;

facilitating storage of the set of encoded data slices in the set of storage units, where at least two encoded data slices of the set of encoded data slices are stored in each of the storage units of the set of storage units;

detecting a storage error indicating that an encoded data slice of the set of encoded data slices is an error slice;

requesting, in response to the storage error, a partial threshold number of partial encoded data slices for select encoded data slices of the set of encoded data slices;

performing, by storage units of the set of storage units receiving a request for a partial encoded data slice, a partial encoding function on locally stored encoded data slices of the select encoded data slices to produce a group of partial encoded data slices;

combining, by each of the storage units receiving the request for a partial encoded data slice, a respective group of partial encoded data slices to produce respective partial encoded data slice responses;

receiving a partial threshold number of partial encoded data slice responses;

combining the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice; and

facilitating storage of the rebuilt encoded data slice in the set of storage units.

2. The method of claim 1, wherein a partial encoded data slice for a select encoded data slice is generated by:

determining an encoding matrix utilized to generate the encoded data slice to be rebuilt;

reducing the encoding matrix to produce a square matrix, the square matrix including rows associated with at least a decode threshold number of select encoded data slices;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by an encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the encoded data slice to be rebuilt to produce the partial encoded data slice for the select encoded data slice.

3. The method of claim 1, wherein combining a respective group of partial encoded data slices to produce a respective partial encoded data slice response includes performing an exclusive OR operation on the respective group of partial encoded data slices.

4. The method of claim 1, wherein detecting a storage error includes one or more of interpreting an error message, scanning encoded data slices, or detecting a missing or corrupted encoded data slice.

5. The method of claim 1, wherein requesting a partial threshold number of partial encoded data slices includes issuing, for receipt by storage units of the set of storage units, partial slice requests indicating the identity of the error slice and select slices for a rebuilding process.

6. The method of claim 5, wherein the partial slice requests further include a rebuilding matrix.

7. The method of claim 1, wherein facilitating storage of the rebuilt encoded data slice includes issuing a write slice request to a storage unit associated with the error slice, where the write slice request includes the rebuilt encoded data slice.

8. The method of claim 1, wherein facilitating storage of the set of encoded data slices in the set of storage units includes issuing write slice requests to the storage units of the set of storage units.

9. The method of claim 1, wherein combining the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice includes performing an exclusive OR operation on the partial threshold number of partial encoded data slice responses.

10. A computer readable storage medium comprises:

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

receive a data object for storage in a set of storage units of the DSN;

dispersed storage error encode at least one data segment of the data object to produce a set of encoded data slices that includes an information dispersal algorithm (IDA) width number of encoded data slices, wherein the IDA width number is at least twice the number of storage units in the set of storage units;

facilitate storage of the set of encoded data slices in the set of storage units, where at least two encoded data slices of the set of encoded data slices are stored in each of the storage units of the set of storage units;

detect a storage error indicating that an encoded data slice of the set of encoded data slices is an error slice;

request, in response to the storage error, a partial threshold number of partial encoded data slices for select encoded data slices of the set of encoded data slices;

perform a partial encoding function on locally stored encoded data slices of the select encoded data slices to produce a group of partial encoded data slices;

combine a respective group of partial encoded data slices to produce respective partial encoded data slice responses;

receive a partial threshold number of partial encoded data slice responses;

combine the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice; and

facilitate storage of the rebuilt encoded data slice in the set of storage units.

11. The computer readable storage medium of claim 10, wherein the at least one memory section stores further operational instructions that, when executed by the one or more processing modules to generate a partial encoded data slice for a select encoded data slice, causes the one or more processing modules to:

determine an encoding matrix utilized to generate the encoded data slice to be rebuilt;

reduce the encoding matrix to produce a square matrix, the square matrix including rows associated with at least a decode threshold number of select encoded data slices;

invert the square matrix to produce an inverted matrix;

matrix multiply the inverted matrix by an encoded data slice to produce a vector; and

matrix multiply the vector by a row of the encoding matrix corresponding to the encoded data slice to be rebuilt to produce the partial encoded data slice for the select encoded data slice.

12. The computer readable storage medium of claim 10, wherein combining a respective group of partial encoded data slices to produce a respective partial encoded data slice response includes performing an exclusive OR operation on the respective group of partial encoded data slices.

13. The computer readable storage medium of claim 10, wherein detecting a storage error includes one or more of interpreting an error message, scanning encoded data slices, or detecting a missing or corrupted encoded data slice.

14. The computer readable storage medium of claim 10, wherein requesting a partial threshold number of partial encoded data slices includes issuing, for receipt by storage units of the set of storage units, partial slice requests indicating the identity of the error slice and select encoded slices for a rebuilding process.

15. The computer readable storage medium of claim 14, wherein the partial slice requests further include a rebuilding matrix.

16. The computer readable storage medium of claim 10, wherein combining the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice includes performing an exclusive OR operation on the partial threshold number of partial encoded data slice responses.

17. A computing device of a dispersed storage network (DSN), the computing device comprises:

a network interface;

a memory comprising instructions; and

one or more processing modules in communication with the memory, wherein the one or more processing modules execute the instructions to;

receive a data object for storage in a set of storage units of the DSN;

dispersed storage error encode at least one data segment of the data object to produce a set of encoded data slices that includes an information dispersal algorithm (IDA) width number of encoded data slices, wherein the IDA width number is at least twice the number of storage units in the set of storage units;

facilitate storage of the set of encoded data slices in the set of storage units, where at least two encoded data slices of the set of encoded data slices are stored in each of the storage units of the set of storage units;

detect a storage error indicating that an encoded data slice of the set of encoded data slices is an error slice;

request, in response to the storage error, a partial threshold number of partial encoded data slices for select encoded data slices of the set of encoded data slices, wherein a partial encoded data slice is generated by combining a plurality of slices generated by a partial encoding function;

receive, via the network interface, a partial threshold number of partial encoded data slice responses;

combine the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice; and

facilitate, via the network interface, storage of the rebuilt encoded data slice in the set of storage units.

18. The computing device of claim 17, wherein the partial encoding function includes:

determining an encoding matrix utilized to generate the encoded data slice to be rebuilt;

reducing the encoding matrix to produce a square matrix, the square matrix including rows associated with at least a decode threshold number of select slices;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by a select encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the encoded data slice to be rebuilt to produce the partial encoded data slice for the select encoded data slice.

19. The computing device of claim 17, wherein combining a plurality of slices includes performing an exclusive OR operation on the plurality of slices.

20. The computing device of claim 17, wherein combining the partial threshold number of partial encoded data slice responses to produce a rebuilt encoded data slice corresponding to the error slice includes performing an exclusive OR operation on the partial threshold number of partial encoded data slice responses.