A Distributed Directory Service using the Chord DHT

Irene Zhang, Raluca Ada Popa, Mihir Kedia, Hari Balakrishnan, Barbara Liskov MIT Computer Science and Artificial Intelligence Laboratory

Abstract

1 Introduction

Numerous distributed systems use distributed hash tables for locating data. Distributed hash tables offer many benefits: decentralized operation, a simple interface, scalability, availability and fault tolerance. Unfortunately, DHTs not give applications any control over where data is placed in the system. Distributed systems frequently need control over data placement because objects are large, frequently modified or cannot be stored on untrusted peers. Many distributed systems avoid this problem by storing meta-data in the DHT that points to where the actual data is located. For example, the BitTorrent implementation uses the DHT to locate a tracker that keeps the actual list of servers for the file.

By using the DHT to store meta-data instead of data directly, systems like the BitTorrent implementation reduce the benefits of using a DHT. For each piece of data, there is now a single point of failure, drastically reducing the robustness that DHTs provide. For example in the Pastry DHT [5], typically 8-16 nodes with adjacent node ids must fail simultaneously before a key in the system cannot be found at all. In contrast, if the Pastry DHT is used to store meta-data, data can be lost by just the failure of the node storing the meta-data.

Once a node fails, recovering the meta-data is very difficult and time-consuming. In contrast, DHTs generally have efficient algorithms for quickly rebuilding routing tables. In addition, the meta-data scheme lacks fate-sharing; if the node holding the meta-data fails, the data can no longer be located, although the data itself is still in the system. This problem limits the scalability of the system somewhat because the amount of data lost grows linearly assuming a constant rate of failures.

Load-balancing and hot spots can also pose a problem in the meta-data scheme. If a node is responsible for the meta-data of an especially popular file, the node will see much more traffic than other nodes and may become overloaded. The failures and load balancing problems can be somewhat offset by replicating meta-data across multiple nodes and placing multiple virtual nodes on each physical node, but this solution introduces other issues such as consistency.

We introduce Data-oriented Chord, a modification of the Chord DHT [6] that gives applications control over key placement while preserving the simple design and other benefits of Chord. Like the Chord protocol, Data-oriented Chord supports just one operation: given a key, its maps the key onto a node. Unlike Chord, DOC leaves the key assigned to the client/physical node that inserted the key. The basic idea behind DOC is very simple: instead of using virtual nodes for load balancing, DOC uses virtual nodes to represent keys held by physical nodes. Every time a physical node acquires a new key, the node inserts a new virtual node for that key into the DOC ring, essentially registering as a server for that key. Since keys remain mapped to the node that inserted the key, applications now have control over key placement, and therefore data placement.

The use of virtual nodes to represent data objects or keys can be applied to any DHT that can virtualize a physical node in several locations in the identifier space. For example, the Content-Addressable Network [4] can map a single key onto several points in the coordinate space by using a different hash function for each point. By using a different hash function for each data object, every object on a physical node could be represented by a different point in the coordinate space. This idea could also be applied to Pastry [5], Kademlia [3] and many other DHTs.

The rest of the paper gives a short overview of the original Chord protocol, explains the Data-oriented Chord protocol in depth, describes an example application and provides some performance results based on simulations.

2 The Chord protocol

Chord is a distributed lookup protocol with just one operation: given a key, it maps the key to a node. Nodes are arranged ordered in a ring using the node id and keys are assigned to nodes using consistent hashing. Each node keeps pointers to its successor and predecessor in the ring, and log n other nodes. The other log n pointers, called fingers, are used to optimize lookups. Fingers are placed at powers of two; the i-th finger is a node that is at least 2^{i} away in the id space.

Lookups hop from node to node around the Chord ring until the node that the key is assigned to is found. Only maintaining the successor pointer is necessary for correctness because key lookups can progress around the ring until the node holding the key is found. Using only successor pointers, the number of hops needed for each lookup will increase linearly with respect to the number of nodes in the system. With the addition of log n fingers at every node, the distance to the destination can be halved at each hop, so lookups take log n hops on average.

3 Data-oriented Chord Protocol

The basic idea behind Data-oriented Chord is a simple modification of the original Chord protocol: using virtual nodes to represent keys held by physical nodes. First, we will present the base protocol and then we will address some of its limitations with optimizations.

3.1 Consistent Hashing

The consistent hash function in Data-oriented Chord assigns each virtual node an (m + n)-bit identifier. Since more than one physical node may hold a particular key, one key must map to multiple virtual nodes. So the identifier for a virtual node is chosen as follows: the higher m-bits of the id are chosen by hashing the key using a base hash function like the SHA-1, and the lower n-bits are chosen randomly when the virtual node is inserted. Ids are ordered in a ring modulo 2^{m+n}, divided into ranges of size 2^{n} for each key. Within each key range, the virtual nodes divide the id space randomly.

For each key lookup, the consistent hash function creates a (m + n)-bit identifier where the higher mbits are a hash of the key and the lower n-bits are chosen randomly. The virtual node that is the successor in the key range of the lookup identifier is the one

Figure 1: Data-oriented Chord ring. Each node in the Chord ring represents a virtual node and the virtual nodes of the same color reside on the same physical node. Even with only successor pointers, each physical node already has quite a bit of information about the other nodes. For example, the red physical node knows the blue physical node has key 129 and the green physical node has keys 61 and 251. Unfortunately, even with multiple successor pointers on each physical node, searches are still linear because there are no guarantees about where the successor pointers will be located.

