6.824 2002 Lecture 22: Distributed Hash Tables You're all familiar with Gnutella &c Internet, set of peer nodes Nodes form an overlay network, with "neighbors" The overlay helps nodes search for files Gnutella floods keyword queries over the entire overlay Robust to technical and legal attacks. Because it is symmetric: no centralized mechanisms. Contrast to Napster. Hard to use Gnutella as a building block in larger system. Queries are not well defined. Hard to retrieve a specific piece of data (no names). Queries are slow. Data is tied to the node that publishes it, so it might disappear. No notion of data integrity. Proposal: distributed hash table put(key, value) get(key) -> value Two layers: 1) route(key, msg), 2) key/value storage Potential applications: file system, use DHT as a sort of distributed disk drive keys are like block numbers Petal is a little bit like this location tracking keys are e.g. cell phone numbers a value is a phone's current location "permanent urls" Today I'll talk mostly about lookup (lower layer). Basic idea Give each node a unique ID Have a rule for assigning keys to nodes based on node/key ID e.g. key X goes on node node with nearest ID to X Now how, given X, do we find that node? Arrange nodes in an ID-space, based on ID i.e. use ID as coordinates Examples: 1D line, 2D square, Tree based on bits, hypercube, or ID circle Build routing tables to allow ID-space navigation Each node knows about ID-space neighbors Perhaps each node knows a few farther-away nodes To move long distances quickly What does a complete algorithm have to do? 1. Define IDs, document ID to node ID assignment 2. Define per-node routing table contents 3. Lookup algorithm that uses routing tables 4. Join procedure to reflect new nodes in tables 5. Failure recovery The "Pastry" peer-to-peer lookup system By Rowstron and Druschel http://www.research.microsoft.com/~antr/pastry/ An example system of this type Assignment of key IDs to node IDs? IDs are 128-bit numbers Node IDs chosen by MD5 hash of IP address Key stored on node with numerically closest ID If node and key IDs are uniform, we get reasonable load balance. Routing? Query is at some node. Node needs to forward the query to a node "closer" to key. Note key ID and node ID share some high bits of ID prefix. Routing forwards to node that shares more bits of prefix. Sharing more bits of prefix is the definition of "closer". We're descending a b-ary tree, one digit at a time Not the same as "numerically closer..." Edge effects. How can we ensure every node always knows some node "closer" to any key? I.e. what's the structure of the Pastry routing table? Routing table contents Divide ID into digits One routing table row per digit position Each row contains one colum per digit value Entry refers to a node w/ same prefix, but different value for this digit "Refers" means contains ID and IP address Example. 2 bits per digit. 3 digits per ID. ID of this node: 102 022 102 223 312 102 113 122 130 100 101 102 103 This node (102) shows up in each row. There may be many choices for each entry (e.g. 021 rather than 022) We can use *any* node with the right prefix: just need to correct the digit. Note real Pastry uses 128 bit IDs, 4-bit digits. To forward with the routing table: Row index: position of highest digit in which key disagrees with our ID. Column index: value of that digit. Send query to that node. If we reach the end of the key ID, we're done: key ID == node ID. This takes log_b messages. There's a complete tree rooted at every node Starts at that node's row 0 Threaded through other nodes' row 1, &c Every node acts as a root, so there's no root hotspot This is *better* than simply arranging the nodes in one tree But what if no node exists for a particular routing table entry? There are more possible IDs than there are nodes. So we won't be able to fill all routing table entries. E.g. maybe node 103 does not exist. Indeed, only log_b(N) rows are likely to exist. We can't correct digits: what do we do now? Forward to a node that's numerically closer. We may happen to know one in our routing table. What if routing table contains no numerically closer node? Perhaps we are the right node! But maybe not -- maybe node closest to key doesn't share many bits with us. So it isn't in our table. Suppose 113, 122, and 130 didn't exist. Key 123. Prefix routing might find node 103. But there may be a node 200, which is numerically closer to 123. How can we know if we're closest, or forward to closest? Easy if each node knows its numeric neighbor nodes. Each node maintains a "leaf set" Refers to the L nodes with numerically closest IDs. L/2 of them on each side of us. Now we can tell if node on other side of key is numerically closer. So node 103 would know about node 200. That's the complete routing story.