METHOD AND APPARATUS FOR REBUILDING DATA IN A DISPERSED DATA STORAGE NETWORK

• US 20130275833A1
• Filed: 06/10/2013
• Published: 10/17/2013
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Thornton, Vance T., Bellanca, Jamie, Hendrickson, Dustin M., Mark, Zachary J., Volvovski, Ilya
• Granted Patent: US 8,713,358 B2
• Time in Patent Office: Days
• US Class Current: 714/764
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• 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/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• 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: 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: 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 method begins a first rebuilder application identifying a data slice having a storage error. The method continues with the first rebuilder application or a second rebuilder application identifying a data segment based on the identified data slice. The method continues with the second rebuilder application identifying one or more other slice servers that are storing other data slices of the encoded data segment. The method continues with the second rebuilder application receiving a sufficient number of the other data slices to reconstruct the data segment and decoding them to reconstruct the data segment. The method continues with the second rebuilder application encoding the reconstructed data segment in accordance with the information dispersal algorithm to produce a new set of data slices and selecting one of them as the rebuild data slice.

Claims

1. A method for execution by one or more computers associated with a dispersed data storage network, the method comprises:

identifying, by a first rebuilder application operating on a first slice server, a data slice having a storage error;

identifying, by the first rebuilder application or by a second rebuilder application operating on the second slice server, a data segment based on the identified data slice, wherein the data segment was encoded in accordance with an information dispersal function to produce a set of data slices, which includes the identified data slice;

identifying, by the second rebuilder application operating on the second slice server, one or more other slice servers that are storing other data slices of the set of data slices;

retrieving, by the second rebuilder application operating on the second slice server from the one or more other slice servers, a sufficient number of the other data slices to reconstruct the data segment;

decoding, by the second rebuilder application operating on the second slice server, the sufficient number of the other data slices in accordance with the information dispersal function to reconstruct the data segment;

encoding, by the second rebuilder application operating on the second slice server, the reconstructed data segment in accordance with the information dispersal algorithm to produce a new set of data slices; and

selecting, by the second rebuilder application operating on the second slice server, a data slice of the new set of data slices as a rebuilt data slice of the identified data slice.

2. The method of claim 1 further comprises:

outputting, by the second rebuilder application operating on the second slice server, the rebuilt data slice to the first slice server for storage therein.

3. The method of claim 1, wherein the identifying the data slice comprises:

performing, by a rebuild detector of the first or second rebuilder application, a storage error detection process to identify the storage error, wherein the storage error is one of;

a missing data slice, an outdated data slice, and a corrupted data slice.

4. The method of claim 1, wherein the identifying the data segment comprises:

generating, by a rebuild recorder of the first or second rebuilder application, a rebuild record based on the identified data slice, wherein the rebuild record includes one or more of;

an identifier of the identified data slice, an identifier associated with the data segment, a transaction identifier associated with the data segment, and identifiers of the other data slices.

5. The method of claim 1 further comprises:

releasing, by a rebuild recorder of the second rebuilder application, a rebuild record regarding the identified data slice and the data segment to a rebuild agent of the second rebuilder application;

decoding, by the rebuild agent, the sufficient number of the other data slices by;

arranging the sufficient number of other data slices into a reconstructed coded matrix; and

decoding the reconstructed coded matrix using a decoding matrix function in accordance with the information dispersal algorithm to reconstruct the data segment; and

encoding, by a rebuild agent, the reconstructed data segment by;

arranging the reconstructed data segment into the data matrix;

encoding the data matrix using an encoding matrix function in accordance with the information dispersal algorithm to produce a coded matrix; and

arranging the coded matrix into the new set of data slices.

6. A method for execution by one or more computers associated with a dispersed data storage network, the method comprises:

identifying, by a plurality of rebuilder applications operating on the one or more computers, a plurality of data slices having storage errors;

allocating a first set of the plurality of data slices having storage errors to a first rebuilder application of the plurality of rebuilder applications;

allocating a second set of the plurality of data slices having storage errors to a second rebuilder application of the plurality of rebuilder applications;

for a first data slice of the first set of the plurality of data slices;

identifying, by the first rebuilder application, a first data segment based on the first data slice, wherein the first data segment was encoded in accordance with an information dispersal function to produce a first set of data slices, which includes the first data slice;

identifying, by the first rebuilder application, one or more other slice servers that are storing other data slices of the first set of data slices;

