LISTING DATA OBJECTS USING A HIERARCHICAL DISPERSED STORAGE INDEX

• US 20130232152A1
• 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
• Granted Patent: US 10,089,344 B2
• Time in Patent Office: Days
• 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 receiving a request for a data index list that identifies data objects having one or more common attributes, searching a hierarchical ordered index structure to identify a data object level index node corresponding to a first data object boundary match, and determining whether the data object level index node corresponds to a second data object boundary match. When the data object level index node does not correspond to the second data object boundary match, the method continues with the DS processing module searching an adjacent data object level index node to determine whether the adjacent data object level index node corresponds to the second data object boundary match. When the adjacent data object level index node corresponds to the second data object boundary match, the method continues with the DS processing module generating the data index list.

Claims

1. A method for execution by a processing module of a computer, the method comprises:

receiving, via an interface of the computer, a request for a data index list that identifies data objects having one or more common attributes of an attribute category, wherein indexing of a plurality of data objects is organized in accordance with an ordering of attributes of the attribute category and wherein the plurality of data objects is stored in a dispersed storage network (DSN);

searching, by the processing module and based on the one or more common attributes, a hierarchical ordered index structure that maps the indexing of the plurality of data objects to identify a data object level index node of the hierarchical ordered index structure that includes a first boundary data object index key corresponding to a first data object boundary match of the one or more common attributes;

determining, by the processing module, whether the data object level index node includes a second boundary data object index key corresponding to a second data object boundary match of the one or more common attributes;

when the data object level index node does not include the second boundary data object index key, searching, by the processing module, an adjacent data object level index node of the hierarchical ordered index structure to determine whether the adjacent data object level index node includes the second boundary data object index key;

when the adjacent data object level index node includes the second boundary data object index key, generating, by the processing module, the data index list to include the first boundary data object index key, a first ordered set of data object index keys of the data object level index node, the second boundary data object index key, and a second ordered set of data object index keys of the adjacent data object level index node; and

outputting, via the interface, the data index list.

2. The method of claim 1, wherein the generating the data index list further comprises:

determining DSN addresses corresponding to data object index keys of the data index list; and

adding the DSN addresses to the data index list.

3. The method of claim 1 further comprises:

receiving, via the interface, a read request regarding a data object identified in the data index list;

determining, by the processing module, a DSN address for the data object;

identifying, by the processing module, a set of dispersed storage (DS) servers based on the DSN address; and

sending, via the interface, a set of read requests to the set of DS servers to retrieve a set of data slices, wherein a data segment of the data object is stored as the set of data slices in the set of DS servers.

4. The method of claim 1, wherein the searching the hierarchical ordered index structure comprises:

identifying a category index node based on the request;

retrieving, via the interface, a set of category index slices from the DSN;

reconstructing a category index file from the set of category index slices;

interpreting the category index file based on the one or more common attributes to identify a next level index node; and

when the next level index node is not the data object level index node, entering a loop that includes;

retrieving, via the interface, a set of next level index slices from the DSN;

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

interpreting the next index file based on the one or more common attributes to identify a new next level index node;

determining whether the new next level index node is the data object level index node;

when the new next level index node is the data object level index node, exiting the loop; and

when the new next level index node is not the data object level index node, repeating the loop with the new next level index node as the next level index node.

5. The method of claim 1 further comprises:

identifying, by the processing module, the first data object boundary match of the one or more common attributes by identifying a first one of a plurality of index keys associated with the data object level index node that includes an indication that substantially matches the one or more common attributes, wherein the plurality of index keys are sequentially ordered in accordance with indicators corresponding to attributes of the attribute category.

6. The method of claim 1 further comprises:

when the data object level index node includes the second boundary data object index key, generating, by the processing module, the data index list to include the first boundary data object index key, the second boundary data object index key, and an ordered set of data object index keys between the first and second boundary data object index keys.

7. The method of claim 1 further comprises:

when the adjacent data object level index node does not include the second boundary data object index key, entering a loop that includes;

searching, by the processing module, a next adjacent data object level index node of the hierarchical ordered index structure to determine whether the next adjacent data object level index node includes the second boundary data object index key;

when the next adjacent data object level index node includes the second boundary data object index key, exiting the loop and generating, by the processing module, the data index list; and

