Retrieving data utilizing a distributed index

• US 9,507,786 B2
• Filed: 12/18/2012
• Issued: 11/29/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, Leggette, Wesley, Gray, Adam Michael, Volvovski, Ilya, Baptist, Andrew
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US13/718,961
• Publication Number:
  US 20130198226A1
• Time in Patent Office: 1,442 Days
• Field of Search: 707/769, 707/770, 707/741, 707/827
• 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 begins by a dispersed storage (DS) processing module receiving a request to retrieve a data object based on a search attribute. The method continues with the DS processing module retrieving and decoding a set of encoded index data slices to reconstruct an index file. The method continues with the DS processing module identifying a child index file, retrieving and decoding a set of encoded child index data slices to reconstruct the child index file, and determining whether the child index file includes a dispersed storage network (DSN) address for the data object. When the child index file includes the DSN address for the data object, the method continues with the DS processing module retrieving a plurality of sets of encoded data slices based on the DSN address and decoding the plurality of sets of 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;

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

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

decoding 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;

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

retrieving 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;

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

determining 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, 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 one of the plurality of child index files comprises:

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.

3. The method of claim 1, wherein the determining whether the one of the plurality of child index files includes the DSN address comprises:

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

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

4. The method of claim 1 further comprises:

determining 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, responding to the request with the data object from the one of the plurality of child index files.

5. The method of claim 1 further comprises:

when the one of the plurality of child index files does not include the DSN address for the data object, entering a loop that includes;

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

retrieving 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;

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

determining 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 of child index files does not include the DSN address for the data object, repeating in accordance with the one of the other plurality of child index files; and

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