Prioritized data rebuilding in a dispersed storage network

• US 10,120,739 B2
• Filed: 07/06/2017
• Issued: 11/06/2018
• Est. Priority Date: 12/02/2014
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Gladwin, S. Christopher, Kazi, Asimuddin
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US15/642,875
• Publication Number:
  US 20170300374A1
• Time in Patent Office: 488 Days
• Field of Search: None
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• 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/1084 Degraded mode, e.g. caused by single or multiple storage removals or disk failures
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 16/18 File system types
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A method begins with a processing module querying distributed storage network (DSN) storage units regarding storage errors associated with a data segment. The method continues with the processing module receiving query responses and depending on the responses, assigning a first threshold priority or a second threshold priority to encoded data slices (EDSs) associated with the data segment. The method proceeds with the processing module, depending on the assigned threshold priority, issuing read slice requests and rebuilding EDS associated with the data segment.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

transmitting a plurality of queries to a plurality of storage units of the DSN, wherein each query of the plurality of queries is directed at a storage unit of a plurality of storage units of the DSN associated with a first data segment;

receiving one or more query response message of a plurality of query response messages from the plurality of storage units of the DSN, wherein each query response message of the plurality of query response messages is associated with a query of the plurality of queries;

determining, based on the plurality of query response messages received from the plurality of storage units of the DSN, whether a first threshold number of error-free dispersed storage error encoded data slices (EDSs) has been stored in the plurality of storage units of the DSN, wherein the first threshold number of error-free dispersed storage error EDSs were produced from the first data segment;

when the first threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assigning a first rebuilding priority to the first data segment;

when the first threshold number of error-free dispersed storage error EDSs has not been stored in the plurality of storage units of the DSN, determining whether a second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN;

when the second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assigning a second rebuilding priority to the first data segment; and

when a number of error-free dispersed storage error EDSs is between the first threshold number of error-free dispersed storage error EDSs and the second threshold number of error-free dispersed storage error EDSs, issuing a decode threshold number of read slice requests to storage units known to store available error-free EDSs; and

rebuilding one or more dispersed storage error EDSs associated with the first data segment that are not error-free.

2. The method of claim 1, further comprising:

when the second threshold number of error-free dispersed storage error EDSs has not been stored in the plurality of storage units of the DSN, determining whether a third threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN; and

when the number of error-free dispersed storage error EDSs is between the second threshold number of error-free dispersed storage error EDSs and the third threshold number of error-free dispersed storage error EDSs, issuing one or more read slice requests to storage units known to store available error-free EDSs; and

rebuilding one or more dispersed storage error EDSs associated with the first data segment that are not error-free.

3. The method of claim 1, further comprising:

transmitting at least a second threshold number of list slice message requests to the plurality of storage units of the DSN, wherein the at least a second threshold number of list slice message requests is associated with a second data segment;

receiving a second plurality of list slice response messages from the plurality of storage units of the DSN, wherein a number of list slice response messages are associated with the second threshold number of list slice message requests;

determining, based on the second plurality of list slice response messages received from the plurality of storage units of the DSN, whether the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN;

when the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN, assigning the first rebuilding priority to the first data segment;

when the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has not been stored in the plurality of storage units of the DSN, determining whether the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN;

when the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN, assigning a second rebuilding priority to the first data segment; and

when the number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests is between the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests and the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests, issuing a decode threshold number of read slice requests to storage units known to store available error-free EDSs associated with the second threshold number of list slice message requests; and

rebuilding one or more dispersed storage error EDSs associated with the second data segment that are not error-free.

4. The method of claim 1, wherein the DSN includes a plurality of storage sites and the plurality of storage units of the DSN are distributed between at least two of the plurality of storage sites and further wherein each of the at least two of the plurality of storage sites includes a number of storage units sufficient to store each of the second threshold number of error-free dispersed storage error EDSs in a separate storage unit.

5. The method of claim 1, wherein the first threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs.

6. The method of claim 5, wherein the second threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs and less than the first threshold number of error-free dispersed storage error EDS s.

7. The method of claim 1, wherein the rebuilding one or more dispersed storage error EDSs associated with the first data segment that are not error-free further comprises:

rebuilding a number of dispersed storage error EDSs such that the number of error-free dispersed storage error EDSs is equal to or greater than the second threshold number of error-free dispersed storage error EDSs.

8. The method of claim 1, wherein the rebuilding one or more dispersed storage error EDSs associated with the first data segment that are not error-free further comprises:

rebuilding a number of dispersed storage error EDSs such that the number of error-free dispersed storage error EDSs is equal to or greater than the first threshold number of error-free dispersed storage error EDSs, based on at least one of predetermined DSN system performance level, current DSN traffic load, and predetermined network traffic level.

9. The method of claim 1, wherein each query of the plurality of queries is a list slice request and each query response message of the plurality of query response messages is a list slice message, and further wherein each list slice message includes an indication of a storage error in a storage unit associated with the first data segment.

10. A computing device comprising:

an interface configured to interface and communicate with a dispersed or distributed storage network (DSN);

memory that stores operational instructions;

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