when the next adjacent data object level index node does not include the second boundary data object index key, repeating the loop using a second next adjacent data object level index node as the next adjacent data object level index node.

8. The method of claim 1, wherein the indexing of the plurality of data objects comprises:

a corresponding plurality of data object index keys that is ordered in accordance with the ordering of attributes of the attribute category, wherein a data object index key of the plurality of corresponding data object index keys uniquely identifies one of the plurality of data objects in accordance with the attribute category.

9. A dispersed storage (DS) module of a computing device, the DS module comprises:

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

receive, via an interface of the computing device, a request for a data index list that identifies data objects having one or more common attributes of an attribute category, wherein indexing of a plurality of data objects is organized in accordance with an ordering of attributes of the attribute category and wherein the plurality of data objects is stored in a dispersed storage network (DSN);

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

search, based on the one or more common attributes, a hierarchical ordered index structure that maps the indexing of the plurality of data objects to identify a data object level index node of the hierarchical ordered index structure that includes a first boundary data object index key corresponding to a first data object boundary match of the one or more common attributes;

determine whether the data object level index node includes a second boundary data object index key corresponding to a second data object boundary match of the one or more common attributes; and

when the data object level index node does not include the second boundary data object index key, search an adjacent data object level index node of the hierarchical ordered index structure to determine whether the adjacent data object level index node includes the second boundary data object index key; and

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

when the adjacent data object level index node includes the second boundary data object index key, generate the data index list to include the first boundary data object index key, a first ordered set of data object index keys of the data object level index node, the second boundary data object index key, and a second ordered set of data object index keys of the adjacent data object level index node; and

output, via the interface, the data index list.

10. The DS module of claim 9, wherein the third module further functions to generate the data index list by:

determining DSN addresses corresponding to data object index keys of the data index list; and

adding the DSN addresses to the data index list.

11. The DS module of claim 9 further comprises:

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

receive, via the interface, a read request regarding a data object identified in the data index list;

determine a DSN address for the data object;

identify a set of dispersed storage (DS) servers based on the DSN address; and

send, via the interface, a set of read requests to the set of DS servers to retrieve a set of data slices, wherein a data segment of the data object is stored as the set of data slices in the set of DS servers.

12. The DS module of claim 9, wherein the second module functions to search the hierarchical ordered index structure by:

identifying a category index node based on the request;

retrieving a set of category index slices from the DSN;

reconstructing a category index file from the set of category index slices;

interpreting the category index file based on the one or more common attributes to identify a next level index node; and

when the next level index node is not the data object level index node, entering a loop that includes;

retrieving a set of next level index slices from the DSN;

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

interpreting the next index file based on the one or more common attributes to identify a new next level index node;

determining whether the new next level index node is the data object level index node;

when the new next level index node is the data object level index node, exiting the loop; and

when the new next level index node is not the data object level index node, repeating the loop with the new next level index node as the next level index node.

13. The DS module of claim 9 further comprises:

the second module further functions to;

identify the first data object boundary match of the one or more common attributes by identifying a first one of a plurality of index keys associated with the data object level index node that includes an indication that substantially matches the one or more common attributes, wherein the plurality of index keys are sequentially ordered in accordance with indicators corresponding to attributes of the attribute category.

14. The DS module of claim 9 further comprises:

the third module further functions to;

when the data object level index node includes the second boundary data object index key, generate the data index list to include the first boundary data object index key, the second boundary data object index key, and an ordered set of data object index keys between the first and second boundary data object index keys.

15. The DS module of claim 9 further comprises:

the second module further functions to;

when the adjacent data object level index node does not include the second boundary data object index key, enter a loop to;

search a next adjacent data object level index node of the hierarchical ordered index structure to determine whether the next adjacent data object level index node includes the second boundary data object index key;

when the next adjacent data object level index node includes the second boundary data object index key, exit the loop and generate the data index list; and

when the next adjacent data object level index node does not include the second boundary data object index key, repeat the loop using a second next adjacent data object level index node as the next adjacent data object level index node.

16. The DS module of claim 9, wherein the indexing of the plurality of data objects comprises:

a corresponding plurality of data object index keys that is ordered in accordance with the ordering of attributes of the attribute category, wherein a data object index key of the plurality of corresponding data object index keys uniquely identifies one of the plurality of data objects in accordance with the attribute category.