Method and apparatus for slice partial rebuilding in a dispersed storage network

• US 9,940,197 B2
• Filed: 02/27/2014
• Issued: 04/10/2018
• Est. Priority Date: 07/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg, Baptist, Andrew, Mark, Zachary J., Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Birkhimer, Christopher D
• Application Number:
  US14/192,098
• Publication Number:
  US 20140181578A1
• Time in Patent Office: 1,503 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 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;

partition a data object into a plurality of data segments;

encode the plurality of data segments in accordance with an information dispersal error coding scheme to generate sets of error coded (EC) data slices, wherein each set of the sets of EC data slices includes a pillar number of data slices, and wherein each set of the sets of EC data slices corresponds to a respective one of the plurality of data segments, and wherein, based on a plurality of distributed data storage parameters, a threshold number of EC data slices within a set of EC data slices is required to reconstruct a corresponding data segment;

identify an EC data slice of a plurality of EC data slices that requires rebuilding to produce an identified data slice, wherein the plurality of encoded data slices are associated with a first data segment of the plurality of data segments;

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 EC data slices and wherein the number M corresponds to a number of the plurality of EC data slices needed to reconstruct the first data segment based on the information dispersal error coding scheme; and

generate, without reconstructing the first data segment, a rebuilt EC data slice corresponding to the identified EC 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 first data segment are interleaved into a number X of the plurality of EC 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 EC data slices of the first data segment;

and

wherein the number M corresponds to a threshold number of the number X of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme 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 EC 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 EC 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 EC 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 EC 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 EC 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 EC data slice of a plurality of EC data slices, wherein the plurality of EC data slices are generated from an encoded data segment based on an information dispersal error coding scheme, and wherein the plurality of EC data slices includes a pillar number of data slices, and wherein, based on a plurality of distributed data storage parameters, a threshold number of EC data slices within a set of EC data slices is required to reconstruct the data segment;

generate, without reconstructing the data segment, an encoded slice partial from the identified data slice; and

transmit the encoded slice partial to one of a 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 EC 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 EC data slices of the data segment;

and

wherein a number M corresponds to a threshold number of the number R of the plurality of EC data slices needed to reconstruct the encoded data segment based on an information dispersal error coding scheme, 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 a plurality of EC data slices and includes a number M of columns equal to the number M of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme.

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 a plurality of EC data slices and includes a number M of columns equal to the number M of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme.

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 error encoded (EC) data slices, wherein the plurality of EC data slices are generated from a data segment based on an information dispersal error coding scheme, and wherein the plurality of EC data slices includes a pillar number of data slices, and wherein, based on a plurality of distributed data storage parameters, a threshold number of EC data slices within a set of EC data slices is required to reconstruct the data segment;

generating, without reconstructing the data segment, an encoded slice partial from the identified data slice; and

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

16. The method of claim 15, wherein the plurality of encoded data slices are generated from the data segment based on an information dispersal error coding scheme 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 EC data slices, wherein a number M corresponds to a threshold number of the number R of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme 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 a plurality of EC data slices and includes a number M of columns equal to the number M of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme.

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 the plurality of EC data slices and includes a number M of columns equal to the number M of the plurality of EC data slices needed to reconstruct the data segment based on the information dispersal error coding scheme.

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