Range based rebuilder for use with a dispersed data storage network

• US 8,352,782 B2
• Filed: 12/29/2009
• Issued: 01/08/2013
• Est. Priority Date: 09/30/2005
• Status: Expired due to Fees

• 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
• Primary Examiner(s): LOHN, JOSHUA A
• Application Number:
  US12/648,691
• Publication Number:
  US 20100306578A1
• Time in Patent Office: 1,106 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 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/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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 message is generated by a computer operating on a dispersed data storage network indicating the inaccessibility of a plurality of data slices. A rebuilder application operates on the dispersed data storage grid and rebuilds inaccessible data slices, including those identified by the message.

Claims

1. A method of rebuilding data stored on a dispersed data storage network comprising a plurality of networked computers including a plurality of slice servers, each of said slice servers storing a plurality of data slices, each of said data slices being identified by a data slice identifier, whereby n of said data slices are associated with a corresponding data segment, and whereby m of said associated data slices are required to reconstruct said corresponding data segment, and further whereby m is less than n−

1, said method comprising the steps of;

receiving a message from one of said networked computers, said message indicative of the inaccessibility of a plurality of data slices;

adding data slice identifiers identifying said plurality of data slices to a list of data slices to be rebuilt;

for each data slice identified by said list of data slices to be rebuilt;

determining a corresponding data segment;

reading at least m data slices associated with said corresponding data segment, said at least m data slices not identified on said list of data slices to be rebuilt;

decoding the retrieved at least m number of data slices by arranging coded values of the retrieved at least m number of data slices into a reconstructed coded matrix and multiplying the reconstructed coded matrix by a decoding matrix in accordance with an information dispersal algorithm to reconstruct the data segment;

encoding the reconstructed data segment by arranging data words of the reconstructed data segment into a data matrix and multiplying the data matrix by the encoding matrix in accordance with the information dispersal algorithm to produce a coded matrix that is arranged into a new plurality of data slices;

writing one of the new plurality of data slices to one of said plurality of slice servers to rebuild said data slice identified by said list of data slices to be rebuilt.

2. The method of claim 1 wherein said message specifies a range of data slice identifiers corresponding to a plurality of inaccessible data slices.

3. The method of claim 1 wherein said message specifies an inaccessible device and further comprising the step of accessing a database relating said inaccessible device to a list of data slice identifiers corresponding to said plurality of inaccessible data slices.

4. The method of claim 3 wherein said inaccessible device is one of the group consisting of a data store associated with a slice server, a slice server, and a site including a plurality of slice servers.

5. A method of rebuilding data stored on a dispersed data storage network comprising a plurality of networked computers including a plurality of slice servers, each of said slice servers storing a plurality of data slices, each of said data slices being identified by a data slice identifier and including a data portion and a first checksum, whereby n of said data slices are associated with a corresponding data segment, and whereby m of said associated data slices are required to reconstruct said corresponding data segment, and further whereby m is less than n, said method comprising the steps of:

reading a data slice stored on one of said slice servers;

computing a second checksum based on the data portion of said data slice;

comparing said second checksum with said first checksum;

adding a data slice identifier identifying said data slice to a list of data slices to be rebuilt when said first checksum does not match said second checksum;

receiving a message from one of said networked computers, said message indicative of the inaccessibility of a plurality of data slices;

adding data slice identifiers identifying said plurality of data slices to said list of data slices to be rebuilt;

for each data slice identifier on said list of data slices to be rebuilt;

determining a corresponding data segment;

reading at least m data slices associated with said corresponding data segment, said at least m data slices not identified on said list of data slices to be rebuilt;

decoding the retrieved at least m number of data slices by arranging coded values of the retrieved at least m number of data slices into a reconstructed coded matrix and multiplying the reconstructed coded matrix by a decoding matrix in accordance with an information dispersal algorithm to reconstruct the data segment;

encoding the reconstructed data segment by arranging data words of the reconstructed data segment into a data matrix and multiplying the data matrix by the encoding matrix in accordance with the information dispersal algorithm to produce a coded matrix that is arranged into a new plurality of data slices;

writing one of the new plurality of data slices to one of said plurality of slice servers to rebuild said data slice identified by said list of data slices to be rebuilt.

6. The method of claim 5 wherein said message specifies a range of data slice identifiers corresponding to a plurality of inaccessible data slices.

7. The method of claim 5 wherein said message specifies an inaccessible device and further comprising the step of accessing a database relating said inaccessible device to a list of data slice identifiers corresponding to said plurality of inaccessible data slices.

