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

• US 20100161916A1
• Filed: 03/02/2010
• Published: 06/24/2010
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: MARK, ZACHARY J., VOLVOVSKI, ILYA, BELLANCA, JAMIE, THORNTON, VANCE T., HENDRICKSON, DUSTIN M.
• Granted Patent: US 8,560,882 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• 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 identifying a data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of data slices that constitute a data segment and wherein each of the plurality of data slices is assigned for storage by a corresponding one of a plurality of data slice servers. The method continues by retrieving at least m number of data slices from at least m number of the plurality of data slice servers, wherein m data slices of the plurality of data slices enable reconstruction of the data segment, and wherein the at least m number of data slices does not include the identified data slice. The method continues by reconstructing the identified data slice from the at least m number of data slices to produce a rebuilt data slice. The method continues by writing the rebuilt data slice to the corresponding one of the plurality of data slice servers or to a new slice server.

Claims

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

identifying a data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of data slices that constitute a data segment and wherein each of the plurality of data slices is assigned for storage by a corresponding one of a plurality of data slice servers;

retrieving at least m number of data slices from at least m number of the plurality of data slice servers, wherein m data slices of the plurality of data slices enable reconstruction of the data segment, and wherein the at least m number of data slices does not include the identified data slice;

reconstructing the identified data slice from the at least m number of data slices to produce a rebuilt data slice; and

writing the rebuilt data slice to the corresponding one of the plurality of data slice servers or to a new slice server.

2. The method of claim 1, wherein the retrieving further comprises:

transmitting a rebuild message to the at least m number of the plurality of data slice servers, wherein the rebuild message identifies at least one of;

a corresponding data slice of the plurality of data slices; and

the data segment;

receiving the at least m number of data slices from the at least m number of the plurality of data slice servers.

3. The method of claim 1, wherein the reconstructing the identified data slice further comprises:

reconstructing the data segment from the at least m number of data slices to produce a reconstructed data segment;

applying an information dispersal algorithm on the reconstructed data segment to produce a plurality of rebuilt data slices; and

utilizing one of the plurality of rebuilt data slices as the rebuilt data slice.

4. The method of claim 3 further comprises:

transmitting a write command to the plurality of slice servers, wherein the write command instructs a slice server of the plurality of slice servers to overwrite a corresponding one of the data slices with a corresponding one of the plurality of rebuilt data slices.

5. The method of claim 1 further comprises:

updating a transaction identification value of the rebuilt data slice.

6. The method of claim 1 further comprises:

prior to rebuilding the identified data slice, recording the identified data slice to produce a recorded data slice; and

reconstructing the recorded data slice to produce the rebuilt data slice.

7. The method of claim 1 further comprises:

determining a cause for the identified data slice requiring rebuilding;

when the cause for the identified data slice requiring rebuilding is one of corruption or out-of-date, writing the rebuilt data slice to the corresponding one of the plurality of slice servers assigned to store the identified data slice;

determining a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is a missing data slice;

writing the rebuild data slice to the new slice server; and

updating the plurality of slice servers to include the new slice server and to remove the slice server corresponding to the identified data slice.

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

identifying a data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of data slices that constitute a data segment and wherein each of the plurality of data slices is assigned for storage by a corresponding one of a plurality of data slice servers;

retrieving at least m number of data slices from at least m number of the plurality of data slice servers, wherein m data slices of the plurality of data slices enable reconstruction of the data segment, and wherein the at least m number of data slices does not include the identified data slice;

reconstructing the data segment from the at least m number of data slices to produce a reconstructed data segment;

performing an information dispersal algorithm on the reconstructed data segment to produce a plurality of rebuilt data slices; and

writing the plurality of rebuilt data slices to the plurality of slice servers or to a new plurality of slice servers.

9. The method of claim 8 further comprises:

the new plurality of slice servers including at least one of the plurality of slice servers but not including the slice server assigned to store the identified data slice.

10. The method of claim 8, wherein the retrieving further comprises:

transmitting a rebuild message to the at least m number of the plurality of data slice servers, wherein the rebuild message identifies at least one of;

a corresponding data slice of the plurality of data slices; and

the data segment;

receiving the at least m number of data slices from the at least m number of the plurality of data slice servers.

11. The method of claim 8 further comprises:

