Kademlia Distributed Hash Table
Kademlia is a distributed hash table where the platform enables the distributed storage of key-value pairs with redundancy.
Kademlia is composed of distributed processors connected together which we call nodes. Each node in the system gets a unique ID, and all IDs in Kademlia are of fixed binary length, including the keys that will be stored. Next, we can logically compute a distance between each ID using the binary XOR distance metric. For each node, we have some mechanism to enable fast $\log n$ retrieval of all $k$ nodes recorded in the system that are closest to the desired ID. This mechanism will enable us fast search and retrieval for a node or a key.
To store a key-value pair, we store the pair in $k$ of the nearest nodes found during the search that are closest to the key. That way, when we want to find the key-value pair, we can search for the $k$ nearest nodes to the key, and poll the node to see if they store the value.
Kademlia employs a routing table in each node to enable fast searching for nodes. The routing table stores most of the nodes seen during the lifetime of a node. A routing table is a dynamically splitting k-bucket. A k-bucket is defined as follows:
A k-bucket stores at most $k$ nodes in a range of IDs. The initial k-bucket has a range of $[0, 2^r]$. When a node is seen, it is stored into the k-bucket that contains its range. If the k-bucket is full, we manage as follows:
- If the k-bucket does not contain the ID of its host, then we can replace existing nodes using a custom defined replacement strategy. We can evict the oldest node, or via some other strategy, and replace it with the new node
- If the k-bucket contains the ID of its host, we split the k-bucket into two k-buckets. Now, we have to k-buckets that cover the range $[0,2^{r-1}]$ and $[2^{r-1}, 2^r]$ respectively. Via this splitting strategy, we eventually will be able to get fine-grained storage of all nodes closest to the host ID
To interact with Kademlia, there are 4 methods available
- $PING$
- $STORE$
- $FIND\_NODE(hash)$
$FIND\_VALUE(key)$
- $PING$ is used to verify if a node is alive
- $FIND\_NODE(hash)$ is used to find all nodes that are closest to the given hash. Starting from the host, we find all $k’$ nodes that are closest to the hash in the routing table. We then recursively query each of the nodes until we get $k$ of the nodes that have an ID that is closest to the hash.
- $STORE$ is used to store a key-value pair into Kademlia. When storing, we use $FIND\_NODE$ to find $k$ of the closest nodes that have an ID closest to the $key$ we want to store. We then store the key-value pair into those nodes. We perform multiple stores of the same value for redundancy.
- $FIND\_VALUE$ is used a wrapper for $FIND\_NODE$.