Rebuilding data on a dispersed storage network

• US 8,880,799 B2
• Filed: 03/31/2008
• Issued: 11/04/2014
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Foster, Lynn, Resch, Jason, Volvovski, Ilya, Quigley, John, Dhuse, Greg, Thornton, Vance, Hendrickson, Dusty, Mark, Zachary
• Primary Examiner(s): KROFCHECK, MICHAEL C
• Application Number:
  US12/080,042
• Publication Number:
  US 20080183975A1
• Time in Patent Office: 2,409 Days
• US Class Current: 711/114
• 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 rebuilder application operates on a dispersed data storage grid and rebuilds stored data segments that have been compromised in some manner. The rebuilder application actively scans for compromised data segments, and is also notified during partially failed writes to the dispersed data storage network, and during reads from the dispersed data storage network when a data slice is detected that is compromised. Records are created for compromised data segments, and put into a rebuild list, which the rebuilder application processes.

Claims

1. A method of rebuilding data on a dispersed data storage network, said method comprising the steps of:

identifying, by a computer of the dispersed data storage network, a data segment that has at least one data slice requiring rebuilding, wherein the data segment is encoded in accordance with an information dispersal algorithm to produce a set of data slices that are stored on slice servers of the dispersed data storage network, wherein the set of data slices are different from one another and includes the at least one data slice requiring rebuilding, wherein the at least one slice requiring rebuilding is a subset of the set of data slices, wherein the at least one data slice that requires rebuilding from the data segment is identified based on one or more of;

determining that the at least one data slice requiring rebuilding is outdated with respect to other data slices of the set of data slices;

determining that the at least one data slice requiring rebuilding is missing;

determining that the at least one data slice requiring rebuilding is corrupted;

determining that the at least one data slice requiring rebuilding failed a read operation;

determining that the at least one data slice requiring rebuilding failed a write operation;

requesting, by the computer from at least some of the slice servers, at least a reconstruction number of data slices of the set of data slices, wherein the at least a reconstruction number of data slices does not include the at least one data slice requiring rebuilding;

reconstructing, by the computer, the data segment from the at least a reconstruction number of data slices to produce a reconstructed data segment;

encoding, by the computer, the reconstructed data segment in accordance with the information dispersal algorithm to reproduce the set of data slices including at least one new data slice that corresponds to the at least one data slice that requires rebuilding; and

writing, by the computer, the at least one new data slice to one or more of the slice servers such that a full set of data slices are stored in the slice servers for the data segment.

2. The method of claim 1 wherein the computer comprises one or more of:

a client computer, a grid access computer, and a manager appliance.

3. The method of claim 1 wherein the determining that the at least one data slice requiring rebuilding is outdated comprises:

comparing a transaction number of the at least one data slice requiring rebuilding with transaction numbers of the other data slices of the set of data slices; and

when the transaction number of the at least one data slice requiring rebuilding does not substantially match the transaction numbers of the other data slices of the set of data slices, indicating that the at least data slice requiring rebuilding is outdated.

4. The method of claim 1 wherein the determining that the at least one data slice requiring rebuilding is outdated comprises:

comparing a version of the data segment associated with the at least one data slice requiring rebuilding with the version of the data segment associated with the other data slices of the set of data slices; and

when the version of the data segment associated with the at least one data slice requiring rebuilding does not substantially match the version of the data segment associated with the other data slices of the set of data slices, indicating that the at least one data slice requiring rebuilding is outdated.

5. The method of claim 1, wherein the determining that the at least one data slice requiring rebuilding is missing comprises at least one of:

determining that one of the slice servers storing the at least one data slice requiring rebuilding is unavailable; and

determining that the one of the slice servers that is identified as storing the at least one data slice requiring rebuilding is not storing the at least one data slice requiring rebuilding.

6. The method of claim 1, wherein the determining that the at least one data slice requiring rebuilding is corrupted comprises:

retrieving a checksum from the at least one data slice requiring rebuilding;

calculating a new checksum for the at least one data slice requiring rebuilding;

comparing the checksum with the new checksum; and

when the checksum does not substantially match the new checksum, indicating that the at least one data slice requiring rebuilding is corrupted.

7. The method of claim 1, wherein the encoding the reconstructed data segment comprises:

arranging the reconstructed data segment into a data matrix;

generating a coded matrix of coded values based on the data matrix and an encoding matrix of the information dispersal algorithm;

