Expanding a hierarchical dispersed storage index

• US 8,935,256 B2
• Filed: 02/25/2013
• Issued: 01/13/2015
• Est. Priority Date: 03/02/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Leggette, Wesley, Gray, Adam Michael, Volvovski, Ilya, Baptist, Andrew, Resch, Jason K.
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US13/775,769
• Publication Number:
  US 20130275480A1
• Time in Patent Office: 687 Days
• Field of Search: 707/741, 707/746, 707/797
• US Class Current: 707/741
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method begins by a dispersed storage (DS) processing module determining to expand a hierarchical ordered index structure and retrieving a root index node. The method continues with the DS processing module identifying immediate children index nodes, dividing the immediate children index nodes into sets of children index nodes, creating, for each of the sets of children index nodes, a sub-root index node to produce a set of sub-root index nodes, creating a new root index node to include entries for each of the sub-root index nodes of the set of sub-root index nodes, and temporarily storing the new root index node and the set of sub-root index nodes in a dispersed storage network (DSN). When the root index node has not changed, the method continues with the DS processing module updating the hierarchical ordered index structure with the new root index node and the set of sub-root index nodes.

Claims

1. A method for execution by a processing module of a computer of a multiple computer dispersed storage network (MCDSN) that stores a plurality of data objects, the method comprises:

determining to expand a hierarchical ordered index structure of a plurality of data object index entries, wherein the hierarchical ordered index structure is in accordance with an ordering of attributes of an attribute category, and wherein the plurality of data object index entries is stored in a multitude of data object level index nodes and is associated with the plurality of data objects; and

when the hierarchical ordered index structure is to be expanded, entering a loop that includes;

retrieving a root index node of the hierarchical ordered index structure from a set of MCDSN storage servers of the MCDSN;

identifying immediate children index nodes of the root index node from entries of the root index node;

dividing the immediate children index nodes into sets of children index nodes;

creating, for each of the sets of children index nodes, a sub-root index node to produce a set of sub-root index nodes, wherein the sub-root index node includes entries for each child index node of the set of children index nodes;

creating a new root index node to include entries for each of the sub-root index nodes of the set of sub-root index nodes;

temporarily storing the new root index node and the set of sub-root index nodes in the MCDSN;

when the root index node has not changed, updating the hierarchical ordered index structure with the new root index node and the set of sub-root index nodes; and

when the root index node has changed, repeating the loop with the changed root index node being the root index node.

2. The method of claim 1, wherein the determining to expand the hierarchical ordered index structure comprises at least one of:

determining that the root index node includes too many entries of the immediate children index nodes;

determining that the root index node is being accessed too frequently in a given time frame;

receiving a request;

detecting that an access performance level of the hierarchical ordered index structure compares unfavorably to a desired access performance level threshold; and

determining an estimated growth rate of the hierarchical ordered index structure and expanding in accordance with the estimated growth rate.

3. The method of claim 1, wherein the immediate children index nodes comprise:

intermediate index nodes of the hierarchical ordered index structure, wherein the intermediate index nodes hierarchically lie between the root index node and the multitude of data object level index nodes.

4. The method of claim 1, wherein the immediate children index nodes comprise:

at least some of the multitude of data object level index nodes.

5. The method of claim 1, wherein the dividing the immediate children index nodes into the sets of children index nodes comprises:

determining a number of sets that the immediate children index nodes will be divided into; and

based on the number of sets and the ordering of attributes of the attribute category, dividing the immediate children index nodes into the sets of children index nodes.

6. The method of claim 1, wherein the creating the new root index node to include entries for each of the sub-root index nodes of the set of sub-root index nodes comprises:

creating a first entry for a first sub-root index node of the set of sub-root index nodes to include a first index key and a first MCDSN address; and

creating a second entry for a second sub-root index node of the set of sub-root index nodes to include a second index key and a second MCDSN address.

7. The method of claim 1 further comprises:

determining that the root index node has changed by utilizing a checked-write process of the MCDSN with respect to the root index node.

8. The method of claim 1 further comprises:

determining that the root index node has changed by;

re-retrieving the root index node to produce a re-retrieved root index node;

comparing the re-retrieved root index node with the root index node; and

when the re-retrieved root index node substantially matches the root index node, indicating that the root index node has not changed.

9. The method of claim 1, wherein the updating the hierarchical ordered index structure comprises:

utilizing a three-phase-commit write process to store the new root index node and the set of sub-root index nodes in the MCDSN, wherein, when the three-phase-commit write process is successfully executed, the hierarchical ordered index structure is updated.

10. The method of claim 1, wherein the repeating the loop comprises:

prior to repeating the loop;

deleting the temporary storage of the new root index node and the set of sub-root index nodes in the MCDSN; and

undoing;

the creating of the new root index node;

the creating of the set of sub-root index nodes; and

the dividing of the immediate children index nodes into the sets of children index nodes.

11. A dispersed storage (DS) module of a computing device of a multiple computing device dispersed storage network (MCDDSN) that stores a plurality of data objects, the DS module comprises:

a first module, when operable within the computing device, causes the computing device to;

determine to expand a hierarchical ordered index structure of a plurality of data object index entries, wherein the hierarchical ordered index structure is in accordance with an ordering of attributes of an attribute category, and wherein the plurality of data object index entries is stored in a multitude of data object level index nodes and is associated with the plurality of data objects; and

a second module, when operable within the computing device and when the hierarchical ordered index structure is to be expanded, causes the computing device to enter a loop that causes the computing device to;

retrieve a root index node of the hierarchical ordered index structure from a set of MCDDSN storage servers of the MCDDSN;

identify immediate children index nodes of the root index node from entries of the root index node;

dividing the immediate children index nodes into sets of children index nodes;

create, for each of the sets of children index nodes, a sub-root index node to produce a set of sub-root index nodes, wherein the sub-root index node includes entries for each child index node of the set of children index nodes;

create a new root index node to include entries for each of the sub-root index nodes of the set of sub-root index nodes;

temporarily store the new root index node and the set of sub-root index nodes in the MCDDSN;

when the root index node has not changed, update the hierarchical ordered index structure with the new root index node and the set of sub-root index nodes; and

when the root index node has changed, repeat the loop with the changed root index node being the root index node.

12. The DS module of claim 11, wherein the first module functions to determine to expand the hierarchical ordered index structure by at least one of:

determining that the root index node includes too many entries of the immediate children index nodes;

determining that the root index node is being accessed too frequently in a given time frame;

receiving a request;

detecting that an access performance level of the hierarchical ordered index structure compares unfavorably to a desired access performance level threshold; and

determining an estimated growth rate of the hierarchical ordered index structure and expanding in accordance with the estimated growth rate.

13. The DS module of claim 11, wherein the immediate children index nodes comprise:

intermediate index nodes of the hierarchical ordered index structure, wherein the intermediate index nodes hierarchically lie between the root index node and the multitude of data object level index nodes.

14. The DS module of claim 11, wherein the immediate children index nodes comprise:

at least some of the multitude of data object level index nodes.

15. The DS module of claim 11, wherein the second module functions to divide the immediate children index nodes into the sets of children index nodes by:

determining a number of sets that the immediate children index nodes will be divided into; and

based on the number of sets and the ordering of attributes of the attribute category, dividing the immediate children index nodes into the sets of children index nodes.

16. The DS module of claim 11, wherein the second module functions to create the new root index node to include entries for each of the sub-root index nodes of the set of sub-root index nodes by:

creating a first entry for a first sub-root index node of the set of sub-root index nodes to include a first index key and a first MCDDSN address; and

creating a second entry for a second sub-root index node of the set of sub-root index nodes to include a second index key and a second MCDDSN address.

17. The DS module of claim 11 further comprises:

the second module further functions to determine that the root index node has changed by utilizing a checked-write process of the MCDDSN with respect to the root index node.

18. The DS module of claim 11 further comprises:

the second module further functions to determine that the root index node has changed by;

re-retrieving the root index node to produce a re-retrieved root index node;

comparing the re-retrieved root index node with the root index node; and

when the re-retrieved root index node substantially matches the root index node, indicating that the root index node has not changed.

19. The DS module of claim 11, wherein the second module functions to update the hierarchical ordered index structure by:

utilizing a three-phase-commit write process to store the new root index node and the set of sub-root index nodes in the MCDDSN, wherein, when the three-phase-commit write process is successfully executed, the hierarchical ordered index structure is updated.

20. The DS module of claim 11, wherein the second module functions to repeat the loop by:

prior to repeating the loop;

deleting the temporary storage of the new root index node and the set of sub-root index nodes in the MCDDSN; and

undoing;

the creating of the new root index node;

the creating of the set of sub-root index nodes; and

the dividing of the immediate children index nodes into the sets of children index nodes.