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

• US 20140181578A1
• Filed: 02/27/2014
• Published: 06/26/2014
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Baptist, Andrew, Mark, Zachary J., Resch, Jason K., Volvovski, Ilya
• Granted Patent: US 9,940,197 B2
• Time in Patent Office: Days
• US Class Current: 714/6.24
• 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 storage network, comprises:

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

a grid module operable 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 M of encoded slice partials from the plurality of additional storage units, wherein the number M of encoded slice partials are generated from a corresponding M number of the plurality of encoded data slices and wherein the number M 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 M of encoded slice partials.

2. The first storage unit of claim 1, wherein portions of the data segment are interleaved into a number X of the plurality of encoded data slices for storage in the first storage unit and the plurality of additional storage units and wherein the identified data slice is one of the number X of the plurality of encoded data slices of the data segment;

and

wherein the number M corresponds to a threshold number of the number X of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function, wherein the number M equals less than the number X.

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

receive a first summation of two or more of the number M 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.

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

receive a second summation of two or more of the number M 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.

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

receive a first summation of two or more of the number M 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 M of encoded slice partials from two or more additional storage units located at a second site;

receive one or more of the number M 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.

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

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

generate the rebuilt encoded data slice from the first summation.

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

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

receive one or more of the number M 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 M of encoded slice partials; and

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

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

a grid module operable 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 an encoded 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 encoded data segment is interleaved into a number R of the plurality of encoded data slices for storage in the first storage unit and a plurality of additional storage units and wherein the identified data slice is one of the number R of the plurality of encoded data slices of the data segment;

and

wherein a number M corresponds to a threshold number of the number R of the plurality of encoded data slices needed to reconstruct the encoded data segment based on an error encoding dispersal function, wherein the number M equals less than the number R.

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

de-slice the identified data slice to generate a portion of the 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.

11. The first storage unit of claim 10, wherein the grid module is further operable 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 M of columns equal to the number M of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

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

R matrix A′

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

13. The first storage unit of claim 12, 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 M of columns equal to the number M of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

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

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

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 the plurality of encoded data slices are generated from a data segment based on an error encoding dispersal function by:

arranging data blocks of the data segment into a data matrix;

generating an encoded data matrix based on the data matrix and an encoding matrix; and

arranging data blocks of the encoded data matrix into an R number of the plurality of encoded data slices, wherein a number M corresponds to a threshold number of the number R of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function, wherein the number M equals less than the number R.

17. The method of claim 16, 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.

18. The method of claim 17, 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 M of columns equal to the number M 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 18, 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 M of columns equal to the number M of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.

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