Fast distributed object lookup for a computer network

A system and method related for performing lookup operations for objects distributed among different nodes in a peer-to-peer network are disclosed. Various nodes in the peer-to-peer network may store objects. Objects stored on a given node may be accessed by other nodes in the peer-to-peer network. To access an object, a node may first perform a lookup operation to determine where the object is stored, i.e., to determine which node in the peer-to-peer network stores the object. The peer-to-peer network may utilize a method to improve the performance of object lookup operations. In one embodiment, the method may allow object lookup operations to be performed with a latency on the order of one hop.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to computer networks and, more particularly, to a method for improving the performance of lookup operations for objects distributed among different computer systems in a computer network.

2. Description of the Related Art

Peer-to-peer networking has seen rapid growth in recent years. A peer-to-peer or P2P network is generally used to describe a decentralized network of peer computing nodes, where each node may have similar capabilities and/or responsibilities. A pure peer-to-peer network may not utilize centralized servers. Instead, a given peer node may be equally capable of serving as either a client or a server for other peer nodes. Thus, participating peer nodes in the peer-to-peer network may communicate directly with each other. Work may be done and information may be shared through interaction among the peers.

A peer-to-peer network may be created to fulfill some specific need, or it may be created as a general-purpose network. Some P2P networks are created to deliver one type of service and thus typically run one application. For example, Napster was created to enable users to share music files. Other P2P networks are intended as general purpose networks which may support a large variety of applications. Any of various kinds of distributed applications may execute on a P2P network. Exemplary peer-to-peer applications include file sharing, messaging applications, distributed data storage, distributed processing, etc.

Nodes in a peer-to-peer network often need to access files or other information stored on other nodes in the peer-to-peer network. To access a particular file or particular information, a node may first need to determine which node the file or information is stored on in the peer-to-peer network. Determining which node the file or information is stored on is referred to herein as a lookup operation. Peer-to-peer systems capable of performing lookup operations have been developed, including PASTRY, CHORD, TAPESTRY, and SYMPHONY. In existing peer-to-peer networks, a lookup operation is typically performed by the node needing to access the file sending a query to one or more other nodes to determine the file's location. The query may be propagated on to other nodes in the network until reaching a node that knows where the file is located. Information specifying the file location may then be propagated back from this node to the node that originally issued the query.

This technique of performing a lookup operation takes multiple hops. In a peer-to-peer network having N nodes, the average latency for such a lookup operation is on the order of log(N). In comparison with centralized networking schemes, this is a very high latency operation and limits the performance of the system. Thus, it would be desirable to provide a technique for improving the performance of lookup operations for a peer-to-peer network.

SUMMARY

Various embodiments of a system and method related to performing lookup operations for objects distributed among different nodes in a peer-to-peer network are disclosed. A plurality of nodes may be coupled to each other to form the peer-to-peer network. Coupling the plurality of nodes to each other may comprise creating a plurality of links. Each link may comprise a virtual communication channel between a first node and a second node.

Various nodes in the peer-to-peer network may store objects. As used herein, an “object” may comprise a portion of data, such as a file or other type of data entity. Objects stored on a given node may be accessed by other nodes in the peer-to-peer network. To access an object, a node may first perform a lookup operation to determine where the object is stored, i.e., to determine which node in the peer-to-peer network stores the object. The peer-to-peer network may utilize a method to improve the performance of object lookup operations.

According to one embodiment of the method, object location information may be stored on a plurality of nodes in the peer-to-peer network. In one embodiment, a mapping between objects and nodes may be utilized to determine which node should store the object location information for each object. Object location information for each object may be stored on the node that is specified by the mapping. In various embodiments, any kind of mapping between objects and nodes may be utilized. The mapping may also be utilized to determine where the location information for an object is stored when a first node needs to access the object.

DETAILED DESCRIPTION

FIG. 1illustrates a diagram of one embodiment of a peer-to-peer network100. The peer-to-peer network100includes computing nodes (e.g., computer systems)110A-110E, although in various embodiments any number of nodes may be present. It is noted that throughout this disclosure, drawing features identified by the same reference number followed by a letter (e.g., nodes110A-110E) may be collectively referred to by that reference number alone (e.g., nodes110) where appropriate.

