Utilizing a hierarchical index in a dispersed storage network

Patent metadata

Field	Value
Publication number	US-10855759-B2
Application number	US-201715397118-A
Country	US
Kind code	B2
Filing date	Jan 3, 2017
Priority date	Jan 26, 2016
Publication date	Dec 1, 2020
Grant date	Dec 1, 2020

Abstract

A method for execution by a dispersed storage and task (DST) processing unit includes generating contention level data by evaluating an update contention level in response to determining to update an entry of a node of a dispersed hierarchical index. The update of the node is executed when the contention level data indicates that the update contention level is favorable. An index update request is generated for transmission to an index update unit via a network when the contention level data indicates that the update contention level is unfavorable.

First claim

What is claimed is:

1. A method for execution by a dispersed storage and task (DST) processing unit that includes a processor, the method comprises:
generating contention level data by evaluating an update contention level in response to determining to update an entry of a node of a dispersed hierarchical index;
executing the update of the node when the contention level data indicates that the update contention level is favorable; and
generating an index update request for transmission to an index update unit via a network when the contention level data indicates that the update contention level is unfavorable.

2. The method of claim 1 , wherein the update contention level is evaluated by comparing the update contention level to an update contention threshold value.

3. The method of claim 1 , wherein the update contention level is calculated based on at least one update identifier associated with recent updating of at least one additional node of the dispersed hierarchical index.

4. The method of claim 1 , further comprising:
generating a request for index status for transmission to the index update unit via the network and receiving index status data of the node in response; and
calculating the update contention level based on the index status data.

5. The method of claim 4 , wherein index status data includes an index update rate, and wherein generating the contention level data includes comparing the index update rate to an index update rate threshold level.

6. The method of claim 1 , further comprising:
receiving an update request via the network that includes an identifier of the node;
wherein the contention level data is generated in response to receiving the update request.

7. The method of claim 1 , wherein the update includes at least one of: adding the node to the dispersed hierarchical index as a new node, deleting the node from the dispersed hierarchical index, or modifying an entry of the node.

8. The method of claim 1 , wherein executing the update includes:
generating a plurality of read requests for transmission via the network to a plurality of storage units and receiving an original plurality of encoded slices associated with the node in response;
generating a reproduced node by performing a decoding function on the original plurality of encoded slices;
updating an entry of the reproduced node;
generating an updated plurality of encoded slices by performing an encoding function on the reproduced node; and
generating a plurality of write requests that include the updated plurality of encoded slices for transmission to the plurality of storage units via the network.

9. The method of claim 1 , wherein the index update request includes at least one of: a new entry, an identifier the new entry, a node identifier, a requester identifier, a dispersed hierarchical index identifier, or an update type.

10. The method of claim 1 , wherein the index update unit prioritizes a plurality of index update requests in accordance with a prioritization approach.

11. The method of claim 1 , wherein update contention level is unfavorable, further comprising:
receiving via the network an update success response from the index update unit when the update is performed successfully; and
receiving via the network an update failure response from the index update unit when the update is not successful.

12. A processing system of a dispersed storage and task (DST) processing unit 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:
generate contention level data by evaluating an update contention level in response to determining to update an entry of a node of a dispersed hierarchical index;
execute the update of the node when the contention level data indicates that the update contention level is favorable; and
generate an index update request for transmission to an index update unit via a network when the contention level data indicates that the update contention level is unfavorable.

13. The processing system of claim 12 , wherein the update contention level is evaluated by comparing the update contention level to an update contention threshold value.

14. The processing system of claim 12 , wherein the operational instructions, when executed by the at least one processor, further cause the processing system to:
generate a request for index status for transmission to the index update unit via the network and receive index status data of the node in response; and
calculate the update contention level based on the index status data.

15. The processing system of claim 14 , wherein index status data includes an index update rate, and wherein generating the contention level data includes comparing the index update rate to an index update rate threshold level.

16. The processing system of claim 12 , wherein the update includes at least one of: adding the node to the dispersed hierarchical index as a new node, deleting the node from the dispersed hierarchical index, or modifying an entry of the node.

17. The processing system of claim 12 , wherein executing the update includes:
generating a plurality of read requests for transmission via the network to a plurality of storage units and receiving an original plurality of encoded slices associated with the node in response;
generating a reproduced node by performing a decoding function on the original plurality of encoded slices;
updating an entry of the reproduced node;
generating an updated plurality of encoded slices by performing an encoding function on the reproduced node; and
generating a plurality of write requests that include the updated plurality of encoded slices for transmission to the plurality of storage units via the network.

18. The processing system of claim 12 , wherein the index update request includes at least one of: a new entry, an identifier the new entry, a node identifier, a requester identifier, a dispersed hierarchical index identifier, or an update type.

19. The processing system of claim 12 , wherein update contention level is unfavorable, and wherein the operational instructions, when executed by the at least one processor, further cause the processing system to:
receive via the network an update success response from the index update unit when the update is performed successfully; and
receive via the network an update failure response from the index update unit when the update is not successful.

20. 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:
generate contention level data by evaluating an update contention level in response to determining to update an entry of a node of a dispersed hierarchical index;
execute the update of the node when the contention level data indicates that the update contention level is favorable; and
generate an index update request for transmission to an index update unit via a network when the contention level data indicates that the update contention level is unfavorable.

Assignees

• IBM
• Pure Storage Inc

Inventors

• Dhuse Greg R
• Gray Adam M
• Horan Scott M
• Khadiwala Ravi V
• Reid Tyler K
• Resch Jason K
• Scholl Daniel J
• Volvovski Ilya

Classifications

• H04L67/568

  Storing data temporarily at an intermediate stage, e.g. caching · CPC title

• H04L67/55

  Push-based network services · CPC title

• G06F3/0647

  Migration mechanisms · CPC title

• H03M13/3761

  using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes · CPC title

• G06F12/0813

  with a network or matrix configuration · CPC title