Cooperative decentralized rebuild scanning

• US 9,891,995 B2
• Filed: 09/30/2016
• Issued: 02/13/2018
• Est. Priority Date: 01/31/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Nguyen, Phong H
• Application Number:
  US15/283,091
• Publication Number:
  US 20170024284A1
• Time in Patent Office: 501 Days
• Field of Search: 707741, 707769, 707770, 707827
• 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 16/119 Details of migration of file systems migration mechanisms in storage systems G06F3/0647
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• 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 for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method begins by receiving one or more list requests within a timeframe. The method continues by identifying one or more slice name ranges associated with the one or more list requests to produce active address ranges. The method continues by determining a scan address range based on the active address ranges utilizing a range selection approach. The method continues by generating a pillar width number of list requests for an associated set of distributed storage and task (DST) execution units based on the scan address range and sending the pillar width number of list requests to the associated set of DST execution units.

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:

receiving one or more list requests within a timeframe;

identifying one or more slice name ranges associated with the one or more list requests to produce active address ranges, wherein the identifying includes extracting start and stop slice name ranges from the one or more list requests to produce sub-ranges, aggregating the sub-ranges to produce aggregated sub-ranges, and sorting the aggregated sub-ranges to produce the active address ranges;

determining a scan address range based on the active address ranges utilizing a range selection approach;

generating a pillar width number of list requests for an associated set of distributed storage and task (DST) execution units based on the scan address range; and

sending the pillar width number of list requests to the associated set of DST execution units.

2. The method of claim 1, wherein receiving one or more list requests includes receiving a list request from another DST execution unit, where a storage set of DST execution units includes the other DST execution unit and the DST execution unit.

3. The method of claim 2, wherein the one or more list requests include one or more of a list range request and a list digest request.

4. The method of claim 3, wherein the list range request and a list digest request includes one or more of:

a start slice name range, a maximum count indicator, or an end slice name range.

5. The method of claim 1, wherein the active address ranges indicate address ranges associated with active slice error scanning performed by a storage set of DST execution units.

6. The method of claim 1, wherein the determining includes obtaining a range selection approach and utilizing the range selection approach to select a scan address range such that the scan address range does not overlap with the active address ranges.

7. The method of claim 1, wherein, when the scan address range does not overlap with the active address ranges, the execution by one or more processing modules does not duplicate active slice error scanning.

8. The method of claim 1, wherein the range selection approach includes one or more requirements, where each requirement may include one of:

not duplicating a scan address range is part of the active address ranges, incrementing the scan address range up with regards to a previous scan address range, decrementing the range address range down with regards to the previous scan address range, dividing a total address range into a plurality of range portions, or randomly selecting a range portion when the range portion is not included in the active address ranges.

9. The method of claim 1, wherein the generating includes generating each request for each DST execution unit to include a start slice name range of the scan address range and an end slice name range of the scan address range in accordance with a pillar association of the DST execution unit.

10. The method of claim 9, wherein the start slice name range and the end slice name range of a list request is associated with a unique slice index that corresponds to the pillar association of the DST execution unit.

11. The method of claim 1 further comprises one or more of:

processing a list range request or processing a list digest request of the one or more list requests.

12. The method of claim 11, wherein the processing of the list range request includes one or more of:

identifying locally stored slices corresponding to one or more slice names within a range between a start slice name range and an end slice name range of the list request;

generating a list response that includes a slice name of the one or more slice names, a slice revision count, and a slice revision and a slice length corresponding to each revision;

or sending a list range response to a requesting entity.

13. The method of claim 12, wherein the processing of the list digest request includes one or more of:

identifying locally stored slices corresponding to one or more slice names within a range between the start slice name range and the end slice name range of the list request;

generating a list response that includes a digest across each slice name of the one or more slice names, the slice revision count, and the slice revision and the slice length corresponding to each revision;

or sending a list digest response to a requesting entity.

14. The method of claim 1 further comprises receiving list responses from the associated set of DST execution units in response to sending the pillar width number of list requests to the associated set of DST execution units.

15. The method of claim 1, wherein the receiving includes one or more of receiving list responses, identifying differences between the list responses as potential slice errors, and indicating the potential slice errors.

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

an interface;

a local memory; and

a processing module operably coupled to the interface and the local memory, wherein the processing module functions to;

receive one or more list requests within a timeframe;

identify one or more slice name ranges associated with the one or more list requests to produce active address ranges, wherein the identify one or more slice name ranges includes extracting start and stop slice name ranges from the one or more list requests to produce sub-ranges, aggregating the sub-ranges to produce aggregated sub-ranges, and sorting the aggregated sub-ranges to produce the active address ranges;

determine a scan address range based on the active address ranges utilizing a range selection approach;

generate a pillar width number of list requests for an associated set of distributed storage and task (DST) execution units based on the scan address range; and

send the pillar width number of list requests to the associated set of DST execution units.

17. The computing device of claim 16 further comprises processing one or more of:

a list range request or a list digest request of the one or more list requests.

18. The computing device of claim 16 further comprises receiving list responses from the associated set of DST execution units in response to sending the pillar width number of list requests to the associated set of DST execution units.

19. The computing device of claim 16 further comprises receiving a list request from another DST execution unit, where a storage set of DST execution units, includes the other DST execution unit and the DST execution unit.