IP Library › Granted Patent US 7,680,950

Granted Patent B1

US 7,680,950 · App. 10/704,271 · Granted Mar 16, 2010

Efficient search for storage objects in a network

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 7,680,950
App. No.: 10/704,271
Granted: Mar 16, 2010
Kind: B1

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A system and method related to efficiently searching for an object in a network including a plurality of realms, e.g., a plurality of local area networks (LANs). The method may ensure that nodes within a LAN are able to locate objects within that LAN using only computing resources on the local LAN. Thus, expensive WAN transfers may be avoided where possible. The system may also scale to many nodes. Nodes may not be required to know about every other node in the system. Mechanisms for re-distributing object location information among nodes as nodes are added to and removed from the system are also described.

Claims (87)

1. A computer-readable storage medium storing program instructions executable to implement a method comprising:

a first node in a first LAN selecting a second node in the first LAN to store location information for a first object, wherein the location information specifies that the first object is stored on the first node, wherein each node in the first LAN has a node ID and the first object has an object ID, and wherein the first node selects the second node based on a deterministic relation that depends on the object ID of the first object irrespective of the node ID of the first node;

the first node sending the location information for the first object to the second node;

the second node storing the location information for the first object in response to receiving the location information;

the first node selecting a second LAN to store the location information for the first object;

the first node sending the location information for the first object to the second LAN; and

a third node in the second LAN storing the location information for the first object in response to receiving the location information;

a fourth node in the first LAN performing a search operation to locate the first object, wherein said performing the search operation comprises:

the fourth node selecting the second node to query for the location information for the first object;

the fourth node querying the second node for the location information for the first object; and

the fourth node receiving the location information for the first object from the second node in response to said querying.

2. The computer-readable storage medium of claim 1 ,

wherein said first node sending the location information for the first object to the second LAN comprises the first node sending the location information for the first object to a representative node in the second LAN;

wherein the representative node forwards the location information for the first object to the third node for storage.

3. The computer-readable storage medium of claim 1 , wherein the method implemented by the program instructions further comprises:

the fourth node accessing the first object stored on the first node in response to receiving the location information for the first object from the second node.

4. The computer-readable storage medium of claim 1 , wherein the method implemented by the program instructions further comprises:

a fourth node in a third LAN performing a search operation to locate the first object, wherein said performing the search operation comprises:

the fourth node selecting a fifth node in the third LAN to query for the location information for the first object;

the fourth node querying the fifth node for the location information for the first object;

the fourth node receiving an indication from the fifth node that the fifth node does not have the location information for the first object;

the fourth node selecting the second LAN as a remote LAN to query for the location information for the first object;

the fourth node sending a query for the location information for the first object to the second LAN; and

the fourth node receiving the location information for the first object from the third node in the second LAN in response to the query sent to the second LAN.

5. The computer-readable storage medium of claim 4 ,

wherein said fourth node sending the query for the location information for the first object to the second LAN comprises the fourth node sending the query to a representative node in the second LAN;

wherein the representative node forwards the query to the third node.

6. The computer-readable storage medium of claim 1 ,

wherein the first LAN and the second LAN are LANs of a plurality of LANs, wherein each LAN of the plurality of LANs has a LAN ID;

wherein the first node selects the second LAN to store the location information for the first object based on a relation between the object ID of the first object and the LAN IDs of the LANs.

7. The computer-readable storage medium of claim 6 , wherein the method implemented by the program instructions further comprises:

the first node transforming the object ID of the first object;

wherein said selecting the second LAN based on the relation between the object ID of the first object and the LAN IDs of the LANs comprises selecting the second LAN based on a relation between the transformed object ID of the first object and the LAN IDs of the LANs.

8. The computer-readable storage medium of claim 1 , wherein the first object comprises a storage object.

9. A system comprising:

a plurality of nodes, wherein each node is included in one of a plurality of local area networks (LANs);

wherein the plurality of nodes includes a first node in a first LAN of the plurality of LANs, wherein the first node stores a first object, wherein the first node is configured to:

select a second node in the first LAN to store location information for the first object, wherein the location information specifies that the first object is stored on the first node, wherein each node in the first LAN has a node ID and the first object has an object ID, and wherein the first node selects the second node based on a deterministic relation that depends on the object ID of the first object irrespective of the node ID of the first node; and

send the location information for the first object to the second node;

wherein the second node is configured to store the location information for the first object in response to receiving the location information;

wherein the first node is further configured to:

select a second LAN to store the location information for the first object; and

send the location information for the first object to the second LAN; and

wherein a third node in the second LAN is configured to store the location information for the first object in response to receiving the location information;

wherein the first LAN also includes a fourth node configured to:

select the second node to query for the location information for the first object; and

query the second node for the location information for the first object;

wherein the second node is configured to send the location information for the first object to the fourth node in response to said querying.

10. The system of claim 9 ,

wherein the representative node is configured to forward the location information for the first object to the third node for storage.

11. The system of claim 9 wherein the fourth node is further configured to access the first object on the first node in response to receiving the location information for the first object from the second node.

12. The system of claim 9 ,

wherein the plurality of LANs also includes a third LAN including a fourth node;

wherein the fourth node is configured to:

select a fifth node in the third LAN to query for the location information for the first object;

query the fifth node for the location information for the first object;

receive an indication from the fifth node that the fifth node does not have the location information for the first object;

select the second LAN as a remote LAN to query for the location information for the first object; and

send a query for the location information for the first object to the second LAN;

wherein the third node in the second LAN is configured to send the location information for the first object to the fourth node in response to the query sent to the second LAN.

13. The system of claim 12 ,

wherein said fourth node sending the query for the location information for the first object to the second LAN comprises the fourth node sending the query to a representative node in the second LAN;

wherein the representative node is configured to forward the query to the third node.

14. The system of claim 9 ,

wherein each LAN of the plurality of LANs has a LAN ID;

wherein the first, node is configured to select the second LAN to store the location information for the first object based on a relation between the object ID of the first object and the LAN IDs of the LANs.

15. The system of claim 14 ,

wherein the first node is further configured to transform the object ID of the first object;

16. The system of claim 9 , wherein the first object comprises storage object.

17. The system of claim 9 ,

wherein in response to a new node joining the first LAN, the second node is configured to:

determine that the location information for the first object should be stored on the new node instead of the second node; and

communicate with the new node to transfer the location information for the first object to the new node.

18. A method comprising:

a first node in a first LAN selecting a second node in the first LAN to store location information for a first object,

wherein the location information specifies that the first object is stored on the first node, wherein each node in the first LAN has a node ID and the first object has an object ID, and wherein the first node selects the second node based on a deterministic relation that depends on the object ID of the first object irrespective of the node ID of the first node;