Allocating rebuilding queue entries in a dispersed storage network

• US 10,241,866 B2
• Filed: 02/22/2017
• Issued: 03/26/2019
• Est. Priority Date: 01/04/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Gray, Adam M., Leggette, Wesley B., Resch, Jason K., Volvovski, Ilya
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US15/439,383
• Publication Number:
  US 20170161147A1
• Time in Patent Office: 762 Days
• Field of Search: 714763
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2201/81 Threshold
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/1054 Parity-fast hardware, i.e. dedicated fast hardware for RAID systems with parity
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method for execution by a processing system in dispersed storage and task network (DSTN) that includes a processor, includes: identifying a slice name of a slice in error of a set of slices stored in a set of dispersed storage (DS) units; identifying a number of slice errors of the set of slices; generating a queue entry that includes the slice name of the slice in error, a rebuilding task indicator, an identity of the set of slices, and the number of slice errors; identifying a rebuilding queue based on the number of slice errors, wherein the rebuilding queue is associated with one of: the set of DS units or another set of DS units; and facilitating storing the queue entry in the identified rebuilding queue.

Claims

1. A method for execution by a processing system in dispersed storage and task network (DSTN) that includes a processor, the method comprises:

identifying a slice name of a slice in error of a set of slices stored in a set of dispersed storage (DS) units;

identifying a number of slice errors of the set of slices;

generating a queue entry that includes the slice name of the slice in error, a rebuilding task indicator, an identity of the set of slices, and the number of slice errors;

identifying a rebuilding queue based on the number of slice errors, wherein the rebuilding queue is associated with one of;

the set of DS units or another set of DS units; and

storing the queue entry in the identified rebuilding queue.

2. The method of claim 1, wherein identifying the slice name of the slice in error includes generating and outputting, to the set of DS units, a set of list slice requests to include a slice name range to be scanned for errors, receiving list slice responses, and identifying the slice name of the slice in error based on a comparison of list slice responses.

3. The method of claim 1, wherein the rebuilding task indicator includes a rebuilding opcode.

4. The method of claim 1, wherein the identity of the set of slices includes a source name.

5. The method of claim 1, wherein identifying the rebuilding queue includes one or more of:

a lookup that retrieves the rebuilding queue from a queue list based on the number of slice errors or receiving the rebuilding queue in response to a query that includes on the number of slice errors.

6. The method of claim 1, wherein storing the queue entry in the identified rebuilding queue includes:

generating a set of queue entry slice names based on one or more of;

a queue vault identifier, a queue name associated with the identified rebuilding queue, a DS processing module identifier associated with the processing module, a client identifier based on a vault lookup, or a current timestamp;

encoding the queue entry using a dispersed storage error coding function to produce a set of queue entry slices;

generating a set of write slice requests that includes the set of queue entry slices and the set of queue entry slice names; and

outputting the set of write slice requests to one of;

the set of DS units or the another set of DS units.

7. The method of claim 1, further comprising:

removing the queue entry from the rebuilding queue to rebuild the slice in error, when the rebuilding queue is associated with a highest number of slices in error.

8. The method of claim 1, further comprising:

deleting the queue entry from the rebuilding queue when rebuilding of the slice in error is complete.

9. A processing system of a dispersed storage and task network (DSTN) comprises:

at least one processor;

a memory that stores operational instructions, that when executed by the at least one processor cause the processing system to operations including;

identifying a slice name of a slice in error of a set of slices stored in a set of dispersed storage (DS) units;

identifying a number of slice errors of the set of slices;

generating a queue entry that includes the slice name of the slice in error, a rebuilding task indicator, an identity of the set of slices, and the number of slice errors;

identifying a rebuilding queue based on the number of slice errors, wherein the rebuilding queue is associated with one of;

the set of DS units or another set of DS units; and

storing the queue entry in the identified rebuilding queue.

10. The processing system of claim 9, wherein identifying the slice name of the slice in error includes generating and outputting, to the set of DS units, a set of list slice requests to include a slice name range to be scanned for errors, receiving list slice responses, and identifying the slice name of the slice in error based on a comparison of list slice responses.

11. The processing system of claim 9, wherein the rebuilding task indicator includes a rebuilding opcode.

12. The processing system of claim 9, wherein the identity of the set of slices includes a source name.

13. The processing system of claim 9, wherein identifying the rebuilding queue includes one or more of:

a lookup that retrieves the rebuilding queue from a queue list based on the number of slice errors or receiving the rebuilding queue in response to a query that includes on the number of slice errors.

14. The processing system of claim 9, wherein storing the queue entry in the identified rebuilding queue includes:

generating a set of queue entry slice names based on one or more of;

a queue vault identifier, a queue name associated with the identified rebuilding queue, a DS processing module identifier associated with the processing module, a client identifier based on a vault lookup, or a current timestamp;

encoding the queue entry using a dispersed storage error coding function to produce a set of queue entry slices;

generating a set of write slice requests that includes the set of queue entry slices and the set of queue entry slice names; and

outputting the set of write slice requests to one of;

the set of DS units or the another set of DS units.

15. The processing system of claim 9, further comprising:

removing the queue entry from the rebuilding queue to rebuild the slice in error, when the rebuilding queue is associated with a highest number of slices in error.

16. The processing system of claim 9, further comprising:

deleting the queue entry from the rebuilding queue when rebuilding of the slice in error is complete.

17. A non-transitory computer readable storage medium comprises:

at least one memory section that stores operational instructions that, when executed by a processing system of a dispersed storage network (DSN) that includes a processor and a memory, causes the processing system to perform operations including;

identifying a slice name of a slice in error of a set of slices stored in a set of dispersed storage (DS) units;

identifying a number of slice errors of the set of slices;

generating a queue entry that includes the slice name of the slice in error, a rebuilding task indicator, an identity of the set of slices, and the number of slice errors;

identifying a rebuilding queue based on the number of slice errors, wherein the rebuilding queue is associated with one of;

the set of DS units or another set of DS units; and

storing the queue entry in the identified rebuilding queue.

18. The non-transitory computer readable storage medium of claim 17, wherein identifying the rebuilding queue includes one or more of:

a lookup that retrieves the rebuilding queue from a queue list based on the number of slice errors or receiving the rebuilding queue in response to a query that includes on the number of slice errors.

19. The non-transitory computer readable storage medium of claim 17, wherein storing the queue entry in the identified rebuilding queue includes:

generating a set of queue entry slice names based on one or more of;

a queue vault identifier, a queue name associated with the identified rebuilding queue, a DS processing module identifier associated with the processing module, a client identifier based on a vault lookup, or a current timestamp;

encoding the queue entry using a dispersed storage error coding function to produce a set of queue entry slices;

generating a set of write slice requests that includes the set of queue entry slices and the set of queue entry slice names; and

outputting the set of write slice requests to one of;

the set of DS units or the another set of DS units.

20. The non-transitory computer readable storage medium of claim 17, wherein the operations further include:

removing the queue entry from the rebuilding queue to rebuild the slice in error, when the rebuilding queue is associated with a highest number of slices in error.