The Distributed Hash Table
The Kademlia Distributed Hash Table is used in libp2p to provide peer discovery and content routing.
In simple terms, a hash table is a set of records in which every record holds a
key -> value mapping.
In a distributed hash table, the records are spread across the network, which means that every node holds a subset of records.
When searching for a specific record, we do not have a centralized registry; therefore, we must ask peers in the network until the record is found. This search is not random however, but guided by the DHT distance metric.
The Distance Metric
The main operation provided by a hash table is retrieving a value by its key. In order to decide who stores which keys, keys are hashed and compared against PeerIDs (which are already hashes), which allows the DHT to compute a distance metric. The distance metric represents the distance between two IDs; therefore, it is a logical distance, not a physical distance. The DHT distance allows peers to classify how “close” a key is and accepting to store only keys that are close to them. Thus, storing something on the DHT involves finding a node in it that is close enough to the key.
The closeness of a key to a peer is computed by a distance function (i.e.
distance(key_id, peer_id)), which applies an XOR operation to the IDs. The XOR result is converted into an integer to quantify the distance between the IDs. For example,
distance(key1, peer9) = 4 means that the distance between the
peer9 peer and the
key1 key is
The mathematical explanation about the distance function is not trivial, and it is beyond the outcomes of this lecture; however, you can find more information on the topic here.
The Routing Table
The distance metrics can be calculated not only between keys and peer IDs, but also between peer IDs themselves. In order to facilitate the discovery of peers in the network (i.e. be able to answer
FIND_NODES operation), a peer keeps a list of peers divided into buckets depending on the distance to them. Buckets for close distances are bigger.
Thus, a node may not be storing certain key, but it is usually able to provide a list of known nodes that are closer to the key than itself, thus helping in the lookup for the closest nodes.
The internals of the routing table are beyond the outcomes of this lecture, but you can read more on the topic here. You can also take a look at the Go implementation of the routing table.
The libp2p DHT is based on the Kademlia DHT, so it incorporates most of its core concepts with some extra functionalities. Nodes communicate using libp2p streams. The operations provided by the protocol are:
FIND_NODE: given a key, find the closest nodes to the key.
PUT_VALUE: add a
key -> valuemapping to the DHT.
GET_VALUE: given a key, find the corresponding value.
ADD_PROVIDERS: advertising in the network that a peer is providing a given key.
GET_PROVIDERS: finding out what peers provide the value for the given key.
Find the Closest Nodes
FIND_NODE operation returns the k closest nodes of a peer to a given key.
The close nodes of a peer are kept in the routing table. To find the closest nodes of a peer to a specific key, we first compute the distance of every close node to the key (i.e.,
distance(close_peer, key)). Then, we take the nodes with the lowest distance.
Because a peer might have many close nodes, a parameter,
k, is used to limit the number of nodes that we should consider. For example, if
k = 4, we should only consider the four nodes with the lowest distance to the key. To understand it better, consider the following diagram:
Peer 1has four close peers, which are stored in its routing table.
FIND_NODE(key1)operation returns the k closest nodes to the
key1key. The distance between every close peer and the key is computed (i.e.
distance(close_peer, key1)). Then, the k nodes with the lowest distance are selected (in the example,
k = 2).
To store a value, a mapping of the form
key -> value is created in the DHT. For every key, an ID is generated by using the same format as peer IDs. Remember that having an ID for every key in the same format as peer IDs means that we can calculate distances between key IDs and peer IDs.
When storing a value, we get the k closest nodes of a peer to a specific key (i.e.
FIND_NODE(key)) until we find a node that does not have closer nodes to key than itself. To get a better understanding, consider that we want to store a
key key in following network diagram:
Peer 1wants to store a new key; therefore, it finds the k closest nodes to the key (in this example,
k = 2).
Peer 3are selected.
Peer 2finds its k closest nodes to the key. Because it does not have a node that is closer to the key than itself, it stores the key.
Peer 3finds its k closest nodes too:
Peer 7are selected.
Peer 7do not have nodes closer to the key than themselves; therefore, they store the key.
Because the record is stored in the closest peers, there will be several nodes storing the same record, which can lead to inconsistencies at some point. Validation strategies are required. You can read about validation in the official specifications.
Although both peers and keys share the same ID format, peer IDs are not part of the keys. Instead, a peer, with a given peer ID, holds a set of keys.
To find a value for a given key, we iteratively find the k closest nodes of a peer. Consider the following network diagram:
Every peer has a parameter, dist, which represents the distance from the peer to the target key (
key1). For example,
Peer 5 with
dist = 10 means that
distance(peer5, key1) = 5.
The arrows represent the close nodes of every peer.
For simplicity, only one node (
Peer 10) contains the key.
Consider the following diagram, where we select the k closest node on every iteration (
k = 2).
You are in
Peer 1, and you want to find
key1. The traversal of nodes will be:
Peer 1has three close nodes. The
Peer 3as the closest nodes because they have the lowest distance to the key.
Peer 1, a
FINDE_NODE(key1)request is sent to the close nodes of
Peer 8). The nodes with the lowest distance to the key are selected:
Peer 1, a
FIND_NODE(key1)request is sent to
Peer 10holds the key, so the value is returned.
Note that the previous example is just a very high-level explanation of the algorithm. For a deeper look, refer to the specification. For example, a validation strategy is needed because several peers might return different values for the same key.
In storage systems (e.g., IPFS), a DHT key might represent a specific file’s CID. Therefore, searching for a particular key means finding what peers hold a specific file.
Although you can use the
GET_VALUE operation to retrieve a specific key, the DHT also provides the
ADD_PROVIDER operations to advertise content. While the
GET_VALUE operation takes the bytes of a key as a parameter,
GET_PROVIDERS takes a CID string. In other words,
GET_PROVIDERS is specific to IPFS, while
GET_VALUE is a generic operation from the Kademlia specification.
ADD_PROVIDER creates a provider record announcing to the network that a node is providing a specific CID. By default, the record expires after 24 hours.
GET_PROVIDERS returns the peers storing the CID (i.e., the key).
There is a proposal to remove the specific
Expand Your Knowledge
The DHT is a complex topic that involves understanding several concepts. The following video provides more information.
If you want to get more information, refer to the following links: