Splitting an index node of a hierarchical dispersed storage index

• US 8,930,375 B2
• Filed: 02/25/2013
• Issued: 01/06/2015
• Est. Priority Date: 03/02/2012
• Status: Active Grant

• 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,734
• Publication Number:
  US 20130238630A1
• Time in Patent Office: 680 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 remove data object index entries from a data object level index node, identifying data object index entries to extract, and creating a temporary sibling data object level index node to include the identified data object index entries. The method continues with the DS processing module initiating updating of an hierarchical ordered index structure by identifying an address for storing the temporary sibling data object level index node, setting up linking the temporary sibling data object level index node to a next level node and to an adjacent data object level index node, and determining whether a change has occurred. When the change has not occurred, the method continues with the DS processing module removing the data object index entries from the data object level index node and commencing the updating of the hierarchical ordered index structure.

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 remove data object index entries from a data object level index node, wherein a plurality of data object index entries is associated with the plurality of data objects, wherein the plurality of data object index entries is organized into a hierarchical ordered index structure in accordance with an ordering of attributes of an attribute category, wherein the hierarchical ordered index structure includes the data object level index node; and

when the data object index entries of the data object level index node are to be removed, entering a loop that includes;

identifying the data object index entries of the data object level index node to extract;

creating a temporary sibling data object level index node to include the identified extracted data object index entries;

initiating updating of the hierarchical ordered index structure, wherein the initiating includes;

identifying a MCDSN address for storing the temporary sibling data object level index node;

setting up linking the temporary sibling data object level index node to a next level node of the hierarchical ordered index structure;

setting up linking the temporary sibling data object level index node to the data object level index node and to an adjacent data object level index node; and

prior to removing the data object index entries from the data object level index node, determining whether a change has occurred to at least one of;

the data object level index node;

the adjacent data object level index node; and

the next level node; and

when the change has not occurred;

removing the data object index entries from the data object level index node; and

commencing the updating of the hierarchical ordered index structure; and

when the change has occurred, repeating the loop.

2. The method of claim 1, wherein the removing the data object index entries from the data object level index node comprises:

dispersed storage error decoding a set of encoded data object index slices to recapture the data object level index node;

deleting the data object index entries from the recaptured data object level index node to produce a reduced data object level index node;

updating an adjacent data object level index node identifier of the reduced data object level index node to identify the temporary sibling data object level index node to produce an updated data object level index node;

dispersed storage error encoding the updated data object level index node to produce a set of encoded updated data object index slices; and

issuing a set of checked-write commands to store the set of encoded updated data object index slices in the MCDSN.

3. The method of claim 1, wherein the determining whether the change has occurred to the data object level index node comprises:

receiving a revision level discrepancy response from at least one of a set of MCDSN storage nodes to indicate that the data object level index node has changed.

4. The method of claim 1, wherein the setting up linking the temporary sibling data object level index node to the next level node comprises:

obtaining the MCDSN address for storing the temporary sibling data object level index node;

generating a new child node entry corresponding to the temporary sibling data object level index node that includes the MCDSN address for storing the temporary sibling data object level index node; and

requesting updating the next level node to include the new child node entry.

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

dispersed storage error encoding the temporary sibling data object level index node to produce a set of encoded sibling index slices;

issuing a set of write commands to store the set of encoded sibling index slices at the MCDSN address for storing the temporary sibling data object level index node;

reconstructing the next level node from a set of next level index slices;

updating the reconstructed next level node to include an identifier to identify the temporary sibling data object level index node to produce an updated next level node; and

dispersed storage error encoding the updated next level node to produce a set of updated next level index slices.

6. The method of claim 1, wherein the determining to remove the data object index entries from the data object level index node comprises at least one of:

determining that the data object level index node includes too many data object index entries;

determining that the data object level index node includes too many data object index entry accesses in a given time frame;

receiving a request;

determining that the hierarchical ordered index structure includes too few data object level index nodes; and

detecting that an access performance level of the hierarchical ordered index structure compares unfavorably to a minimum access performance level threshold.

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

undoing the initiating of the updating of the hierarchical ordered index structure using a checked write MCDSN process.

8. 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 remove data object index entries from a data object level index node, wherein a plurality of data object index entries is associated with the plurality of data objects, wherein the plurality of data object index entries is organized into a hierarchical ordered index structure in accordance with an ordering of attributes of an attribute category, wherein the hierarchical ordered index structure includes the data object level index node; and

a second module, when operable within the computing device and when the data object index entries of the data object level index node are to be removed, causes the computing device to enter a loop that causes the computing device to;

identify the data object index entries of the data object level index node to extract;

create a temporary sibling data object level index node to include the identified extracted data object index entries;

initiate updating of the hierarchical ordered index structure, wherein the initiating causes the computing device to;

identify a MCDDSN address for storing the temporary sibling data object level index node;

set up linking the temporary sibling data object level index node to a next level node of the hierarchical ordered index structure;

set up linking the temporary sibling data object level index node to the data object level index node and to an adjacent data object level index node; and

prior to removing the data object index entries from the data object level index node, determine whether a change has occurred to at least one of;

the data object level index node;

the adjacent data object level index node; and

the next level node; and

when the change has not occurred;

remove the data object index entries from the data object level index node; and

commence the updating of the hierarchical ordered index structure; and

when the change has occurred, repeat the loop.

9. The DS module of claim 8, wherein the second module functions to remove the data object index entries from the data object level index node by:

dispersed storage error decoding a set of encoded data object index slices to recapture the data object level index node;

deleting the data object index entries from the recaptured data object level index node to produce a reduced data object level index node;

updating an adjacent data object level index node identifier of the reduced data object level index node to identify the temporary sibling data object level index node to produce an updated data object level index node;

dispersed storage error encoding the updated data object level index node to produce a set of encoded updated data object index slices; and

issuing a set of checked-write commands to store the set of encoded updated data object index slices in the MCDDSN.

10. The DS module of claim 8, wherein the second module functions to determine whether the change has occurred to the data object level index node by:

receiving a revision level discrepancy response from at least one of a set of MCDDSN storage nodes to indicate that the data object level index node has changed.

11. The DS module of claim 8, wherein the second module functions to set up linking the temporary sibling data object level index node to the next level node by:

obtaining the MCDDSN address for storing the temporary sibling data object level index node;

generating a new child node entry corresponding to the temporary sibling data object level index node that includes the MCDDSN address for storing the temporary sibling data object level index node; and

requesting updating the next level node to include the new child node entry.

12. The DS module of claim 8, wherein the second module functions to commence the updating of the hierarchical ordered index structure by:

dispersed storage error encoding the temporary sibling data object level index node to produce a set of encoded sibling index slices;

issuing a set of write commands to store the set of encoded sibling index slices at the MCDDSN address for storing the temporary sibling data object level index node;

reconstructing the next level node from a set of next level index slices;

updating the reconstructed next level node to include an identifier to identify the temporary sibling data object level index node to produce an updated next level node; and

dispersed storage error encoding the updated next level node to produce a set of updated next level index slices.

13. The DS module of claim 8, wherein the first module functions to determine to remove the data object index entries from the data object level index node by at least one of:

determining that the data object level index node includes too many data object index entries;

determining that the data object level index node includes too many data object index entry accesses in a given time frame;

receiving a request;

determining that the hierarchical ordered index structure includes too few data object level index nodes; and

detecting that an access performance level of the hierarchical ordered index structure compares unfavorably to a minimum access performance level threshold.

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

undoing the initiating of the updating of the hierarchical ordered index structure using a checked write MCDDSN process.