METHOD AND APPARATUS FOR SLICE PARTIAL REBUILDING IN A DISPERSED STORAGE NETWORK

• US 20110029711A1
• Filed: 04/26/2010
• Published: 02/03/2011
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: MARK, ZACHARY J., RESCH, JASON K., VOLVOVSKI, ILYA, BAPTIST, ANDREW, DHUSE, GREG
• Granted Patent: US 8,706,980 B2
• Time in Patent Office: Days
• US Class Current: 711/4
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• 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/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

A dispersed storage system includes a plurality of storage units that each include a partial rebuild grid module. The partial rebuild grid module includes partial rebuilding functionality to reconstruct one of a plurality of encoded data slices wherein the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function. In the partial rebuilding process, a data slice is rebuilt by combining in any order slice partials generated from at least a threshold number T of the plurality of data slices.

Claims

1. A first storage unit in a dispersed storage network, comprises:

a network interface for interfacing with a plurality of additional storage units in the dispersed storage network; and

a grid module operably coupled to;

identify an encoded data slice of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function;

receive one or more sums of at least a number T of encoded slice partials from the plurality of additional storage units, wherein each of the encoded slice partials are generated from a corresponding one of the plurality of encoded data slices and wherein the number T corresponds to a number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the one or more sums of at least the number T of encoded slice partials.

2. The first storage unit of claim 1, wherein the grid module is further operably coupled to:

receive a first summation of two or more of the number T of encoded slice partials from two or more of the additional storage units located at a first site; and

generate the rebuilt encoded data slice from the first summation.

3. The first storage unit of claim 2, wherein the grid module is further operably coupled to:

receive a second summation of two or more of the number T of encoded slice partials from two or more additional storage units located at a second site;

determine a partial slice sum from the first summation and the second summation; and

generate the rebuilt encoded data slice from the partial slice sum.

4. The first storage unit of claim 1, wherein the grid module is further operably coupled to:

receive a first summation of two or more of the number T of encoded slice partials from two or more additional storage units located at a first site; and

receive a second summation of two or more of the number T of encoded slice partials from two or more additional storage units located at a second site;

receive one or more of the number T of encoded slice partials from one or more additional storage units located at a same site with the first storage unit;

determine a third summation of the one or more encoded slice partials; and

determine a partial slice sum from the first summation, the second summation and the third summation; and

generate the rebuilt encoded data slice from the partial slice sum.

5. The first storage unit of claim 1, wherein the grid module is further operably coupled to:

receive a first summation of the number T of encoded slice partials from one of the additional storage units; and

generate the rebuilt encoded data slice from the first summation.

6. The first storage unit of claim 1, wherein the grid module is further operably coupled to:

receive a first summation of two or more of the number T of encoded slice partials from one of the additional storage units;

receive one or more of the number T of encoded slice partials from one or more additional storage units located at a same site with the first storage unit;

determine a partial slice sum from the first summation and the one or more of the number T of encoded slice partials; and

generate the rebuilt encoded data slice from the partial slice sum.

7. The first storage unit of claim 1, wherein the grid module is further operably coupled to:

store the rebuilt encoded data slice at the first storage unit.

8. A first storage unit in a dispersed storage network, comprises:

a network interface for interfacing with one or more of a plurality of additional storage units in the dispersed storage network; and

a grid module operably coupled to;

receive a partial rebuild request that identifies an identified data slice of a plurality of encoded data slices, wherein the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function;

generate an encoded slice partial from the identified data slice; and

transmit the encoded slice partial to one of the plurality of additional storage units.

9. The first storage unit of claim 8, wherein the grid module is further operably coupled to:

de-slice the identified data slice to generate a portion of an encoded data segment;

decode the portion of the encoded data segment to generate a portion of a decoded data segment; and

encode the portion of the decoded data segment to generate the encoded slice partial.

10. The first storage unit of claim 9, wherein the grid module is further operably coupled to:

multiply the portion of the encoded data segment with a M×

R matrix A′

to generate the portion of the decoded data segment, wherein the matrix A′

includes a number R of rows equal to the number R of plurality of encoded data slices and includes a number T of columns equal to the number T of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

11. The first storage unit of claim 10, wherein one column of the M×

R matrix A′

includes positive numbers in at least the number T of the number R of the rows, wherein a row corresponding to the identified slice is a zero.

12. The first storage unit of claim 9, wherein the grid module is further operably coupled to:

multiply the portion of the decoded data segment with a M×

R second matrix A, wherein the second matrix A includes a number R of rows equal to the number R of plurality of encoded data slices and includes a number T of columns equal to the number T of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

13. The first storage unit of claim 12, wherein one row in the M×

R second matrix A corresponding to the identified slice includes positive numbers and other rows include zeros.

14. The first storage unit of claim 9, wherein the grid module is further operably coupled to:

receive additional encoded slice partials from one or more additional storage units located at a same site with the first storage unit;

determine a partial slice sum from the encoded slice partial and the additional encoded slice partials; and

transmit the partial slice sum to one of the plurality of additional storage units.

15. A method for partial rebuilding in a dispersed storage network, comprising:

receiving a partial rebuild request that identifies an identified data slice of a plurality of encoded data slices, wherein the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function;

generating an encoded slice partial from the identified data slice; and

transmitting the encoded slice partial to one of the plurality of additional storage units.

16. The method of claim 15, wherein generating the encoded slice partial comprises:

de-slicing the identified data slice to generate a portion of an encoded data segment;

decoding the portion of the encoded data segment to generate a portion of a decoded data segment; and

encoding the portion of the decoded data segment to generate the encoded slice partial.

17. The method of claim 15, wherein decoding the portion of the encoded data segment comprises:

multiplying the portion of the encoded data segment with a M×

R matrix A′

to generate the portion of the decoded data segment, wherein the matrix A′

includes a number R of rows equal to the number R of plurality of encoded data slices and includes a number T of columns equal to the number T of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

18. The method of claim 15, wherein encoding the portion of the decoded data segment comprises:

multiplying the portion of the decoded data segment with a M×

R second matrix A, wherein the second matrix A includes a number R of rows equal to the number R of plurality of encoded data slices and includes a number T of columns equal to the number T of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

19. The method of claim 15 further comprising:

receiving additional encoded slice partials from one or more additional storage units located at a same site with the first storage unit;

determining a partial slice sum from the encoded slice partial and the additional encoded slice partials; and

transmitting the partial slice sum to one of the plurality of additional storage units.

20. A method for partial rebuilding in a dispersed storage network, comprising:

identifying at a first storage unit a stored encoded data slice of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function;

determining a summation of at least a number T of encoded slice partials, wherein each of the encoded slice partials are generated from a corresponding one of the plurality of encoded data slices and wherein the number T corresponds to a number of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function; and

generating a rebuilt encoded data slice corresponding to the identified data slice from the summation.