Distributed Hash Table
   HOME

TheInfoList



OR:

A distributed hash table (DHT) is a
distributed system A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another from any system. Distributed computing is a field of computer sci ...
that provides a lookup service similar to a
hash table In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
: key–value pairs are stored in a DHT, and any participating
node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines ...
can efficiently retrieve the value associated with a given
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (map ...
. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. ''Keys'' are unique identifiers which map to particular ''values'', which in turn can be anything from addresses, to documents, to arbitrary
data In the pursuit of knowledge, data (; ) is a collection of discrete values that convey information, describing quantity, quality, fact, statistics, other basic units of meaning, or simply sequences of symbols that may be further interpreted ...
. 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 is a network addressing and routing methodology in which a single destination IP address is shared by devices (generally servers) in multiple locations. Routers direct packets addressed to this destination to the location nearest the sen ...
, cooperative
web caching A Web cache (or HTTP cache) is a system for optimizing the World Wide Web. It is implemented both client-side and server-side. The caching of multimedias and other files can result in less overall delay when browsing the Web. Parts of the syste ...
,
distributed file system A clustered file system is a file system which is shared by being simultaneously mounted on multiple servers. There are several approaches to clustering, most of which do not employ a clustered file system (only direct attached storage fo ...
s,
domain name services The Domain Name System (DNS) is a hierarchical and distributed naming system for computers, services, and other resources in the Internet or other Internet Protocol (IP) networks. It associates various information with domain names assigned t ...
,
instant messaging Instant messaging (IM) technology is a type of online chat allowing real-time text transmission over the Internet or another computer network. Messages are typically transmitted between two or more parties, when each user inputs text and trigge ...
,
multicast In computer networking, multicast is group communication where data transmission is addressed to a group of destination computers simultaneously. Multicast can be one-to-many or many-to-many distribution. Multicast should not be confused with ...
, and also
peer-to-peer file sharing Peer-to-peer file sharing is the distribution and sharing of digital media using peer-to-peer (P2P) networking technology. P2P file sharing allows users to access media files such as books, music, movies, and games using a P2P software program th ...
and content distribution systems. Notable distributed networks that use DHTs include BitTorrent's distributed tracker, the
Kad network The Kad network is a peer-to-peer (P2P) 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 node ...
, the Storm botnet, the Tox instant messenger,
Freenet Freenet is a peer-to-peer platform for censorship-resistant, anonymous communication. It uses a decentralized distributed data store to keep and deliver information, and has a suite of free software for publishing and communicating on the Web ...
, the
YaCy ''YaCy'' (pronounced “ya see”) is a free distributed search engine, built on the principles of peer-to-peer (P2P) networks created by Michael Christen in 2003. The engine is written in Java and distributed on several hundred computers, , so- ...
search engine, and the
InterPlanetary File System The InterPlanetary File System (IPFS) is a protocol, hypermedia and file sharing peer-to-peer network for storing and sharing data in a distributed file system. IPFS uses content-addressing to uniquely identify each file in a global namespace ...
.


History

DHT research was originally motivated, in part, by
peer-to-peer Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network. They are said to form a peer-to-peer n ...
(P2P) systems such as
Freenet Freenet is a peer-to-peer platform for censorship-resistant, anonymous communication. It uses a decentralized distributed data store to keep and deliver information, and has a suite of free software for publishing and communicating on the Web ...
,
Gnutella Gnutella is a peer-to-peer network protocol. Founded in 2000, it was the first decentralized peer-to-peer network of its kind, leading to other, later networks adopting the model. In June 2005, Gnutella's population was 1.81 million computer ...
, BitTorrent 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 Bandwidth commonly refers to: * Bandwidth (signal processing) or ''analog bandwidth'', ''frequency bandwidth'', or ''radio bandwidth'', a measure of the width of a frequency range * Bandwidth (computing), the rate of data transfer, bit rate or thr ...
and
hard disk A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnet ...
capacity to provide a file-sharing service. These systems differed in how they located the data offered by their peers. Napster, the first large-scale P2P content delivery system, required 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 queries 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
query flooding Query flooding is a method to search for a resource on a peer-to-peer network. It is simple and scales very poorly and thus is rarely used. Early versions of the Gnutella protocol operated by query flooding; newer versions use more efficient searc ...
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 A single point of failure (SPOF) is a part of a system that, if it fails, will stop the entire system from working. SPOFs are undesirable in any system with a goal of high availability or reliability, be it a business practice, software appl ...
, this method was significantly less efficient than Napster. Later versions of Gnutella clients moved to a
dynamic querying Dynamics (from Greek δυναμικός ''dynamikos'' "powerful", from δύναμις ''dynamis'' "power") or dynamic may refer to: Physics and engineering * Dynamics (mechanics) ** Aerodynamics, the study of the motion of air ** Analytical dyna ...
model which vastly improved efficiency. Freenet is fully distributed, but employs a
heuristic A heuristic (; ), or heuristic technique, is any approach to problem solving or self-discovery that employs a practical method that is not guaranteed to be optimal, perfect, or rational, but is nevertheless sufficient for reaching an immediate, ...
key-based routing Key-based routing (KBR) is a lookup method used in conjunction with distributed hash tables (DHTs) and certain other overlay networks. While DHTs provide a method to find a host responsible for a certain piece of data, KBR provides a method to fi ...
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 Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone net ...
can be generalized to any key type where a closeness operation can be defined. In 2001, four systems— CAN, Chord,
Pastry Pastry is baked food made with a dough of flour, water and shortening (solid fats, including butter or lard) that may be savoury or sweetened. Sweetened pastries are often described as '' bakers' confectionery''. The word "pastries" sugges ...
, and
Tapestry Tapestry is a form of textile art, traditionally woven by hand on a loom. Tapestry is weft-faced weaving, in which all the warp threads are hidden in the completed work, unlike most woven textiles, where both the warp and the weft threads may ...
—ignited DHTs as a popular research topic. A project called the Infrastructure for Resilient Internet Systems (Iris) was funded by a $12 million grant from the United States
National Science Foundation The National Science Foundation (NSF) is an independent agency of the United States government that supports fundamental research and education in all the non-medical fields of science and engineering. Its medical counterpart is the National I ...
in 2002. Researchers included
Sylvia Ratnasamy Sylvia Ratnasamy (born 1976) is a Belgian-Indian computer scientist. She is best known as one of the inventors of the distributed hash table (DHT). Her doctoral dissertation proposed the content-addressable networks, one of the original DHTs, a ...
,
Ion Stoica Ion Stoica is a Romanian-American computer scientist specializing in distributed systems, cloud computing and computer networking. He is a professor of computer science at the University of California, Berkeley and co-director of AMPLab. He co-fo ...
, Hari Balakrishnan and
Scott Shenker Scott J. Shenker (born January 24, 1956 in Alexandria, Virginia) is an American computer scientist, and professor of computer science at the University of California, Berkeley. He is also the leader of the Extensible Internet Group at the Intern ...
. Outside academia, DHT technology has been adopted as a component of BitTorrent and in the Coral Content Distribution Network.


Properties

DHTs characteristically emphasize the following properties: * Autonomy and decentralization: The nodes collectively form the system without any central coordination. *
Fault tolerance Fault tolerance is the property that enables a system to continue operating properly in the event of the failure of one or more faults within some of its components. If its operating quality decreases at all, the decrease is proportional to the ...
: The system should be reliable (in some sense) even with nodes continuously joining, leaving, and failing. *
Scalability Scalability is the property of a system to handle a growing amount of work by adding resources to the system. In an economic context, a scalable business model implies that a company can increase sales given increased resources. For example, a ...
: 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(log ''n'') of the ''n'' 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 may refer to: * Security, being protected against danger or loss(es) **Physical security, security measures that are designed to deny unauthorized access to facilities, equipment, and resources **Information security, defending information ...
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 File sharing is the practice of distributing or providing access to digital media, such as computer programs, multimedia (audio, images and video), documents or electronic books. Common methods of storage, transmission and dispersion include r ...
) systems; see
anonymous P2P An anonymous P2P communication system is a peer-to-peer distributed application in which the nodes, which are used to share resources, or participants are anonymous or pseudonymous. Anonymity of participants is usually achieved by special routi ...
.


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 strings. A keyspace partitioning scheme splits ownership of this keyspace among the participating nodes. An
overlay network An overlay network is a computer network that is layered on top of another network. Structure Nodes in the overlay network can be thought of as being connected by virtual or logical links, each of which corresponds to a path, perhaps through ...
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 index a file with given and in the DHT, the
SHA-1 In cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20- byte) hash value known as a message digest – typically rendered as 40 hexadec ...
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 hashing In computer science, consistent hashing is a special kind of hashing technique such that when a hash table is resized, only n/m keys need to be remapped on average where n is the number of keys and m is the number of slots. In contrast, in most tr ...
or rendezvous hashing to map keys to nodes. The two algorithms appear to have been devised independently and simultaneously to solve the distributed hash table problem. Both consistent hashing and rendezvous hashing have 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 computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
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 Churn may refer to: * Churn drill, large-diameter drilling machine large holes appropriate for holes in the ground Dairy-product terms * Butter churn, device for churning butter * Churning (butter), the process of creating butter out of mil ...
(node arrival and failure).