retrieving, by the first rebuilder application from the one or more other slice servers, a sufficient number of the other data slices to reconstruct the data segment;

decoding, by the first rebuilder application, the sufficient number of the other data slices in accordance with the information dispersal function to reconstruct the first data segment;

encoding, by the first rebuilder application, the reconstructed first data segment in accordance with the information dispersal algorithm to produce a new first set of data slices; and

selecting, by the first rebuilder application, a data slice of the new first set of data slices as a rebuilt first data slice of the first data slice.

7. The method of claim 6 further comprises:

for a second data slice of the second set of the plurality of data slices;

identifying, by the second rebuilder application, a second data segment based on the second data slice, wherein the second data segment was encoded in accordance with the information dispersal function to produce a second set of data slices, which includes the second data slice;

identifying, by the second rebuilder application, another one or more other slice servers that are storing second other data slices of the second set of data slices;

retrieving, by the second rebuilder application from the other one or more other slice servers, a sufficient number of the second other data slices to reconstruct the second data segment;

decoding, by the second rebuilder application, the sufficient number of the second other data slices in accordance with the information dispersal function to reconstruct the second data segment;

encoding, by the second rebuilder application, the reconstructed second data segment in accordance with the information dispersal algorithm to produce a new second set of data slices; and

selecting, by the second rebuilder application, a data slice of the new second set of data slices as a rebuilt second data slice of the second data slice.

8. The method of claim 6 further comprises:

allocating the first set of the plurality of data slices having storage errors to the first rebuilder application based on data slices falling within a first address range; and

allocating the second set of the plurality of data slices having storage errors to the second rebuilder application based on data slices falling within a first address range.

9. A dispersed data storage network comprises:

a first slice server that includes;

a first network interface for interfacing with a network;

first memory for storing first data slices and for storing a first rebuilder application; and

a first central processing unit operable to execute the first rebuilder application; and

a second slice server that includes;

a second network interface for interfacing with the network;

second memory for storing second data slices and for storing a second rebuilder application; and

a second central processing unit operable to execute the second rebuilder application, wherein, when the first and second central processing units are executing the first and second rebuilder applications;

the first rebuilder application identifies a data slice of the first data slices to produce an identified data slice, wherein the identified data slice has a storage error;

the first rebuilder application or the second rebuilder application identifies a data segment based on the identified data slice, wherein the data segment was encoded in accordance with an information dispersal function to produce a set of data slices, which includes the identified data slice;

the second rebuilder application;

identifies one or more other slice servers that are storing other data slices of the set of data slices;

retrieves, from the one or more other slice servers, a sufficient number of the other data slices to reconstruct the data segment;

decodes the sufficient number of the other data slices in accordance with the information dispersal function to reconstruct the data segment;

encodes the reconstructed data segment in accordance with the information dispersal algorithm to produce a new set of data slices; and

selects a data slice of the new set of data slices as a rebuilt data slice of the identified data slice.

10. The dispersed data storage network of claim 9 further comprises:

the second rebuilder application outputting the rebuilt data slice to the first slice server for storage therein.

11. The dispersed data storage network of claim 9, wherein the first rebuilder application identifies the data slice by:

performing, by a rebuild detector of the first rebuilder application, a storage error detection process to identify the storage error, wherein the storage error is one of;

a missing data slice, an outdated data slice, and a corrupted data slice.

12. The dispersed data storage network of claim 9, wherein the first or second rebuilder application identifies the data segment by:

generating, by a rebuild recorder of the first or second second rebuilder application, a rebuild record based on the identified data slice, wherein the rebuild record includes one or more of;

an identifier of the identified data slice, an identifier associated with the data segment, a transaction identifier associated with the data segment, and identifiers of the other data slices.

13. The dispersed data storage network of claim 9 further comprises:

releasing, by a rebuild recorder of the second rebuilder application, a rebuild record regarding the identified data slice and the data segment to a rebuild agent of the second rebuilder application;

decoding, by the rebuild agent, the sufficient number of the other data slices by;

arranging the sufficient number of other data slices into a reconstructed coded matrix; and

decoding the reconstructed coded matrix using a decoding matrix function in accordance with the information dispersal algorithm to reconstruct the data segment; and

encoding, by a rebuild agent, the reconstructed data segment by;

arranging the reconstructed data segment into the data matrix;

encoding the data matrix using an encoding matrix function in accordance with the information dispersal algorithm to produce a coded matrix; and

arranging the coded matrix into the new set of data slices.