Wikifreedia

distributed-hash-table

c21b1a6cdb247ccbd938dcb16b15a4fa382d00ffd7b12d5cbbad172a0cd4d170
abhay@formstr.app
Published 11/1/2024
0
0
All versions

A '''distributed hash table''' ('''DHT''') is a Distributed computing|distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node (networking) node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys, to arbitrary 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 systems, 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 Kad network, the Storm botnet, the Tox (protocol)/Tox instant messenger, Freenet, the YaCy search engine, and the Inter Planetary File System.

History

DHT research was originally motivated, in part, by P2P systems such as Freenet, Gnutella, 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 and hard disk 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 model, in essence, each search would result in a message being broadcast to every machine in the network. While avoiding a single point of failure, this method was significantly less efficient than Napster. Later versions of Gnutella clients moved to a dynamic querying model which vastly improved efficiency.

Freenet 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 - Content addressable network Pastry, and Tapestry 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 in 2002. Researchers included Sylvia Ratnasamy, Ion Stoica, Hari Balakrishnan and Scott Shenker . Outside academia, DHT technology has been adopted as a component of BitTorrent and in PlanetLab projects such as 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: 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(log ''n'') of the ''n'' participants 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. Anonymity, though this is less common than in many other peer-to-peer (especially file sharing) systems.

Structure

The structure of a DHT can be decomposed into several main components. 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 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 filename and data in the DHT, the SHA-1 hash of filename is generated, producing a 160-bit key k, and a message put(k, data) 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 k 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 filename to produce k and asking any DHT node to find the data associated with k with a message get(k). The message will again be routed through the overlay to the node responsible for k, which will reply with the stored data.

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 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 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).

Consistent hashing

Consistent hashing employs a function δ ( 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 xis the closest ID, measured according to δ ( k m , i x ). For example, the Chord DHT uses consistent hashing, which treats nodes as points on a circle, and δ ( 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 i1 and i 2 are two adjacent IDs, with a shorter clockwise distance from i1 to i2, then the node with ID i2 owns all the keys that fall between i1 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 {S1, S2, …​, Sn }, one for each server. Given some key k, a client computes n hash weights w1 = h(S1, k), w2 = h(S2, k), …​, wn = h(Sn, k). The client associates that key with the server corresponding to the highest hash weight for that key. A server with ID Sx owns all the keys km for which the hash weight h ( Sx , km ) 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 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 based on random walk sampling also assuring logarithmic search time.

Other authors

No one else has published this topic yet.