iKen BirmanCornell University. CS5410 Fall 2008. What is a Distributed Hash Table (DHT)?y Exactly that ☺y A service, distributed over multiple machines, with hh bl ihash table semanticsy Put(key, value), Value = Get(key)yDesigned to work in a peer‐to‐peer (P2P) environmentDesigned to work in a peertopeer (P2P) environmenty No central controly Nodes under different administrative controlB f i “i f ” yBut of course can operate in an “infrastructure” senseMore specificallyy Hash table semantics:y Put(key, value), y Value = Get(key)l fly Key is a single flat stringy Limited semantics compared to keyword searchy Put() causes value to be stored at one (or more) peer(s)G() i l f yGet() retrieves value from a peery Put() and Get() accomplished with unicast routed messagesy In other words, it scalesOth API ll t t li ti lik tifi ti h yOther API calls to support application, like notification when neighbors come and goP2P “environment”y Nodes come and go at will (possibly quite frequently‐‐‐a few minutes)Nd h h iiyNodes have heterogeneous capacitiesy Bandwidth, processing, and storageyNd bh bdlyNodes may behave badlyy Promise to do something (store a file) and not do it (free‐loaders)()y Attack the systemSeveral flavors, each with variantsy Tapestry (Berkeley)y Based on Plaxton trees‐‐‐similar to hypercube routingyThe first* DHTyThe first* DHTy Complex and hard to maintain (hard to understand too!)y CAN (ACIRI), Chord (MIT), and Pastry (Rice/MSR Cambridge)ySecond wa ve of DHTs (contemporary with and ySecond wa ve of DHTs (contemporary with and independent of each other)* Landmark Routing, 1988, used a form of DHTcalled Assured Destination Binding (ADB)Basics of all DHTsy Goal is to build some “structured” ov erla y network with the following characteristics:13111127characteristics:y Node IDs can be mapped to the hash key space3397py Given a hash key as a “destination address”, you can route through the network to a given node5881network to a given nodey Always route to the same node no matter where you start fromySimple example (doesn’t scale)y Circular number space 0 to 127y Routing rule is to move counter‐lki il d ID ≥k 13111127clockwise until current node ID ≥key, and last hop node ID < key3397y Example: key = 42yObviously you will route to node 58 5881yObviously you will route to node 58 from no matter where you startBuilding any DHTy New comer always starts with at least one known member131111273397815824Building any DHTy New comer always starts with at least one known memberN h f “lf” i h 13111127yNewcomer searches for “self” in the networkyhash key = newcomer’s node ID3397yhash key = newcomer s node IDy Search results in a node in the vicinity where newcomer needs to be815824Building any DHTy New comer always starts with at least one known memberN h f “lf” i h 13111127yNewcomer searches for “self” in the networkyhash key = newcomer’s node ID339724yhash key = newcomer s node IDy Search results in a node in the vicinity where newcomer needs to be8158y Links are added/removed to satisfy properties of networkBuilding any DHTy New comer always starts with at least one known memberyNew comer searches for “self” in the 13111127yNew comer searches for self in the networky hash key = newcomer’s node ID339724y Search results in a node in the vicinity where newcomer needs to beyLinks are added/removed to satisfy 8158yLinks are added/removed to satisfy properties of networky Objects that now hash to new node are transferred to new nodeInsertion/lookup for any DHTy Hash name of object to produce keyy Well‐known wa y to do thisk d dd13111127y Use key as destination address to route through networkyRoutes to the target node339724yRoutes to the target nodey Insert object, or retriev e object, at the target node8158gfoo.htm→93Properties of most DHTsy Memory requirements grow (something like) logarithmically with NRi h lh (hi lik ) yRouting path length grows (something like) logarithmically with NyCost of adding or removing a node grows (something yCost of adding or removing a node grows (something like) logarithmically with NyHas caching, replication, etc…Has caching, replication, etc…DHT Issuesy Resilience to failuresy Load BalanceHt ityHeterogeneityy Number of objects at each nodey Routing hot spotsg py Lookup hot spotsy Locality (performance issue)y Churn (performance and correctness issue)y SecurityWe’re going to look at four DHTsyAt varying levels of detail…y CAN (Content Addressable Network)yACIRI (now ICIR)yACIRI (now ICIR)y Chordy MITy Kelipsy CornellyPastryPastryy Rice/Microsoft CambridgeThings we’re going to look atyWhat is the structure?y How does routing work in the structure?H d it dl ith d dt?yHow does it deal with node departures?y How does it scale?yHow does it deal with locality?yHow does it deal with locality?y What are the security issues?CAN structure is acartesiancoordinateCAN structur e is a cartesiancoordinate space in a D dimensional torus1CAN graphics care of Santashil PalChaudhuri, Rice UnivSimple example in two p pdimensions1 2Nt t “t ” d “id ”Note: torus wraps on “top” and “sides”312Each node in CAN network occupiesEach node in CAN network occupies a “square” in the space3124With relatively uniform square sizesNeighbors in CAN networky Neighbor is a node that:y Overlaps d-1 dimensionsyAbuts along one Abuts along one dimensionRoute to neighbors closer to targetZ1Z2Z3Z4Zny d‐dimensional spacey n zonesZ1Z2Z3Z4…Zn(a,b)y Zone is space occupied by a “square” in one dimensionyAvg route path lengthyAvg. route path lengthy (d/4)(n 1/d)y Number neighbors = O(d)y Tunable (vary d or n)y Can factor proximity into route decision(x,y)route decisionCh d ilIDChord uses a circular ID spaceN10K5, K10Key ID Node IDN32N100CircularID SpaceK11, K30K100N32N80K11, K30K65, K70N80N60K33, K40, K52K65, K70• Successor: node with next highest IDChord slides care of Robert Morris, MITBasic LookupN10N5N110“Where is key 50?”N20N99“Key 50 isN32N40Key 50 isAt N60”N80N60N40• Lookups find the ID’s predecessor• Correct if successors are correctSuccessor Lists Ensure Robust LookupSuccessor Lists Ensure Robust LookupN10N5N11010, 20, 3220, 32, 405, 10, 20N32N20N9932, 40, 6040, 60, 80110, 5, 10N80N60N4060, 80, 9980 99 11099, 110, 5• Each node remembers r