Searching cloud-based distributed storage resources using a set of expendable probes

Patent metadata

Field	Value
Publication number	US-9298732-B2
Application number	US-89373710-A
Country	US
Kind code	B2
Filing date	Sep 29, 2010
Priority date	Sep 29, 2010
Publication date	Mar 29, 2016
Grant date	Mar 29, 2016

Abstract

Embodiments relate to 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.

First claim

What is claimed is:

1. A method comprising:
initiating, by a processor of a centralized server of a cloud management system, a search for a file stored in a cloud-based network, the search based on a plurality of nodes in a hash structure storing a plurality of file links, wherein the search is initiated at a first starting node of the hash structure;
searching, by the processor of the cloud management system, a first subset of the plurality of nodes to find the file using a first iteration of an expandable set of probes spanning the first subset of the plurality of nodes, starting at the first starting node, wherein the searching the first subset of the plurality of nodes using the first iteration of the expandable set of probes comprises transmitting a respective probe to a respective target node of the first subset of the plurality of nodes to locate the file at the respective target node; and
upon not finding the file in the first subset of the plurality of nodes by the first iteration of the expandable set of probes, performing, by the processor of the cloud management system, an expanded search comprising:
expanding the expandable set of probes from a first number of probes in the first iteration to a second number of probes in a second iteration spanning a second subset of the plurality of nodes that is at least double the number of the first subset of the plurality of nodes, wherein the second number of probes in the expandable set of probes in the second iteration is based on a function applied to the first number of probes in the expandable set in the first iteration, and
searching, by the processor of the cloud management system, the second subset of the plurality of probes to find the file using the second iteration of the expandable set of probes spanning the second subset starting at a second starting node, wherein the searching the second subset of the plurality of nodes using the second iteration of the expandable set of probes comprises transmitting a first probe to a first target node of the second subset while concurrently transmitting a second probe to a second target node of the second subset to locate the file at the first target node or the second target node, wherein the second starting node is determined by incrementing by one position in the hash structure from a last node of the first subset of the plurality of nodes.

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 , further comprising repeating performing the expanded search if the file is not found.

5. The method of claim 4 , further comprising terminating the repetition of performing the expanded search if a last node of the hash structure is reached without locating the file.

6. The method of claim 4 , wherein the span of the expandable set of probes is at least doubled for each repetition of performing the expanded search.

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

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

9. The method of claim 1 , wherein the first subset of the plurality of nodes comprises one node.

10. The method of claim 1 , further comprising:
upon finding the file in the first subset of the plurality of nodes, accessing the file.

11. A system comprising:
an interface to a plurality of storage resources in at least one cloud network; and
a processor of a centralized server, to communicate with the plurality of storage resources in the at least one cloud network via the interface, the processor to:
initiate a search for a file based on a plurality of nodes in a hash structure storing a plurality of file links to a plurality of locations in the plurality of storage resources, at a first starting node of the hash structure,
search a first subset of the plurality of nodes to find the file using a first iteration of an expandable set of probes spanning the first subset of the plurality of nodes, starting at the first starting node, the processor to search the first subset is to transmit a respective probe to a respective target node of the first subset of the plurality of nodes to locate the file at the respective target node, and
upon not finding the file in the first subset of the plurality of nodes by the first iteration of the expandable set of probes, perform an expanded search, the expanded search comprising:
expanding the expandable set of probes from a first number of probes in the first iteration to a second number of probes in a second iteration spanning a second subset of the plurality of nodes that is at least double the number of the first subset of the plurality of nodes, wherein the second number of probes in the expandable set of probes in the second iteration is based on a function applied to the first number of probes in the expandable set in the first iteration, and
searching the second subset of the plurality of probes to find the file using the second iteration of the expandable set of probes spanning the second subset starting at a second starting node, wherein the searching the second subset of the plurality of nodes using the second iteration of the expandable set of probes comprises transmitting a first probe to a first target node of the second subset while concurrently transmitting a second probe to a second target node of the second subset to locate the file at the first target node or the second target node, wherein the second starting node is determined by incrementing by one position in the hash structure from a last node of the first subset of the plurality of nodes.

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 processor is further to repeat performing the expanded search if the file is not found.

15. The system of claim 14 , wherein the processor is further to terminate the repetition of performing the expanded search if a last node of the hash structure is reached without locating the file.

16. The system of claim 14 , wherein the span of the expandable set of probes is at least doubled for each repetition of performing the expanded search.

17. The system of claim 11 , wherein the processor is to initiate the search after following a plurality of original links to the file stored in the hash structure fails to locate the file.

18. The system of claim 11 , wherein the processor is further to insert a link in the plurality of file links to the file when located in the subset of the plurality of nodes.

19. The system of claim 11 , wherein the first subset of the plurality of nodes comprises one node.

20. A non-transitory computer readable storage medium having instructions that, when executed by a processor of a centralized server of a cloud management system, cause the processor to:
initiate, by the processor of the centralized server of the cloud management system, a search for a file store

Assignees

• Darcy Jeffrey
• Red Hat Inc

Inventors

• Darcy Jeffrey

Classifications

• G06F16/1824 Primary

  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) · CPC title

• G06F16/134

  Distributed indices · CPC title

• G06F17/30094

  Physics · mapped topic

• G06F17/30197 Primary

  Physics · mapped topic