Distributed Hash Table - DHT Implementations

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