●●●● ●●●● ●●●● ●●●● Idea: hash tables ●0●● ●●●● a hash table associates data with keys lookup(key)→data hash table insert(key, data) 0 Key is hashed to find bucket in hash table key hash function >pos 3 Each bucket is expected to Beatles" h(key) %N 1 hold #items/#buckets items hash bucket e In a distributed hash table (DHT), nodes are the hash buckets Key is hashed to find lookup(key)→data responsible peer node insert(key, data) Data and load are balanced key hash function >pos across nodes " Beatles h(key)%N N-1 node Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 6 Idea: Hash Tables ⚫ A hash table associates data with keys ⚫ Key is hashed to find bucket in hash table ⚫ Each bucket is expected to hold #items/#buckets items ⚫ In a Distributed Hash Table (DHT), nodes are the hash buckets ⚫ Key is hashed to find responsible peer node ⚫ Data and load are balanced across nodes key pos 0 hash function 1 2 N-1 3 ... x y z lookup (key) → data insert (key, data) “Beattles” 2 hash table hash bucket h(key)%N 0 1 2 ... node key hash function pos lookup (key) → data insert (key, data) “Beattles” 2 h(key)%N N-1
●●●● ●●●● ●●●● ●●●● DHTS: Problems ●●●● ●●●● Problem 1(dynamicity): adding or removing nodes With hash mod N, virtually every key will change its location! hk)modm≠h(kmod(m+1)≠h(Kmod(m-1) Solution: use consistent hashing Define a fixed hash space All hash values fall within that space and do not depend on the number of peers(hash bucket) Each key goes to peer closest to its ID in hash space (according to some proximity metric Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 7 DHTs: Problems ⚫ Problem 1 (dynamicity): adding or removing nodes ⚫ With hash mod N, virtually every key will change its location! h(k) mod m ≠ h(k) mod (m+1) ≠ h(k) mod (m-1) ⚫ Solution: use consistent hashing ⚫ Define a fixed hash space ⚫ All hash values fall within that space and do not depend on the number of peers (hash bucket) ⚫ Each key goes to peer closest to its ID in hash space (according to some proximity metric)
●●●● ●●●● ●●●● ●●●● DHTS: Problems(cont'd) ●0●● ●●●● o Problem 2(size): all nodes must be known to insert or lookup data e Works with small and static server populations Solution: each peer knows of only a few neighbors Messages are routed through neighbors via multiple hops(overlay routing) Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 8 DHTs: Problems (cont’d) ⚫ Problem 2 (size): all nodes must be known to insert or lookup data ⚫ Works with small and static server populations ⚫ Solution: each peer knows of only a few “neighbors” ⚫ Messages are routed through neighbors via multiple hops (overlay routing)
●●●● ●●●● ●●●● ●●●● What Makes a Good DHT Design ●●●● ●●●● For each object, the node(s) responsible for that object should be reachable via a" path(small diameter) The different DHTs differ fundamentally only in the routing approach The number of neighbors for each node should remain reasonable(small degree) DHT routing mechanisms should be decentralized(no single point of failure or bottleneck Should gracefully handle nodes joining and leaving o Repartition the affected keys over existing nodes Reorganize the neighbor sets Bootstrap mechanisms to connect new nodes into the dht To achieve good performance, DHT must provide low stretch Minimize ratio of DHT routing Vs. unicast latency Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 9 What Makes a Good DHT Design ⚫ For each object, the node(s) responsible for that object should be reachable via a “short” path (small diameter) ⚫ The different DHTs differ fundamentally only in the routing approach ⚫ The number of neighbors for each node should remain “reasonable” (small degree) ⚫ DHT routing mechanisms should be decentralized (no single point of failure or bottleneck) ⚫ Should gracefully handle nodes joining and leaving ⚫ Repartition the affected keys over existing nodes ⚫ Reorganize the neighbor sets ⚫ Bootstrap mechanisms to connect new nodes into the DHT ⚫ To achieve good performance, DHT must provide low stretch ⚫ Minimize ratio of DHT routing vs. unicast latency
●●●● ●●●● ●●●● ●●●● DHT Interface ●●●● ●●●● Minimal interface(data-centric Lookup(key)->IP address Supports a wide range of applications, because few restrictions o Keys have no semantic meaning o value is application dependent o dhTs do not store the data o Data storage can be build on top of DhTS Lookup(key)→data Insert(key, data) Peer-to-Peer Networks -P. Felber
Peer-to-Peer Networks — P. Felber 10 DHT Interface ⚫ Minimal interface (data-centric) Lookup(key) → IP address ⚫ Supports a wide range of applications, because few restrictions ⚫ Keys have no semantic meaning ⚫ Value is application dependent ⚫ DHTs do not store the data ⚫ Data storage can be build on top of DHTs Lookup(key) → data Insert(key, data)