Distributed hash table
Encyclopedia
A distributed hash table (DHT) is a class of a decentralized distributed system
that provides a lookup service similar to a hash table
; (key, value) pairs are stored in a DHT, and any participating node
can efficiently retrieve the value associated with a given key. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.
DHTs form an infrastructure that can be used to build more complex services, such as anycast
, cooperative Web caching
, distributed file system
s, domain name services
, instant messaging
, multicast
, and also peer-to-peer
file sharing
and content distribution systems. Notable distributed networks that use DHTs include BitTorrent's distributed tracker, the Coral Content Distribution Network
, the Kad network
, the Storm botnet
, and YaCy
.
systems such as Freenet
, gnutella
, and Napster
, which took 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.
These systems differed in how they found the data their peers contained:
Distributed hash tables use a more structured key-based routing in order to attain both the decentralization of Freenet and gnutella, and the efficiency and guaranteed results of Napster. One drawback is that, like Freenet, DHTs only directly support exact-match search, rather than keyword search, although Freenet's routing algorithm can be generalized to any key type where a closeness operation can be defined.
In 2001, four systems—CAN
, Chord, Pastry
, and Tapestry
—ignited DHTs as a popular research topic, and this area of research remains active. Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network
.
A key technique used to achieve these goals is that any one node needs to coordinate with only a few other nodes in the system – most commonly, O
(log n) of the
participants (see below) – so that only a limited amount of work needs to be done for each change in membership.
Some DHT designs seek to be secure
against malicious participants and to allow participants to remain anonymous
, though this is less common than in many other peer-to-peer
(especially file sharing
) systems; see anonymous P2P
.
Finally, DHTs must deal with more traditional distributed systems issues such as load balancing
, data integrity
, and performance (in particular, ensuring that operations such as routing and data storage or retrieval complete quickly).
s. A keyspace partitioning scheme splits ownership of this keyspace among the participating nodes. An overlay network then connects the nodes, allowing them to find the owner of any given key in the keyspace.
Once these components are in place, a typical use of the DHT for storage and retrieval might proceed as follows. Suppose the keyspace is the set of 160-bit strings. To store a file with given
and 
in the DHT, the SHA-1 hash of 
is generated, producing a 160-bit key 
, and a message 
is sent to any node participating in the DHT. The message is forwarded from node to node through the overlay network until it reaches the single node responsible for key 
as specified by the keyspace partitioning. That node then stores the key and the data. Any other client can then retrieve the contents of the file by again hashing 
to produce 
and asking any DHT node to find the data associated with 
with a message 
. The message will again be routed through the overlay to the node responsible for 
, which will reply with the stored 
.
The keyspace partitioning and overlay network components are described below with the goal of capturing the principal ideas common to most DHTs; many designs differ in the details.
to map keys to nodes. This technique employs a function
that defines an abstract notion of the distance between the keys 
and 
, which is unrelated to geographical distance
or network latency
. Each node is assigned a single key called its identifier (ID). A node with ID
owns all the keys 
for which 
is the closest ID, measured according to 
.
Consistent hashing has the essential property that removal or addition of one node changes only the set of keys owned by the nodes with adjacent IDs, and leaves all other nodes unaffected. Contrast this with a traditional hash table
in which addition or removal of one bucket causes nearly the entire keyspace to be remapped. Since any change in ownership typically corresponds to bandwidth
-intensive movement of objects stored in the DHT from one node to another, minimizing such reorganization is required to efficiently support high rates of churn (node arrival and failure).
Locality-preserving hashing ensures that similar keys are assigned to similar objects. This can enable a more efficient execution of range queries.
Self-Chord decouples object keys from peer IDs and sorts keys along the ring with a statistical approach based on the swarm intelligence
paradigm. Sorting ensures that similar keys are stored by neighbour nodes and that discovery procedures, including range queries, can be performed in logarithmic time.
s to other nodes (its neighbors or routing table
). Together, these links form the overlay network
. A node picks its neighbors according to a certain structure, called the network's topology
.
All DHT topologies share some variant of the most essential property: for any key
, each node either has a node ID that owns 
or has a link to a node whose node ID is closer to 
, in terms of the keyspace distance defined above. It is then easy to route a message to the owner of any key 
using the following greedy algorithm
(that is not necessarily globally optimal): at each step, forward the message to the neighbor whose ID is closest to
. When there is no such neighbor, then we must have arrived at the closest node, which is the owner of 
as defined above. This style of routing is sometimes called key-based routing.
Beyond basic routing correctness, two important constraints on the topology are to guarantee that the maximum number of hops
in any route (route length) is low, so that requests complete quickly; and that the maximum number of neighbors of any node (maximum node degree
) is low, so that maintenance overhead is not excessive. Of course, having shorter routes requires higher maximum degree. Some common choices for maximum degree and route length are as follows, where
is the number of nodes in the DHT, using Big O notation
:
The most common third choice is not optimal in terms of degree/route length tradeoff, as such topologies typically allow more flexibility in choice of neighbors. Many DHTs use that flexibility to pick neighbors that are close in terms of latency in the physical underlying network.
Maximum route length is closely related to diameter: the maximum number of hops in any shortest path between nodes. Clearly, the network's worst case route length is at least as large as its diameter, so DHTs are limited by the degree/diameter tradeoff that is fundamental in graph theory
. Route length can be greater than diameter, since the greedy routing algorithm may not find shortest paths.
, range queries, or to collect statistics. Two systems that are based on this approach are Structella, which implements flooding and random walks on a Pastry overlay, and DQ-DHT, which implements a dynamic querying search algorithm over a Chord network.
Distributed computing
Distributed computing is a field of computer science that studies distributed systems. A distributed system consists of multiple autonomous computers that communicate through a computer network. The computers interact with each other in order to achieve a common goal...
that provides a lookup service similar to a hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
; (key, value) pairs are stored in a DHT, and any participating node
Node (networking)
In communication networks, a node is a connection point, either a redistribution point or a communication endpoint . The definition of a node depends on the network and protocol layer referred to...
can efficiently retrieve the value associated with a given key. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.
DHTs form an infrastructure that can be used to build more complex services, such as anycast
Anycast
Anycast is a network addressing and routing methodology in which datagrams from a single sender are routed to the topologically nearest node in a group of potential receivers all identified by the same destination address.-Addressing methodologies:...
, cooperative Web caching
Web cache
A web cache is a mechanism for the temporary storage of web documents, such as HTML pages and images, to reduce bandwidth usage, server load, and perceived lag...
, distributed file system
Distributed file system
Network file system may refer to:* A distributed file system, which is accessed over a computer network* Network File System , a specific brand of distributed file system...
s, domain name services
Domain name system
The Domain Name System is a hierarchical distributed naming system for computers, services, or any resource connected to the Internet or a private network. It associates various information with domain names assigned to each of the participating entities...
, instant messaging
Instant messaging
Instant Messaging is a form of real-time direct text-based chatting communication in push mode between two or more people using personal computers or other devices, along with shared clients. The user's text is conveyed over a network, such as the Internet...
, multicast
Multicast
In computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
, and also peer-to-peer
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
file sharing
File sharing
File sharing is the practice of distributing or providing access to digitally stored information, such as computer programs, multimedia , documents, or electronic books. It may be implemented through a variety of ways...
and content distribution systems. Notable distributed networks that use DHTs include BitTorrent's distributed tracker, the Coral Content Distribution Network
Coral Content Distribution Network
The Coral Content Distribution Network, sometimes called Coral Cache or Coral, is a free peer-to-peer content distribution network designed and operated by Michael Freedman...
, the Kad network
Kad Network
The Kad network is a peer-to-peer network which implements the Kademlia P2P overlay protocol. The majority of users on the Kad Network are also connected to servers on the eDonkey network, and Kad Network clients typically query known nodes on the eDonkey network in order to find an initial node...
, the Storm botnet
Storm botnet
The Storm botnet or Storm worm botnet is a remotely controlled network of "zombie" computers that have been linked by the Storm Worm, a Trojan horse spread through e-mail spam...
, and YaCy
YaCy
YaCy is a free distributed search engine, built on principles of peer-to-peer networks. Its core is a computer program written in Java distributed on several hundred computers, , so-called YaCy-peers...
.
History
DHT research was originally motivated, in part, by peer-to-peerPeer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
systems such as Freenet
Freenet
Freenet is a decentralized, censorship-resistant distributed data store originally designed by Ian Clarke. According to Clarke, Freenet aims to provide freedom of speech through a peer-to-peer network with strong protection of anonymity; as part of supporting its users' freedom, Freenet is free and...
, gnutella
Gnutella
Gnutella is a large peer-to-peer network which, at the time of its creation, was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model...
, and Napster
Napster
Napster is an online music store and a Best Buy company. It was originally founded as a pioneering peer-to-peer file sharing Internet service that emphasized sharing audio files that were typically digitally encoded music as MP3 format files...
, which took advantage of resources distributed across the Internet to provide a single useful application. In particular, they took advantage of increased bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
and hard disk
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...
capacity to provide a file-sharing service.
These systems differed in how they found the data their peers contained:
- Napster, the first large-scale P2P content delivery system to exist, had a central index server: each node, upon joining, would send a list of locally held files to the server, which would perform searches and refer the querier to the nodes that held the results. This central component left the system vulnerable to attacks and lawsuits.
- 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 failureSingle point of failureA single point of failure is a part of a system that, if it fails, will stop the entire system from working. They are undesirable in any system with a goal of high availability or reliability, be it a business practice, software application, or other industrial system.-Overview:Systems can be made...
, this method was significantly less efficient than Napster. - Finally, FreenetFreenetFreenet is a decentralized, censorship-resistant distributed data store originally designed by Ian Clarke. According to Clarke, Freenet aims to provide freedom of speech through a peer-to-peer network with strong protection of anonymity; as part of supporting its users' freedom, Freenet is free and...
is fully distributed, but employs a heuristic key-based routing in which each file is associated with a key, and files with similar keys tend to cluster on a similar set of nodes. Queries are likely to be routed through the network to such a cluster without needing to visit many peers. However, Freenet does not guarantee that data will be found.
Distributed hash tables use a more structured key-based routing in order to attain both the decentralization of Freenet and gnutella, and the efficiency and guaranteed results of Napster. One drawback is that, like Freenet, DHTs only directly support exact-match search, rather than keyword search, although Freenet's routing algorithm can be generalized to any key type where a closeness operation can be defined.
In 2001, four systems—CAN
Content addressable network
The Content Addressable Network is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale...
, Chord, Pastry
Pastry (DHT)
Pastry is an overlay and routing network for the implementation of a distributed hash table similar to Chord. The key-value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the...
, and Tapestry
Tapestry (DHT)
Tapestry is a distributed hash table which provides a decentralized object location, routing, and multicasting infrastructure for distributed applications...
—ignited DHTs as a popular research topic, and this area of research remains active. Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network
Coral Content Distribution Network
The Coral Content Distribution Network, sometimes called Coral Cache or Coral, is a free peer-to-peer content distribution network designed and operated by Michael Freedman...
.
Properties
DHTs characteristically emphasize the following properties:- DecentralizationDecentralized computingDecentralized computing is the allocation of resources, both hardware and software, to each individual workstation, or office location. In contrast, centralized computing exists when the majority of functions are carried out, or obtained from a remote centralized location. Decentralized computing...
: the nodes collectively form the system without any central coordination. - Fault tolerance: the system should be reliable (in some sense) even with nodes continuously joining, leaving, and failing.
- Scalability: the system should function efficiently even with thousands or millions of nodes.
A key technique used to achieve these goals is that any one node needs to coordinate with only a few other nodes in the system – most commonly, O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(log n) of the
participants (see below) – so that only a limited amount of work needs to be done for each change in membership.Some DHT designs seek to be secure
Secure
Secure may refer to:* Security, being protected against danger or loss** Securitate , the secret service of Communist Romania* Security , e.g. secured loans...
against malicious participants and to allow participants to remain anonymous
Anonymity
Anonymity is derived from the Greek word ἀνωνυμία, anonymia, meaning "without a name" or "namelessness". In colloquial use, anonymity typically refers to the state of an individual's personal identity, or personally identifiable information, being publicly unknown.There are many reasons why a...
, though this is less common than in many other peer-to-peer
Peer-to-peer
Peer-to-peer computing or networking is a distributed application architecture that partitions tasks or workloads among peers. Peers are equally privileged, equipotent participants in the application...
(especially file sharing
File sharing
File sharing is the practice of distributing or providing access to digitally stored information, such as computer programs, multimedia , documents, or electronic books. It may be implemented through a variety of ways...
) systems; see anonymous P2P
Anonymous P2P
An anonymous P2P communication system is a peer-to-peer distributed application in which the nodes or participants are anonymous or pseudonymous...
.
Finally, DHTs must deal with more traditional distributed systems issues such as load balancing
Load balancing (computing)
Load balancing is a computer networking methodology to distribute workload across multiple computers or a computer cluster, network links, central processing units, disk drives, or other resources, to achieve optimal resource utilization, maximize throughput, minimize response time, and avoid...
, data integrity
Data integrity
Data Integrity in its broadest meaning refers to the trustworthiness of system resources over their entire life cycle. In more analytic terms, it is "the representational faithfulness of information to the true state of the object that the information represents, where representational faithfulness...
, and performance (in particular, ensuring that operations such as routing and data storage or retrieval complete quickly).
Structure
The structure of a DHT can be decomposed into several main components. The foundation is an abstract keyspace, such as the set of 160-bit stringString (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
s. A keyspace partitioning scheme splits ownership of this keyspace among the participating nodes. An overlay network then connects the nodes, allowing them to find the owner of any given key in the keyspace.
Once these components are in place, a typical use of the DHT for storage and retrieval might proceed as follows. Suppose the keyspace is the set of 160-bit strings. To store a file with given
and in the DHT, the SHA-1 hash of is generated, producing a 160-bit key , and a message is sent to any node participating in the DHT. The message is forwarded from node to node through the overlay network until it reaches the single node responsible for key as specified by the keyspace partitioning. That node then stores the key and the data. Any other client can then retrieve the contents of the file by again hashing to produce and asking any DHT node to find the data associated with with a message . The message will again be routed through the overlay to the node responsible for , which will reply with the stored .The keyspace partitioning and overlay network components are described below with the goal of capturing the principal ideas common to most DHTs; many designs differ in the details.
Keyspace partitioning
Most DHTs use some variant of consistent hashingConsistent hashing
Consistent hashing is a special kind of hashing. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped...
to map keys to nodes. This technique employs a function
that defines an abstract notion of the distance between the keys and , which is unrelated to geographical distanceDistance
Distance is a numerical description of how far apart objects are. In physics or everyday discussion, distance may refer to a physical length, or an estimation based on other criteria . In mathematics, a distance function or metric is a generalization of the concept of physical distance...
or network latency
Latency (engineering)
Latency is a measure of time delay experienced in a system, the precise definition of which depends on the system and the time being measured. Latencies may have different meaning in different contexts.-Packet-switched networks:...
. Each node is assigned a single key called its identifier (ID). A node with ID
owns all the keys for which is the closest ID, measured according to .
Example. The Chord DHT treats keys as points on a circle, andis the distance traveling clockwise around the circle from
to
. Thus, the circular keyspace is split into contiguous segments whose endpoints are the node identifiers. If
and
are two adjacent IDs, then the node with ID
owns all the keys that fall between
and
.
Consistent hashing has the essential property that removal or addition of one node changes only the set of keys owned by the nodes with adjacent IDs, and leaves all other nodes unaffected. Contrast this with a traditional hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
in which addition or removal of one bucket causes nearly the entire keyspace to be remapped. Since any change in ownership typically corresponds to bandwidth
Bandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
-intensive movement of objects stored in the DHT from one node to another, minimizing such reorganization is required to efficiently support high rates of churn (node arrival and failure).
Locality-preserving hashing ensures that similar keys are assigned to similar objects. This can enable a more efficient execution of range queries.
Self-Chord decouples object keys from peer IDs and sorts keys along the ring with a statistical approach based on the swarm intelligence
Swarm intelligence
Swarm intelligence is the collective behaviour of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence...
paradigm. Sorting ensures that similar keys are stored by neighbour nodes and that discovery procedures, including range queries, can be performed in logarithmic time.
Overlay network
Each node maintains a set of linkData link
In telecommunication a data link is the means of connecting one location to another for the purpose of transmitting and receiving information. It can also refer to a set of electronics assemblies, consisting of a transmitter and a receiver and the interconnecting data telecommunication circuit...
s to other nodes (its neighbors or routing table
Routing table
In computer networking a routing table, or Routing Information Base , is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics associated with those routes. The routing table contains information about the...
). Together, these links form the overlay network
Overlay network
An overlay network is a computer network which is built on the top of another network. Nodes in the overlay can be thought of as being connected by virtual or logical links, each of which corresponds to a path, perhaps through many physical links, in the underlying network...
. A node picks its neighbors according to a certain structure, called the network's topology
Network topology
Network topology is the layout pattern of interconnections of the various elements of a computer or biological network....
.
All DHT topologies share some variant of the most essential property: for any key
, each node either has a node ID that owns or has a link to a node whose node ID is closer to , in terms of the keyspace distance defined above. It is then easy to route a message to the owner of any key using the following greedy algorithmGreedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
(that is not necessarily globally optimal): at each step, forward the message to the neighbor whose ID is closest to
. When there is no such neighbor, then we must have arrived at the closest node, which is the owner of as defined above. This style of routing is sometimes called key-based routing.Beyond basic routing correctness, two important constraints on the topology are to guarantee that the maximum number of hops
Hop (networking)
Data packets often have to go through routers , if not several, before they reach their final destination. Each time packets are passed to the next router a hop occurs. .- Hop Count :The distance between two hosts...
in any route (route length) is low, so that requests complete quickly; and that the maximum number of neighbors of any node (maximum node degree
Degree (graph theory)
In graph theory, the degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice. The degree of a vertex v is denoted \deg. The maximum degree of a graph G, denoted by Δ, and the minimum degree of a graph, denoted by δ, are the maximum and minimum degree...
) is low, so that maintenance overhead is not excessive. Of course, having shorter routes requires higher maximum degree. Some common choices for maximum degree and route length are as follows, where
is the number of nodes in the DHT, using Big O notationBig O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
:
| Degree | Route length | Notice |
|---|---|---|
 |
 |
|
 |
 |
|
 |
 |
most common, but not optimal (degree/route length) |
 |
 |
|
 |
 |
The most common third choice is not optimal in terms of degree/route length tradeoff, as such topologies typically allow more flexibility in choice of neighbors. Many DHTs use that flexibility to pick neighbors that are close in terms of latency in the physical underlying network.
Maximum route length is closely related to diameter: the maximum number of hops in any shortest path between nodes. Clearly, the network's worst case route length is at least as large as its diameter, so DHTs are limited by the degree/diameter tradeoff that is fundamental in graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Route length can be greater than diameter, since the greedy routing algorithm may not find shortest paths.
Algorithms for overlay networks
Aside from routing, there exist many algorithms that exploit the structure of the overlay network for sending a message to all nodes, or a subset of nodes, in a DHT. These algorithms are used by applications to do overlay multicastOverlay multicast
Also known as End System or Peer-to-Peer Multicast.High bandwidth multi-source multicast among widely distributed nodes is a critical capability for a wide range of important applications including audio and video conferencing, multi-party games and content distribution...
, range queries, or to collect statistics. Two systems that are based on this approach are Structella, which implements flooding and random walks on a Pastry overlay, and DQ-DHT, which implements a dynamic querying search algorithm over a Chord network.
DHT implementations
Most notable differences encountered in practical instances of DHT implementations include at least the following:- The address space is a parameter of DHT. Several real world DHTs use 128-bit or 160-bit key space
- Some real-world DHTs use hash functions other than SHA-1.
- In the real world the key
could be a hash of a file's content rather than a hash of a file's name to provide content-addressable storageContent-addressable storageContent-addressable storage, also referred to as associative storage or abbreviated CAS, is a mechanism for storing information that can be retrieved based on its content, not its storage location. It is typically used for high-speed storage and retrieval of fixed content, such as documents stored...
, so that renaming of the file does not prevent users from finding it. - Some DHTs may also publish objects of different types. For example, key
could be the node 
and associated data could describe how to contact this node. This allows publication-of-presence information and often used in IM applications, etc. In the simplest case, 
is just a random number that is directly used as key 
(so in a 160-bit DHT 
will be a 160-bit number, usually randomly chosen). In some DHTs, publishing of nodes IDs is also used to optimize DHT operations. - Redundancy can be added to improve reliability. The
key pair can be stored in more than one node corresponding to the key. Usually, rather than selecting just one node, real world DHT algorithms select 
suitable nodes, with 
being an implementation-specific parameter of the DHT. In some DHT designs, nodes agree to handle a certain keyspace range, the size of which may be chosen dynamically, rather than hard-coded. - Some advanced DHTs like KademliaKademliaKademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A...
perform iterative lookups through the DHT first in order to select a set of suitable nodes and send
messages only to those nodes, thus drastically reducing useless traffic, since published messages are only sent to nodes that seem suitable for storing the key 
; and iterative lookups cover just a small set of nodes rather than the entire DHT, reducing useless forwarding. In such DHTs, forwarding of 
messages may only occur as part of a self-healing algorithm: if a target node receives a 
message, but believes that 
is out of its handled range and a closer node (in terms of DHT keyspace) is known, the message is forwarded to that node. Otherwise, data are indexed locally. This leads to a somewhat self-balancing DHT behavior. Of course, such an algorithm requires nodes to publish their presence data in the DHT so the iterative lookups can be performed.
DHT protocols and implementations
- Apache Cassandra
- BitTorrent DHT (based on KademliaKademliaKademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A...
as provided by Khashmir) - CANContent addressable networkThe Content Addressable Network is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale...
(Content Addressable Network) - Chord
- KademliaKademliaKademlia is a distributed hash table for decentralized peer-to-peer computer networks designed by Petar Maymounkov and David Mazières in 2002. It specifies the structure of the network and the exchange of information through node lookups. Kademlia nodes communicate among themselves using UDP. A...
- PastryPastry (DHT)Pastry is an overlay and routing network for the implementation of a distributed hash table similar to Chord. The key-value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the...
- P-GridP-GridP-Grid is a self-organizing structured peer-to-peer system, which can accommodate arbitrary key distributions , still providing storage load-balancing and efficient search by using randomized routing.- Salient features :* Good storage load-balancing despite arbitrary load-distribution over the...
- TapestryTapestry (DHT)Tapestry is a distributed hash table which provides a decentralized object location, routing, and multicasting infrastructure for distributed applications...
- TomP2PTomP2PTomP2P is a distributed hash table which provides a decentralized key-value infrastructure for distributed applications. Each peer has a table that can be configured either to be disk-based or memory-based to store its values.- Overview and Key Concept :...
Applications employing DHTs
- BTDiggBTDiggBTDigg is the first BitTorrent DHT search engine.It analyses the DHT network in the real-time and providesfull-text search over active torrents in European and Asian languages.Site name is acronym from BitTorrent Digger.-Features:...
: BitTorrent DHT search engine - CodeenCodeenCoDeeN is a proxy server system created at Princeton University in 2003 and deployed for general use on PlanetLab.It operates as per the following:# Users set their internet caches to a nearby high bandwidth proxy that participates in the system....
: Web caching - Coral Content Distribution NetworkCoral Content Distribution NetworkThe Coral Content Distribution Network, sometimes called Coral Cache or Coral, is a free peer-to-peer content distribution network designed and operated by Michael Freedman...
- Dijjer: Freenet-like distribution network
- FAROOFAROOFAROO is a universal web search engine based on peer-to-peer technology. It uses a distributed crawler that stores search data on users' computers instead of a central server. Whenever a user visits a website, it is automatically indexed and distributed to the network...
: Peer-to-peer Web search engine - FreenetFreenetFreenet is a decentralized, censorship-resistant distributed data store originally designed by Ian Clarke. According to Clarke, Freenet aims to provide freedom of speech through a peer-to-peer network with strong protection of anonymity; as part of supporting its users' freedom, Freenet is free and...
: A censorship-resistant anonymous network - GNUnetGNUnetGNUnet is a free software framework for decentralized, peer-to-peer networking. The framework offers link encryption, peer discovery and resource allocation....
: Freenet-like distribution network including a DHT implementation - JXTAJXTAJXTA is an open source peer-to-peer protocol specification begun by Sun Microsystems in 2001. The JXTA protocols are defined as a set of XML messages which allow any device connected to a network to exchange messages and collaborate independently of the underlying network topology.As JXTA is based...
: Opensource P2P platform - maidsafe: C++ implementation of Kademlia, with NAT traversal and crypto libraries. On its home page listed as "Available as a technology licence and a software solution written in cross platform C++."
- WebSphere eXtreme Scale: proprietary DHT implementation by IBM, used for object caching
- YaCyYaCyYaCy is a free distributed search engine, built on principles of peer-to-peer networks. Its core is a computer program written in Java distributed on several hundred computers, , so-called YaCy-peers...
: distributed search engineWeb search engineA web search engine is designed to search for information on the World Wide Web and FTP servers. The search results are generally presented in a list of results often referred to as SERPS, or "search engine results pages". The information may consist of web pages, images, information and other... - CloudSNAP: a decentralized web application deployment platform
See also
- membaseMembaseMembase is an Open Source distributed, key-value database management system optimized for storing data behind interactive web applications. These applications must service many concurrent users; creating, storing, retrieving, aggregating, manipulating and presenting data...
: a persistent, replicated, clustered distributed object storage system compatible with memcached protocol - memcachedMemcachedIn computing, memcached is a general-purpose distributed memory caching system that was originally developed by Danga Interactive for LiveJournal, but is now used by many other sites. It is often used to speed up dynamic database-driven websites by caching data and objects in RAM to reduce the...
: a high-performance, distributed memory object caching system - prefix hash treePrefix hash treeA prefix hash tree is a distributed data structure that enables more sophisticated queries over a distributed hash table . The prefix hash tree uses the lookup interface of a DHT to construct a trie-based data structure that is both efficient , and resilient A prefix hash tree (PHT) is a...
: sophisticated querying over DHTs - most distributed data storeDistributed data storeA distributed data store is a blurred concept and means either a distributed database where users store their information on a number of nodes, or a network in which a user stores their information on a number of peer network nodes ....
s employ some form of DHT for lookup.
External links
- Distributed Hash Tables, Part 1 by Brandon Wiley.
- Distributed Hash Tables links Carles Pairot's Page on DHT and P2P research
- Tangosol Coherence includes a structure similar to a DHT, though all nodes have knowledge of the other participants
- kademlia.scs.cs.nyu.edu Archive.org snapshots of kademlia.scs.cs.nyu.edu
- Hazelcast open source DHT implementation
- scale4j highly scalable domain oriented data-distributed platform for java
- IEEE Survey on overlay network schemes covering unstructured and structured decentralized overlay networks including DHTs (Chord, Pastry, Tapestry and others) by Eng-Keong. Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma and Steve Lim.