Determining missing encoded data slices

• US 10,318,382 B2
• Filed: 10/03/2018
• Issued: 06/11/2019
• Est. Priority Date: 01/31/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Shirley, Jr., Thomas F., Grube, Gary W., Cilfone, Bart R., Khadiwala, Ravi V., Dhuse, Greg R., Cocagne, Thomas D., Storm, Michael C., Vedpathak, Yogesh R., Leggette, Wesley B., Resch, Jason K., Baptist, Andrew D., Volvovski, Ilya
• Primary Examiner(s): Yu, Jae U
• Application Number:
  US16/150,841
• Publication Number:
  US 20190034278A1
• Time in Patent Office: 251 Days
• Field of Search: 711148
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0617 in relation to availability
• 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 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• 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]

Abstract

A method includes determining, by a computing device of a dispersed storage network (DSN), a source name for a data object to be scanned for missing encoded data slices. The method further includes issuing list source requests to the set of storage units. When a list source response is not received from a storage unit of the set of storage units within a response timeframe, the method further includes identifying one or more encoded data slices stored on the storage unit as potentially missing encoded data slices; determining a next level missing encoded data slice determination approach for the storage unit based on one or more of: a number of potentially missing encoded data slices, a performance goal, a network loading level, a rebuilding loading level, a predetermination, and an entry of a system registry; and executing the next level missing encoded data slice determination approach.

Claims

1. A method comprises:

determining, by a computing device of a dispersed storage network (DSN), a source name for a data object to be scanned for missing encoded data slices, wherein the data object is stored as a plurality of sets of encoded data slices on a set of storage units of the DSN;

issuing, by the computing device, list source requests to the set of storage units; and

when a list source response is not received from a storage unit of the set of storage units within a response timeframe;

identifying, by the computing device, one or more encoded data slices stored on the storage unit as potentially missing encoded data slices;

determining, by the computing device, a next level missing encoded data slice determination approach for the storage unit based on one or more of;

a number of potentially missing encoded data slices, a performance goal, a network loading level, a rebuilding loading level, a predetermination, and an entry of a system registry; and

executing, by the computing device, the next level missing encoded data slice determination approach.

2. The method of claim 1 further comprises:

when one or more list source responses are received within the response timeframe;

identifying, by the computing device, missing encoded data slices from the plurality of sets of encoded data slices based on the received list source responses.

3. The method of claim 1, wherein the list source requests include requests to list slice names of encoded data slices associated with the source name stored by the set of storage units.

4. The method of claim 1, wherein the next level missing slice determination approach includes:

when “

n−

k+x”

or less encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices are potentially missing, wherein “

n”

is a width number, “

k”

is a decode threshold number, and “

x”

is an integer between 1 and “

n−

k−

1,”

wherein the width number is a total number of encoded data slices of the set of encoded data slices and the decode threshold number is a minimum number of encoded data slices of the set of encoded data slices required to recover a data segment of the data object, and wherein the data segment is dispersed storage error encoded to produce the set of encoded data slices;

flagging, by the computing device, the potentially missing encoded data slices as missing encoded data slices.

5. The method of claim 4 further comprises one of:

rebuilding, by the computing device, the flagged missing encoded data slices; and

instructing, by the computing device, one or more other computing devices of the DSN to rebuild the flagged missing encoded data slices.

6. The method of claim 4 further comprises:

scheduling, by the computing device, rebuilding the flagged missing encoded data slices for a later time.

7. The method of claim 4 further comprises:

initiating, by the computing device, storage of one or more foster slices for the flagged missing encoded data slices on an available storage unit of the set of storage units.

8. The method of claim 1, wherein the next level missing slice determination approach includes:

when “

n−

k+x”

or less encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices are not potentially missing, wherein “

n”

is a width number, “

k”

is a decode threshold number, and “

x”

is an integer between 1 and “

n−

k−

1,”

wherein the width number is a total number of encoded data slices of the set of encoded data slices and the decode threshold number is a minimum number of encoded data slices of the set of encoded data slices required to recover a data segment of the data object, and wherein the data segment is dispersed storage error encoded to produce the set of encoded data slices;

waiting, by the computing device, a time period for the storage unit to become available, wherein the time period is set based on one or more of;

performance requirements, rebuild delay, and network bandwidth; and

sending, by the computing device, a list source request to the storage unit.

