Distributed hash table
|
|
Distributed hash tables (DHTs) are a class of decentralized, distributed systems and algorithms being developed to provide a scalable, self-configuring infrastructure with a clean programming interface. This infrastructure can then be used to support more complex services. DHTs can be used to store data, as well as route and disseminate information. DHTs are named after hash tables because they assign responsibility for a piece of data based on a hash function (often SHA-1); each node acts like a bucket in a hash table. A DHT provides an efficient lookup algorithm (or network routing method) that allows one participating node to quickly determine which other machine is responsible for a given piece of data.
| Contents |
Background
DHT research was originally motivated, in part, by peer-to-peer systems such as Napster and Gnutella. These systems were able to take advantage of resources distributed across the Internet to provide a single useful application. In particular, they took advantage of increased bandwidth and hard disk capacity to provide a file sharing service. Napster and Gnutella themselves were different solutions to a search problem — how to find files located on different computers around the world that have no knowledge of one another. Napster solved this problem by letting the central server act as an index and introduction service: when computers joined the Napster network, they would notify a central server of the files they held locally. Searches were performed on the server, which would refer the querier to the machines that held files relevant to the search. This central component left the system vulnerable to attack. In response, Gnutella and similar networks moved to a flooding query model — in essence, each search would result in a message being broadcast to every other machine in the network. While avoiding a single point of failure, this method was significantly less efficient than Napster. Distributed hash tables attempt to find a more optimal method for organizing nodes while still avoiding the problems of Napster.
Properties
A DHT typically seeks to achieve some or all of the following properties:
- Decentralized operation: every node should be able to function independently and collectively from the complete system without any central coordination.
- Scalability: the system should function efficiently even with large number of nodes. That is, it should scale.
- Load balance: keys (i.e. data) should be distributed fairly among the different participants, particularly important when they have dissimilar capabilities or commitments.
- Fault tolerance: the system should be reliable (in some sense) even if nodes fail or leave the system.
- Performance: Operations such as routing and data storage or retrieval should complete quickly.
- Data integrity: It should be easy to verify the correctness of data stored in or retrieved from the system.
- Data replication: the system automatically makes multiple copies of important data, to protect from data loss, increase availability, and reduce routing delays.
- Security/Robustness: The system should continue to function "correctly" even if some (possibly large) fraction of the nodes are conspiring to prevent correct operation.
- Anonymity: The system should not allow observers to determine who is doing what inside the system.
It is difficult to achieve all of these properties simultaneously; research into achieving these goals is on-going.
Structure
Nodes in a DHT are organized in a network overlay with a particular topology (such as a circle or a hypercube) over some space (such as the real interval <math>[0, 1)<math>). Each node has a logical identifier that determines its logical position in the overlay. A join protocol allows a new node to bootstrap into the existing system, usually by contacting a node that is known to be in the system already. This protocol introduces the node to a set of neighbors and typically facilitates the construction of the new node's routing table.
Routing tables are used by DHT nodes to efficiently determine what other node is responsible for a given piece of data. Data is given a key (in the same identifier space) and assigned to the closest node in the overlay. The definition of closest varies depending on the DHT and the topology chosen and usually does not have to do with the physical distance between nodes — for example, a DHT that places nodes in a Euclidean space might simply choose the node whose coordinates give the smallest Euclidean distance to the key. The routing table allows any node to find the closest node to any given key efficiently, often in <math>O(\log n)<math> network hops (or in some cases <math>O(1)<math> hops). This style of routing is sometimes called key based routing.
Examples
DHT Research:
- Project IRIS (http://www.project-iris.net/) (Infrastructure for Resilient Internet Systems)
Popular routing algorithms:
- CAN (Content Addressable Network)
- Chord
- Kademlia
- Pastry/FreePastry (http://freepastry.rice.edu/FreePastry/)
- Tapestry
DHTs for Storage:
- OpenDHT (http://www.opendht.org/)
- Bamboo (http://www.bamboo-dht.org/)
- DHash/Chord (http://www.pdos.lcs.mit.edu/chord/)
- Bunshin (http://ants.etse.urv.es/bunshin/)
Applications:
- Azureus: BitTorrent (file sharing) client.
- BitComet: BitTorrent client.
- The Circle: File sharing and chat.
- Coral: Content distribution network.
- Freenet: Anonymous datastore.
- Dijjer (http://www.dijjer.org): Freenet-like distribution network.
- OceanStore (http://oceanstore.cs.berkeley.edu): Archival storage.
- P-Grid
Articles
- "Looking up data in P2P systems (http://www.project-iris.net/irisbib/papers/dht:cacm03/paper.pdf)." by Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris, and Ion Stoica. In Communications of the ACM, February 2003.
- Distributed Hash Tables, Part 1 (http://linuxjournal.com/article/6797) by Brandon Wiley.
- A modular architecture of DHTs (http://www-db.stanford.edu/~manku/phd/index.html) by Gurmeet Singh Manku.
- Sloppy Hashing and Self-Organizing Clusters (http://www.scs.cs.nyu.edu/coral/pubs/): publications from the Coral project.de:Verteilte Hashtabelle