Consistent hashing

Consistent hashing employs a function \delta(k_1, k_2) that defines an abstract notion of the distance between the keys k_1 and k_2, which is unrelated to geographical distance or network latency. Each node is assigned a single key called its ''identifier'' (ID). A node with ID i_x owns all the keys k_m for which i_x is the closest ID, measured according to \delta(k_m, i_x). For example, the Chord DHT uses consistent hashing, which treats nodes as points on a circle, and \delta(k_1, k_2) is the distance traveling clockwise around the circle from k_1 to k_2. Thus, the circular keyspace is split into contiguous segments whose endpoints are the node identifiers. If i_1 and i_2 are two adjacent IDs, with a shorter clockwise distance from i_1 to i_2, then the node with ID i_2 owns all the keys that fall between i_1 and i_2.


Rendezvous hashing

In rendezvous hashing, also called highest random weight (HRW) hashing, all clients use the same hash function h() (chosen ahead of time) to associate a key to one of the ''n'' available servers. Each client has the same list of identifiers , one for each server. Given some key ''k'', a client computes ''n'' hash weights . The client associates that key with the server corresponding to the highest hash weight for that key. A server with ID S_x owns all the keys k_m for which the hash weight h(S_x, k_m) is higher than the hash weight of any other node for that key.


Locality-preserving hashing

