MERGING INDEX NODES OF A HIERARCHICAL DISPERSED STORAGE INDEX

• US 20130232306A1
• Filed: 02/25/2013
• Published: 09/05/2013
• 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.
• Granted Patent: US 9,171,031 B2
• Time in Patent Office: Days
• US Class Current: 711/154
• 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 merge two data object level index nodes and merging the two nodes into a temporarily merged data object level index node. The method continues with the DS processing module initiating updating of a hierarchical ordered index structure by identifying an address for storing the temporarily merged data object level index node, setting up deletion of the two data object level index nodes, setting up linking the temporarily merged data object level index node to a next level node of the hierarchical ordered index structure, and determining whether a change has occurred to at least one of one or more of the two data object level index nodes and the next level node. When the change has not occurred, the method continues with the DS processing module 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 (DSN) that stores a plurality of data objects, the method comprises:

determining to merge two data object level index nodes, 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 two data object level index nodes; and

when the two data object level index nodes are to be merged, entering a loop that includes;

merging the two data object level index nodes into a temporarily merged data object level index node;

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

identifying a DSN address for storing the temporarily merged data object level index node;

setting up deletion of the two data object level index nodes;

setting up linking the temporarily merged data object level index node to a next level node of the hierarchical ordered index structure; and

determining, subsequent to merging the two data object level index nodes, whether a change has occurred to at least one of;

one or more of the two data object level index nodes; and

the next level node; and

when the change has not occurred, 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 initiating updating of the hierarchical ordered index structure comprises:

setting up linking the temporarily merged data object level index node to one or more adjacent data object level nodes of the hierarchical ordered index structure; and

determining, subsequent to merging the two data object level index nodes, whether the change has occurred to the one or more adjacent data object level nodes.

3. The method of claim 2 further comprises:

setting up the linking the temporarily merged data object level index node to the one or more adjacent data object level nodes by;

obtaining the DSN address for storing the temporarily merged data object level index node; and

requesting updating an entry of each of the one or more adjacent data object level nodes by overwriting a DSN address for one of the two data object level index nodes with the DSN address for storing the temporarily merged data object level index node.

4. The method of claim 1, wherein the setting up deletion of the two data object level index nodes comprises:

identifying a first set of DSN storage nodes storing a first set of encoded index slices for a first one of the two data object level index nodes;

identifying a second set of DSN storage nodes storing a second set of encoded index slices for a second one of the two data object level index nodes;

sending a first set of deletion commands to the first set of DSN storage nodes; and

sending a second set of deletion commands to the second set of DSN storage nodes.

5. The method of claim 4, wherein the determining whether the change has occurred to the one or more of the two data object level index nodes comprises at least one of:

receiving a first revision level discrepancy response from one or more of the first set of DSN storage nodes to indicate that a first one of the one or more of the two data object level index nodes has changed; and

receiving a second revision level discrepancy response from one or more of the second set of DSN storage nodes to indicate that a second one of the one or more of the two data object level index nodes has changed.

6. The method of claim 1, wherein the setting up linking the temporarily merged data object level index node to the next level node comprises:

obtaining the DSN address for storing the temporarily merged data object level index node;

identifying a first entry of the next level node corresponding to a first one of the two data object level index nodes;

identifying a second entry of the next level node corresponding to a second one of the two data object level index nodes;

requesting updating the first entry of the next level node by overwriting a DSN address of the first one of the two data object level index nodes with the DSN address for storing the temporarily merged data object level index node; and

requesting deleting of the second entry.

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

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

issuing a set of write commands to store the set of encoded merged index slices at the DSN address for storing the temporarily merged data object level index node;

issuing a first set of delete commands to a first set of DSN storage nodes that is storing a first set of encoded index slices of a first one of the two data object level index nodes;

issuing a second set of delete commands to a second set of DSN storage nodes that is storing a second set of encoded index slices of a second one of the two data object level index nodes;

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

updating the reconstructed next level node to include the DSN address of the temporarily merged 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.

8. The method of claim 1, wherein the merging the two data object level index nodes comprises:

aggregating first data object index entries of a first one of the two data object level index nodes with second data object index entries of a second one of the two data object level index nodes to produce unsorted merged data object index entries;

sorting the unsorted merged data object index entries in accordance with the ordering of attributes of the attribute category to produce sorted merged data object index entries; and

generating an adjacent data object level index node reference based on one or more adjacent data object level index nodes of the two data object level index nodes.

9. The method of claim 1, wherein the determining to merge the two data object level index nodes comprises at least one of:

determining that at least one of the two data object level index nodes includes too few data object index entries;

determining that the at least one of the two data object level index nodes includes too few data object index entry accesses in a given time frame;

receiving a request;

determining that the hierarchical ordered index structure includes too many 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.

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

undoing the merging of the temporarily merged data object level index node; and

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

11. A dispersed storage (DS) module of a computing device of a multiple computing device dispersed storage network (DSN) 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 merge two data object level index nodes, 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 two data object level index nodes; and

a second module, when operable within the computing device and when the two data object level index nodes are to be merged, causes the computing device to enter a loop that causes the computing device to;

merge the two data object level index nodes into a temporarily merged data object level index node;

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

identify a DSN address for storing the temporarily merged data object level index node;

set up deletion of the two data object level index nodes;

set up linking the temporarily merged data object level index node to a next level node of the hierarchical ordered index structure; and

determine, subsequent to merging the two data object level index nodes, whether a change has occurred to at least one of;

one or more of the two data object level index nodes; and

the next level node; and

when the change has not occurred, commence the updating of the hierarchical ordered index structure; and

when the change has occurred, repeat the loop.

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

setting up linking the temporarily merged data object level index node to one or more adjacent data object level nodes of the hierarchical ordered index structure; and

determining, subsequent to merging the two data object level index nodes, whether the change has occurred to the one or more adjacent data object level nodes.

13. The DS module of claim 12 further comprises:

the second module further functions to set up the linking the temporarily merged data object level index node to the one or more adjacent data object level nodes by;

obtaining the DSN address for storing the temporarily merged data object level index node; and

requesting updating an entry of each of the one or more adjacent data object level nodes by overwriting a DSN address for one of the two data object level index nodes with the DSN address for storing the temporarily merged data object level index node.

14. The DS module of claim 11, wherein the second module functions to set up deletion of the two data object level index nodes by:

identifying a first set of DSN storage nodes storing a first set of encoded index slices for a first one of the two data object level index nodes;

identifying a second set of DSN storage nodes storing a second set of encoded index slices for a second one of the two data object level index nodes;

sending a first set of deletion commands to the first set of DSN storage nodes; and

sending a second set of deletion commands to the second set of DSN storage nodes.

15. The DS module of claim 14, wherein the second module functions to determine whether the change has occurred to the one or more of the two data object level index nodes by at least one of:

receiving a first revision level discrepancy response from one or more of the first set of DSN storage nodes to indicate that a first one of the one or more of the two data object level index nodes has changed; and

receiving a second revision level discrepancy response from one or more of the second set of DSN storage nodes to indicate that a second one of the one or more of the two data object level index nodes has changed.

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

obtaining the DSN address for storing the temporarily merged data object level index node;

identifying a first entry of the next level node corresponding to a first one of the two data object level index nodes;

identifying a second entry of the next level node corresponding to a second one of the two data object level index nodes;

requesting updating the first entry of the next level node by overwriting a DSN address of the first one of the two data object level index nodes with the DSN address for storing the temporarily merged data object level index node; and

requesting deleting of the second entry.

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

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

issuing a set of write commands to store the set of encoded merged index slices at the DSN address for storing the temporarily merged data object level index node;

issuing a first set of delete commands to a first set of DSN storage nodes that is storing a first set of encoded index slices of a first one of the two data object level index nodes;

issuing a second set of delete commands to a second set of DSN storage nodes that is storing a second set of encoded index slices of a second one of the two data object level index nodes;

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

updating the reconstructed next level node to include the DSN address of the temporarily merged 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.

18. The DS module of claim 11, wherein the second module functions to merge the two data object level index nodes by:

aggregating first data object index entries of a first one of the two data object level index nodes with second data object index entries of a second one of the two data object level index nodes to produce unsorted merged data object index entries;

sorting the unsorted merged data object index entries in accordance with the ordering of attributes of the attribute category to produce sorted merged data object index entries; and

generating an adjacent data object level index node reference based on one or more adjacent data object level index nodes of the two data object level index nodes.

19. The DS module of claim 11, wherein the first module functions to determine to merge the two data object level index nodes by at least one of:

determining that at least one of the two data object level index nodes includes too few data object index entries;

determining that the at least one of the two data object level index nodes includes too few data object index entry accesses in a given time frame;

receiving a request;

determining that the hierarchical ordered index structure includes too many 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.

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

undoing the merging of the temporarily merged data object level index node; and

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