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

• US 20130275844A1
• 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,868,969 B2
• Time in Patent Office: Days
• US Class Current: 714/807
• 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 by determining that a disk drive of a slice server has been replaced with a new disk drive. The method continues by identifying a data slice that was stored on the disk drive and identifying a data segment based on the identified data slice. The method continues by identifying other slice servers that are storing other data slices of the encoded data segment. The method continues by retrieving, from the other slice servers, a sufficient number of the other data slices to reconstruct the data segment and decoding the sufficient number of the other data slices to reconstruct the data segment. The method continues by encoding the reconstructed data segment in accordance with the information dispersal algorithm to produce a new set of data slices. The method continues by selecting a data slice of the new set of data slices as a rebuilt data slice.

Claims

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

determining that a disk drive of a slice server has been replaced with a new disk drive;

identifying a data slice that was stored on the disk drive;

identifying 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 one or more other slice servers that are storing other data slices of the set of data slices;

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

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

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

selecting 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 the rebuilt data slice to the slice server for storage therein.

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

ascertaining a range of data slices assigned to the disk drive;

determining whether the data slice is within the range of data slices; and

when the data slice is within the range of data slices, identifying the data slice.

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

accessing a rebuild record to identify the data segment based on the identified data slice.

5. The method of claim 1 further comprises:

decoding 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 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:

determining whether a data slice stored by a slice server is outdated, is corrupt, is missing, or has a checksum error;

when the data slice is outdated, is corrupt, is missing, or has a checksum error, identifying a data segment based on the 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 one or more other slice servers that are storing other data slices of the set of data slices;

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

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

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

selecting a data slice of the new set of data slices as a rebuilt data slice of the data slice.

7. The method of claim 6, wherein determining that the data slice is outdated comprises:

determining a transaction identifier associated with the data slice;

determining whether the transaction identifier corresponds to a current transaction regarding the data segment based on transaction identifiers of at least some of the other data slices; and

when the transaction identifier does not correspond to the current transaction regarding the data segment, indicating that the data slice is outdated.

8. The method of claim 6, wherein the determining that the data slice has the checksum error comprises:

receiving the data slice, wherein the data slice includes an appended checksum;

calculating a checksum for the received data slice;

comparing the calculated checksum with the appended checksum; and

when the calculated checksum does not match the appended checksum, indicating that the data slice has the checksum error.

9. The method of claim 6, wherein the identifying the data segment comprises:

accessing a rebuild record to identify the data segment based on the identified data slice.

10. The method of claim 6 further comprises:

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

11. A computer for use within a dispersed data storage network, the computer comprises:

a network interface for interfacing with a network, wherein a plurality of data slice servers is operably coupled to the network; and

a central processing unit, wherein the central processing unit is operably coupled to;

determine that a disk drive of a slice server has been replaced with a new disk drive;

identify a data slice that was stored on the disk drive;

identify 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;

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

retrieve, from the one or more other slice servers via the network interface, a sufficient number of the other data slices to reconstruct the data segment;

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

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

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

12. The computer of claim 11, wherein the central processing unit is further operable to:

output, via the network interface, the rebuilt data slice to the slice server for storage therein.

13. The computer of claim 11, wherein the central processing unit is further operable to identify the data slice by:

ascertaining a range of data slices assigned to the disk drive;

determining whether the data slice is within the range of data slices; and

when the data slice is within the range of data slices, identifying the data slice.

14. The computer of claim 11, wherein the central processing unit is further operable to identify the data segment by:

accessing a rebuild record to identify the data segment based on the identified data slice.

15. The computer of claim 11, wherein the central processing unit is further operable to:

decode 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

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

16. A computer for use within a dispersed data storage network, the computer comprises:

a network interface for interfacing with a network, wherein a plurality of data slice servers is operably coupled to the network; and

a central processing unit, wherein the central processing unit is operably coupled to;

determine whether a data slice stored by a slice server is outdated, is corrupt, is missing, or has a checksum error;

when the data slice is outdated, is corrupt, is missing, or has a checksum error, identify a data segment based on the 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;

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

retrieve, from the one or more other slice servers via the network interface, a sufficient number of the other data slices to reconstruct the data segment;

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

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

select a data slice of the new set of data slices as a rebuilt data slice of the data slice.

17. The computer of claim 16, wherein the central processing unit is further operable to determine that the data slice is outdated by:

determining a transaction identifier associated with the data slice;

determining whether the transaction identifier corresponds to a current transaction regarding the data segment based on transaction identifiers of at least some of the other data slices; and

when the transaction identifier does not correspond to the current transaction regarding the data segment, indicating that the data slice is outdated.

18. The computer of claim 16, wherein the central processing unit is further operable to determine that the data slice has the checksum error by:

receiving the data slice, wherein the data slice includes an appended checksum;

calculating a checksum for the received data slice;

comparing the calculated checksum with the appended checksum; and

when the calculated checksum does not match the appended checksum, indicating that the data slice has the checksum error.

19. The computer of claim 16, wherein the central processing unit is further operable to identify the data segment by:

accessing a rebuild record to identify the data segment based on the identified data slice.

20. The computer of claim 16, wherein the central processing unit is further operable to:

decode 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

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