Locality-preserving hashing ensures that similar keys are assigned to similar objects. This can enable a more efficient execution of range queries, however, in contrast to using consistent hashing, there is no more assurance that the keys (and thus the load) is uniformly randomly distributed over the key space and the participating peers. DHT protocols such as Self-Chord and Oscar address such issues. 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 (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. The concept is employed in work on artificial intelligence. The expression was introduced by Gerardo Beni and Jing Wang in 1989, in ...
paradigm. Sorting ensures that similar keys are stored by neighbour nodes and that discovery procedures, including range queries, can be performed in logarithmic time. Oscar constructs a navigable
small-world network A small-world network is a type of mathematical graph in which most nodes are not neighbors of one another, but the neighbors of any given node are likely to be neighbors of each other and most nodes can be reached from every other node by a sm ...
based on
random walk In mathematics, a random walk is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...
sampling also assuring logarithmic search time.


Overlay network

Each node maintains a set of links to other nodes (its ''neighbors'' or
routing table In computer networking, a routing table, or routing information base (RIB), is a data table stored in a router or a network host that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with tho ...
). 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 A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
(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 Key-based routing (KBR) is a lookup method used in conjunction with distributed hash tables (DHTs) and certain other overlay networks. While DHTs provide a method to find a host responsible for a certain piece of data, KBR provides a method to fi ...
. Beyond basic routing correctness, two important constraints on the topology are to guarantee that the maximum number of
hops Hops are the flowers (also called seed cones or strobiles) of the hop plant ''Humulus lupulus'', a member of the Cannabaceae family of flowering plants. They are used primarily as a bittering, flavouring, and stability agent in beer, to whi ...
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 may refer to: As a unit of measurement * Degree (angle), a unit of angle measurement ** Degree of geographical latitude ** Degree of geographical longitude * Degree symbol (°), a notation used in science, engineering, and mathematics ...
) 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 Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
: The most common choice, O(\log n) degree/route length, is not optimal in terms of degree/route length tradeoff, but 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. In general, all DHTs construct navigable small-world network topologies, which trade-off route length vs. network degree. Maximum route length is closely related to
diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...
: 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 In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
. 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 multicast, 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.


Security

Because of the decentralization, fault tolerance, and scalability of DHTs, they are inherently more resilient against a hostile attacker than a centralized system. Open systems for
distributed data storage A distributed data store is a computer network where information is stored on more than one node, often in a replicated fashion. It is usually specifically used to refer to either a distributed database where users store information on a ''numb ...
that are robust against massive hostile attackers are feasible. A DHT system that is carefully designed to have Byzantine fault tolerance can defend against a security weakness, known as the
Sybil attack Sibyls were oracular women believed to possess prophetic powers in ancient Greece. Sybil or Sibyl may also refer to: Films * ''Sybil'' (1921 film) * ''Sybil'' (1976 film), a film starring Sally Field * ''Sybil'' (2007 film), a remake of the 19 ...
, which affects most current DHT designs. Whanau is a DHT designed to be resistant to Sybil attacks. Petar Maymounkov, one of the original authors of
Kademlia Kademlia 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. Kademl ...
, has proposed a way to circumvent the weakness to the Sybil attack by incorporating social trust relationships into the system design. The new system, codenamed Tonika or also known by its domain name as 5ttt, is based on an algorithm design known as "electric routing" and co-authored with the mathematician Jonathan Kelner. Maymounkov has now undertaken a comprehensive implementation effort of this new system. However, research into effective defences against Sybil attacks is generally considered an open question, and wide variety of potential defences are proposed every year in top security research conferences.


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 cryptography, SHA-1 (Secure Hash Algorithm 1) is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20- byte) hash value known as a message digest – typically rendered as 40 hexadec ...
. * 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 storage Content-addressable storage (CAS), also referred to as content-addressed storage or fixed-content storage, is a way to store information so it can be retrieved based on its content, not its name or location. It has been used for high-speed storage ...
, 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
Kademlia Kademlia 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. Kademl ...
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. * Since on most machines sending messages is much more expensive than local hash table accesses, it makes sense to bundle many messages concerning a particular node into a single batch. Assuming each node has a local batch consisting of at most operations, the bundling procedure is as follows. Each node first sorts its local batch by the identifier of the node responsible for the operation. Using
bucket sort Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the b ...
, this can be done in , where is the number of nodes in the DHT. When there are multiple operations addressing the same key within one batch, the batch is condensed before being sent out. For example, multiple lookups of the same key can be reduced to one or multiple increments can be reduced to a single add operation. This reduction can be implemented with the help of a temporary local hash table. Finally, the operations are sent to the respective nodes.