transmit at least a first threshold number of list slice message requests to a plurality of storage units of the DSN, wherein the at least a first threshold number of list slice message requests is associated with a first data segment;

receive a plurality of list slice response messages from the plurality of storage units of the DSN, wherein a number of list slice response messages are associated with the first threshold number of list slice message requests;

determine, based on the plurality of list slice response messages received from the plurality of storage units of the DSN, whether a first threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN;

when the first threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assign a first rebuilding priority to the first data segment;

when the first threshold number of error-free dispersed storage error EDSs has not been stored in the plurality of storage units of the DSN, determine whether a second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN;

when the second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assign a second rebuilding priority to the first data segment; and

when a number of error-free dispersed storage error EDSs is between the first threshold number of error-free dispersed storage error EDSs and the second threshold number of error-free dispersed storage error EDSs, issue a decode threshold number of read slice requests to storage units known to store available error-free EDSs; and

rebuild one or more dispersed storage error EDSs associated with the first data segment that are not error-free.

11. The computing device of claim 10, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

when the second threshold number of error-free dispersed storage error EDSs has not been stored in the plurality of storage units of the DSN, determine whether a third threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN; and

when the number of error-free dispersed storage error EDSs is between the second threshold number of error-free dispersed storage error EDSs and the third threshold number of error-free dispersed storage error EDSs, issue one or more read slice requests to storage units known to store available error-free EDSs; and

rebuild one or more dispersed storage error EDSs associated with the first data segment that are not error-free.

12. The computing device of claim 10, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

transmit at least a second threshold number of list slice message requests to the plurality of storage units of the DSN, wherein the at least a second threshold number of list slice message requests is associated with a second data segment;

receive a second plurality of list slice response messages from the plurality of storage units of the DSN, wherein the number of list slice response messages are associated with the second threshold number of list slice message requests;

determine, based on the plurality of list slice response messages received from the plurality of storage units of the DSN, whether the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN;

when the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN, assign the first rebuilding priority to the first data segment;

when the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has not been stored in the plurality of storage units of the DSN, determine whether the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN;

when the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests has been stored in the plurality of storage units of the DSN, assign a second rebuilding priority to the first data segment; and

when the number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests is between the first threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests and the second threshold number of error-free dispersed storage error EDSs associated with the second threshold number of list slice message requests, issue a decode threshold number of read slice requests to storage units known to store available error-free EDSs associated with the second threshold number of list slice message requests; and

rebuild one or more dispersed storage error EDSs associated with the second data segment that are not error-free.

13. The computing device of claim 10, wherein the DSN includes a plurality of storage sites and the plurality of storage units of the DSN are distributed between at least two of the plurality of storage sites and further wherein each of the at least two of the plurality of storage sites includes a number of storage units sufficient to store each of the second threshold number of error-free dispersed storage error EDSs in a separate storage unit.

14. The computing device of claim 10, wherein the first threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs.

15. The computing device of claim 10, wherein the second threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs and less than the first threshold number of error-free dispersed storage error EDSs.

16. The computing device of claim 10, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

rebuild a number of dispersed storage error EDSs such that the number of error-free dispersed storage error EDSs is equal to or greater than the second threshold number of error-free dispersed storage error EDSs.

17. The computing device of claim 10, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

rebuild a number of dispersed storage error EDSs such that the number of error-free dispersed storage error EDSs is equal to or greater than the first threshold number of error-free dispersed storage error EDSs, based on at least one of predetermined DSN system performance level, current DSN traffic load, and predetermined network traffic level.

18. A non-transitory computer readable storage device comprises:

a first memory section that stores operational instructions that, when executed by a computing device, causes the computing device to transmit at least a first threshold number of list slice message requests to a plurality of storage units of a distributed storage network (DSN), wherein the at least a first threshold number of list slice message requests is associated with a first data segment;

a second memory section that stores operational instructions that, when executed by the computing device, causes the computing device to;

receive a plurality of list slice response messages from the plurality of storage units of the DSN;

determine, based on the plurality of list slice response messages received from the plurality of storage units of the DSN, whether a first threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN; and

when the first threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assign a first rebuilding priority to the first data segment;

when the first threshold number of error-free dispersed storage error EDSs has not been stored in the plurality of storage units of the DSN, determine whether a second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN; and

when the second threshold number of error-free dispersed storage error EDSs has been stored in the plurality of storage units of the DSN, assign a second rebuilding priority to the first data segment;

when a number of error-free dispersed storage error EDSs is between the first threshold number of error-free dispersed storage error EDSs and the second threshold number of error-free dispersed storage error EDSs, issue a decode threshold number of read slice requests to storage units known to store available error-free EDSs; and

rebuild one or more dispersed storage error EDSs associated with the first data segment that are not error-free.

19. The non-transitory computer readable storage device of claim 18, wherein the first threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs.

20. The non-transitory computer readable storage device of claim 19, wherein the second threshold number of error-free dispersed storage error EDSs is less than an information dispersal algorithm (IDA) width number of dispersed storage error EDSs and less than the first threshold number of error-free dispersed storage error EDSs.