Retrieving indexed data from a dispersed storage network

• US 9,465,861 B2
• Filed: 07/16/2013
• Issued: 10/11/2016
• Est. Priority Date: 01/31/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg, Volvovski, Ilya, Gray, Adam Michael, Baptist, Andrew
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/943,352
• Publication Number:
  US 20130304746A1
• Time in Patent Office: 1,183 Days
• Field of Search: 707/741, 707/770
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 16/322 Trees

Abstract

A method begins by a dispersed storage (DS) processing module traversing multiple index structures based on search criteria to identify an object retrieval structure. The method continues with the DS processing module retrieving a set of encoded data slices corresponding to the object retrieval structure from a dispersed storage network (DSN) and decoding the set of encoded data slices in accordance with a dispersed storage error coding function to recover the object retrieval structure. The method continues with the DS processing module identifying one of one or more data version records of the recovered object retrieval structure based on the search criteria to produce an identified data version record and determining DSN addressing information for at least a portion of data based on information of the identified data version record.

Claims

1. A method for execution by one or more processing modules of one or more computing devices, the method comprises:

traversing multiple index structures based on search criteria to identify an object retrieval structure, wherein the object retrieval structure includes a data object section and data allocation table, wherein the data object section includes a data object name and one or more data index keys, and wherein the data allocation table includes one or more data version records, and wherein a data version record of the one or more data version records includes a data version identifier, one or more data version index keys, and one or more data portion records, wherein the identifying the object retrieval structure includes;

interpreting the search criteria to identify a set of search index keys;

traversing the multiple index structures based on the set of search index keys to identify sets of object retrieval structures; and

identifying a common object retrieval structure of the sets of object retrieval structures as the object retrieval structure when the one or more data index keys of the object retrieval structure corresponds to the set of search index keys;

retrieving a set of encoded data slices corresponding to the object retrieval structure from a dispersed storage network (DSN);

decoding the set of encoded data slices in accordance with a dispersed storage error coding function to recover the object retrieval structure;

identifying one of the one or more data version records of the recovered object retrieval structure based on the search criteria to produce an identified data version record; and

determining DSN addressing information for at least a portion of data based on information of the identified data version record.

2. The method of claim 1, wherein the traversing the multiple index structures comprises:

interpreting the search criteria to identify a set of search index keys;

for each search index key of the set of search index keys, identifying an index structure as one of the multiple index structures; and

traversing each index structure of the multiple index structures based on a corresponding one of the set of search index keys to identify the object retrieval structure.

3. The method of claim 1, wherein the retrieving the set of encoded data slices comprises:

determining DSN addresses for the set of encoded data slices; and

issuing retrieval requests for the set of encoded data slices, wherein the retrieval requests includes the DSN addresses.

4. The method of claim 1, wherein the identifying the one of the one or more data version records comprises:

interpreting the search criteria to identify a set of search index keys; and

identifying the one of the one or more data version records when the one or more data version index keys of the one of the one or more data version records corresponds to the set of search index keys.

5. The method of claim 1 further comprises:

the data version record including the data version identifier, the one or more data version index keys, and a plurality of data portion records, wherein a data portion record of the plurality of data portion records includes a data portion identifier and one or more data portion index keys;

interpreting the search criteria to identify a set of search index keys; and

identifying one of the plurality of data portion records when the one or more data portion index keys of the one of the plurality of data portion records corresponds to the set of search index keys, wherein the one of the plurality of data portion records references the portion of the data.

6. The method of claim 5, wherein the determining the DSN addressing information comprises:

interpreting the data portion identifier of the one of the plurality of data portion records to determine a source name for the portion of the data; and

converting the source name into the DSN addressing information.

7. The method of claim 1 further comprises:

traversing the multiple index structures based on the search criteria to identify a second object retrieval structure;

retrieving a second set of encoded data slices corresponding to the second object retrieval structure from the DSN;

decoding the second set of encoded data slices in accordance with the dispersed storage error coding function to recover the second object retrieval structure;

identifying a second data version record of the second recovered object retrieval structure based on the search criteria to produce a second identified data version record; and

determining second DSN addressing information for at least a portion of second data based on information of the second identified data version record.

8. The method of claim 1, wherein traversing one of the multiple index structures comprises:

requesting a set of root index slices from the DSN;

recovering a root index node of the one of the multiple index structures from the set of root index slices;

entering a loop, wherein the loop includes;

identifying a next index node of the one of the multiple index structures based on the search criteria from a current index node of the one of the multiple index structures, wherein the current index node is the root index node when the loop is entered;

requesting a set of next index slices from the DSN;

recovering the next index node from the set of next index slices;

determining whether the next index node is a leaf index node;

when the next index node is not the leaf index node, repeating the loop with the next index node being the current index node; and

when the next index node is the leaf index node, exiting the loop; and

identifying one or more object retrieval structures from the leaf index node based on the search criteria, wherein the one or more object retrieval structures includes the object retrieval structure.

9. A dispersed storage (DS) module comprises:

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

traverse multiple index structures based on search criteria to identify an object retrieval structure, wherein the object retrieval structure includes a data object section and data allocation table, wherein the data object section includes a data object name and one or more data index keys, and wherein the data allocation table includes one or more data version records, and wherein a data version record of the one or more data version records includes a data version identifier, one or more data version index keys, and one or more data portion records, wherein the identifying the object retrieval structure includes;

interpreting the search criteria to identify a set of search index keys;

traversing the multiple index structures based on the set of search index keys to identify sets of object retrieval structures; and

identifying a common object retrieval structure of the sets of object retrieval structures as the object retrieval structure when the one or more data index keys of the object retrieval structure corresponds to the set of search index keys;

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

retrieve a set of encoded data slices corresponding to the object retrieval structure from a dispersed storage network (DSN); and

decode the set of encoded data slices in accordance with a dispersed storage error coding function to recover the object retrieval structure;

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

identify one of the one or more data version records of the recovered object retrieval structure based on the search criteria to produce an identified data version record; and

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

determine DSN addressing information for at least a portion of data based on information of the identified data version record.

10. The DS module of claim 9, wherein the first module functions to traverse the multiple index structures by:

interpreting the search criteria to identify a set of search index keys;

for each search index key of the set of search index keys, identifying an index structure as one of the multiple index structures; and

traversing each index structure of the multiple index structures based on a corresponding one of the set of search index keys to identify the object retrieval structure.

11. The DS module of claim 9, wherein the second module functions to retrieve the set of encoded data slices by:

determining DSN addresses for the set of encoded data slices; and

issuing retrieval requests for the set of encoded data slices, wherein the retrieval requests includes the DSN addresses.

12. The DS module of claim 9, wherein the third module functions to identify the one of the one or more data version records by:

interpreting the search criteria to identify a set of search index keys; and

identifying the one of the one or more data version records when the one or more data version index keys of the one of the one or more data version records corresponds to the set of search index keys.

13. The DS module of claim 9 further comprises:

the data version record including the data version identifier, the one or more data version index keys, and a plurality of data portion records, wherein a data portion record of the plurality of data portion records includes a data portion identifier and one or more data portion index keys; and

the fourth module further functions to;

interpret the search criteria to identify a set of search index keys; and

identify one of the plurality of data portion records when the one or more data portion index keys of the one of the plurality of data portion records corresponds to the set of search index keys, wherein the one of the plurality of data portion records references the portion of the data.

14. The DS module of claim 13, wherein the fourth module functions to determine the DSN addressing information by:

interpreting the data portion identifier of the one of the plurality of data portion records to determine a source name for the portion of the data; and

converting the source name into the DSN addressing information.

15. The DS module of claim 9 further comprises:

the first module further functions to traverse the multiple index structures based on the search criteria to identify a second object retrieval structure;

the second module further functions to;

retrieve a second set of encoded data slices corresponding to the second object retrieval structure from the DSN; and

decoding the second set of encoded data slices in accordance with the dispersed storage error coding function to recover the second object retrieval structure;

the third module further functions to identify a second data version record of the second recovered object retrieval structure based on the search criteria to produce a second identified data version record; and

the fourth module further functions to determine second DSN addressing information for at least a portion of second data based on information of the second identified data version record.

16. The DS module of claim 9, wherein the first module further functions to traverse one of the multiple index structures by:

requesting a set of root index slices from the DSN;

recovering a root index node of the one of the multiple index structures from the set of root index slices;

entering a loop, wherein the loop includes;

identifying a next index node of the one of the multiple index structures based on the search criteria from a current index node of the one of the multiple index structures, wherein the current index node is the root index node when the loop is entered;

requesting a set of next index slices from the DSN;

recovering the next index node from the set of next index slices;

determining whether the next index node is a leaf index node;

when the next index node is not the leaf index node, repeating the loop with the next index node being the current index node; and

when the next index node is the leaf index node, exiting the loop; and

identifying one or more object retrieval structures from the leaf index node based on the search criteria, wherein the one or more object retrieval structures includes the object retrieval structure.