November 1, 2010 at 12:38 Kademlia DHT: Basics
Hello!
In this article, as I hope in the following, I want to talk about one of the modern structured peer-to-peer networks. This material includes my processing of documentation, descriptions and articles found on the topic. As an introduction, a general brief theory of p2p networks, DHT, is presented, and only then the main part, to which the note is devoted, follows.
The distribution of data, processor time and other resources between users is forced to look for solutions for networking at different levels and interactions.
Instead of client-server interaction, p2p (point-to-point) networks come to provide a greater level of scalability, autonomy, anonymity, and fault tolerance.
The following will give a general classification.
According to the degree of centralization, the following types of p2p networks can be distinguished:
Cons of this type of network:
Hybrid - Networks that contain two types of nodes: general purpose and super-nodes (Super Peer). The latter are assigned dynamically depending on certain conditions and allow you to control the routing and indexing of data on the network.
Cons and pros depend on the degree of "hybridity" - which characteristics it inherits from centralized and which from decentralized (which will be discussed later).
Decentralized - This type of network implies a complete lack of servers. This eliminates the bottleneck from the network.
Minuses:
Decentralized networks can be divided into structured and unstructured. In the first case, the network topology is built according to certain rules that allow you to organize a quick data search, however, alas, only by exact coincidence. Each node, in fact, is responsible for its own data area (how such areas are distinguished, their type, arrangement of routing tables - all this depends on the particular network topology). In unstructured networks, it is not known in advance where the request can be sent, therefore, in the simplest version, the option of flood requests is used: the node sends the request to neighbors, those of their own, etc.). It is important that TTL (Time To Live) is defined for such requests, which allows them to be cut off after a certain number of network jumps. Obviously that at low TTL, the network will produce false search results (without reaching some sources), and at high - the time for requests, and the amount of traffic can inadmissibly increase. However, unlike structured networks, it is possible to search not only for exact matches, which is important for file-sharing systems. The scalability of unstructured networks, if not absent, is very problematic (the presence of TTL and the growing time to search for data).
When designing the topology and protocols of structured networks, the following relations are considered optimal:
- The size of the routing table on each node: O (log (n))
- The complexity of the search: O (log (n))
DHT (Distributed Hash Table) - a distributed hash table. This structure is often used for decentralized topologies. However, this is not the only choice (as the literature suggests, however, it is better to do further independent searches here).
For each value (data) on each node, a hash is calculated according to certain rules (for example, using SHA-1), which becomes the key. Also, the node identifier is calculated (the same length as the hash, and often the same function). Thus, each host has its own identifier. Keys are published online. The node is responsible for the keys of the table that are close to it in a certain metric (ie distance), here it is implied that the key is “similar” to the identifier, if we omit the language of mathematics. Due to this, each node occupies its own area of responsibility when storing keys and related information (coordinates of the node on which the value is located). This allows you to organize the search algorithm according to exact values in a certain way (first, calculate the value key for the search, for example, a file name,
DHT fully delivers resiliency and scalability. In combination with Peer Exchange, for example, DHT allows you to intercept the functions of a Torrent tracker.
The creators of this topology are Petar Maymounkov and David Mazières. The protocol and table building are based on determining the distance between nodes through an XOR metric:
d (x, y) = x XOR y. It is important to note that distance is the result of the XOR operation, interpreted as a number, not the number of different bits (this criterion can also generate a metric in the key / identifier space). Those. with a key length of 4 bits: d (2,5) = 0010 XOR 0101 = 0111 = 7. The
XOR metric satisfies all axioms of the metric:
This property is noted in connection with the possibility of formal proof of theses on the size of routing tables and the complexity of the search. (In fairness, provided as an outline).
An algorithm for constructing routing tables is based on calculating the distances between nodes (by applying a metric to their identifiers).
Each i-th column of the table is responsible for storing information about nodes at a distance from 2 ^ (i + 1) to 2 ^ i. Thus, the last column for node 0111 can contain information about any nodes 1xxx, the penultimate one about nodes 00xx, and even one level closer - about nodes 010x.
Of course, in a real network, the key length is usually applied to 128, or 160 bits. Depends on the implementation.
Further, a restriction is introduced on the number of stored nodes at each level, K. Therefore, the columns of the table limited to such K are called K-buckets (unfortunately, the Russian equivalent sounds completely dissonant).
If we look at the binary search tree, the sheets of which contain the identifiers of the nodes, it becomes clear that such a K-buckets structure is not random: each node (as in the example 110) receives knowledge of at least one member of each subtree (for 110 marked with filled ovals). Thus, each K-bucket reflects the connection of the node with no more than K participants of the subtree at level i.
The Kademlia protocol contains 4 types of messages:
PING is needed to verify the existence of a particular node in the network. For example, it is used when trying to add a node to the K-bucket, when it is already full: existing nodes are polled, if there is no answer, then the node is inserted. It is worth noting that older nodes are located at the bottom of the K-bucket, this is based on experimental data suggesting that the longer the node remains on the network, the less likely it is to leave it. Therefore, they will be interviewed only after newer ones.
STORE request that allows you to place information on a given node. Before executing STORE, the node must find K the values closest to the key that it is going to publish, and only then send it to each STORE with the key and its coordinates. Storage immediately on K nodes allows you to increase the availability of information.
FIND_VALUE query, which is often repeated to form an iteration, allowing you to find the value by key. Implements a value search in the network. It returns either K of the nearest nodes, or the value itself, depending on the achievement of the node that stores the desired data. Iterations stop just when the value is returned (success), or when the K nodes already polled are returned (there is no value in the network).
FIND_NODE is a query used to find the closest K to a given identifier (the behavior is similar to FIND_VALUE, only never returns a value, always nodes!). It is used, for example, when connecting a node to the network according to the following scheme:
- Contact with the bootstrap node
- Sending a FIND_NODE request with its identifier to the bs node, further iterative sending
- Updating K-buckets (in this case, both the K-buckets of the new node are updated, as well as all the requests passed by (here the symmetry of the XOR metric is on hand))
As you can see, the protocol in its specification practically does not cover security issues, which is reflected in Research and attack work on Kademlia-based networks.
Of the features, it is worth emphasizing the presence of replication, the lifetime of the value (the need to re-post it after a certain period of time), parallelism when sending FIND_ * requests in order to reach the necessary nodes in a shorter time (denoted by α, in implementations it is usually equal to 3). With each passing request, an attempt is made to update the K-bucket, which allows you to keep the routing tables as optimal as possible.
First of all, the most famous Kademlia-based network is the Kad Network, available on aMule / eMule . Bootstrap uses existing nodes in eDonkey.
Khashmir - Kademlia Python implementation used in BitTorrent
Of the currently developing and active libraries, I would also
mention maidsafe-dht - C ++ infrastructure implementation with support for UDT and NAT Traversal .
Mojito - Java library from LimeWire.
I would like to receive comments on what should be delved into in more detail, as the article is extremely superficial. In order to arouse interest, and not put all the cards at once on the table. I myself plan in the next article about Kademlia to talk about security issues, attacks and their prevention.
In this article, as I hope in the following, I want to talk about one of the modern structured peer-to-peer networks. This material includes my processing of documentation, descriptions and articles found on the topic. As an introduction, a general brief theory of p2p networks, DHT, is presented, and only then the main part, to which the note is devoted, follows.
1. General p2p theory
The distribution of data, processor time and other resources between users is forced to look for solutions for networking at different levels and interactions.
Instead of client-server interaction, p2p (point-to-point) networks come to provide a greater level of scalability, autonomy, anonymity, and fault tolerance.
The following will give a general classification.
According to the degree of centralization, the following types of p2p networks can be distinguished:
- Centralized
- Hybrid
- Fully decentralized
Cons of this type of network:
- The server represents a network bottleneck. Failure leads to a complete loss of system performance.
- Server Legislative Vulnerability
- With a significant increase in the network population, the server will undergo a kind of DDoS attack, leading to its failure.
- The whole process from searching to receiving a file is carried out according to the shortest possible scheme: a search request to the server, delivery of results from the server, connection to the desired node.
Moreover, it is quite possible to search not only for exact matches, which is important, as will be shown later.
Hybrid - Networks that contain two types of nodes: general purpose and super-nodes (Super Peer). The latter are assigned dynamically depending on certain conditions and allow you to control the routing and indexing of data on the network.
Cons and pros depend on the degree of "hybridity" - which characteristics it inherits from centralized and which from decentralized (which will be discussed later).
Decentralized - This type of network implies a complete lack of servers. This eliminates the bottleneck from the network.
Minuses:
- Certain routing and search algorithms are needed, sometimes not guaranteeing the reliability of the result.
- To be included in such a network, you need to know the coordinates of at least one node, therefore, lists with a certain amount of address data of network participants must be published in publicly available sources (for example, on sites). The connection process itself implies a bootstrap / bootstrap stage, which is why such lists are also called bootstrap lists.
- Server exclusion allows the network to be fault tolerant, even with a rapidly growing / falling number of participants.
- Greater censorship protection
Decentralized networks can be divided into structured and unstructured. In the first case, the network topology is built according to certain rules that allow you to organize a quick data search, however, alas, only by exact coincidence. Each node, in fact, is responsible for its own data area (how such areas are distinguished, their type, arrangement of routing tables - all this depends on the particular network topology). In unstructured networks, it is not known in advance where the request can be sent, therefore, in the simplest version, the option of flood requests is used: the node sends the request to neighbors, those of their own, etc.). It is important that TTL (Time To Live) is defined for such requests, which allows them to be cut off after a certain number of network jumps. Obviously that at low TTL, the network will produce false search results (without reaching some sources), and at high - the time for requests, and the amount of traffic can inadmissibly increase. However, unlike structured networks, it is possible to search not only for exact matches, which is important for file-sharing systems. The scalability of unstructured networks, if not absent, is very problematic (the presence of TTL and the growing time to search for data).
When designing the topology and protocols of structured networks, the following relations are considered optimal:
- The size of the routing table on each node: O (log (n))
- The complexity of the search: O (log (n))
2. DHT
DHT (Distributed Hash Table) - a distributed hash table. This structure is often used for decentralized topologies. However, this is not the only choice (as the literature suggests, however, it is better to do further independent searches here).
For each value (data) on each node, a hash is calculated according to certain rules (for example, using SHA-1), which becomes the key. Also, the node identifier is calculated (the same length as the hash, and often the same function). Thus, each host has its own identifier. Keys are published online. The node is responsible for the keys of the table that are close to it in a certain metric (ie distance), here it is implied that the key is “similar” to the identifier, if we omit the language of mathematics. Due to this, each node occupies its own area of responsibility when storing keys and related information (coordinates of the node on which the value is located). This allows you to organize the search algorithm according to exact values in a certain way (first, calculate the value key for the search, for example, a file name,
DHT fully delivers resiliency and scalability. In combination with Peer Exchange, for example, DHT allows you to intercept the functions of a Torrent tracker.
3. Kademlia
Metrics
The creators of this topology are Petar Maymounkov and David Mazières. The protocol and table building are based on determining the distance between nodes through an XOR metric:
d (x, y) = x XOR y. It is important to note that distance is the result of the XOR operation, interpreted as a number, not the number of different bits (this criterion can also generate a metric in the key / identifier space). Those. with a key length of 4 bits: d (2,5) = 0010 XOR 0101 = 0111 = 7. The
XOR metric satisfies all axioms of the metric:
- d(x, y) >= 0 // Неотрицательность
- d(x, y) == 0 <=> x == y
- d(x, y) = d(y, x) // Симметричность
- d(x, y) <= d(x, z) + d(z, y) // Неравенство треугольника
This property is noted in connection with the possibility of formal proof of theses on the size of routing tables and the complexity of the search. (In fairness, provided as an outline).
Routing table
An algorithm for constructing routing tables is based on calculating the distances between nodes (by applying a metric to their identifiers).
Each i-th column of the table is responsible for storing information about nodes at a distance from 2 ^ (i + 1) to 2 ^ i. Thus, the last column for node 0111 can contain information about any nodes 1xxx, the penultimate one about nodes 00xx, and even one level closer - about nodes 010x.
Of course, in a real network, the key length is usually applied to 128, or 160 bits. Depends on the implementation.
Further, a restriction is introduced on the number of stored nodes at each level, K. Therefore, the columns of the table limited to such K are called K-buckets (unfortunately, the Russian equivalent sounds completely dissonant).
If we look at the binary search tree, the sheets of which contain the identifiers of the nodes, it becomes clear that such a K-buckets structure is not random: each node (as in the example 110) receives knowledge of at least one member of each subtree (for 110 marked with filled ovals). Thus, each K-bucket reflects the connection of the node with no more than K participants of the subtree at level i.
Protocol
The Kademlia protocol contains 4 types of messages:
- Ping
- STORE
- FIND_VALUE
- FIND_NODE
PING is needed to verify the existence of a particular node in the network. For example, it is used when trying to add a node to the K-bucket, when it is already full: existing nodes are polled, if there is no answer, then the node is inserted. It is worth noting that older nodes are located at the bottom of the K-bucket, this is based on experimental data suggesting that the longer the node remains on the network, the less likely it is to leave it. Therefore, they will be interviewed only after newer ones.
STORE request that allows you to place information on a given node. Before executing STORE, the node must find K the values closest to the key that it is going to publish, and only then send it to each STORE with the key and its coordinates. Storage immediately on K nodes allows you to increase the availability of information.
FIND_VALUE query, which is often repeated to form an iteration, allowing you to find the value by key. Implements a value search in the network. It returns either K of the nearest nodes, or the value itself, depending on the achievement of the node that stores the desired data. Iterations stop just when the value is returned (success), or when the K nodes already polled are returned (there is no value in the network).
FIND_NODE is a query used to find the closest K to a given identifier (the behavior is similar to FIND_VALUE, only never returns a value, always nodes!). It is used, for example, when connecting a node to the network according to the following scheme:
- Contact with the bootstrap node
- Sending a FIND_NODE request with its identifier to the bs node, further iterative sending
- Updating K-buckets (in this case, both the K-buckets of the new node are updated, as well as all the requests passed by (here the symmetry of the XOR metric is on hand))
As you can see, the protocol in its specification practically does not cover security issues, which is reflected in Research and attack work on Kademlia-based networks.
Of the features, it is worth emphasizing the presence of replication, the lifetime of the value (the need to re-post it after a certain period of time), parallelism when sending FIND_ * requests in order to reach the necessary nodes in a shorter time (denoted by α, in implementations it is usually equal to 3). With each passing request, an attempt is made to update the K-bucket, which allows you to keep the routing tables as optimal as possible.
4. Implementations
First of all, the most famous Kademlia-based network is the Kad Network, available on aMule / eMule . Bootstrap uses existing nodes in eDonkey.
Khashmir - Kademlia Python implementation used in BitTorrent
Of the currently developing and active libraries, I would also
mention maidsafe-dht - C ++ infrastructure implementation with support for UDT and NAT Traversal .
Mojito - Java library from LimeWire.
5. What next?
I would like to receive comments on what should be delved into in more detail, as the article is extremely superficial. In order to arouse interest, and not put all the cards at once on the table. I myself plan in the next article about Kademlia to talk about security issues, attacks and their prevention.
6. Materials and links
- P2P (ENG wikipedia)
- DHT (ENG wikipedia)
- Kademlia (ENG wikipedia)
- Kademlia: A Design Specification
- Kademlia: A Peer to peer information system Based on the XOR Metric
- Theotokis, Spinellis. A Survey of Peer-to-Peer Content Distribution Technologies
- Peer-to-Peer Computing. Principles and Applications. // Springer, 2010