Chord 10234b
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report r6l17
Overview 4q3b3c
& View Chord as PDF for free.
More details 26j3b
- Words: 1,506
- Pages: 25
Chord A Scalable Peer-to-peer Lookup Service for Internet Applications
CS294-4: Peer-to-peer Systems Markus Böhning [email protected]
What is Chord? What does it do?
In short: a peer-to-peer lookup service
Solves problem of locating a data item in a collection of distributed nodes, considering frequent node arrivals and departures
Core operation in most p2p systems is efficient location of data items
s just one operation: given a key, it maps the key onto a node
2
Chord Characteristics
Simplicity, provable correctness, and provable performance
Each Chord node needs routing information about only a few other nodes
Resolves lookups via messages to other nodes (iteratively or recursively)
Maintains routing information as nodes and leave the system
3
Mapping onto Nodes vs. Values
Traditional name and location services provide a direct mapping between keys and values
What are examples of values? A value can be an address, a document, or an arbitrary data item
Chord can easily implement a mapping onto values by storing each key/value pair at node to which that key maps
4
Napster, Gnutella etc. vs. Chord
Compared to Napster and its centralized servers, Chord avoids single points of control or failure by a decentralized technology
Compared to Gnutella and its widespread use of broadcasts, Chord avoids the lack of scalability through a small number of important information for rounting
5
DNS vs. Chord Chord
DNS
provides a host name to IP address mapping
can provide same service: Name = key, value = IP
relies on a set of special root servers
requires no special servers
imposes no naming structure
can also be used to find data objects that are not tied to certain machines
names reflect istrative boundaries is specialized to finding named hosts or services
6
Freenet vs. Chord
both decentralized and symmetric
both automatically adapt when hosts leave and
Freenet does not assign responsibility for documents to specific servers, instead lookups are searches for cached copies + allows Freenet to provide anonymity
− prevents guaranteed retrieval of existing documents
Chord − does not provide anonymity + but its lookup operation runs in predictable time and always results in success or definitive failure
7
Addressed Difficult Problems (1)
Load balance: distributed hash function, spreading keys evenly over nodes
Decentralization: chord is fully distributed, no node more important than other, improves robustness
Scalability: logarithmic growth of lookup costs with number of nodes in network, even very large systems are feasible
8
Addressed Difficult Problems (2)
Availability: chord automatically adjusts its internal tables to ensure that the node responsible for a key can always be found
Flexible naming: no constraints on the structure of the keys – key-space is flat, flexibility in how to map names to Chord keys
9
Example Application using Chord: Cooperative Mirroring File System Block Store
Block Store
Block Store
Chord
Chord
Chord
Client
Server
Server
Highest layer provides a file-like interface to including -friendly naming and authentication
This file systems maps operations to lower-level block operations
Block storage uses Chord to identify responsible node for storing a block and then talk to the block storage server on that node
10
The Base Chord Protocol (1)
Specifies how to find the locations of keys
How new nodes the system
How to recover from the failure or planned departure of existing nodes
11
Consistent Hashing
Hash function assigns each node and key an m-bit identifier using a base hash function such as SHA-1
ID(node) = hash(IP, Port)
ID(key) = hash(key)
Properties of consistent hashing:
Function balances load: all nodes receive roughly the same number of keys – good?
When an Nth node s (or leaves) the network, only an O(1/N) fraction of the keys are moved to a different location
12
Successor Nodes identifier node
6 1
0
successor(6) = 0
6
identifier circle
6 5
key
successor(1) = 1
1
7
X
2
2
successor(2) = 3
3 4
2
13
Node s and Departures 6 6
1
0
successor(6) = 7
1
7 6
successor(1) = 3
2 5
3 4
2 1
14
Scalable Key Location
A very small amount of routing information suffices to implement consistent hashing in a distributed environment
Each node need only be aware of its successor node on the circle
Queries for a given identifier can be ed around the circle via these successor pointers
Resolution scheme correct, BUT inefficient: it may require traversing all N nodes!
15
Acceleration of Lookups
Lookups are accelerated by maintaining additional routing information
Each node maintains a routing table with (at most) m entries (where N=2m) called the finger table
ith entry in the table at node n contains the identity of the first node, s, that succeeds n by at least 2i-1 on the identifier circle (clarification on next slide)
s = successor(n + 2i-1)
s is called the ith finger of node n, denoted by n.finger(i).node
(all arithmetic mod 2)
16
Finger Tables (1) finger table start int. 1 2 4
[1,2) [2,4) [4,0)
1
6
1 3 0 finger table start int.
0 7
succ.
keys 6
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
0 0 0
17
Finger Tables (2) - characteristics
Each node stores information about only a small number of other nodes, and knows more about nodes closely following it than about nodes farther away
A node’s finger table generally does not contain enough information to determine the successor of an arbitrary key k
Repetitive queries to nodes that immediately precede the given key will lead to the key’s successor eventually
18
Node s – with Finger Tables finger table start int. 1 2 4
[1,2) [2,4) [4,0)
finger table start int. 7 0 2
[7,0) [0,2) [2,6)
keys succ.
1
0 0 3
6
1 3 0 6 finger table start int.
0 7
succ.
keys 6
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0 6
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
6 0 6 0 0
19
Node Departures – with Finger Tables finger table start int. 1 2 4
[1,2) [2,4) [4,0)
finger table start int. 7 0 2
[7,0) [0,2) [2,6)
succ. 0 0 3
keys 6
1
6
succ. 3 1 3 0 6 finger table start int.
0 7
keys
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0 6
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
6 6 0
20
Source of Inconsistencies: Concurrent Operations and Failures
Basic “stabilization” protocol is used to keep nodes’ successor pointers up to date, which is sufficient to guarantee correctness of lookups
Those successor pointers can then be used to the finger table entries
Every node runs stabilize periodically to find newly ed nodes
21
Stabilization after
n s
pred(ns) = n
n
nil
np
succ(np) = ns
succ(np) = n
pred(ns) = np
ns
predecessor = nil n acquires ns as successor via some n’ n notifies ns being the new predecessor ns acquires n as its predecessor
np runs stabilize
np asks ns for its predecessor (now n)
np acquires n as its successor
np notifies n
n will acquire np as its predecessor
all predecessor and successor pointers are now correct
fingers still need to be fixed, but old fingers will still work
22
Failure Recovery
Key step in failure recovery is maintaining correct successor pointers
To help achieve this, each node maintains a successor-list of its r nearest successors on the ring
If node n notices that its successor has failed, it replaces it with the first live entry in the list
stabilize will correct finger table entries and successor-list entries pointing to failed node
Performance is sensitive to the frequency of node s and leaves versus the frequency at which the stabilization protocol is invoked
23
Chord – The Math
Every node is responsible for about K/N keys (N nodes, K keys)
When a node s or leaves an N-node network, only O(K/N) keys change hands (and only to and from ing or leaving node)
Lookups need O(log N) messages
To reestablish routing invariants and finger tables after node ing or leaving, only O(log2N) messages are required
24
Experimental Results
Latency grows slowly with the total number of nodes
Path length for lookups is about ½ log2N
Chord is robust in the face of multiple node failures
25
CS294-4: Peer-to-peer Systems Markus Böhning [email protected]
What is Chord? What does it do?
In short: a peer-to-peer lookup service
Solves problem of locating a data item in a collection of distributed nodes, considering frequent node arrivals and departures
Core operation in most p2p systems is efficient location of data items
s just one operation: given a key, it maps the key onto a node
2
Chord Characteristics
Simplicity, provable correctness, and provable performance
Each Chord node needs routing information about only a few other nodes
Resolves lookups via messages to other nodes (iteratively or recursively)
Maintains routing information as nodes and leave the system
3
Mapping onto Nodes vs. Values
Traditional name and location services provide a direct mapping between keys and values
What are examples of values? A value can be an address, a document, or an arbitrary data item
Chord can easily implement a mapping onto values by storing each key/value pair at node to which that key maps
4
Napster, Gnutella etc. vs. Chord
Compared to Napster and its centralized servers, Chord avoids single points of control or failure by a decentralized technology
Compared to Gnutella and its widespread use of broadcasts, Chord avoids the lack of scalability through a small number of important information for rounting
5
DNS vs. Chord Chord
DNS
provides a host name to IP address mapping
can provide same service: Name = key, value = IP
relies on a set of special root servers
requires no special servers
imposes no naming structure
can also be used to find data objects that are not tied to certain machines
names reflect istrative boundaries is specialized to finding named hosts or services
6
Freenet vs. Chord
both decentralized and symmetric
both automatically adapt when hosts leave and
Freenet does not assign responsibility for documents to specific servers, instead lookups are searches for cached copies + allows Freenet to provide anonymity
− prevents guaranteed retrieval of existing documents
Chord − does not provide anonymity + but its lookup operation runs in predictable time and always results in success or definitive failure
7
Addressed Difficult Problems (1)
Load balance: distributed hash function, spreading keys evenly over nodes
Decentralization: chord is fully distributed, no node more important than other, improves robustness
Scalability: logarithmic growth of lookup costs with number of nodes in network, even very large systems are feasible
8
Addressed Difficult Problems (2)
Availability: chord automatically adjusts its internal tables to ensure that the node responsible for a key can always be found
Flexible naming: no constraints on the structure of the keys – key-space is flat, flexibility in how to map names to Chord keys
9
Example Application using Chord: Cooperative Mirroring File System Block Store
Block Store
Block Store
Chord
Chord
Chord
Client
Server
Server
Highest layer provides a file-like interface to including -friendly naming and authentication
This file systems maps operations to lower-level block operations
Block storage uses Chord to identify responsible node for storing a block and then talk to the block storage server on that node
10
The Base Chord Protocol (1)
Specifies how to find the locations of keys
How new nodes the system
How to recover from the failure or planned departure of existing nodes
11
Consistent Hashing
Hash function assigns each node and key an m-bit identifier using a base hash function such as SHA-1
ID(node) = hash(IP, Port)
ID(key) = hash(key)
Properties of consistent hashing:
Function balances load: all nodes receive roughly the same number of keys – good?
When an Nth node s (or leaves) the network, only an O(1/N) fraction of the keys are moved to a different location
12
Successor Nodes identifier node
6 1
0
successor(6) = 0
6
identifier circle
6 5
key
successor(1) = 1
1
7
X
2
2
successor(2) = 3
3 4
2
13
Node s and Departures 6 6
1
0
successor(6) = 7
1
7 6
successor(1) = 3
2 5
3 4
2 1
14
Scalable Key Location
A very small amount of routing information suffices to implement consistent hashing in a distributed environment
Each node need only be aware of its successor node on the circle
Queries for a given identifier can be ed around the circle via these successor pointers
Resolution scheme correct, BUT inefficient: it may require traversing all N nodes!
15
Acceleration of Lookups
Lookups are accelerated by maintaining additional routing information
Each node maintains a routing table with (at most) m entries (where N=2m) called the finger table
ith entry in the table at node n contains the identity of the first node, s, that succeeds n by at least 2i-1 on the identifier circle (clarification on next slide)
s = successor(n + 2i-1)
s is called the ith finger of node n, denoted by n.finger(i).node
(all arithmetic mod 2)
16
Finger Tables (1) finger table start int. 1 2 4
[1,2) [2,4) [4,0)
1
6
1 3 0 finger table start int.
0 7
succ.
keys 6
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
0 0 0
17
Finger Tables (2) - characteristics
Each node stores information about only a small number of other nodes, and knows more about nodes closely following it than about nodes farther away
A node’s finger table generally does not contain enough information to determine the successor of an arbitrary key k
Repetitive queries to nodes that immediately precede the given key will lead to the key’s successor eventually
18
Node s – with Finger Tables finger table start int. 1 2 4
[1,2) [2,4) [4,0)
finger table start int. 7 0 2
[7,0) [0,2) [2,6)
keys succ.
1
0 0 3
6
1 3 0 6 finger table start int.
0 7
succ.
keys 6
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0 6
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
6 0 6 0 0
19
Node Departures – with Finger Tables finger table start int. 1 2 4
[1,2) [2,4) [4,0)
finger table start int. 7 0 2
[7,0) [0,2) [2,6)
succ. 0 0 3
keys 6
1
6
succ. 3 1 3 0 6 finger table start int.
0 7
keys
2 3 5
[2,3) [3,5) [5,1)
succ.
keys 1
3 3 0 6
2 5
3 4
finger table start int. 4 5 7
[4,5) [5,7) [7,3)
succ.
keys 2
6 6 0
20
Source of Inconsistencies: Concurrent Operations and Failures
Basic “stabilization” protocol is used to keep nodes’ successor pointers up to date, which is sufficient to guarantee correctness of lookups
Those successor pointers can then be used to the finger table entries
Every node runs stabilize periodically to find newly ed nodes
21
Stabilization after
n s
pred(ns) = n
n
nil
np
succ(np) = ns
succ(np) = n
pred(ns) = np
ns
predecessor = nil n acquires ns as successor via some n’ n notifies ns being the new predecessor ns acquires n as its predecessor
np runs stabilize
np asks ns for its predecessor (now n)
np acquires n as its successor
np notifies n
n will acquire np as its predecessor
all predecessor and successor pointers are now correct
fingers still need to be fixed, but old fingers will still work
22
Failure Recovery
Key step in failure recovery is maintaining correct successor pointers
To help achieve this, each node maintains a successor-list of its r nearest successors on the ring
If node n notices that its successor has failed, it replaces it with the first live entry in the list
stabilize will correct finger table entries and successor-list entries pointing to failed node
Performance is sensitive to the frequency of node s and leaves versus the frequency at which the stabilization protocol is invoked
23
Chord – The Math
Every node is responsible for about K/N keys (N nodes, K keys)
When a node s or leaves an N-node network, only O(K/N) keys change hands (and only to and from ing or leaving node)
Lookups need O(log N) messages
To reestablish routing invariants and finger tables after node ing or leaving, only O(log2N) messages are required
24
Experimental Results
Latency grows slowly with the total number of nodes
Path length for lookups is about ½ log2N
Chord is robust in the face of multiple node failures
25
Related Documents 171j1w
Chord 10234b
August 2021 0
Chord 10234b
August 2021 0
Chord 10234b
November 2019 243
Chord 10234b
August 2021 0
Chord 10234b
December 2019 54
Chord 10234b
November 2019 50More Documents from "Sharkup Laser" 2i6e
Chord 10234b
August 2021 0
Philsat Practice Items Booklet 6e1ms
January 2021 0
Norma Nte Inen 2 402-2010 53306o
July 2020 3
Profits And Gains From Business Or Profession-notes (1) h5m68
November 2019 63
Brother Hl 2130 Tn410 Toner Engrane Reset 1i166c
May 2022 0