As shown, nodes110A-110E may be coupled through a network102. In various embodiments, the network102may include any type of network or combination of networks. For example, the network102may include any type or combination of local area network (LAN), a wide area network (WAN), an Intranet, the Internet, etc. Example local area networks include Ethernet networks and Token Ring networks. Also, each node110may be coupled to the network102using any type of wired or wireless connection mediums. For example, wired mediums may include: a modem connected to plain old telephone service (POTS), Ethernet, fiber channel, etc. Wireless connection mediums may include a satellite link, a modem link through a cellular service, a wireless link such as Wi-Fi™, a wireless connection using a wireless communication protocol such as IEEE 802.11 (wireless Ethernet), Bluetooth, etc.

The peer-to-peer network100may comprise a decentralized network of nodes110where each node may have similar capabilities and/or responsibilities. As described below, each node110may communicate directly with at least a subset of the other nodes110. Messages may be propagated through the network100in a decentralized manner.

Referring now toFIG. 2, a diagram of one embodiment of a node110in the peer-to-peer network100is illustrated. Generally speaking, node110may include any of various hardware and software components. In the illustrated embodiment, node110includes a processor120coupled to a memory122, which is in turn coupled to a storage124. Node110may also include a network connection126through which the node110couples to the network102.

The processor120may be configured to execute instructions and to operate on data stored within memory122. In one embodiment, processor120may operate in conjunction with memory122in a paged mode, such that frequently used pages of memory may be paged in and out of memory122from storage124according to conventional techniques. It is noted that processor120is representative of any type of processor. For example, in one embodiment, processor120may be compatible with the x86 architecture, while in another embodiment processor120may be compatible with the SPARC™ family of processors.

Memory122may be configured to store instructions and/or data. In one embodiment, memory122may include one or more forms of random access memory (RAM) such as dynamic RAM (DRAM) or synchronous DRAM (SDRAM). However, in other embodiments, memory122may include any other type of memory instead or in addition.

Storage124may be configured to store instructions and/or data, e.g., may be configured to persistently store instructions and/or data. In one embodiment, storage124may include non-volatile memory, such as magnetic media, e.g., one or more hard drives, or optical storage. In one embodiment, storage124may include a mass storage device or system. For example, in one embodiment, storage124may be implemented as one or more hard disks configured independently or as a disk storage system. In one embodiment, the disk storage system may be an example of a redundant array of inexpensive disks (RAID) system. In an alternative embodiment, the disk storage system may be a disk array, or Just a Bunch Of Disks (JBOD), (used to refer to disks that are not configured according to RAID). In yet other embodiments, storage124may include tape drives, optical storage devices or RAM disks, for example.

As shown inFIG. 2, storage124may store a plurality of objects136. As used herein, an “object” may comprise a portion of data. In various embodiments, an object may include data or information of any kind, and the data or information may be structured or stored in any of various ways. In one embodiment, each object may comprise a file. In other embodiments, objects may comprise program modules or components, data portions stored in a database, or various other types of data entities.

The objects136may be accessed by various nodes110in the peer-to-peer network100. To access an object, a node110may first perform a lookup operation to determine where the object is stored, i.e., to determine which node110in the peer-to-peer network100stores the object on its respective storage124. The peer-to-peer network100may utilize a technique to improve the performance of object lookup operations. In one embodiment, the technique may allow object lookup operations to be performed with a latency on the order of 1 hop. In one embodiment, memory122of each node110may store object storage software130and directory service software131that are involved with performing object lookup operations, as described in detail below. In one embodiment, memory122may also store client application software128. For example, the client application software128may utilize the objects136, and object lookup operations may be performed when the client application software128needs to access objects136.

Referring again toFIG. 2, network connection126may include any type of hardware for coupling the node110to the network102, e.g., depending on the type of node110and type of network102. As shown inFIG. 2, memory122may also store network software132. The network software132may include software that is executable by processor120to interact with or control the network connection126, e.g., to send and receive messages or data via the network connection126.

In one embodiment, as each node110joins the peer-to-peer network100, the node may establish links142with at least a subset of other nodes110in the network100. As used herein, a link142comprises a virtual communication channel or connection between two nodes110. The network software132may be responsible for performing a node discovery process and creating links with other nodes as a node comes online in the network100. The resulting set of connected nodes is referred to herein as a link mesh140.FIG. 3illustrates an exemplary link mesh140for a set of nodes110. Each hexagon represents a node110, and each line represents a link142between two nodes110.

