ALLOCATING DELEGATES FOR MODIFICATION OF AN INDEX STRUCTURE
A method to assign delegate devices for updating a hierarchical index structure includes determining a number of delegate devices to assign for updating the hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure. The method further includes determining a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices. The method further includes, for the node layer, assigning each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof. The method further includes generating a list of delegate device responsibilities based on the assigning.
1 . A method for a computing device to assign delegate devices for updating a hierarchical index structure that is usable for identifying data stored in memory of a dispersed storage network (DSN), the method comprises:
determining a number of delegate devices to assign for updating the hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure;
identifying a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices;
for the node layer, assigning each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof; and
generating a list of delegate device responsibilities based on the assigning.
2 . The method of claim 1 , wherein a delegate device of the number of delegate devices comprises one or more of:
a computing device of the DSN;
a managing unit of the DSN;
a storage unit of the memory of the DSN;
an index update module; and
an integrity unit of the DSN.
3 . The method of claim 1 , wherein the determining the number of delegate devices comprises one or more of:
accessing a list of devices of the DSN designated as the delegate devices;
implementing a query and response protocol with a plurality of devices of the DSN; and
receiving a message that identifies the number of delegate devices.
4 . The method of claim 1 , wherein the determining the number of delegate devices comprises:
determining a size of the hierarchical index structure;
determining a use volume of the hierarchical index structure; and
determining the number of delegate devices based on the size and use volume of the hierarchical index structure.
5 . The method of claim 1 further comprises:
sending the list of delegate device responsibilities to one or more of: devices of the DSN and the delegate devices.
6 . The method of claim 1 , wherein the assigning comprises:
when the number of nodes in the node layer equals the number of delegate devices:
assigning a first delegate device of the number of delegate devices to a first node of the number of nodes; and
assigning a second delegate device of the number of delegate devices to a second node of the number of nodes.
7 . The method of claim 1 , wherein the assigning comprises:
when the number of nodes in the node layer is greater than the number of delegate devices:
identifying additional delegate devices to increase the number of delegate devices to substantially match the number of nodes to produce an updated number of delegate devices;
assigning a first delegate device of the updated number of delegate devices to a first node of the number of nodes; and
assigning a second delegate device of the updated number of delegate devices to a second node of the number of nodes.
8 . The method of claim 1 , wherein the assigning comprises:
when the number of nodes in the node layer is greater than the number of delegate devices:
identifying a first delegate device of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices;
assigning each delegate device of the other delegate devices one node of the number of nodes; and
assigning the first delegate device at least two nodes of remaining nodes of the number of nodes, wherein the remaining nodes corresponds to a total number of nodes in the number of nodes less a number of nodes individually assigned to the other delegate devices.
9 . The method of claim 1 further comprises:
determining that a new node is added to the number of nodes of the node layer;
determining whether to assign the new node to one of the number of delegate devices or to add a new delegate device to the number of delegate devices;
when determined to assign the new node to one of the number of delegate devices, selecting the one of the number of delegate devices based on the one of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices; and
when determined to add the new delegate device, selecting a device of the DSN to function as the new delegate device and assigning the new node to the new delegate device.
10 . A computing device of a dispersed storage network (DSN) comprises:
a network interface;
memory; and
a processing module operably coupled to the network interface and the memory, wherein the processing module is operable to:
determine a number of delegate devices to assign for updating a hierarchical index structure, wherein the hierarchical index structure is a self-balancing structure;
identify a node layer of the hierarchical index structure that has at least an equivalent number of nodes as the number of delegate devices;
for the node layer, assign each delegate device of the number of delegate devices a unique one or more nodes of the node layer and corresponding child nodes thereof; and
generate a list of delegate device responsibilities based on the assigning.
11 . The computing device of claim 10 , wherein a delegate device of the number of delegate devices comprises one or more of:
a computing device of the DSN;
a managing unit of the DSN;
a storage unit of the memory of the DSN;
an index update module; and
an integrity unit of the DSN.
12 . The computing device of claim 10 , wherein the processing module is further operable to determine the number of delegate devices by one or more of:
accessing a list of devices of the DSN designated as the delegate devices;
implementing a query and response protocol with a plurality of devices of the DSN; and
receiving a message that identifies the number of delegate devices.
13 . The computing device of claim 10 , wherein the processing module is further operable to determine the number of delegate devices comprises:
determining a size of the hierarchical index structure;
determining a use volume of the hierarchical index structure; and
determining the number of delegate devices based on the size and use volume of the hierarchical index structure.
14 . The computing device of claim 10 , wherein the processing module is further operable to:
send, via the network interface, the list of delegate device responsibilities to one or more of: devices of the DSN and the delegate devices.
15 . The computing device of claim 10 , wherein the processing module is further operable to assign by:
when the number of nodes in the node layer equals the number of delegate devices:
assigning a first delegate device of the number of delegate devices to a first node of the number of nodes; and
assigning a second delegate device of the number of delegate devices to a second node of the number of nodes.
16 . The computing device of claim 10 , wherein the processing module is further operable to assign by:
when the number of nodes in the node layer is greater than the number of delegate devices:
identifying additional delegate devices to increase the number of delegate devices to substantially match the number of nodes to produce an updated number of delegate devices;
assigning a first delegate device of the updated number of delegate devices to a first node of the number of nodes; and
assigning a second delegate device of the updated number of delegate devices to a second node of the number of nodes.
17 . The computing device of claim 10 , wherein the processing module is further operable to assign by:
when the number of nodes in the node layer is greater than the number of delegate devices:
identifying a first delegate device of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices;
assigning each delegate device of the other delegate devices one node of the number of nodes; and
assigning the first delegate device at least two nodes of remaining nodes of the number of nodes, wherein the remaining nodes corresponds to a total number of nodes in the number of nodes less a number of nodes individually assigned to the other delegate devices.
18 . The computing device of claim 10 , wherein the processing module is further operable to:
determine that a new node is added to the number of nodes of the node layer;
determine whether to assign the new node to one of the number of delegate devices or to add a new delegate device to the number of delegate devices;
when determined to assign the new node to one of the number of delegate devices, select the one of the number of delegate devices based on the one of the number of delegate devices having a higher level of processing capabilities than other delegate devices of the number of delegate devices; and
when determined to add the new delegate device, select a device of the DSN to function as the new delegate device and assigning the new node to the new delegate device.