Examples


DHT protocols and implementations

*
Apache Cassandra Cassandra is a free and open-source, distributed, wide-column store, NoSQL database management system designed to handle large amounts of data across many commodity servers, providing high availability with no single point of failure. Cassand ...
*
BATON Overlay The BAlanced Tree Overlay Network (BATON) is a distributed tree structure for peer-to-peer (P2P) systems. Different from other overlays that use a distributed hash table (DHT), such as in the Chord system, BATON organizes peers in a distributed ...
*
Mainline DHT Mainline DHT is the name given to the Kademlia-based distributed hash table (DHT) used by BitTorrent clients to find peers via the BitTorrent protocol. The idea of using a DHT for distributed tracking in BitTorrent was first implemented in Azure ...
– standard DHT used by BitTorrent (based on
Kademlia Kademlia 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. Kademl ...
as provided by Khashmir) *
Content addressable network The content-addressable network (CAN) is a distributed, decentralized P2P infrastructure that provides hash table functionality on an Internet-like scale. CAN was one of the original four distributed hash table proposals, introduced concurrently wi ...
(CAN) * Chord *
Koorde In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord DHT and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets hops per node (where is the number of nodes in the ...
*
Kademlia Kademlia 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. Kademl ...
*
Pastry Pastry is baked food made with a dough of flour, water and shortening (solid fats, including butter or lard) that may be savoury or sweetened. Sweetened pastries are often described as '' bakers' confectionery''. The word "pastries" sugges ...
*
P-Grid In distributed data storage, a P-Grid is a self-organizing structured peer-to-peer system, which can accommodate arbitrary key distributions (and hence support lexicographic key ordering and range queries), still providing storage load-balancing and ...
*
Riak Riak (pronounced "ree-ack" ) is a distributed NoSQL key-value data store based on Amazon's Dynamo paper, including its "tunable AP" approach, that is tunable consistency, to the tradeoffs imposed by the CAP Theorem. Riak offers high availability, ...
*
Tapestry Tapestry is a form of textile art, traditionally woven by hand on a loom. Tapestry is weft-faced weaving, in which all the warp threads are hidden in the completed work, unlike most woven textiles, where both the warp and the weft threads may ...
* TomP2P *
Voldemort Lord Voldemort ( , in the films) is a sobriquet for Tom Marvolo Riddle, a character and the main antagonist in J. K. Rowling's series of ''Harry Potter'' novels. The character first appeared in '' Harry Potter and the Philosopher's Ston ...


Applications using DHTs

* BTDigg: BitTorrent DHT search engine *
Codeen CoDeeN 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 syst ...
: web caching *
Freenet Freenet is a peer-to-peer platform for censorship-resistant, anonymous communication. It uses a decentralized distributed data store to keep and deliver information, and has a suite of free software for publishing and communicating on the Web ...
: a censorship-resistant anonymous network *
GlusterFS Gluster Inc. (formerly known as Z RESEARCH) was a software company that provided an open source platform for scale-out public and private cloud storage. The company was privately funded and headquartered in Sunnyvale, California, with an enginee ...
: a distributed file system used for storage virtualization *
GNUnet GNUnet is a software framework for decentralized, peer-to-peer networking and an official GNU package. The framework offers link encryption, peer discovery, resource allocation, communication over many transports (such as TCP, UDP, HTTP ...
: Freenet-like distribution network including a DHT implementation *
I2P The Invisible Internet Project (I2P) is an anonymous network layer (implemented as a mix network) that allows for censorship-resistant, peer-to-peer communication. Anonymous connections are achieved by encrypting the user's traffic (by using ...
: An open-source anonymous peer-to-peer network * I2P-Bote: serverless secure anonymous email *
IPFS The InterPlanetary File System (IPFS) is a protocol, hypermedia and file sharing peer-to-peer network for storing and sharing data in a distributed file system. IPFS uses content-addressing to uniquely identify each file in a global namespac ...
: A content-addressable, peer-to-peer hypermedia distribution protocol *
JXTA JXTA (Juxtapose) was an open-source peer-to-peer protocol specification begun by Sun Microsystems in 2001. The JXTA protocols were defined as a set of XML messages which allow any device connected to a network to exchange messages and collabora ...
: open-source P2P platform *
LBRY LBRY (), is a blockchain-based file-sharing and payment network that powers decentralized platforms, primarily social networks and video platforms. LBRY's creators also created Odysee, an open-source video-sharing website that uses the networ ...
: A blockchain-based content sharing protocol which uses a
Kademlia Kademlia 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. Kademl ...
-influenced DHT system for content distribution *
Oracle Coherence In computing, Oracle Coherence (originally Tangosol Coherence) is a Java-based distributed cache and in-memory data grid. It is claimed to be "intended for systems that require high availability, high scalability and low latency, particularly in ...
: an in-memory data grid built on top of a Java DHT implementation *
Perfect Dark ''Perfect Dark'' is a first-person shooter developed and published by Rare for the Nintendo 64 video game console in 2000. The first game of the '' Perfect Dark'' series, it follows Joanna Dark, an agent of the Carrington Institute research ...
: a
peer-to-peer Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network. They are said to form a peer-to-peer n ...
file-sharing File sharing is the practice of distributing or providing access to digital media, such as computer programs, multimedia (audio, images and video), documents or electronic books. Common methods of storage, transmission and dispersion include ...
application from Japan *
Retroshare Retroshare is a free and open-source peer-to-peer communication and file sharing app based on a friend-to-friend network built by GNU Privacy Guard (GPG). Optionally, peers may exchange certificates and IP addresses to their friends and vice ...
: a
Friend-to-friend A friend-to-friend (or F2F) computer network is a type of peer-to-peer network in which users only make direct connections with people they know. Passwords or digital signatures can be used for authentication. Unlike other kinds of private P2P ...
networkRetroshare FAQ
retrieved December 2011 *
Jami Nūr ad-Dīn 'Abd ar-Rahmān Jāmī ( fa, نورالدین عبدالرحمن جامی; 7 November 1414 – 9 November 1492), also known as Mawlanā Nūr al-Dīn 'Abd al-Rahmān or Abd-Al-Rahmān Nur-Al-Din Muhammad Dashti, or simply as J ...
: a privacy-preserving voice, video and chat communication platform, based on a Kademlia-like DHT *
Tox Tox or TOX may refer to: Science and technology * TOX, a protein encoded by the TOX gene * Tox screen, medical diagnostic screening for toxic substances Computing * Tox (protocol), peer-to-peer instant messaging software * tox (Python testing ...
: an
instant messaging Instant messaging (IM) technology is a type of online chat allowing real-time text transmission over the Internet or another computer network. Messages are typically transmitted between two or more parties, when each user inputs text and trigge ...
system intended to function as a
Skype Skype () is a proprietary telecommunications application operated by Skype Technologies, a division of Microsoft, best known for VoIP-based videotelephony, videoconferencing and voice calls. It also has instant messaging, file transfer, deb ...
replacement *
Twister Twister may refer to: Weather * Tornado Aviation * Pipistrel Twister, a Slovenian ultralight trike * Silence Twister, a German homebuilt aircraft design * Wings of Change Twister, an Austrian paraglider design Entertainment * ''Twister'' (1989 ...
: a
microblogging Microblogging is a form of social network that permits only short posts. They "allow users to exchange small elements of content such as short sentences, individual images, or video links",. Retrieved June 5, 2014 which may be the major reason for ...
peer-to-peer Peer-to-peer (P2P) computing or networking is a distributed application architecture that partitions tasks or workloads between peers. Peers are equally privileged, equipotent participants in the network. They are said to form a peer-to-peer n ...
platform *
YaCy ''YaCy'' (pronounced “ya see”) is a free distributed search engine, built on the principles of peer-to-peer (P2P) networks created by Michael Christen in 2003. The engine is written in Java and distributed on several hundred computers, , so- ...
: a distributed
search engine A search engine is a software system designed to carry out web searches. They search the World Wide Web in a systematic way for particular information specified in a textual web search query. The search results are generally presented in a ...


See also

*
Couchbase Server Couchbase Server, originally known as Membase, is an open-source, distributed ( shared-nothing architecture) multi-model NoSQL document-oriented database software package optimized for interactive applications. These applications may serve many ...
: a persistent, replicated, clustered distributed object storage system compatible with memcached protocol. *
Memcached Memcached (pronounced variously ''mem-cash-dee'' or ''mem-cashed'') is a general-purpose distributed memory-caching system. It is often used to speed up dynamic database-driven websites by caching data and objects in RAM to reduce the number of ...
: a high-performance, distributed memory object caching system. *
Prefix hash tree A prefix hash tree (PHT) is a distributed data structure that enables more sophisticated queries over a distributed hash table (DHT). The prefix hash tree uses the lookup interface of a DHT to construct a trie-based data structure that is both eff ...
: sophisticated querying over DHTs. *
Merkle tree In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" (node) is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a ''branch'', ''inner node'', or ''inode'') ...
: tree having every non-leaf node labelled with the hash of the labels of its children nodes. * Most
distributed data store A distributed data store is a computer network where information is stored on more than one node, often in a replicated fashion. It is usually specifically used to refer to either a distributed database where users store information on a ''numb ...
s employ some form of DHT for lookup. *
Skip graph Skip graphs are a kind of distributed data structure based on skip lists. They were invented in 2003 by James Aspnes and Gauri Shah. A nearly identical data structure called SkipNet was independently invented by Nicholas Harvey, Michael Jones, Ste ...
s are an efficient data structure for implementing DHTs.


References


External links


Distributed Hash Tables, Part 1
by Brandon Wiley.

Carles Pairot's Page on DHT and P2P research
kademlia.scs.cs.nyu.edu
Archive.org snapshots of kademlia.scs.cs.nyu.edu * covering unstructured and structured decentralized overlay networks including DHTs (Chord, Pastry, Tapestry and others).
Mainline DHT Measurement
at Department of Computer Science, University of Helsinki, Finland. {{DEFAULTSORT:Distributed Hash Table Distributed data storage File sharing Distributed data structures Hash based data structures Network architecture Hashing