Transcript 投影片 1

Thesis Proposal
Data Consistency in DHTs
Background
• Peer-to-peer systems have become increasingly
popular
• Lots of P2P applications around us
– File sharing, file storage, Real time broadcasting, …
• Advantages of P2P system
–
–
–
–
Scalable
load balance,
fault-tolerant,
low-cost deployment
• Why is it so magic?
Core of P2P
• Each peer is a server and a client
• DHT
– Every peer can find each other and cooperate
– A hashed ID maps to a peer or an object
– The object would be stored on the closest peer
Usages of DHT
• Directory service
– Very little amount of information, such as URI,
metadata, …
– Don’t need to modified
• Storage
– Data, such as files, …
– Immutable, only for downloading and
uploading
• What is the next?
Mutable DHT
• Most of DHT are for immutable data
• Immutable
– Data wouldn’t be modified
– Operations of DHT
• ping, search, publish
• Mutable
– Data would be modified
– Operations of DHT
• ping, search, publish, delete, modified
What is the challenge?
• Churn
– Peer join, leave, fail randomly
• Replica
– Fault-tolerant
• Problem
– Object consistency
• Replicas are consistent on
different nodes
What is the challenge?
• Network dynamic
– Partial unreachability
• Problem
– Key consistency
• Only one node is the root
of a key
Related work
• Consensus system
– Primary data maintainer
– Clients modify the data on primary one
– Do consensus algorithm
• After data modified
• After churn happened
• Quorum system
– No primary one
– Clients try to lock every replica
before modifying
Related work
• Authorization
– Contact the original closest one
– Get Authorized token of the closer partition
– Be the root of the partition
Questions
• Is key consistency really a big assumption
on realistic environment?
• For what kind of churn and mutability, do
we need a strong consistency mechanism?
• The importance of key and data
consistency mechanisms
– If we can guarantee only one of them, than
what is the result on different situations?
Experimental Plan
• Create a realistic network environment for
simulation
• Result of data consistency on different
churn and mutability
– DHT without any mechanism
– DHT with key consistency mechanism
– DHT with data consistency mechanism
– DHT with key and data consistency
mechanisms
Network Environment for Simulation
• Partial unreachability
– Path outage probability of internet
– Path outage duration and inter-duration
• Distribution of Node up and down
– Statistics of real p2p network
• Topology
– Hierarchical topology (few depth of AS’)
– BRITE
References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Non-Transitive Connectivity and DHTs
Key consistency in DHTs
Toward Fault-tolerant Atomic Data Access in Mutable Distributed
Hash Tables
Etna: a Fault-tolerant Algorithm for Atomic Mutable DHT Data
PaxonDHT: Achieving Consensus in Distributed Hash Tables
MUREX: A Mutable Replica Control Scheme for Structured Peerto-Peer Storage Systems
A Practical Distributed Mutual Exclusion Protocol in Dynamic
Peer-to-Peer Systems
An Experimental Study of the Skype Peer-to-Peer VoIP System
Actively Monitoring Peers in KAD
An Analysis of Network Reachability Using BGP Data
PlanetSeeer: Internet Path Failure Monitoring and
Characterization in Wide-Area services
Quantifying the Effects of Routing dynamics on End-to-End
Internet Path Failures