Slide 1Two types of P2P SystemsDHT=Distributed Hash TableComparative PerformanceSlide 5ChordRing of peersPeer pointers (1): successorsPeer pointers (2): finger tablesWhat about the files?Mapping FilesSearchSlide 13Slide 14AnalysisAnalysis (contd.)Search under peer failuresSlide 18Slide 19Search under peer failures (2)Slide 21Need to deal with dynamic changesNew peers joiningNew peers joining (2)New peers joining (3)Experimental ResultsLookupsFault-toleranceWrap-up NotesSummaryMidterm ExamNext WeekOptional SlidesStabilization ProtocolIndranil Gupta (Indy)September 23, 2010Lecture 10Peer-to-peer Systems IIReading: Chord paper on website (Sec 1-4, 6-7) 2010, I. GuptaComputer Science 425 Distributed SystemsCS 425 / CSE 424 / ECE 428Fall 20102Systems that work well in practice but with no big/famous names• Non-academic P2P systemse.g., Gnutella, Napster (previous lecture)Systems with big/famous namesfrom academia, with varied uses• Academic P2P systemse.g., Chord (this lecture)Two types of P2P Systems3DHT=Distributed Hash Table•A hash table allows you to insert, lookup and delete objects with keys•A distributed hash table allows you to do the same in a distributed setting (objects=files)•DHT also sometimes called a key-value store when used within a cloud •Performance Concerns:–Load balancing–Fault-tolerance–Efficiency of lookups and inserts•Napster, Gnutella, FastTrack are all DHTs (sort of)•So is Chord, a structured peer to peer system that we study next4Comparative PerformanceMemory LookupLatency#Messagesfor a lookupNapster O(1)(O(N)@server)O(1) O(1)Gnutella O(N) O(N) O(N)5Comparative PerformanceMemory LookupLatency#Messagesfor a lookupNapster O(1)(O(N)@server)O(1) O(1)Gnutella O(N) O(N) O(N)Chord O(log(N)) O(log(N)) O(log(N))6Chord•Developers: I. Stoica, D. Karger, F. Kaashoek, H. Balakrishnan, R. Morris, Berkeley and MIT•Intelligent choice of neighbors to reduce latency and message cost of routing (lookups/inserts)•Uses Consistent Hashing on node’s (peer’s) address–SHA-1(ip_address,port) 160 bit string –Truncated to m bits–Called peer id (number between 0 and )–Not unique but id conflicts very unlikely–Can then map peers to one of logical points on a circlem212 m7Ring of peersN80N112N96N160Say m=7N32N456 nodes8Peer pointers (1): successorsN800Say m=7N32N45N112N96N16(similarly predecessors)9Peer pointers (2): finger tablesN8080 + 2080 + 2180 + 2280 + 2380 + 2480 + 2580 + 260Say m=7N32N45ith entry at peer with id n is first peer with id >= n 2i(mod2m)N112N96N16i ft[i]0 961 962 963 964 965 1126 16Finger Table at N8010What about the files?•Filenames also mapped using same consistent hash function–SHA-1(filename) 160 bit string (key)–File is stored at first peer with id greater than its key (mod ) •File cnn.com/index.html that maps to key K42 is stored at first peer with id greater than 42–Note that we are considering a different file-sharing application here : cooperative web caching–The same discussion applies to any other file sharing application, including that of mp3 files.2m11Mapping FilesN800Say m=7N32N45File with key K42 stored hereN112N96N1612SearchN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereWho has cnn.com/index.html?(hashes to K42)N112N96N1613SearchN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereAt node n, send query for key k to largest successor/finger entry <= kif none exist, send query to successor(n) N112N96N16Who has cnn.com/index.html?(hashes to K42)14SearchN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereAt node n, send query for key k to largest successor/finger entry <= kif none exist, send query to successor(n) All “arrows” are RPCsN112N96N16Who has cnn.com/index.html?(hashes to K42)15AnalysisSearch takes O(log(N)) timeProof –(intuition): at each step, distance between query and peer-with-file reduces by a factor of at least 2 (why?)Takes at most m steps: is at most a constant multiplicative factor above N, lookup is O(log(N)) –(intuition): after log(N) forwardings, distance to key is at most (why?)Number of node identifiers in a range of is O(log(N)) with high probability (why? SHA-1!)So using successors in that range will be okNm/2Nm/2m2HereNext hopKey16Analysis (contd.)•O(log(N)) search time holds for file insertions too (in general for routing to any key)–“Routing” can thus be used as a building block for•All operations: insert, lookup, delete•O(log(N)) time true only if finger and successor entries correct•When might these entries be wrong?–When you have failures17Search under peer failuresN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXXXLookup fails (N16 does not know N45)N112N96N16Who has cnn.com/index.html?(hashes to K42)18Search under peer failuresN800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXOne solution: maintain r multiple successor entriesIn case of failure, use successor entriesN112N96N16Who has cnn.com/index.html?(hashes to K42)19Search under peer failures•Choosing r=2log(N) suffices to maintain lookup correctness w.h.p.–Say 50% of nodes fail–Pr(at given node, at least one successor alive)=–Pr(above is true at all alive nodes)=2log211)21(1NN1)11(212/2NNeN20Search under peer failures (2)N800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXXLookup fails (N45 is dead)N112N96N16Who has cnn.com/index.html?(hashes to K42)21Search under peer failures (2)N800Say m=7N32N45File cnn.com/index.html with key K42 stored hereXOne solution: replicate file/key at r successors and predecessorsN112N96N16K42 replicatedK42 replicatedWho has cnn.com/index.html?(hashes to K42)22Need to deal with dynamic changesPeers fail•New peers join•Peers leave–P2P systems have a high rate of churn (node join, leave and failure)•25% per hour in Overnet (eDonkey)•100% per hour in Gnutella•Lower in managed clusters, e.g., CSIL•Common feature in all distributed systems, including cloudsSo, all the time, need to: Need to update successors and fingers, and copy keys23New peers joiningN800Say m=7N32N45N112N96N16N40Introducer directs N40 to N45 (and N32)N32 updates successor to N40N40 initializes successor to N45, and inits fingers from itN40 periodically talks to its neighbors to update finger tableStabilization Protocol(followed byall nodes)24New peers
View Full Document
Unlocking...