CSE 124 Lecture Notes - Lecture 23: Hash Table, Overlay Network, Gnutella
26 May 2018
School
Department
Course
Professor
What is a Peer-to-Peer (P2P) System?
- a distributed system architecture where:
- no centralized control
- nodes are “roughly” symmetric in function
- LARGE number of unreliable nodes!
P2P Adoption
- successful in “some niche” acreas
1. Client-to-client file sharing
2. Digital Currency: NO single owner (i.e. Bitcoin)
3. Voice/video telephony: user to user
- Service is in charge of managing the clients
Example: Bittorrent
1. User clicks DL link
2. User’s BitTorrent (BT) client talks to “tracker”
- Tracker tells it list of peers who have file
3. User’s BT client DLs file from one (or more) peers
4. User’s BT client tells “tracker” it has a copy now, too
5. User’s BT client serves the file to others for a while
Centralized Lookup (Napster)
- centralized DB containing IP addresses
Simple, but O(N) state and a single point of failure!
Flooded Queries (Original Gnutella)
- build up a “partial snapshot”, and send this query to the snapshot
- a query has to be sent on O(N = # of peers) PER lookup
How is this robust? - b/c you’re flooding requests, if the content you’re looking for is popular, it’s
likely that any subset of these pointers is eventually going to get you there
- arrows are NOT network links, but rather TCP connections!
Can we make it robust, reasonable state, and reasonable # of hops?
Overlay network - process of constructing links between nodes
What is a DHT (and why) ?
Local hash table:
Key = Hash(name)
put(key, value)
get(key) → value
Service: constant-time insertion AND lookup
Why might DHT design be hard?
Document Summary
Successful in some niche acreas: client-to-client file sharing, digital currency : no single owner (i. e. bitcoin, voice/video telephony : user to user. Service is in charge of managing the clients. Example: bittorrent: user clicks dl link, user"s bittorrent (bt) client talks to tracker . Simple, but o(n) state and a single point of failure! Build up a partial snapshot , and send this query to the snapshot. A query has to be sent on o(n = # of peers) per lookup. How is this robust? - b/c you"re flooding requests, if the content you"re looking for is popular, it"s likely that any subset of these pointers is eventually going to get you there. Arrows are not network links, but rather tcp connections! Overlay network - process of constructing links between nodes. Key = hash(name) put(key, value) get(key) value. Nodes that are going to communicate are also going to run their identifier functions as well.
