SYSTEMS AND METHODS FOR SEARCHING A CLOUD-BASED DISTRIBUTED STORAGE RESOURCES USING A SET OF EXPANDABLE PROBES

• US 20120078948A1
• Filed: 09/29/2010
• Published: 03/29/2012
• Est. Priority Date: 09/29/2010
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: Darcy, Jeffrey
• Granted Patent: US 9,298,732 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/134 Distributed indices
• CPC Class Codes: G06F 16/1824 implemented using Network-attached Storage [NAS] architecture distributed or networked storage systems G06F3/067; protocols for distributed storage of data in a network H04L67/1097

Abstract

Embodiments relate to systems and methods for searching a cloud-based file storage system using a set of expandable probes. Platforms and techniques are provided to search for a file whose location in cloud storage resources is recorded in a consistent hash ring structure. In a hash ring, a file name can generate a hash output corresponding to a position around a circle. The closest clockwise node to that location can contain the file itself, or a link to another location containing or leading to the file. When a link has become obsolete and no longer points to the file, it may be necessary to search for that file. Embodiments perform a graduated search for the missing file, starting one node from the original node, then trying two adjacent nodes, then four adjacent nodes and so forth in expanding fashion, until the file is found or the hash structure is exhausted.

Claims

1. A method of performing a search for a file stored in a cloud-based network, comprising:

a) initiating a search for the file based on a set of nodes in a hash structure storing file links, at a first starting node of the hash structure;

b) searching a first subset of nodes corresponding to an expandable set of probes spanning a first subset of the set of nodes, starting at the first starting node;

c) accessing the file if the file is found via a file link stored in the first subset of the set of nodes; and

d) if the file is not found in the first subset of the set of nodes—

identifying a second starting node in the hash structure,

expanding the expandable set of probes to span an additional subset of the set of nodes greater than the first subset, and

searching a second subset of nodes in the hash structure corresponding to the expandable set of probes, starting at the second starting node.

2. The method of claim 1, wherein the hash structure comprises a consistent hash ring.

3. The method of claim 1, wherein the first starting node comprises a node incremented by one position in the hash structure from an original node storing a last known valid link to the file.

4. The method of claim 1, wherein the second starting node comprises a node incremented by one position in the hash structure from a last node of the first subset of nodes.

5. The method of claim 1, further comprising repeating (d) if the file is not found.

6. The method of claim 5, further comprising terminating the repetition of (d) if a last node of the hash structure is reached without locating the file.

7. The method of claim 5, wherein the span of the expandable set of probes is at least doubled for each repetition of (d).

8. The method of claim 1, wherein the initiating a search comprises initiating a search after following a set of original links to the file stored in the hash structure fails to locate the file.

9. The method of claim 1, further comprising inserting a link in the set of file links to the file when located in the second subset of the set of nodes.

10. The method of claim 1, wherein the first subset of the set of nodes comprises one node.

11. A system for performing a search for a file stored in a cloud-based network comprising:

an interface to a set of storage resources in at least one cloud network; and

a processor, communicating with the set of storage resources in the at least one cloud network via the interface, the processor being configured to—

initiate a search for the file based on a set of nodes in a hash structure storing file links to locations in the set of storage resources, at a first starting node of the hash structure,

search a first subset of nodes corresponding to an expandable set of probes spanning a first subset of the set of nodes, starting at the first starting node,

access the file if the file is found via a file link stored in the first subset of the set of nodes, and

if the file is not found in the first subset of the set of nodes—

identify a second starting node in the hash structure,

expand the expandable set of probes to span an additional subset of the set of nodes greater than the first subset, and

searching a second subset of nodes in the hash structure corresponding to the expandable set of probes, starting at the second starting node.

12. The system of claim 11, wherein the hash structure comprises a consistent hash ring.

13. The system of claim 11, wherein the first starting node comprises a node incremented by one position in the hash structure from an original node storing a last known valid link to the file.

14. The system of claim 11, wherein the second starting node comprises a node incremented by one position in the hash structure from a last node of the first subset of nodes.

15. The system of claim 11, wherein the processor is further configured to repeat (d) if the file is not found.

16. The system of claim 15, wherein the process is further configured to terminate the repetition of (d) if a last node of the hash structure is reached without locating the file.

17. The system of claim 15, wherein the span of the expandable set of probes is at least doubled for each repetition of (d).

18. The system of claim 11, wherein the initiating a search comprises initiating a search after following a set of original links to the file stored in the hash structure fails to locate the file.

19. The system of claim 11, wherein the processor is further configured to insert a link in the set of file links to the file when located in the second subset of the set of nodes.

20. The system of claim 11, wherein the first subset of the set of nodes comprises one node.