RETRIEVING DATA UTILIZING A DISTRIBUTED INDEX

• US 20160328412A1
• Filed: 07/18/2016
• Published: 11/10/2016
• Est. Priority Date: 01/31/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Dhuse, Greg, Leggette, Wesley, Gray, Adam Michael, Volvovski, Ilya, Baptist, Andrew
• Granted Patent: US 9,715,504 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• 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/119 Details of migration of file systems migration mechanisms in storage systems G06F3/0647
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method includes receiving a request to retrieve a data object. The method further includes identifying an index file based on the search attribute. The method further includes entering a loop that includes: determining an address for a current index file; retrieving encoded data slices based on the address; decoding the encoded data slices to reproduce the current index file; determining whether the current index file includes the address for the data object; when the current index file does not include the address for the data object: identifying the other index file based on the search attribute; and repeating the loop for the other index file; and when the current index file includes the address for the data object, exiting the loop. The method further includes retrieving encoded data slices based on the address. The method further includes decoding the encoded data slices to recapture the data object.

Claims

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

receiving a request to retrieve a data object, wherein the request includes a search attribute regarding the data object;

identifying an index file based on the search attribute;

entering a loop that includes;

determining a distributed storage network (DSN) address for a current index file, wherein the current index file is the index file or another index file;

retrieving a set of encoded data slices from a DSN based on the DSN address;

decoding the set of encoded data slices to reproduce the current index file;

determining whether the current index file includes the DSN address for the data object;

when the current index file does not include the DSN address for the data object;

identifying the other index file from a plurality of index files indexed by the current index file based on the search attribute; and

repeating the loop for the other index file; and

when the current index file includes the DSN address for the data object, exiting the loop;

retrieving a plurality of sets of encoded data slices based on the DSN address for the data object; and

decoding the plurality of sets of encoded data slices to recapture the data object.

2. The method of claim 1, wherein the identifying the index file comprises:

identifying the index file from one of a plurality of root index files based on the search attribute.

3. The method of claim 1, wherein the identifying the other index file comprises:

comparing the search attribute to an index key associated with the other index file; and

identifying the other index file when the comparing is favorable.

4. The method of claim 1, wherein the determining whether the current index file includes the DSN address comprises:

interpreting an index file type indicator of the current index file; and

when the index file indicator of the current index file is a leaf node, determining that the current index file includes the DSN address.

5. The method of claim 1, wherein the loop further comprises:

determining whether the current index file includes the data object; and

when the current index files include the data object;

exiting the loop; and

responding to the request with the data object from the current index file.

6. A dispersed storage (DS) module comprises:

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

receive a request to retrieve a data object, wherein the request includes a search attribute regarding the data object;

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

determine a dispersed storage network (DSN) address for an index file based on the search attribute;

retrieve a set of encoded index data slices from a DSN based on the DSN address; and

decode the set of encoded index data slices to reconstruct the index file, wherein the index file includes a plurality of DSN child index addresses regarding a plurality of child index files;

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

identify one of the plurality of child index files based on the search attribute;

retrieve a set of encoded child index data slices from the DSN based on one of the plurality of DSN child index addresses corresponding to the one of the plurality of child index files; and

decode the set of encoded child index data slices to reconstruct the one of the plurality of child index files; and

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

determine whether the one of the plurality of child index files includes a DSN address for the data object;

when the one of the plurality of child index files includes the DSN address for the data object, retrieve a plurality of sets of encoded data slices based on the DSN address for the data object; and

decode the plurality of sets of encoded data slices to recapture the data object.

7. The DS module of claim 6, wherein the second module functions to identify the one of the plurality of child index files by:

comparing the search attribute to an index key associated with the one of the plurality of child index files; and

identifying the one of the plurality of child index files when the comparing is favorable.

8. The DS module of claim 6, wherein the fourth module functions to determine whether the one of the plurality of child index files includes the DSN address by:

interpreting an index file type indicator of the one of the plurality child index files; and

when the index file indicator of the one of the plurality child index files is a leaf node, determining that the one of the plurality child index files includes the DSN address.

9. The DS module of claim 6 further comprises:

the fourth module further functions to;

determine whether the one of the plurality of child index files includes the data object; and

when the one of the plurality of child index files includes the data object, respond to the request with the data object from the one of the plurality child index files.

10. The DS module of claim 6 further comprises:

the fourth module further functions to, when the one of the plurality of child index files does not include the DSN address for the data object, enter a loop where the fourth module functions to;

identify, from the one of the plurality of child index files, one of another plurality of child index files based on the search attribute;

retrieve another set of encoded child data slices from the DSN based on one of another plurality of DSN child index addresses corresponding to the one of the other plurality of child index files;

decode the other set of encoded child data slices to reproduce the one of the other plurality of child index files;

determine whether the one of the other plurality of child index files includes the DSN address for the data object;

when the one of the other plurality child index files does not include the DSN address for the data object, repeat in accordance with the one of the other plurality child index files; and

when the one of the other plurality of child index files includes the DSN address for the data object, exit the loop.

11. A dispersed storage (DS) module comprises:

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

receive a request to retrieve a data object, wherein the request includes a search attribute regarding the data object;

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

identify an index file based on the search attribute;

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

enter a loop where the third module functions to;

determine a distributed storage network (DSN) address for a current index file, wherein the current index file is the index file or another index file;

retrieve a set of encoded data slices from a DSN based on the DSN address;

decode the set of encoded data slices to reproduce the current index file;

determine whether the current index file includes the DSN address for the data object;

when the current index file does not include the DSN address for the data object;

identify the other index file from a plurality of index files indexed by the current index file based on the search attribute; and

repeat the loop for the other index file; and

when the current index file includes the DSN address for the data object, exit the loop; and

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

retrieve a plurality of sets of encoded data slices based on the DSN address for the data object; and

decode the plurality of sets of encoded data slices to recapture the data object.

12. The DS module of claim 11, wherein the second module functions to identify the index file by:

identifying the index file from one of a plurality of root index files based on the search attribute.

13. The DS module of claim 11, wherein the third module functions to identify the other index file by:

comparing the search attribute to an index key associated with the other index file; and

identifying the other index file when the comparing is favorable.

14. The DS module of claim 11, wherein the third module functions to determine whether the current index file includes the DSN address by:

interpreting an index file type indicator of the current index file; and

when the index file indicator of the current index file is a leaf node, determining that the current index file includes the DSN address.

15. The DS module of claim 11, wherein the loop further comprises:

the third module further functions to;

determine whether the current index file includes the data object; and

when the current index files include the data object;

exit the loop; and

respond to the request with the data object from the current index file.