Prioritizing rebuilding of encoded data slices

Patent metadata

Field	Value
Publication number	US-10282440-B2
Application number	US-201615006845-A
Country	US
Kind code	B2
Filing date	Jan 26, 2016
Priority date	Mar 31, 2015
Publication date	May 7, 2019
Grant date	May 7, 2019

Abstract

A method begins by a first computing device of a plurality of computing devices accessing a rebuild hierarchical index structure to identify a data object having encoded data slices requiring rebuilding, where the structure includes a plurality of nodes that organizes a plurality of data objects based on a level of need of rebuilding. The method continues with the first computing device utilizing a rebuilding function to rebuild one or more of the identified encoded data slices to be rebuilt to produce one or more rebuilt encoded data slices and sending a write request to memory of a dispersed storage network to store the one or more rebuilt encoded data slices. The method continues with the first or another computing device updating the level of need of rebuilding of the identified data object and updating the rebuild hierarchical index structure based on the updated level of need of rebuilding.

First claim

What is claimed is:

1. A method comprises:
accessing, by a first computing device of a plurality of computing devices, a rebuild hierarchical index structure to identify a data object having encoded data slices requiring rebuilding to produce an identified data object and identified encoded data slices to be rebuilt, wherein the rebuild hierarchical index structure includes a plurality of nodes that organizes a plurality of data objects based on a level of need of rebuilding, wherein the plurality of data objects includes the data object;
utilizing, by the first computing device, a rebuilding function in accordance with rebuilding processing parameters to rebuild one or more of the identified encoded data slices to be rebuilt to produce one or more rebuilt encoded data slices;
sending, by the first computing device, a write request to memory of a dispersed storage network to store the one or more rebuilt encoded data slices;
updating the level of need of rebuilding of the identified data object to produce an updated level of need of rebuilding; and
updating the rebuild hierarchical index structure based on the updated level of need of rebuilding.

2. The method of claim 1 , wherein the plurality of nodes of the rebuild hierarchical index structure comprises:
a root node that identifies the plurality of data objects based on a common storage parameter;
a plurality of intermediate index nodes that is linked to the root node and further categorizes the plurality of data objects based on one or more common naming conventions for encoded data slices of one of the plurality of data objects, wherein the one of the plurality of data objects is divided into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed storage error encoded into a set of encoded data slices, and wherein the encoded data slices of the one of the plurality of data objects includes the plurality of sets of encoded data slices; and
a plurality of leaf nodes, wherein a leaf node of the plurality of leaf nodes is linked to one or more intermediate index nodes of the plurality of intermediate index nodes, wherein the plurality of leaf nodes further categorizes the plurality of data objects based on the level of need of rebuilding.

3. The method of claim 2 further comprises:
determining the level of need of rebuilding based on one or more rebuilding factors of a plurality of rebuilding factors, wherein the plurality of rebuilding factors includes:
a data size of a corresponding data object;
a number of encoded data slices in the identified encoded data slices to be rebuilt;
a number of data segments of the plurality of data segments having an encoded data slice requiring rebuilding;
dispersed storage error encoding parameters; and
a number of data segments of the plurality of data segments having more than one encoded data slice requiring rebuilding.

4. The method of claim 1 , wherein the accessing to identify the identified data object comprises:
searching the rebuild hierarchical index structure to find one of the plurality of data objects having a level of need of rebuilding above a need threshold and within a range of data objects of the plurality of data objects.

5. The method of claim 1 , wherein the rebuilding processing parameters comprises one or more of:
a number of encoded data slices in the identified encoded data slices to be rebuilt;
available processing resources of the first computing device for executing the rebuilding function; and
an acceptable level of need for rebuilding.

6. The method of claim 1 further comprises:
updating, by the first computing device or another computing device of the plurality of computing devices, the level of need of rebuilding of the identified data object to produce an updated level of need of rebuilding; and
updating, by the first computing device or the other computing device, the rebuild hierarchical index structure based on the updated level of need of rebuilding.

7. The method of claim 1 , wherein the updating the rebuild hierarchical index structure comprises:
querying a storage unit regarding a group of encoded data slices stored therein;
identifying an encoded data slice of the group of encoded data slices requiring rebuilding to produce a newly identified encoded data slice in need of rebuilding;
identifying a data object associated with the newly identified encoded data slice in need of rebuilding;
determining whether the associated data object is included in the plurality of data objects; and
when the associated data object is included in the plurality of data objects:
updating the identified encoded data slices to be rebuilt to include the newly identified encoded data slice in need of rebuilding;
increasing the level of need of rebuilding for the data object; and
adjusting the associated data object's positioning within the rebuild hierarchical index structure based on the increased level of need of rebuilding.

8. The method of claim 7 further comprises:
when the associated data object is not included in the plurality of data objects:
adding the associated data object to the plurality of data objects;
determining the level of need of rebuilding for the associated data object; and
inserting the associated data object into the rebuild hierarchical index structure based on the determined level of need of rebuilding.

9. The method of claim 1 , wherein the updating the rebuild hierarchical index structure comprises:
determining a number of encoded data slices of the identified encoded data slices to be rebuilt that have been rebuilt to produce a number of rebuilt encoded data slices;
updating the identified encoded data slices to be rebuilt to remove the number of rebuilt encoded data slices;
decreasing the level of need of rebuilding for the data object based on the updated identified encoded data slices; and
adjusting the data object's positioning within the rebuild hierarchical index structure based on the decreased level of need of rebuilding.

10. A non-transitory computer readable storage medium comprises:
at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a plurality of computing devices of a dispersed storage network (DSN), causes the one or more computing devices to:
access, by a first computing device of the plurality of computing devices, a rebuild hierarchical index structure to identify a data object having encoded data slices requiring rebuilding to produce an identified data object and identified encoded data slices to be rebuilt, wherein the rebuild hierarchical index structure includes a plurality of nodes that organizes a plurality of data objects based on a level of need of rebuilding, wherein the plurality of data objects includes the data object;
utilize, by the first computing device, a rebuilding function in accordance with rebuilding processing parameters to rebuild one or more of the identified encoded data slices to be rebuilt to produce one or more rebuilt encoded data slices;
send, by the first computing device, a write request to memory of a dispersed storage network to store the one or more rebuilt encoded data slices;
update the level of need of rebuilding of the identified data object to produce an updated level of need of rebuilding; and
update the rebuild hierarchical index structure based on the updated level of need of rebuilding.

11. The non-transitory computer readable storage medium of claim 10 , wherein the plurality of nodes of the rebuild hierarchical index structure comprises:
a root node that identifies the plurality of data objec

Assignees

• IBM

Inventors

• Dhuse Greg
• Khadiwala Ravi
• Cocagne Thomas Darrel
• Baptist Andrew
• Kaczmarek Joseph Martin

Classifications

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2272 Primary

  Management thereof · CPC title

• G06F17/30321

  Physics · mapped topic

• G06F17/30336 Primary

  Physics · mapped topic