程序代写 ECS656U/ECS796P

ECS656U/ECS796P
Distributed Systems

What this lecture is about

• Joining/Leaving in DHTs
• Key-Value store • Memcached
(thanks to prof. Stoica)

What have we seen so far?
• P2Pnetworksintroduction
• Three basic architectures for locating and distributing content
• Centralized directory (Napster, early BitTorrent)
• Query flooding (Gnutella)
• Hierarchical and non-hierarchical overlay designs (Kazaa, BT DHT)
• WefinishedlookingatDHTsandhowtolocatecontent

This was the last slide: Chord (finger tables) analysis on lookup
Each node stores a subset of successors:
• O(log N) memory
The search space is halved at each hop:
• O(logN)communication
More robust: unless the authority peer of the key ID fails, lookup operations work correctly
simple algorithm
simple algorithm++
memory O(N)
communication overhead O(1) O(N)

The fundamentals of P2P: the Chord example
localization
how to find a resource?
how to enter a P2P network?
distribution
how to distribute resources?
how to leave a P2P network?

Chord: joining the network
A peer that wants to joint the DHT:

Chord: joining the network
A peer that wants to joint the DHT: • computes its own id
• computes its own finger table
2+2! mod64=3
2+2″ mod64=4
2+2# mod64=6
2+2$ mod64=14
2+2% mod64=30
2+2& mod64=46

Chord: joining the network
A peer that wants to joint the DHT: • computes its own id
• computes its own finger table
peer 4 has authority over 3
2+2! mod64=3
2+2″ mod64=4
2+2# mod64=6
2+2$ mod64=14
2+2% mod64=30
2+2& mod64=46

Chord: joining the network
A peer that wants to joint the DHT: 2 • computes its own id peer 7
• computes its own finger table
• ask any peer who has authority

Chord: joining the network
A peer that wants to joint the DHT: 2 • computes its own id peer 7
• computes its own finger table
• ask any peer who has authority
peer 4 has authority over 2

Chord: joining the network
A peer that wants to joint the DHT:
• computes its own id
• computes its own finger table
• ask any peer who has authority over id
• Trigger updates of the others’ tables without creating anomalities!

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
2 is closer than 60 à notify(8)

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
periodically notify peer 4

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
2 is closer than 60 à notify(2)

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
• Safe to move resource mapping

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
• Safe to move resource mapping
• Now? Trigger finger tables update
for the other peers! 48

Chord: joining the network
Steps to trigger update:
• Notify succ/pred pointers
• Safe to move resource mapping
• Now? Trigger finger tables update
for the other peers! 48
• Peer 7 has authority over [61,2]
• Finger table has 6 entries (0 < i < 5) • i= 5 means PeerID+25 = PeerID + 32 • Who are the Peers that might fall in Peer 7 authority field for i= 5 ? Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • Peer 7 has authority over [61,2] • Finger table has 6 entries (0 < i < 5) • i= 5 means PeerID+25 = PeerID + 32 • Who are the Peers that might fall in Peer 7 authority field for i= 5 ? 60 < (PeerID + 32) mod64 < 3 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • Peer 7 has authority over [61,2] • Finger table has 6 entries (0 < i < 5) • i= 5 means PeerID+25 = PeerID + 32 • Who are the Peers that might fall in Peer 7 authority field for i= 5 ? 60<(35+32)mod64<3 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • Peer 7 has authority over (61,2) • Finger table has 6 entries (0 < i < 5) • i= 5 means PeerID+25 = PeerID + 32 • Who are the Peers that might fall in Peer 7 authority field for i= 5 ? If PeerID = 35, then (35+32)mod64 = 3, which is Peer 4. So, the Peers we are looking for haveID<35 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • Peer 7 has authority over (61,2) • Finger table has 6 entries (0 < i < 5) • i= 5 means PeerID+25 = PeerID + 32 • Who are the Peers that might fall in Peer 7 authority field for i= 5 ? If PeerID = 35, then (35+32)mod64 = 3, which is Peer 4. So, the Peers we are looking for haveID<35 Who is the closest Peer withID<35? Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 update(target= 32, new-peer=2) Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! update(target= 32, new-peer=2) 32+2! mod64=33 32+2" mod64=34 32+2# mod64=36 32+2$ mod64=40 32+2% mod64=48 32+2& mod64=0 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 update(target= 32, new-peer=2) 32+2! mod64=33 32+2" mod64=34 32+2# mod64=36 32+2$ mod64=40 32+2% mod64=48 32+2& mod64=0 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • Now Peer 3 is fine! • But, Peer 2 might not be! Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! • Now Peer 3 is fine! • But, Peer 2 might not be! • Peer 3 sends a message to Peer 2 to warn a potential Finger table update! update(16,2) Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 do not propagate update further, i.e., to peer 4 16+2! mod64=17 16+2" mod64=18 16+2# mod64=20 16+2$ mod64=24 16+2% mod64=32 16+2& mod64=48 no update needed Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? 60 < (PeerID + 16) mod64 < 3 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! 48 • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? 60<(51+16)mod64<3 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? If PeerID = 51, then (51+16)mod64 = 3, which is Peer 4. So, the Peers we are looking for haveID<51 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? If PeerID = 51, then (51+16)mod64 = 3, which is Peer 4. So, the Peers we are looking for haveID<51 We already checked the area related to ID<35wheni=5 Chord: joining the network Steps to trigger update: • Notify succ/pred pointers • Safe to move resource mapping • Now? Trigger finger tables update for the other peers! • The case i = 5 now completed!!! • What about i = 4 now? • i=4meansPeerID+24=PeerID+16 • Who are the Peers that might fall in Peer 7 authority field for i= 4 ? We are looking for Peers thathave34 The value is stored in a database in the form of a two-value tuple. One is the identifier(key) and other is the actual data(Value), and hence it is called as Key Value Store.

The key-value abstraction
• (twitter.com): user ID –> user profile (e.g., posting history, photos, friends..)
• (amazon.com): item number –> information about it
• (kayak.com): flight number –> information about flight (e.g., availability)
• (yourbank.com): account number –> information about it

The key-value abstraction (cont’d)
• It’s a dictionary data-structure
• But distributed. (Too much data, you can maintain them in a single server)
• Sound familiar? Here the connection with DHTs!
• It is not surprising that key-value stores reuse many techniques from DHTs

Too much data to maintain in a single server
Key Idea: partition set of key-values across many machines
key, value

Challenges
• Fault Tolerance: handle machine failures without losing data and without degradation in performance
• Scalability:
• Need to scale to thousands of machines
• Need to allow easy addition of new machines
• Consistency: maintain data consistency in face of node failures and message losses

Directory-based architecture: recursive query
• Have a node maintain the mapping between keys and the machines (nodes) that
store the values associated with the keys. • Having the master to relay the requests
Master/Directory
N1 N2 N3 N50

Directory-based architecture: iterative query
• Have a node maintain the mapping between keys and the machines (nodes) that
store the values associated with the keys.
• Return node to requester and let requester contact node
put(K14, V14)
Master/Directory
N1 N2 N3 N50

Directory-based architecture: iterative query
• The same solution applies also to retrieve a value… get(K14)
Master/Directory
N1 N2 N3 N50

Directory-based architecture: iterative query
• The same solution appli

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts