Likelihood based rebuilding of missing encoded data slices

• US 9,626,248 B2
• Filed: 07/10/2014
• Issued: 04/18/2017
• Est. Priority Date: 11/25/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Hoffman, Steven Mark, Resch, Jason K., Gladwin, S. Christopher
• Primary Examiner(s): BRYAN, JASON B
• Application Number:
  US14/327,582
• Publication Number:
  US 20140325266A1
• Time in Patent Office: 1,013 Days
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G11B 5/09 Digital recording

Abstract

A method begins by a processing module of a dispersed storage network (DSN) detecting a likelihood of having a missing encoded data slice based on local physical to DSN address mapping information. When the likelihood of having the missing encoded data slice exists, the method continues with the processing module sending a query regarding the missing encoded data slice to another storage unit of the DSN and receiving a response to the query from the other storage unit. When the response includes identity of a related encoded data slice of a set of encoded data slices, the method continues with the processing module commencing execution of a rebuilding function to generate a new encoded data slice to replace the missing encoded data slice.

Claims

1. A method for execution by a storage unit of a dispersed storage network (DSN), the method comprises:

detecting a likelihood of the storage unit having a missing encoded data slice based on local physical-to-DSN address mapping information by interpreting the local physical-to-DSN address mapping information to determine that a sub-range of DSN addresses is not affiliated with a particular memory device of the storage unit; and

when the likelihood of having the missing encoded data slice exists;

sending a query regarding the missing encoded data slice to another storage unit of the DSN;

receiving a response to the query from the other storage unit; and

when the response includes identity of a related encoded data slice of a set of encoded data slices, commencing execution of a rebuilding function to generate a new encoded data slice to replace the missing encoded data slice, wherein a data segment of a data object is encoded into the set of encoded data slices, wherein a threshold number of encoded data slices of the set of encoded data slices is required to recover the data segment, wherein the threshold number is less than a number of encoded data slices in the set of encoded data slices, wherein the other storage unit stores the related encoded data slice, wherein the storage unit has been assigned to store a second encoded data slice of the set of encoded data slices, and wherein the second encoded data slice corresponds to the missing encoded data slice.

2. The method of claim 1, wherein the detecting the likelihood of having a missing encoded data slice further comprises:

interpreting the local physical-to-DSN address mapping information to determine that the sub-range of DSN addresses has a disproportionate amount of encoded data slices having DSN addresses in the sub-range of DSN addresses to other sub-ranges of DSN addresses.

3. The method of claim 1 further comprises:

sending the query to the other storage unit, wherein the query includes a request for the related encoded data slice; and

receiving, as the response, the related encoded data slice from the other storage unit.

4. The method of claim 3 further comprises:

sending the query to storage units of the DSN, wherein the query includes a request for other related encoded data slices of the set of encoded data slices;

receiving, as a set of responses, the other related encoded data slices;

when the related encoded data slice and the other related encoded data slices amounts to the threshold number, decoding the related encoded data slice and the other related encoded data slices to recapture the data segment; and

encoding the data segment to create the new encoded data slice.

5. The method of claim 1, wherein the commencing the execution of the rebuilding function comprises:

sending requests to storage units of the DSN regarding other related encoded data slices of the set of encoded data slices;

receiving, as a set of responses, the other related encoded data slices;

when the related encoded data slice and the other related encoded data slices amounts to the threshold number, decoding the related encoded data slice and the other related encoded data slices to recapture the data segment; and

encoding the data segment to create the new encoded data slice.

6. A storage unit of a dispersed storage network (DSN), the storage unit comprises:

a memory;

an interface; and

a processing module operably coupled to the memory and the interface, wherein the processing module is operable to;

detect a likelihood of the storage unit having a missing encoded data slice based on local physical to DSN address mapping information by interpreting the local physical-to-DSN address mapping information to determine that a sub-range of DSN addresses is not affiliated with a particular memory device of the storage unit; and

when the likelihood of having the missing encoded data slice exists;

send, via the interface, a query regarding the missing encoded data slice to another storage unit of the DSN;

receive, via the interface, a response to the query from the other storage unit; and

when the response includes identity of a related encoded data slice of a set of encoded data slices, commence execution of a rebuilding function to generate a new encoded data slice to replace the missing encoded data slice, wherein a data segment of a data object is encoded into the set of encoded data slices, wherein a threshold number of encoded data slices of the set of encoded data slices is required to recover the data segment, wherein the threshold number is less than a number of encoded data slices in the set of encoded data slices, wherein the other storage unit stores the related encoded data slice, wherein the storage unit has been assigned to store a second encoded data slice of the set of encoded data slices, and wherein the second encoded data slice corresponds to the missing encoded data slice.

7. The storage unit of claim 6, wherein the processing module further functions to detect the likelihood of having a missing encoded data slice by:

interpreting the local physical-to-DSN address mapping information to determine that a sub-range of DSN addresses has a disproportionate amount of encoded data slices having DSN addresses in the sub-range of DSN addresses to other sub-ranges of DSN addresses.

8. The storage unit of claim 6 further comprises:

the processing module is further operable to;

send, via the interface, the query to the other storage unit, wherein the query includes a request for the related encoded data slice; and

receive, as the response via the interface, the related encoded data slice from the other storage unit.

9. The storage unit of claim 8 further comprises:

the processing module is further operable to;

send, via the interface, the query to storage units of the DSN, wherein the query includes a request for other related encoded data slices of the set of encoded data slices;

receive, as a set of responses via the interface, the other related encoded data slices;

when the related encoded data slice and the other related encoded data slices amounts to the threshold number, decode the related encoded data slice and the other related encoded data slices to recapture the data segment; and

encode the data segment to create the new encoded data slice.

10. The storage unit of claim 6, wherein the processing module commences the execution of the rebuilding function by:

sending, via the interface, requests to storage units of the DSN regarding other related encoded data slices of the set of encoded data slices;

receiving, as a set of responses via the interface, the other related encoded data slices;

when the related encoded data slice and the other related encoded data slices amounts to the threshold number, decoding the related encoded data slice and the other related encoded data slices to recapture the data segment; and

encoding the data segment to create the new encoded data slice.