FIG.4—Mapping Between Objects and Nodes

As noted above, the peer-to-peer network100may utilize a technique to improve the performance of object lookup operations. This may involve storing object location information133on a plurality of nodes110in the peer-to-peer network100. For example, a plurality of nodes110in the peer-to-peer network100may act as directory servers. Let U represent the entire collection of all objects136stored on all nodes110in the peer-to-peer network100. Each node110that acts as a directory server may store object location information133for a subset of U, i.e., may store object location information133for one or more objects136selected from the entire collection of all objects136. For each object136for which a given node110stores object location information133, the object136may be stored on any node110in the peer-to-peer network.

In one embodiment, a mapping between objects136and nodes110may be utilized to determine which node110should store the object location information133for each object136. Object location information133for each object136may be stored on the node110that is specified by the mapping. In various embodiments, any kind of mapping between objects136and nodes110may be utilized.

FIG. 4illustrates an exemplary mapping with respect to objects136stored on a node110A, i.e., objects136stored on storage124of node110A. As shown, object136A maps to node110E. Thus, node110A may communicate with node110E to cause object location information133for object136A to be stored on node110E. More particularly, processor120of node110A may execute object storage software130stored in memory122of node110A to cause object location information133for object136A to be stored on node110E. Processor120of node110E may execute directory service software131to create or store the object location information133for object136A on node110E in response to the communication with node110A.

Suppose now that node110C needs to access object136A. Node110C may determine that object136A maps to node110E, i.e., may determine that node110E acts as a directory server for object136A. Thus, node110C may communicate with node110E to obtain the object location information133for object136A. More particularly, directory service software131executing on node110C may communicate with directory service software131executing on node110E to obtain the object location information133for object136A. The object location information133for object136A may specify that object136A is located on node110A. Node110C may thus communicate with node110A to access object136A. In this example, the latency for the lookup operation to obtain the object location information133for object136A is one hop.

In a similar manner, object136B on node110A maps to node110F, object136C maps to node110B, etc. Thus, node110A may also communicate with these nodes110to cause object location information133for the respective objects136to be stored on the corresponding nodes110.

Although not illustrated, nodes110B-110G in this example may also store their own objects136. The objects136stored on nodes110B-110G may be mapped to various nodes110in a similar manner as described above with respect to the objects136stored on node110A. For example, node110B may store an object136Y that maps to node110A. Thus, node110B may communicate with node110A to cause object location information133for object136Y to be stored on node110A.

In various embodiments, various proportions of the nodes110in the peer-to-peer network100may act as directory servers. In other words, objects136stored on various nodes110may be mapped to various proportions of the nodes110. In one embodiment all, substantially all, or a large proportion of the nodes110in the peer-to-peer network100may act as directory servers. Thus, object lookup requests may be directed to nodes110throughout the peer-to-peer network100. In various applications, this may advantageously reinforce the decentralized nature of the peer-to-peer network100.

