Distributed Systems – DHT, DTD, DDD
1
56
lookup(54) 8 distributed systems
54
51
48
42
38
14
21
SEMESTER 2, 2020
32
Life Impact The University of Adelaide Distributed Hash Tables & Distributed Termination and Deadlock Detection
Slide 0 ©2020 University of Adelaide
24
10
30
Distributed Systems – DHT, DTD, DDD
Previously
• P2P
– Decentralised systems with mostly-peer relationships – Attempt to avoid central points of failure (or regulation!)
• BitTorrent
– Data-transfer discussed briefly in Lecture 6
– Each torrent has central tracker: “who has the data?” – Requires torrent-file: metadata, big list of hashes
– How do you do a metadata-search?
Slide 1 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Today…
• Distributed Hash Tables (DHT) – … as applied to P2P filesharing
• Distributed Termination Detection (DTD)
• Distributed Deadlock Detection (DDD)
Slide 2 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Resource discovery in P2P
• Peer-to-peer (P2P) refers to a distributed system that facilitates resource sharing where:
– Resources are owned by many administrative domains (i.e. decentralized)
– Each node can be server or client – Self-organizing overlay network
• Applications based on a P2P architecture: file sharing, content distribution network, computational grid, etc.
Slide 3 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Classification of P2P Lookup
P2P Lookup Scheme
Centralized
• Napster (1999) •…
Decentralized
Unstructured
• Gnutella (2000)
• FastTrack/KaZaA (2001) •…
Structured (DHT)
• Chord (2001)
• CAN (2001)
• Pastry (2001)
• Tapestry (2001) • P-Grid (2001)
• Viceroy (2002) • Tornado (2003) • SkipNet (2003) • R-DHT (2005) • BT = Kademlia
Life Impact The University of Adelaide
Slide 4
©2020 University of Adelaide
Distributed Systems – DHT, DTD, DDD
Centralized Lookup
I have 1.mp3
A
• Effective
– central entity, e.g. directory server,
indexes all resources • Efficient
Who has 1.mp3?
A, B
C
Retrieve a.mp3
E
I have 1.mp3
– One-hop lookup
Not scalable
Single point of failure
Slide 5
Life Impact The University of Adelaide
B D
Main motivation for decentralized scheme
©2020 University of Adelaide
• •
1
1
–
Napster was terminated
in July 2001 due to legal action
Distributed Systems – DHT, DTD, DDD
Decentralized: Unstructured P2P
• Each node stores its own data item (i.e. local indexing)
• Flooding: brute-force undirected search
• Reduce lookup overhead using randomized or heuristic flooding
– Can miss some data items
• A bit naïve, ineffective, inefficient
Slide 6 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Unstructured P2P with Centralized Tracker – BitTorrent
Improving file download effectiveness (throughput) by
• File sharing (swarming)
– Distribute pieces of a file among peers (swarm)
– A peer joins a swarm by asking the tracker for a peer list and connects to those peers.
– Share file among peers in the swarm (download replica)
• Centralized tracker (coordinator)
– Collects information on all peers in the swarm – Responds to requests for that information
• Built-in fairness incentive
– Rechoking favors cooperative peers
Slide 7 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Example: File download in BitTorrent (1)
Slide 8
peer peer
©2020 University of Adelaide
peer peer
peer
peer (downloader)
.torrent (metadata, tracker)
Life Impact The University of Adelaide
peer peer
Distributed Systems – DHT, DTD, DDD
Example: File download in BitTorrent (2)
Slide 9 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Decentralized: Structured P2P
– Distributed Hash Table
Improve lookup efficiency by
•
Distributed Hash Table
– map “keys” to “values” (nodes)
– store (key, value) at the node with index “value”
– support lookup and update operations
– Fast: close to O(1) operation for sparse data
Structured overlay network: topology + node ordering
– Routing to a node in short bounded path length
– Node maintains a small number of routing states (routing table size)
Usual desirables: scalability, fault tolerance
– short bounded lookup path length
– minimum probability of data loss
Slide 10 ©2020 University of Adelaide Life Impact The University of Adelaide
• •
Distributed Systems – DHT, DTD, DDD
P2P Lookup Modes
Property
Centralized
Decentralized
Unstructured
DHT
Data-item distribution
Yes
Optional
Yes (+mapping)
Single point of failure
Yes
Minimized
Minimized
Result guarantee
High
High for popular data items only
High
Lookup path length
One hop
Θ(N)
O(log N) hops
Scalability of Lookup
No / $$$
Trade-off with result guarantee
Yes
Overhead of maintaining overlay
None
Low
High
Slide 11 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Example DHT Protocols
– Content Addressable Network (CAN)
– Pastry
– Tapestry
– Chord
– Kademlia / Mainline (BitTorrent)
– Koorde
– P-Grid
etc
Slide 13 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Use of Hashing
• Cryptographic Hashes used to decide object location(s) – Uniform output distribution
– Hard to find collisions
• Consistent Hashing
– Nodes (n) and keys (k) in one global hash-output space
(k/n keys are remapped when n changes – invariant)
– Each node responsible for some region of keys in hash-space
– Storekatnodenwithsmallestdistance(H(k),H(n))
• Rendezvous Hashing
– Highest Random Weight hashing
– Spread k/n keys out over all other buckets evenly
• Consider implications when a node is lost…
Slide 14 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Overlay Network
How do we discover other nodes?
• Internet-sized routing table on every node? (degree N, diameter 1)
• Remember direct neighbours only? (degree 1, diameter N)
• Pick a better, middling tradeoff
– – –
Slide 15
e.g. one entry per bit of address space degree log(N), diameter log(N)
Each route hop effectively bisects address-space, gets always “closer” to storage node in hash-space
©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Chord (2001) : a relatively-simple DHT
• Each node has m-bit id that is a SHA-1 hash (m=160 bits) of its IP address
• Nodes are arranged in a circle modulo m
• Data is hashed to an id (key) in the same id space
• Node n stores data with id between n and n’s predecessor clock-wise
– 0 stores data of 4-0
– 1 stores data of 1
– 3 stores data of 2-3
n is the successor of all the stored data’s ids
0 71
6
predecessor
churn
3
successor
5
4
m=3
Slide 17 ©2020 University of Adelaide Life Impact The University of Adelaide
2
Distributed Systems – DHT, DTD, DDD
Chord – finger table
• For fast lookup, nodes maintain a finger table with more routing information
– For a node n, the ith entry in its finger table is the first node that succeeds n by at least 2i-1
• Size of finger table?
n+2i-1
succ(n+2i-1)
i
1
1
2
3
4
0
2
3
3
3
5
0
0 71
62
5
4
3
4
0
5
0
7
0
Slide 18 ©2020 University of Adelaide
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Chord – finger table
• For fast lookup, nodes maintain a finger table with more routing information
– For a node n, the ith entry in its finger table is the first node that succeeds n by at least 2i-1
• Size of finger table? O(logN) or O(m)
n+2i-1
succ(n+2i-1) i
0 71
62
1
1
2
3
4
0
2
3
3
3
5
0
5
4
3
4
0
5
0
7
0
Slide 19 ©2020 University of Adelaide
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Chord – lookup
lookup:
hash key to get id
if id == node id – data found
else if id in finger table – data found
else 6 2
1
1
2
3
4
0
2
3
3
3
5
0
0 71
choose p in finger table closest to id if p < id < successor(p)
return successor(p) else
ask n= successor(p) for finger entry closest to id and recurse
5
4
3
4
0
5
0
7
0
Slide 20 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Example: lookup(54) at node 8
Finger table (8)
8+1
14
8+2
14
8+4
14
8+8
21
8+16
32
8+32
42
56
1
lookup(54) 8
+1 +2
+4
14
+8
51
48
42
+32
21
+16
38
24
10
32
30
Slide 21
©2020 University of Adelaide
Life Impact The University of Adelaide
54
Distributed Systems – DHT, DTD, DDD
Chord – lookup time
• Running time of lookup(id)?
0 71
62
1
1
2
3
4
0
2
3
3
3
5
0
– Worst case: Problem size halved at each iteration
logN hops
to locate the finger table
containing id
5
4
3
4
0
5
0
7
0
Slide 22
©2020 University of Adelaide
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Chord – insert (put)
• Insert new node n*
– initialize n* (predecessor
0 71
1
1
2
3
4
6
2
3
3
3
5
6
7
0
0
0
2
3
and finger table)
– update fingers of existing 6 nodes and predecessor
of successor(n*)
– transfer (split) data (churn)
2
5
4
3
4
6
5
6
7
0
Slide 23
©2020 University of Adelaide
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Chord – insert (put)
• Initialization
1
1
2
3
4
6
– –
find p=predecessor(n*) =predecessor(successor(n*))
for each entry n (=n*+2i-1) in n*’s finger table
2
3
3
3
5
6
7
0
0
0
2
3
find successor(n) Running time - O(mlogN) (with high probability)
– Optimization – initialize n*’s finger table by updating from its immediate neighbors
Reduce running time to O(logN)
• Finger table update at other nodes – for each entry n
change successor(n) to n* if predecessor(n*)
Slide 53 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Dijkstra-Scholten Algorithm
The invariants must hold when an interim node sends an ack. So, acks will be sent when
(C-1 ≥ 0) (C-1 > 0 D=0) {follows from INV1 and INV2}
= (C>1)(C≥1D=0) = (C>1)(C=1D=0)
Slide 54 ©2020 University of Adelaide
initiator
0
C=1
1
D=2-1=1
2 ack 3
passive
4 5
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Dijkstra-Scholten Algorithm
Initiator (r): C=0, D=1, m=signal, state:= active; parent:=r
do {for an internal node i}
m=signal(C=1)state=active
send signal to (k) children, D:=D+k, parent:=i;
{send signals down to poll other nodes}
m=ack D:=D-1;
(C=1 D=0) state = passive
send ack to parent; C:= 0; i:=parent {send acks up to obtain global status }
initiator
0
ack
1 23
45
If m = ack i=r then output:=termination
Slide 55 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Mattern’s Credit Recovery
• Another instance of Doomsday; published 1989
– Each process holds credit, starting with 1.0 at the root
– Sum of all credit (in processes and messages), at all times, is 1.0
– Some credit must be sent within each activation message
– Terminating process returns all its credit towards the root
– Termination = all credit has been recovered at the root
• Similar to Dijkstra-Scholten
– Credit-return path is not constrained to the tree
Slide 56 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Distributed deadlock
Assume each process owns a few resources. Review how resources are allocated.
Why deadlocks occur?
– Exclusive (i.e not shared) resources
– Non-preemptive scheduling
– Circular waiting by all or a subset of processes
May occur due to bad designs/bad strategy
Slide 57 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Distributed deadlock
Two ways of handling deadlock
– deadlock prevention
– deadlock detection & recovery
Prevention is more expensive than detection and recovery. So designers may not care about deadlocks, particularly if they are rare.
Slide 58 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
• • •
Wait-for Graph (WFG)
Represents who waits for whom.
No single process can see the WFG. Review how the WFG is formed.
Slide 59 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Another classification
• Resource deadlock
[R1 AND R2 AND R3 …] also known as AND deadlock (all resources)
• Communication deadlock [R1 OR R2 OR R3 …]
also known as OR deadlock
(at least one resource – “channel”)
Slide 60 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
(Distributed) Detection of resource deadlock
Notations
w(j) = true (j is waiting) depend [j,i] = true
j succn(i) (n>0) P(i,s,k) is a probe
(i=initiator, s= sender, k=receiver)
1
2
3
4
P(4,4,3)
initiator
Slide 61 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Detection of resource deadlock
{Program for process k} doP(i,s,k) received
w[k] (k ≠ i) ¬ depend[k, i] send P(i,k,j) to each successor j;
depend[j, i]:= true
P(i,s, k) received w[k] (k = i)
process k is deadlocked
od
Slide 62 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Observations
To detect deadlock, the initiator must be in a cycle
Message complexity = O(|E|)
(edge-chasing algorithm)
E=set of edges
Should the links be FIFO?
Slide 63 ©2020 University of Adelaide
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Communication deadlock
This has a resource deadlock but no communication deadlock
Slide 64 ©2020 University of Adelaide Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Communication deadlock
This has a resource deadlock but no communication deadlock
Slide 65 ©2020 University of Adelaide Life Impact The University of Adelaide
OR
Distributed Systems – DHT, DTD, DDD
Detection of communication deadlock
A process ignores a probe, if it is not waiting for any process. Otherwise,
• first probe
mark the sender as parent;
forwards the probe to successors
• Not the first probe
forward the probe to waiting
successors; update parent.
• ack received from every successor send ack to the parent
Communication deadlock is detected
if the initiator receives ack. Slide 66 ©2020 University of Adelaide
Has many similarities with Dijkstra-Scholten’s termination detection algorithm
Life Impact The University of Adelaide
Distributed Systems – DHT, DTD, DDD
Summary
• Evaluating distributed predicates is hard
• Stable conditions can be detected eventually
• Distributed deadlocks: AND vs OR – circular waiting (necessary condition)
• Distributed deadlock detection
– no central site maintaining resource allocation graph – distributed edge chasing similar to diffusion of DTD
Slide 67 ©2020 University of Adelaide Life Impact The University of Adelaide