Method and apparatus for distributed storage integrity processing

• US 8,555,109 B2
• Filed: 04/26/2010
• Issued: 10/08/2013
• Est. Priority Date: 07/30/2009
• Status: Expired due to Fees

• 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
• Primary Examiner(s): LOHN, JOSHUA A
• Application Number:
  US12/767,364
• Publication Number:
  US 20110029809A1
• Time in Patent Office: 1,261 Days
• Field of Search: 714/6.22, 714/6.24
• US Class Current: 714/6.22
• 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/2056 by mirroring
• 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 distributed storage integrity system in a dispersed storage network includes a scanning agent and a control unit. The scanning agent identifies an encoded data slice that requires rebuilding, wherein the encoded data slice is one of a plurality of encoded data slices generated from a data segment using an error encoding dispersal function. The control unit retrieves at least a number T of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function. The control unit is operable to reconstruct the data segment from at least the number T of the encoded data slices and generate a rebuilt encoded data slice from the reconstructed data segment. The scanning agent is located in a storage unit and the control unit is located in the storage unit or in a storage integrity processing unit, a dispersed storage processing unit or a dispersed storage managing unit.

Claims

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

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

a grid module including;

a rebuild agent operably coupled to;

receive an identification of an identified data slice of a data segment that requires rebuilding from a corresponding one of the plurality of storage units, wherein the data segment is encoded using an error encoding dispersal function to generate an encoded data segment, wherein portions of the encoded data segment are interleaved into a number X of a plurality of encoded data slices for storage in the plurality of storage units and wherein the identified data slice is one of the number X of the plurality of encoded data slices; and

retrieve at least a number T of the plurality of encoded data slices from the plurality of storage units, wherein the number T 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 T equals less than the number X; and

a rebuild module operably coupled to reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment by decoding at least the number T of the plurality of encoded data slices using a decoding matrix A in accordance with the error encoding dispersal function; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment using the error encoding dispersal function.

2. The storage integrity processing unit of claim 1 further comprising:

a rebuild queue operably coupled to store the identification of the identified data slice that requires rebuilding; and

wherein the rebuild agent is further operably coupled to select the identified data slice for rebuilding from the rebuild queue based on one of;

a prioritization algorithm and a first in first out (FIFO) order.

3. The storage integrity processing unit of claim 1 further comprising:

a slice queue operably coupled to store the rebuilt encoded data slice; and

a slice agent operably coupled to select the rebuilt encoded data slice for storage from the slice queue based on one of;

a prioritization algorithm and a first in first out (FIFO) order.

4. The storage integrity processing unit of claim 3, wherein the slice agent is further operably coupled to:

determine whether the corresponding one of the plurality of storage units is available for storage of the reconstructed data slice; and

when the corresponding one of the plurality of storage units is available, assign the rebuilt encoded data slice for storage to the corresponding one of the plurality of storage units.

5. The storage integrity processing unit of claim 3, wherein the slice agent is further operably coupled to:

determine whether the rebuilt encoded data slice is an appropriate version; and

when the rebuilt data slice is an appropriate version, assign the reconstructed data slice for storage to the corresponding one of the plurality of storage units.

6. The storage integrity processing unit of claim 1, wherein the rebuild agent is further operably coupled to:

request the plurality of storage units to scan an address range of encoded data slices, wherein the identified data slice has an address within the address range.

7. The storage integrity processing unit of claim 1, wherein the rebuild module comprises:

a de-slicer module that receives at least the number T of the plurality of encoded data slices and generates an encoded data segment;

a decoder module that decodes the encoded data segment based on the error encoding dispersal function to produce a reconstructed data segment;

an encoder module that receives the reconstructed data segment and generates a re-encoded data segment based on the error coding dispersal function; and

a slicer module that generates a second plurality of encoded data slices from the re-encoded data segment, wherein the second plurality of encoded data slices includes a rebuilt encoded data slice corresponding to the identified data slice.

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

a network interface for interfacing with at least one of;

a storage integrity processing unit and one or more of a plurality of additional storage units; and

a scanning agent operably coupled to;

identify an encoded data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of an X number of a plurality of encoded data slices generated from a data segment encoded using an error encoding dispersal function, wherein the data segment is encoded using the error encoding dispersal function to generate an encoded data segment and wherein the encoded data segment is separated into the X number of the plurality of encoded data slices and wherein the plurality of encoded data slices is stored in the first storage unit and the plurality of additional storage units;

transmit, via the network interface, an identification of the identified data slice to the storage integrity processing unit; and

receive, via the network interface, a reconstructed data slice corresponding to the identified data slice;

wherein the reconstructed data slice is reconstructed using a decoding matrix A in accordance with the error encoding dispersal function.

9. The storage unit of claim 8, wherein the scanning agent is further operably coupled to:

receive a request to scan an address range of encoded data slices, wherein the identified data slice has an address in the address range; and

scan the address range of encoded data slices to determine that the identified data slice requires rebuilding.

10. The storage unit of claim 8, wherein the scanning agent is further operably coupled to:

calculate a checksum using a hash function for the identified data slice; and

determine that the identified data slice has a corrupted data slice error based on the checksum.

11. The storage unit of claim 8, wherein the scanning agent is further operably coupled to:

determine a slice address for the identified data slice from a physical address table;

determine that the identified data slice is not present at the slice address; and

determine that the identified data slice has a missing slice error.

12. The storage unit of claim 8, wherein the scanning agent is further operably coupled to:

determine a current version number for the data segment;

compare a version number for the identified data slice with the current version number; and

when the version number is not the current version number, determine the identified data slice has a version update error.

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

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

a grid module operably coupled to;

identify an encoded data slice of a number X of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein the number X of the plurality of encoded data slices are generated from a data segment encoded using an error encoding dispersal function, wherein the data segment is encoded using the error encoding dispersal function to generate an encoded data segment and the encoded data segment is separated into the number X of the plurality of encoded data slices;

retrieve at least a number T of the number X of the plurality of encoded data slices from the plurality of additional storage units, 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;

reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment by decoding at least the number T of the plurality of encoded data slices using a decoding matrix A in accordance with the error encoding dispersal function; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment.

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

transmit a request message to at least a number T of the plurality of additional storage units, wherein the request message identifies corresponding ones of the plurality of encoded data slices.

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

scan an address range of encoded data slices, wherein the address range corresponds to encoded data slices stored at the first storage unit; and

identify the encoded data slice that requires rebuilding to produce the identified data slice.

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

scan an address range of encoded data slices, wherein the plurality of encoded data slices has addresses within the address range and are assigned for storage in the plurality of additional storage units;

identify the encoded data slice that requires rebuilding to produce an identified data slice.

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

generate an encoded data segment from at least the number T of the plurality of encoded data slices;

decode the encoded data segment based on the error encoding dispersal function to produce a reconstructed data segment;

generate a re-encoded data segment from the reconstructed data segment based on the error coding dispersal function; and

generate a second plurality of encoded data slices from the re-encoded data segment, wherein the second plurality of encoded data slices includes a rebuilt encoded data slice corresponding to the identified data slice.

18. A distributed storage integrity system in a dispersed storage network comprising:

a scanning agent operably coupled to identify an encoded data slice of a number X of a plurality of encoded data slices that requires rebuilding to produce an identified data slice, wherein a data segment is encoded using an error encoding dispersal function to generate an encoded data segment and wherein portions of the encoded data segment are interleaved to generate the number X of the plurality of encoded data slices;

a control unit operably coupled to;

retrieve at least a number T of the number X of the plurality of encoded data slices from the plurality of additional storage units, wherein the number T 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;

reconstruct the data segment from at least the number T of the plurality of encoded data slices to produce a reconstructed data segment by decoding at least the number T of the plurality of encoded data slices using a decoding matrix A in accordance with the error encoding dispersal function; and

generate a rebuilt encoded data slice corresponding to the identified data slice from the reconstructed data segment.

19. The system of claim 18, wherein the scanning agent is located in a storage unit and the control unit is located in one of:

a storage integrity processing unit, a dispersed storage processing unit and a dispersed storage managing unit.

20. The system of claim 18, wherein the scanning agent and the control unit are located in one of a plurality of storage units.

21. The storage integrity processing unit of claim 18, wherein a ratio of the number X to the threshold number T equals at least one of:

5/3, 6/4, 8/5 and 16/10.

22. The storage integrity processing unit of claim 18, wherein the number T equals less than or equal to two less than the X number.

23. The storage integrity processing unit of claim 18, wherein the control unit is operably coupled to decode at least the number T of the plurality of encoded data slices using a decoding matrix A in accordance with the error encoding dispersal function by:

deslicing at least the number T of the plurality of encoded data slices to generate a portion of an encoded data segment; and

multiplying the portion of the encoded data segment with the decoding matrix A, wherein the decoding matrix A is an MxR matrix, wherein the decoding 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 T of the plurality of encoded data slices needed to reconstruct the data segment based on the error encoding dispersal function.