1 Computer Communications - CSCI 551 Copyright © William C. ChengCS551Distributed Hash TablesStructured SystemsBill Chenghttp://merlot.usc.edu/cs551-f122 Computer Communications - CSCI 551 Copyright © William C. Cheng CS551Chord[Stoica01a]Bill Chenghttp://merlot.usc.edu/cs551-f123 Computer Communications - CSCI 551 Copyright © William C. Cheng Chorduses consistent hashingA structured peer-to-peer systemMap key to valueEmphasis on good algorithmic performanceO(log N) route storage, O(log N) lookup cost, O(log2N)cost to join/leavevs. FreeNet w/emphasis on anonymityEasy if static, but must deal with node arrivals and departures4 Computer Communications - CSCI 551 Copyright © William C. Cheng Compare Search in Several Peer-to-PeerSystemsmap keys to linear search spaceNapster: central search engineFreenet: search towards keys, but no guaranteesChord:keep pointers (fingers) into exponential places aroundspaceprobabilistic (depends on hashing)5 Computer Communications - CSCI 551 Copyright © William C. Cheng Hashing Nodes and Databecause this hashing is random,can expect nodes to be evenlydistributed in key spaceNodes hash IP addresses to keyspaceStore data in the successor of thedata item’s keyProperty:If each node maintainssuccessor,... can find any data itemSUCCESSOR(6)=012345670SUCCESSOR(2)=3SUCCESSOR(1)=11266 Computer Communications - CSCI 551 Copyright © William C. Cheng Hashing Nodes and Databecause this hashing is random,can expect nodes to be evenlydistributed in key spaceNodes hash IP addresses to keyspaceStore data in the successor of thedata item’s keyProperty:If each node maintainssuccessor,... can find any data itemSUCCESSOR(6)=012345670SUCCESSOR(2)=3SUCCESSOR(1)=1126Nodes have a successor pointerbut O(n) performanceat each step, we halve the remaining distance (in keyspace) to the targetChallenge: maintaining finger tables!7 Computer Communications - CSCI 551 Copyright © William C. Cheng Improving Search Performance withFinger Tablesi-th finger of node x is successor of x+2i-1Finger tables enable logarithmic lookupx x+20x+21x+22x+23x+2411 2 4 8x x+20x+21x+22x+23x+2411 2 4 8at each step, we halve the remaining distance (in keyspace) to the target8 Computer Communications - CSCI 551 Copyright © William C. Cheng Improving Search Performance withFinger Tables (Cont...)i-th finger of node x is successor of x+2i-1Finger tables enable logarithmic lookupxx+2159x+2158x+2157x+2156Ex: look for key yat each step, we halve the remaining distance (in keyspace) to the target9 Computer Communications - CSCI 551 Copyright © William C. Cheng Improving Search Performance withFinger Tables (Cont...)i-th finger of node x is successor of x+2i-1Finger tables enable logarithmic lookupxx+2159x+2158x+2157x+2156Ex: look for key yycase 1: y is just beyondx+2159forward tosuccessor(x+2159)way more than halfthe distance to ycase 2: y is just insidex+2159forward tosuccessor(x+2158)a little over halfthe distance to yat each step, we halve the remaining distance (in keyspace) to the target10 Computer Communications - CSCI 551 Copyright © William C. Cheng Improving Search Performance withFinger Tables (Cont...)i-th finger of node x is successor of x+2i-1Finger tables enable logarithmic lookupxx+2159x+2158x+2157x+2156Ex: look for key yycase 3: y is just beyondx+2158forward tosuccessor(x+2158)way more than halfthe distance to yat each step, we halve the remaining distance (in keyspace) to the target11 Computer Communications - CSCI 551 Copyright © William C. Cheng Improving Search Performance withFinger Tables (Cont...)i-th finger of node x is successor of x+2i-1Finger tables enable logarithmic lookupxx+2159x+2158x+2157x+2156Ex: look for key yyand so on...12345670124130[1,2)[2,4)[4,0)startfinger tableint. succ.6keys235330[2,3)[3,5)[5,1)startfinger tableint. succ.1keys457000[4,5)[5,7)[7,3)startfinger tableint. succ.2keysi-th finger of node x issuccessor of x+2i-112 Computer Communications - CSCI 551 Copyright © William C. Cheng Finger Tables Example7 1234560finger[1].start=2finger[1].interval=[finger[1].start,finger[2].start)finger[2].start=3finger[3].start=5finger[2].interval=[finger[2].start,finger[3].start)finger[3].interval=[finger[3].start,finger[3].1)13 Computer Communications - CSCI 551 Copyright © William C. Cheng Node Joinscan always fall back on them to find a keyMust keep successors and finger table currentUse successors for correctnessmust update it, but can tolerate temporary errorsUse finger table for performanceKeep successor and predecessor so we can update ourneighborsKey observation: can find successors and fingers by doinga lookup on the existing Chord ring!node.find_successor(key) n = find_predecessor(key); return n.successor;14 Computer Communications - CSCI 551 Copyright © William C. Cheng Finding Predecessor and Successornode.find_predecessor(key) n = node; while (key ∉ (n,n.successor]) n = n.closest_preceding_finger(key); return n;node.closest_preceding_finger(key) for (i=m; i > 0; i--) if (finger[i].node ∈ (node,key)) return finger[i].node; return node;1234567015 Computer Communications - CSCI 551 Copyright © William C. Cheng Join Examplewhen new node enters, it establishes its successor andpredecessor and then builds its finger table, and movesany keys it now "owns"12345670124130[1,2)[2,4)[4,0)startfinger tableint. succ.6keys235330[2,3)[3,5)[5,1)startfinger tableint. succ.1keys457000[4,5)[5,7)[7,3)startfinger tableint. succ.2keysbefore node 6 joins124136[1,2)[2,4)[4,0)startfinger tableint. succ.keys235336[2,3)[3,5)[5,1)startfinger tableint. succ.1keys457660[4,5)[5,7)[7,3)startfinger tableint. succ.2keysbefore node 6 joins702003[7,0)[0,2)[2,6)startfinger tableint. succ.6keys16 Computer Communications - CSCI 551 Copyright © William C. Cheng Robustnessevery 30s, ask successor for its predecessorfix your own successor based on thisStabilization algorithm to confirm ring is correctsuccessor fixes its predecessor if necessaryalso, pick and verify a random finger table entryrebuild finger table entries this wayimportant observation: finger tables can be incorrectfor some time (between network sizes of N and 2N)keep successor list of r successorsDealing with unexpected failures:can use these to replicate datapublic key17 Computer Communications - CSCI 551 Copyright © William C. Cheng Applicationssignatureroot-blockdictionaryblockDinodeblockFdata blockB1data blockB2H(D)H(F)H(B1)H(B2)File
View Full Document
Unlocking...