[SOLVED] ECS656U/ECS796P

ECS656U/ECS796P
Distributed Systems

What this lecture is about

Copyright By Assignmentchef assignmentchef

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: 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: 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

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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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<35Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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<35Who is the closest Peer withID<35?Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor the other peers! 48update(target= 32, new-peer=2)Chord: joining the networkSteps 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=3332+2″ mod64=3432+2# mod64=3632+2$ mod64=4032+2% mod64=4832+2& mod64=0Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor the other peers! 48update(target= 32, new-peer=2)32+2! mod64=3332+2″ mod64=3432+2# mod64=3632+2$ mod64=4032+2% mod64=4832+2& mod64=0 Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor the other peers! 48 Now Peer 3 is fine! But, Peer 2 might not be! Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor the other peers! 48 do not propagate update further, i.e., to peer 416+2! mod64=1716+2″ mod64=1816+2# mod64=2016+2$ mod64=2416+2% mod64=3216+2& mod64=48 no update needed Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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<51We already checked the area related to ID<35wheni=5 Chord: joining the networkSteps to trigger update: Notify succ/pred pointers Safe to move resource mapping Now? Trigger finger tables updatefor 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 (contd)
Its 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: 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
put(K14, V14)
Master/Directory
N1 N2 N3 N50

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
put(K14, V14)
put(K14, V14)
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
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
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
put(K14, V14)
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: assignmentchef QQ: 1823890830 Email: [email protected]