Pastry: Scalable, Decentralized Object Location and Routing For Large-Scale Peer-To-Peer Systems
Pastry: Scalable, Decentralized Object Location and Routing For Large-Scale Peer-To-Peer Systems
Pastry: Scalable, Decentralized Object Location and Routing For Large-Scale Peer-To-Peer Systems
Distribution
Decentralized control
Self-organization
Symmetry (communication, node roles)
Common Issues in P2P
Organize, maintain overlay network
P2P substrate
(self-organizing
Pastry, CAN, Chord
overlay network)
TCP/IP Internet
Distributed Hash Tables (DHT)
nodes
k1,v1 k2,v2 k3,v3
Operations: P2P
P2P
insert(k,v) overlay k4,v4
overlay
lookup(k) network
network
k5,v5 k6,v6
Given a key,
the node efficiently routes the message to
the node whose nodeID is numerically closest
to the key
Sample NodeID Table
Leaf Set
stores numerically closest
nodeIDs
Routing Table
Total no of rows: total # of
bits in a nodeID
Total entries in a row = base
number
Neighborhood set
stores closest nodes
according to proximity
metric
Node State : Leaf Set
Size of L is typically 2b or 2 x 2b
D: Message Key
Li: ith closest NodeId in leaf set
shl(A, B): Length of prefix shared
by nodes A and B
R j: (j, i) entry of routing table
i th
Routing Table: 65a1fcx
Row 0 6
Row 1
5
Row 2
a
Row 3
1 log16 N
rows
Routing Example
d471f1 Properties:
d467c4
d462ba
d46a1c • O(log N)
d4213f routing table size
• O(log N)
Route(d46a1c) d13da3
message forwarding
steps
65a1fc
Self-organization
Initializing and maintaining routing tables and
leaf sets
Node join
A forwards to B C…
nodeID: d46a1c
d4213f
R/T Row#2
X
JOIN
Route(d46a1c) d13da3
R/T Row#1
65a1fc
Neighborhood Set
R/T Row#0
Node Departure (Failure)
Leaf set
Detection: leaf set members exchange keep-alive
messages
Repair: request set from farthest live node in set
Routing Table
Detection: when node attempts to contact the failed
node and there is no response
Repair: get table from peers in the same row, then
higher rows
Node failure in routing table: example
X joins; A is close to X; X0 = A0
so locality holds in X’s routing table
X1 = B1
Entries in B1 (row 1 of X) are close to B, but are they
necessarily close to X?
Locality in Routing Tables
Entries of B1 are reasonable close to X Why?
A is much closer to B than entry in B1 to B because every
time we choose from an exponentially decreasing set of
nodes
Given that:
A message routed from A to B at a distance d cannot be
routed to a node with a distance of less than d from A.
(follows from routing procedure)
Expected distance traveled increases exponentially
The number of
route hops scale
with the size of
network.
The maximum
route length is 5
(=ceil(log16 105))
Overlay:
A virtual d-dimensional Coordinate space
Each peer is responsible for a zone
Routing:
Each peer maintains info about neighbors
Greedy algorithm for routing
Performance Analysis:
Expected: (d/4)(n1/d) steps for lookup
d: dimension
Chord: MIT
Overlay:
Peers are organized in a ring
Successor peer
<k, value> is stored on the
successor of k
Routing:
Finger Table:
More info for close part of the
ring
Large jumps, then shorter jumps
Resembling a binary search –
distance halving
Chord Routing – naïve approach
1
I’m node 2. 15
Please find key 14! 14 2
3
How will you find
the location of
12
node 14?
Can’t
we
Hint: Use successor id 10 accelerate
stored in each node
7
lookup?
m=4
Chord Routing – with finger table Start
3
Int.
[3,4)
node
3
Finger table is used to
Ask ‘node’ for keys within range ‘interval’ 4 [4,6) 7
1 6 [6,10) 7
15
10 [10,2) 10
I’m node 2. 14 2
14 ∈[10,2)
Please find key 14!
3
12