updating a transaction identification value of for each of the plurality of rebuilt data slices.

12. The method of claim 8 further comprises:

determining a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is one of corruption or out-of-date, writing a corresponding one of the plurality of rebuilt data slices to the corresponding one of the plurality of slice servers assigned to store the identified data slice;

determining a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is a missing data slice;

writing a corresponding one of the plurality of rebuild data slices to a new slice server of the new plurality of slice servers.

13. 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;

identify a data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of data slices that constitute a data segment and wherein each of the plurality of data slices is assigned for storage by a corresponding one of a plurality of data slice servers;

retrieve at least m number of data slices from at least m number of the plurality of data slice servers, wherein m data slices of the plurality of data slices enable reconstruction of the data segment, and wherein the at least m number of data slices does not include the identified data slice; and

reconstruct the identified data slice from the at least m number of data slices to produce a rebuilt data slice; and

write the rebuilt data slice to the corresponding one of the plurality of data slice servers or to a new slice server.

14. The computer of claim 13, wherein the central processing unit further functions to retrieve the at least m number of data slices by:

transmitting, via the network interface, a rebuild message to the at least m number of the plurality of data slice servers, wherein the rebuild message identifies at least one of;

a corresponding data slice of the plurality of data slices; and

the data segment;

receiving, via the network interface, the at least m number of data slices from the at least m number of the plurality of data slice servers.

15. The computer of claim 13, wherein the central processing unit further functions to reconstruct the identified data slice by:

reconstructing the data segment from the at least m number of data slices to produce a reconstructed data segment;

applying an information dispersal algorithm on the reconstructed data segment to produce a plurality of rebuilt data slices; and

utilizing one of the plurality of rebuilt data slices as the rebuilt data slice.

16. The computer of claim 15, wherein the central processing unit further functions to:

transmitting, via the network interface, a write command to the plurality of slice servers, wherein the write command instructs a slice server of the plurality of slice servers to overwrite a corresponding one of the data slices with a corresponding one of the plurality of rebuilt data slices.

17. The computer of claim 13, wherein the central processing unit further functions to:

update a transaction identification value of the rebuilt data slice.

18. The computer of claim 13, wherein the central processing unit further functions to:

determine a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is one of corruption or out-of-date, write the rebuilt data slice to the corresponding one of the plurality of slice servers assigned to store the identified data slice;

determine a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is a missing data slice;

write the rebuild data slice to the new slice server; and

update the plurality of slice servers to include the new slice server and to remove the slice server corresponding to the identified data slice.

19. 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;

identify a data slice requiring rebuilding to produce an identified data slice, wherein the identified data slice is one of a plurality of data slices that constitute a data segment and wherein each of the plurality of data slices is assigned for storage by a corresponding one of a plurality of data slice servers;

retrieve at least m number of data slices from at least m number of the plurality of data slice servers, wherein m data slices of the plurality of data slices enable reconstruction of the data segment, and wherein the at least m number of data slices does not include the identified data slice;

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

perform an information dispersal algorithm on the reconstructed data segment to produce a plurality of rebuilt data slices; and

write the plurality of rebuilt data slices to the plurality of slice servers or to a new plurality of slice servers.

20. The computer of claim 19 further comprises:

the new plurality of slice servers including at least one of the plurality of slice servers but not including the slice server assigned to store the identified data slice.

21. The computer of claim 19, wherein the central processing unit further functions to retrieve the at least m number of data slices by:

transmitting a rebuild message to the at least m number of the plurality of data slice servers, wherein the rebuild message identifies at least one of;

a corresponding data slice of the plurality of data slices; and

the data segment;

receiving the at least m number of data slices from the at least m number of the plurality of data slice servers.

22. The computer of claim 19, wherein the central processing unit further functions to:

updating a transaction identification value of for each of the plurality of rebuilt data slices.

23. The computer of claim 19, wherein the central processing unit further functions to:

determine a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is one of corruption or out-of-date, write a corresponding one of the plurality of rebuilt data slices to the corresponding one of the plurality of slice servers assigned to store the identified data slice;

determine a cause for the identified data slice requiring rebuilding; and

when the cause for the identified data slice requiring rebuilding is a missing data slice;

write a corresponding one of the plurality of rebuild data slices to a new slice server of the new plurality of slice servers.