In one embodiment, it may be desirable to map the objects136to the nodes110that act as directory servers in such a way that the number of objects for which each node acts as a directory server is roughly equal (or is in proportion to the node's computing resources). For example, it may be undesirable for any particular node to act as a directory server for a disproportionately large number of objects because this may cause the node to become overloaded with requests for object location information. In one embodiment, the objects136may be mapped to the nodes110in a random or pseudo-random manner, which may achieve a roughly even distribution of object location information across the nodes110.

FIG. 5-Methodfor Storing Object Location Information for a Peer-to-Peer Network

As described above, each node that stores objects may communicate with other nodes to cause object location information for the objects to be stored on the respective nodes to which the objects are mapped.FIG. 5is a flowchart diagram illustrating operations that may be performed according to one embodiment when a first node communicates with a second node to cause object location information for an object to be stored on the second node.

It is noted thatFIG. 5illustrates a representative embodiment, and alternative embodiments are contemplated. In particular,FIG. 5illustrates an embodiment in which the mapping between objects and nodes is based on IDs of the objects and nodes. In other embodiments, other mapping schemes may be utilized, and the mapping may be based on other information.

In one embodiment, each object136and each node110may have an associated ID (identifier). The ID of an object or node may include any type of information usable to uniquely identify the object or node. In one embodiment, each object ID or node ID may comprise a sequence of bits, such as a 128-bit Universally Unique ID (UUID). Universally Unique IDs or UUIDs may be allocated based on known art that ensures that the UUIDs are unique. In one embodiment these UUIDs may be generated randomly or pseudo-randomly.

In301, the first node (e.g., object storage software130executing on the first node) may determine the ID of the object, e.g., by examining the object itself or by utilizing stored ID information that specifies the ID of the object based on other information regarding the object, such as a name of the object.

In303, the first node may determine an ordering of IDs of the nodes that act as directory servers (which may be all or substantially all of the nodes in the peer-to-peer network, as discussed above). The IDs of the nodes may be ordered in any of various ways. In one embodiment, the IDs of the nodes may be placed in increasing order. For example, where the IDs comprise bit sequences, the bit sequences may be compared and placed in increasing numeric order.

In305, the first node may determine where the ID of the object falls in relation to the ordered IDs of the nodes. In307, the first node may select a second node to act as a directory server for the object, where the second node is selected based on where the ID of the object falls in relation to the ordered IDs of the nodes. In various embodiments, various techniques may be used to select the second node.

In one embodiment, the second node may be selected such that the ID of the second node is comparatively greater than the ID of the object and such that there is no other node with an ID that is both comparatively greater than the ID of the object and also comparatively less than the ID of the second node. For example, suppose that there are N nodes that act as directory servers, and thus N ordered node IDs. Determining the ordering of the node IDs may comprise determining an ordering such that for each k from 2 to N, the kthnode ID is greater than the (k−1)thnode ID. Thus, determining where the ID of the object falls in relation to the ordered IDs of the nodes may comprise determining that an ithnode ID in the ordering is greater than the ID of the object and determining that the (i−1)thnode ID is less than the ID of the object. In this example, the node with the ithnode ID may be selected as the second node. (Various techniques may be used to select a second node when boundary conditions occur. For example, if there is no node ID that is greater than the ID of the object, the node with the lowest node ID may be selected as the second node.)

In an alternative embodiment, the second node may be selected such that the ID of the second node is comparatively less than the ID of the object and such that there is no other node with an ID that is both comparatively less than the ID of the object and also comparatively greater than the ID of the second node. In another embodiment, the node with an ID that is comparatively closest to the ID of the object may be chosen as the second node.

In309, the first node may send location information for the object to the second node. The location information for the object may specify that the object is stored on the first node. For example, the first node may send a message to the second node requesting the second node to store the location information for the object.

In311, the second node (e.g., directory service software131executing on the second node) may receive the location information for the object from the first node and may store the location information for the object. In one embodiment, the location information for the object may be stored in memory122of the second node, as illustrated inFIG. 2. Alternatively or in addition, the location information for the object may be stored in storage124of the second node. In various embodiments, the location information may be structured or stored in various ways. For example, the location information for the object may be stored in a hash table keyed on the object ID or stored in another data structure that allows fast lookup of object location information. After storing the location information for the object, the second node may be operable to respond to location queries for the object by returning the stored location information which specifies that the object is stored on the first node.

Thus, each node in the peer-to-peer network that stores one or more objects may perform the operations described above with respect to the first node to cause location information for its objects to be stored on various nodes in the peer-to-peer network. If each node in the peer-to-peer network selects a directory server (i.e., selects the second node) according to the mapping technique described above, then the mapping between objects and nodes may be characterized as follows: Let Node_IDirepresent the ordered node IDs for i=1 to N, where N is the number of nodes that act as directory servers. Thus, Node_ID1<Node_ID2< . . . <Node_IDN. For each object with an ID Object_IDjsuch that Node_IDi-1<Object_IDj<Node_IDithe object maps to the node having Node_IDias its corresponding directory server (regardless of what node the object is stored on).

As noted above, in one embodiment each object ID and node ID may comprise a Universally Unique ID, which may be generated randomly or pseudo-randomly. This may decrease the possibility of any given node being assigned a disproportionately large amount of object location information.

Various techniques may also be utilized to increase the randomness of the mapping of objects to nodes. For example, in a variation of the mapping described above, each node that acts as a directory server may be assigned a plurality of random and unique node IDs. For example, each node may have one primary or actual node ID and multiple secondary node IDs, e.g., 0 to 1000 secondary node IDs. In this embodiment,303may comprise determining an ordering of all IDs (primary and secondary IDs) of the nodes that act as directory servers, e.g., by placing all the node IDs in increasing order.

The second node that acts as a directory server for a given object may then be selected based on where the ID of the object falls in relation to the ordered primary and secondary IDs of the nodes, similarly as described above. For example, if the object ID falls between a first secondary node ID and a second secondary node ID, where the second secondary node ID is greater than the first secondary node ID, then the node having the second secondary node ID may be selected to act as the directory server for the object (or vice versa). Increasing the number of IDs of each node in this manner may help to increase the probability of distributing object location information evenly across the nodes.

In other embodiments, any of various other techniques may be utilized to increase randomness of the mapping of objects to nodes or otherwise achieve a more even distribution of object location information across the nodes.

FIG.6—Method for Looking Up Object Location Information

As described above, each node110that needs to access an object136may first communicate with a node110that acts as a directory server for the object136to obtain location information133for the object136.FIG. 6is a flowchart diagram illustrating operations that may be performed according to one embodiment when a first node communicates with a second node to request location information for an object and communicates with a third node to access the object.

It is noted thatFIG. 6illustrates a representative embodiment, and alternative embodiments are contemplated. In particular,FIG. 6illustrates an embodiment in which the mapping between objects and nodes is based on IDs of the objects and nodes. In other embodiments, other mapping schemes may be utilized, and the mapping may be based on other information.

In351, the first node (e.g., directory service software131executing on the first node) may determine an ID of the object that the first node needs to access. In various embodiments, the ID of the object may be determined in various ways. In one embodiment, the need to access the object may originate from client application software128executing on the first node, and the client application software128may inform the directory service software131of the object ID. In another embodiment, the ID of the object may be determined based on other information regarding the object, such as a name of the object. For example, in one embodiment each object may comprise a file. A file system of each node may maintain information specifying an ID of each file, regardless of where the file is located in the peer-to-peer network. Thus, the directory service software131of the first node may interface with the file system of the first node to obtain the ID of the desired file, e.g., by specifying a name and/or other attributes of the file.

When accessing the object, the directory server for the object may be determined in the same way as when the location information for the object is stored. Thus, in353, the first node may determine an ordering of IDs of nodes in the peer-to-peer network, similarly as described above with respect to303ofFIG. 5. In355, the first node may determine where the ID of the object falls in relation to the ordered IDs of the nodes, similarly as described above with respect to305ofFIG. 5. In357, the first node may select a second node based on where the ID of the object falls in relation to the ordered IDs of the nodes, similarly as described above with respect to307ofFIG. 5. The second node may act as the directory server for the object.

In359, the first node may send a message to the second node to request location information for the object.

In361, the second node may return the location information for the object to the first node, where the location information specifies that the object is stored on a third node.

In363, the first node may communicate with the third node to access the object. As used herein, accessing the object may include obtaining data from the object or obtaining data regarding the object. Accessing the object may also include writing data to the object or writing data regarding the object.

Fault Tolerance

In one embodiment, the methods described above may be modified to achieve greater fault tolerance by storing object location information for a given object on multiple nodes. In other words, multiple nodes110may act as directory servers for each object136. For example, suppose that the mapping between objects and directory servers is performed as described above with reference toFIG. 5. That is, for each object, an ithnode ID may be determined from a set of ordered node IDs such that the ithnode ID is greater than the ID of the object and the (i−1)thnode ID is less than the ID of the object.

In one embodiment, in addition to storing the location information for the object on the node having the ithnode ID, location information for the object may also be stored on the nodes having the (i+1)thnode ID, (i+2)thnode ID, etc., up to the node having the (i+R)thnode ID, where R is set to achieve the desired level of redundancy. Thus, if a first node later needs to access the object, the first node may first attempt to obtain the location information for the object from the node having the ithnode ID. If the node having the ithnode ID is not accessible, e.g., due to a network failure or other problem, then the first node may then attempt to obtain the location information for the object from the node having the (i+1)thnode ID, etc., until the first node finds a working directory server for the object (or until all directory servers for the object have been tried unsuccessfully).

The level of redundancy may be configured as appropriate for a given system and may depend on considerations such as the total number of objects utilized in the system. If there is a very large number of objects, it may not be practical to store redundant object location information on a large number of nodes because of memory constraints on the nodes. Thus, the object location information for each object may be replicated on a relatively small number of nodes.

Navigating a Directory Hierarchy

As noted above, in various embodiments each object136may comprise various kinds of data, where the data may be organized in various ways. In one embodiment, a first object136, also referred to herein as a directory object, may comprise directory information, where the directory information specifies location information for other objects136. For example, a node may access the first object to obtain the directory information, e.g., by first looking up location information for the first object, similarly as described above. The node may then access a second object whose location information is specified by the directory information. The second object may be the object that the node ultimately needs to access, e.g., may be a file object, or the second object may also be a directory object, which specifies additional directory information. In the latter case, the node may access a third object whose location information is specified by the directory information of the second object. Thus, a node may navigate through a directory hierarchy in this manner by repeatedly utilizing location information stored by various objects.

Reducing Cost of Multiple Connections

As a node accesses multiple objects, the node may create multiple temporary connections with the directory servers for the respective objects. For some applications, it may be desirable to reduce the cost of creating and destroying these connections. Various techniques may be utilized to reduce this cost.

In one embodiment, User Datagram Protocol (UDP) messages may be utilized to accomplish the object location lookups. For some applications, UDP may be well suited for the lookup operations because the UDP request and reply messages are short, and a connection does not need to be established between the node performing the lookup and the directory server. To manage the unreliable nature of the UDP protocol, multiple requests and/or re-transmissions and timeouts may be utilized, as described below.

Because of the small cost of UDP-based lookup, a first node may send lookup requests to multiple directory servers responsible for a particular object simultaneously (where the object location information is replicated on multiple directory servers as described above). The first node may utilize the first location information that is received from any of the directory server nodes. In case no reply is received to any of the requests sent within a timeout, a UDP retry request may be sent a small number of times (e.g., 1-3 times). The timeout for retries may be calculated adaptively using exponential backoff. The time spent attempting re-transmissions may optionally be limited by a timeout Tmaxfor the entire lookup operation, which may be specified by a client application that initiates the lookup operation. Thus the client application may be guaranteed a positive or negative search response for the lookup operation within the Tmaxinterval.

The UDP-based lookup technique may be well-suited when the nodes in the peer-to-peer network are connected by a high bandwidth, well connected network such as a LAN, or a corporate site network. In particular, one system for which the UDP-based lookup technique may be well-suited is for an array of blade servers connected by a LAN.

In a high latency, WAN-like network, UDP messages may be considered too unreliable. In such a system, TCP connections may instead be used to provide reliable connections. A combination of directory server based search (for local lookups) and a tree layer based search (for remote lookups over the WAN) may be used in this case (where the tree layer search is performed by topology and routing layer software that maintains a tree-based view of the network).

In one embodiment, the peer-to-peer network may include multiple realms, e.g., where each realm includes nodes that are geographically close or otherwise well connected to each other. In one embodiment, a node that performs a lookup operation may first contact a directory server in its local realm. Location information for some objects may not be stored on the directory servers by default. If a node attempts to lookup location information for an object, and the location information for the object does not exist on the directory server(s), then the search may proceed along a tree that routes the search query to other realms. If the search is successful, then location information for the object may be stored on one or more directory servers in the local realm.

In one embodiment, nodes may publish the presence of certain objects to directory servers, where location information for the objects would not otherwise be stored on the directory server. This may be useful to populate the directory servers in advance with location information for the objects. Location information for objects may be published to directory servers in a local realm and/or remote realms.

It is noted that various embodiments may further include receiving, sending or storing instructions and/or data implemented in accordance with the foregoing description upon a carrier medium. Generally speaking, a carrier medium may include storage media or memory media such as magnetic or optical media, e.g., disk or CD-ROM, volatile or non-volatile media such as RAM (e.g. SDRAM, DDR SDRAM, RDRAM, SRAM, etc.), ROM, etc. as well as transmission media or signals such as electrical, electromagnetic, or digital signals, conveyed via a communication medium such as network and/or a wireless link.