8. The method of claim 7 wherein said inaccessible device is one of the group consisting of a data store associated with a slice server, a slice server, and a site including a plurality of slice servers.

9. A dispersed data storage network comprising a plurality of networked computers including a plurality of slice servers, each of said slice servers storing a plurality of data slices, each of said data slices being identified by a data slice identifier, whereby n of said data slices are associated with a corresponding data segment, and whereby m of said associated data slices are required to reconstruct said corresponding data segment, and further whereby m is less than n, said dispersed data storage network further comprising:

a computer coupled to said plurality of networked computers, said computer running a rebuilder application, said computer adapted to receive a message from one of said networked computers, said message indicative of the inaccessibility of a plurality of data slices, and in response, said rebuilder application;

adding data slice identifiers identifying said plurality of data slices to a list of data slices to be rebuilt;

for each data slice identified by said list of data slices to be rebuilt;

determining a corresponding data segment;

reading at least m data slices associated with said corresponding data segment, said at least m data slices not identified on said list of data slices to be rebuilt;

decoding the retrieved at least m number of data slices by arranging coded values of the retrieved at least m number of data slices into a reconstructed coded matrix and multiplying the reconstructed coded matrix by a decoding matrix in accordance with an information dispersal algorithm to reconstruct the data segment;

encoding the reconstructed data segment by arranging data words of the reconstructed data segment into a data matrix and multiplying the data matrix by the encoding matrix in accordance with the information dispersal algorithm to produce a coded matrix that is arranged into a new plurality of data slices;

writing one of the new plurality of data slices to one of said plurality of slice servers to rebuild said data slice identified by said list of data slices to be rebuilt.

10. The system of claim 9 said computer running the rebuilder application is a grid access computer.

11. The system of claim 9 wherein said message specifies a range of data slice identifiers corresponding to a plurality of inaccessible data slices.

12. The system of claim 9 wherein said message specifies an inaccessible device and said rebuilder application further accessing a database relating said inaccessible device to a list of data slice identifiers corresponding to said plurality of inaccessible data slices.

13. The system of claim 12 wherein said inaccessible device is one of a group consisting of a data store associated with a slice server, a slice server, and a site including a plurality of slice servers.

15. The system of claim 13 wherein said message specifies a range of data slice identifiers corresponding to a plurality of inaccessible data slices.

16. The system of claim 13 wherein said message specifies an inaccessible device and said rebuilder application further accessing a database relating said inaccessible device to a list of data slice identifiers corresponding to said plurality of inaccessible data slices.

17. The system of claim 15 wherein said inaccessible device is one of the group consisting of a data store associated with a slice server, a slice server, and a site including a plurality of slice servers.

14. A dispersed data storage network comprising a plurality of networked computers including a plurality of slice servers, each of said slice servers storing a plurality of data slices, each of said data slices being identified by a data slice identifier and including a data portion and a first checksum, whereby n of said data slices are associated with a corresponding data segment, and whereby m of said associated data slices are required to reconstruct said corresponding data segment, and further whereby m is less than n, said dispersed data storage network further comprising:

a computer coupled to said plurality of networked computers, said computer running a rebuilder application, said rebuilder application;

reading a data slice stored on one of said plurality of slice servers;

computing a second checksum based on the data portion of said data slice;

comparing said second checksum with said first checksum;

adding a data slice identifier identifying said data slice to a list of data slices to be rebuilt when said first checksum does not match said second checksum;

said computer further adapted to receive a message from one of said networked computers, said message indicative of the inaccessibility of a plurality of data slices, and in response, said rebuilder application;

adding data slice identifiers identifying said plurality of data slices to a list of data slices to be rebuilt;

for each data slice identified by said list of data slices to be rebuilt;

determining a corresponding data segment;

reading at least m data slices associated with said corresponding data segment, said at least m data slices not identified on said list of data slices to be rebuilt;

decoding the retrieved at least m number of data slices by arranging coded values of the retrieved at least m number of data slices into a reconstructed coded matrix and multiplying the reconstructed coded matrix by a decoding matrix in accordance with an information dispersal algorithm to reconstruct the data segment;

encoding the reconstructed data segment by arranging data words of the reconstructed data segment into a data matrix and multiplying the data matrix by the encoding matrix in accordance with the information dispersal algorithm to produce a coded matrix that is arranged into a new plurality of data slices;

writing one of the new plurality of data slices to one of said plurality of slice servers to rebuild said data slice identified by said list of data slices to be rebuilt.