arranging the coded values into a new set of data slices; and

selecting at least one new data slice from the new set of data slices.

8. The method of claim 1 further comprises:

determining that the at least one data slice requiring rebuilding failed the read operation by receiving, in response to a read request for the at least one data slice requiring rebuilding, an indication that the at least one data slice requiring rebuilding is corrupted; and

determining that the at least one data slice requiring rebuilding failed the write operation by failing to receive a write response from one or more of the slices servers regarding a write request regarding the at least one data slice requiring rebuilding.

9. A rebuilder recorder/agent that is stored on a computer readable memory and, when executed by a computer, causes the computer to:

identify a data segment that has at least one data slice requiring rebuilding, wherein the data segment is encoded in accordance with an information dispersal algorithm to produce a set of data slices that are stored on slice servers of a dispersed data storage network, wherein the set of data slices are different from one another and includes the at least one data slice requiring rebuilding, wherein the at least one slice requiring rebuilding is a subset of the set of data slices, wherein the at least one data slice that requires rebuilding from the data segment is identified based on one or more of;

determining that the at least one data slice requiring rebuilding is outdated with respect to other data slices of the set of data slices;

determining that the at least one data slice requiring rebuilding is missing;

determining that the at least one data slice requiring rebuilding is corrupted;

determining that the at least one data slice requiring rebuilding failed a read operation;

determining that the at least one data slice requiring rebuilding failed a write operation;

request, from at least some of the slice servers, at least a reconstruction number of data slices of the set of data slices, wherein the at least a reconstruction number of data slices does not include the at least one data slice requiring rebuilding;

reconstruct the data segment from the at least a reconstruction number of data slices to produce a reconstructed data segment;

encode the reconstructed data segment in accordance with the information dispersal algorithm to reproduce the set of data slices including at least one new data slice that corresponds to the at least one data slice requiring rebuilding

write the at least one new data slice to one or more of the slice servers such that a full set of data slices are stored in the slice servers for the data segment.

10. The rebuilder recorder/agent of claim 9 is further operable to determine that the at least one data slice requiring rebuilding is outdated by:

comparing a transaction number of the at least one data slice requiring rebuilding with transaction numbers of the other data slices of the set of data slices; and

when the transaction number of the at least one data slice requiring rebuilding does not substantially match the transaction numbers of the other data slices of the set of data slices, indicating that the at least data slice requiring rebuilding is outdated.

11. The rebuilder recorder/agent of claim 9 is further operable to determine that the at least one data slice requiring rebuilding is outdated by:

comparing a version of the data segment associated with the at least one data slice requiring rebuilding with version of the data segment associated with the other data slices of the set of data slices; and

when the version of the data segment associated with the at least one data slice requiring rebuilding does not substantially match the version of the data segment associated with the other data slices of the set of data slices, indicating that the at least data slice requiring rebuilding is outdated.

12. The rebuilder recorder/agent of claim 9 is further operable to determine that the at least one data slice requiring rebuilding is missing by at least one of:

determining that one of the slice servers storing the at least one data slice requiring rebuilding is unavailable; and

determining that the one of the slice servers that is identified as storing the at least one data slice requiring rebuilding is not storing the at least one data slice requiring rebuilding.

13. The rebuilder recorder/agent of claim 9 is further operable to determine that the at least one data slice requiring rebuilding is corrupted by:

retrieving a checksum from the at least one data slice requiring rebuilding;

calculating a new checksum for the at least one data slice requiring rebuilding;

comparing the checksum with the new checksum; and

when the checksum does not substantially match the new checksum, indicating that the at least one data slice requiring rebuilding is corrupted.

14. The rebuilder recorder/agent of claim 9 is further operable to encode the reconstructed data segment by:

arranging the reconstructed data segment into a data matrix;

generating a coded matrix of coded values based on the data matrix and an encoding matrix of the information dispersal algorithm;

arranging the coded values into a new set of data slices; and

selecting at least one new data slice from the new set of data slices.

15. The rebuilder recorder/agent of claim 9 is further operable to:

determine that the at least one data slice requiring rebuilding failed the read operation by receiving, in response to a read request for the at least one data slice requiring rebuilding, an indication that the at least one data slice requiring rebuilding is corrupted; and

determine that the at least one data slice requiring rebuilding failed the write operation by failing to receive a write response from one or more of the slices servers regarding a write request regarding the at least one data slice requiring rebuilding.