Peer to Peer Networks
P2P is an overlay network
l That is, a logical network
Copyright By PowCoder代写 加微信 powcoder
l E.g.,your“neighbor”isJoeBiden
l P2P = decentralized = no one, even the inventor, can dominate
l Unstructured P2P file sharing network l Apeercandecidewhichfilesithosts
n E.g., Napster, Gnutella, Gossip, Kazaa l Findingafilethusrequiresflooding
l Structured P2P file sharing network l Havetofollowrulestoholdfiles
l E.g.,DistributedHashTable(DHT)
n Use a variant of consistent hashing to map a file to a particular set of peers
l A kind of hashing that only K/n keys need to be remapped when the hash table size
changes (compared with traditional hashing, every key needs to be remapped)
l Standard hashing vs consistent hashing:
l KmodN(e.g.,N=#ofnodes)
l N changes? Need to remap everything
Consistent hashing (hash on an abstract circle)
uniform on the F2
F1 to s1 F2 to s1 F3 to s2 F4 to s2
F2 to s1 F3 to s2 F4 to s3
Chord – DHT (Distributed Hash Table)
l Structured P2P
l A node will store the values for all the keys for which it is responsible l Arrange the peers in a virtual/logical “circle”
n Node N8 is not necessarily close to N14 physically l Issues:
n Searching
n A peer joins n A peer leaves n A peer fails
Chord and Links
l Each node knows its logical neighbors l
l PlaceVinthelowestnodeNjsuchthatj>=h(K) n E.g.,ifh(K)=44,VgoestoN48
n E.g.,ifh(K)=64,VgoestoN1
l Basic searching (w/o links)
l E.g.,N8wantstolookupafilewhoseh(K)=54
n N8 forwards its request to N14
n N14 forwards the request to N21
n … until N56 says that I am the owner
l Notefficient
l For efficiency, in addition to neighbors, keep a finger table at each node i
l Each node stores the id of lowest node whose id is at least > i+1, i+2, i+4, i+8, … l E.g.,fingertableofN8(i.e.,i=8)
l E.g., N8 wants to search for K l Assume h(K) = 54
l It examines its finger table
n Found N42 to ask for K
l N42 finds its successor (N48) ! > 54
l It thus examines its finger table, which is N51
+8 +16 +32
74 – 64 =10
l N51 knows its next is N56, it forwards its requests to N56, which is the lowest node whose ID is > 54.
Adding a node Ni
l Ni must know one existing node Nj
l Nj helps Ni to look for the proper peer
l E.g., adding N26
l A peer can search thru the circle and tell N26’s successor is
n N26 sets its successor as N32
l Temporally the circle becomes
Adding a node N
l Nodes periodically carrying out a stabilization process l N26willthentriggerstabilization
1. Let S be the successor of N
n NsendsamessagetoS(N32)toaskitspredecessorP(N21)
l IfP=N,(normally;nonodesadded),skiptoStep4
2. If P (=N21) lies strictly between N (=N26) and S (=N32)
l then N regards P (=N21) as its successor
l [In this example, we do nothing because the if-condition is invalid]
3. Let S’ be the current successor of N l S’=N32inthisex.
l IfthepredecessorofS’isNilorN(=N26)liesstrictlybetweenS’(=N32)anditspredecessor(=N21) n ThenNsendsamessagetoaskS’(=N32)tosetitspredecessorbeN(=N26)
l In ex. , N32 predecessor is set = N26
4. S’ gives N the data that it should be responsible
l Thatis,all(K,V)whosekeyshashto22to26aremovedfromN32toN26
Adding a node N
l Note: the circle has not stabilized, since N21 and others’ finger tables have not updated yet
l For N21,
l Step1.S=N32
l Step2.N26liesstrictlybetweenN21andN32 n Then N21 regards N26 as successor
l Step3.SinceN26’spredecessorisNil,wemakeN21asthepredecessorofN26.
When a node leaves
l 1. Notifies its predecessor and successor that it is leaving, so they become each other’s predecessor and successor
l 2. Transfers its data to its successor
l [Finger tables have to be recomputed during a stabilization phase]
When a peer fails
l If fail suddenly, data lost! l Replication
n Replicate the data on each node’s predecessor and successor l Cluster nodes into groups (of say 3 or more nodes)
l Nodes in the group are equivalent and can replace each other
l When cluster is too large/small, can split/merge the cluster into two clusters
Unstructured vs. Structured
l Unstructured:
l Resilient to high churn rate
l Lookup? Flooding like / Gossip like -> slower
l Structured:
l Pointers to file need to be updated due to churn l Lookup is faster
l Consistent hashing now heavily used in cloud systems l E.g.,AmazonDynamo
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com