9. The method of claim 1, wherein the next level missing slice determination approach includes:

determining, by the computing device, whether one or more received list source responses indicate storage of the potentially missing encoded data slices on one or more other storage units;

when the one or more received list source responses do not indicate storage of the potentially missing encoded data slices on the one or more other storage units;

waiting, by the computing device, a time period to receive one or more list source responses indicating storage of the potentially missing encoded data slices on one or more other storage units, wherein the time period is set based on one or more of;

performance requirements, rebuild delay, and network bandwidth; and

when the one or more received list source responses indicate storage of the potentially missing encoded data slices on the one or more other storage units;

identifying, by the computing device, the potentially missing encoded data slices as not missing.

10. A computing device of a dispersed storage network (DSN), the computing device comprises:

an interface;

memory; and

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

determine a source name for a data object to be scanned for missing encoded data slices, wherein the data object is stored as a plurality of sets of encoded data slices on a set of storage units of the DSN;

issue list source requests to the set of storage units; and

when a list source response is not received from a storage unit of the set of storage units within a response timeframe;

identify one or more encoded data slices stored on the storage unit as potentially missing encoded data slices;

determine a next level missing encoded data slice determination approach for the storage unit based on one or more of;

a number of potentially missing encoded data slices, a performance goal, a network loading level, a rebuilding loading level, a predetermination, and an entry of a system registry; and

execute the next level missing encoded data slice determination approach.

11. The computing device of claim 10, wherein the processing module is further operable to:

when one or more list source responses are received within the response timeframe;

identify missing encoded data slices from the plurality of sets of encoded data slices based on the received list source responses.

12. The computing device of claim 10, wherein the list source requests include requests to list slice names of encoded data slices associated with the source name stored by the set of storage units.

13. The computing device of claim 10, wherein the next level missing slice determination approach includes:

when “

n−

k+x”

encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices are potentially missing, wherein “

n”

is a width number, “

k”

is a decode threshold number, and “

x”

is an integer between 1 and “

n−

k−

1,”

wherein the width number is a total number of encoded data slices of the set of encoded data slices and the decode threshold number is a minimum number of encoded data slices of the set of encoded data slices required to recover a data segment of the data object, and wherein the data segment is dispersed storage error encoded to produce the set of encoded data slices, the processing module is further operable to;

flag the potentially missing encoded data slices as missing encoded data slices.

14. The computing device of claim 13, wherein the processing module is further operable to:

rebuild the flagged missing encoded data slices;

or

instruct one or more other computing devices of the DSN to rebuild the flagged missing encoded data slices.

15. The computing device of claim 13, wherein the processing module is further operable to:

schedule rebuilding the flagged missing encoded data slices for a later time.

16. The computing device of claim 13, wherein the processing module is further operable to:

initiate storage of one or more foster slices for the flagged missing encoded data slices on an available storage unit of the set of storage units.

17. The computing device of claim 10, wherein the next level missing slice determination approach includes:

when “

n−

k+x”

encoded data slices of a set of encoded data slices of the plurality of sets of encoded data slices are not potentially missing, wherein “

n”

is a width number, “

k”

is a decode threshold number, and “

x”

is an integer between 1 and “

n−

k−

1,”

wherein the width number is a total number of encoded data slices of the set of encoded data slices and the decode threshold number is a minimum number of encoded data slices of the set of encoded data slices required to recover a data segment of the data object, and wherein the data segment is dispersed storage error encoded to produce the set of encoded data slices, the processing module is further operable to;

wait a time period for the storage unit to become available, wherein the time period is set based on one or more of;

performance requirements, rebuild delay, and network bandwidth; and

send a list source request to the storage unit.

18. The computing device of claim 10, wherein the next level missing slice determination approach includes:

determining whether one or more received list source responses indicate storage of the potentially missing encoded data slices on one or more other storage units;

when the one or more received list source responses do not indicate storage of the potentially missing encoded data slices on the one or more other storage units, the processing module is further operable to;

wait a time period to receive one or more list source responses indicating storage of the potentially missing encoded data slices on one or more other storage units, wherein the time period is set based on one or more of;

performance requirements, rebuild delay, and network bandwidth; and

when the one or more received list source responses indicate storage of the potentially missing encoded data slices on the one or more other storage units, the processing module is further operable to;

identify the potentially missing encoded data slices as not missing.