that the key maps to for that lookup. This randomization in the lookup protocol means that a different virtual node gets returned for each lookup, balancing the load across all of the physical nodes that hold a particular key.

3.2 Key Lookup

Each physical node in Data-oriented Chord maintains routing information for each of its virtual nodes, meaning that the amount of routing information maintained by a physical node scales with the number of keys on the node. As in the Chord protocol, only successor pointers for each virtual node are necessary for correctness. Figure 1 shows an example ring with only the successor pointers. To guarantee logarithmic performance on average, physical nodes in DOC also maintain finger tables for each virtual node.

Using the lookup identifier given by the consistent hash function, lookups proceed by first finding the predecessor following the Chord protocol. As a practical optimization, the lookup protocol considers the fingers of all virtual nodes on the physical node at each hop to ensure that a physical node never needs to be contacted twice. Once the predecessor has been found, the first m-bits of the successor’s id are checked to see if the successor is in the key range. If the successor is in the key range, the successor is returned. Otherwise, the predecessor’s id is checked and the predecessor is returned if it is in the key range. If both the predecessor and successor are outside the key range, no nodes in the system have been mapped to that key yet. This check is necessary because the virtual nodes that serve the key are randomly arranged in the key range, so the successor to the last few ids in the key range and the predecessor to the first few ids in the key range might be a virtual node in another key range.

3.3 Node Joins

Physical nodes do not join the Data-oriented Chord ring as in the original Chord protocol. A node only joins the ring when the node has a key, and therefore a virtual node, to insert.

To join the system, physical nodes can contact some well-known node and use the well-known node to run lookups until the node acquires a key. In the base protocol, nodes always register as a server for any key they have looked up, so the well-known node should only be used for one lookup. The well-known node should cut off the new node if the node uses it for more than a few lookup in case the new node is malicious.

When a physical node wants to register as a server for a key, the physical node “joins” the DOC ring using the Chord join protocol and an virtual node identifier given by the consistent hash function. Like the optimization used in the Chord protocol, the virtual node can start with an initial finger table copied from another virtual node and adjust the fingers later using stabilize. If the physical node acquired the key by a lookup, the node can fetch initial finger tables along with the other data associated with the key from node that the key mapped to. Otherwise, the physical node can find the virtual node’s successor using lookup and fetch an initial finger table for the virtual node from the successor.

To leave the system, the physical node can just exit without contacting any other nodes. The node will remove keys and data that belong to itself from the system and the stabilize protocol will eventually fix any pointers that are broken. This ability to leave without contacting other nodes is a huge benefit because failures no longer have any impact.

3.4 Stabilization

Each node runs stabilize according to the Chord protocol to keep successor pointers and finger tables up to date. To reduce the amount of bandwidth spent running the stabilize protocol, physical nodes batch stabilize messages to other physical nodes.

4 Evaluation

4.1 Optimizations

5 Related Work

Data-oriented Chord is aimed at the same applications as other distributed lookup services like Chord, CAN, Pastry and Tapestry. Unlike other DHTs, DOC always maps the key onto the node where the key was inserted. DOC is similar to Tapestry in that applications have control over where data placement, but DOC does not optimize for locality like Tapestry, making DOC much simpler.

Data-oriented Chord is most similar to the contentsharing subrings used in the Arpeggio file-sharing network [1]. Arpeggio uses the Diminished Chord protocol [2] to create a subring for each distinct data object in the system. Nodes that hold a particular object all join the subring for that object. For each file with k servers, Diminished Chord only uses a linear amount of space for each subring, whereas DOC uses O (n log n) space, but Data-oriented Chord maintains the simplicity of the original Chord protocol.

6 Conclusion

We presented Data-oriented Chord, a distributed lookup protocol that offers all of the advantages of DHTs while allowing applications to control data placement.

Data-oriented Chord offers several benefits over storing meta-data in a DHT:

• Fault tolerance with fate sharing: When a nodes fails, only data on that node is lost.

• Load balancing: Each node

• Scales based on the popularity of the file.

References

[1] Clements, A. T., Ports, D. R. K., and Karger, D. R. Arpeggio: Metadata searching and content sharing with Chord. In Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS05) (Ithaca, NY, February 2005).

[2] Karger, D. R., and Ruhl, M. Diminished chord: A protocol for heterogeneous subgroup formation in peer-to-peer networks. In Proceedings of the 4th International Workshop on Peer-to-Peer Systems (IPTPS05) (2004), pp. 288–297.

[3] Maymounkov, P., and Mazières, D. Kademlia: A peer-to-peer information system based on the XOR metric. In Proceedings of the 1st International Workshop on Peer-to-Peer Systems (IPTPS02) (March 2002).

[4] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Schenker, S. A scalable content-addressable network. In SIG-COMM ’01: Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications (New York, NY, USA, 2001), ACM, pp. 161– 172.

[5] Rowstron, A., and Druschel, P. Pastry: Scalable, decentralized object location and routing for large scale peer-to-peer systems. In Proceedings of the 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001) (November 2001).

[6] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM Comput. Commun. Rev. 31, 4 (2001), 149–160.