Last time we looked at Chord (link). It solved the problem of finding data efficiently in P2P networks. Chord works and can scale, but it is not simple. Kademlia is an alternative routing algorithm that is more popular than Chord. That is thanks to its relative simplicity. It can also route more efficiently and is better in high-churn environments (e.g., mobile networks).

Quite The Introduction

Kademlia was proposed in 2002 by Petar Maymounkov and David Mazieres. It takes the same basic approach as other DHTs. The keys and node IDs are 160-bit SHA-1 hashes. Nodes store nearby key-value pairs, and the routing uses the ID of the nodes. XOR is its distance metric, allowing for less rigid routing tables. It achieves lower latency because it sends queries to multiple nodes during an interval. Finally, it uses a single routing algorithm for all hops.

To Tree Or Not

Chord arranges its nodes in a ring. Kademlia treats its nodes like they are leaves in a binary tree. It has buckets corresponding to a unique prefix (e.g., 0011). We put nodes in buckets according to their node ID. The tree is divided into subtrees at each node so that the subtrees don't contain the node. So the highest subtree contains half of the binary tree without the node. The next highest subtree is half of half, and so on. Every node knows of at least one node in each subtree.

For example, Node 3 knows of one or more nodes in each subtree. To locate a specific node, Node 3 calls up the node in the subtree of the target node. In other words, it calls the closest node. Instead of forwarding the call to the next closest node, the receiving node responds with the nodes that Node 3 should query. Then, the initiating node calls its new leads, and the process repeats.

Who Owns What?

Nodes store nearby keys. XOR is used to determine closeness. The distance between 2 IDs is their bitwise XOR expressed as a number. For example, given the nodes 8 and 15, the distances between them and Key 7 are:

Node 8 = 1000

Node 15 = 1111

Key 7 = 0111

Distance Node 8 to Key 7 = 1000 XOR 0111

                                  = 1111

                                  = 15

Distance Node 15 to Key 7 = 1111 XOR 0111

                                  = 1000

                                  = 8

Node 15 stores Key 7 instead of Node 8.

Method Behind The Madness

XOR means that only different nodes can have a non-zero distance from each other. It never results in negative interval values. It is symmetric (i.e., A XOR B = B XOR A) and has the triangle property. The triangle property says that the distance between two nodes (A and C) is always equal to or less than the distance between the two nodes via intermediate nodes. In other words:

d( A, C ) ≤ d( A, B ) + d( B, C )

Non-negative distances mean that the distance between any two nodes is always the same. Therefore, nodes along the lookup path can cache key-value pairs. Symmetry allows nodes to gain valuable information about each other while routing. They can then add that information to their routing table.

To Manage And Update

Kademlia nodes store the contact information (i.e., IP address, UDP port, Node ID) for other nodes in k-buckets. The buckets are lists of up to k nodes sorted by most recently communicated with, in descending order. Each bucket corresponds to an ID prefix. When a node gets any message, it updates the appropriate k-bucket. If the sending node already exists in the bucket, the receiving node moves the sending node to the end of the list. Otherwise, we need to check if the bucket is full. If the bucket has space, the receiving node adds the new node to the end of the bucket. If there is no space in the bucket, we ping the first node in the bucket (i.e., the node that has been silent for the longest time). We remove the first node and add the new node to the end of the bucket if we don’t get a response. Otherwise, we move the first node to the end of the bucket and discard the new node. So, Kademlia uses a least-recently seen eviction policy.

For example, Node 3 receives a query from Node 20 asking for Key 72. Node 3 is not responsible for that key. It will return the nodes closest to the key. Before it does that, it updates its buckets. Node 20 belongs to the 101 bucket. That bucket is full. Node 3 pings the first node in that bucket (Node 21). Node 21 does not respond, so it must no longer be there. Node 3 ejects Node 21 from the bucket and adds Node 20 at the end.

For Etiquette and Decorum

Kademlia defines 4 simple RPCs: ping, store, find_node, and find_value. Ping checks whether a node is alive, and store tells a node to remember a key-value pair. Find_node looks for node ID and returns triples of IP address, UDP port, and Node ID. Find_value works like find_node except that it looks for a value using a key ID. It also returns triples unless it has the key-value pair. In that case, it returns the value. All RPC queries have a random 160-bit RPC ID. Responses to a particular request echo the RPC ID.

And The Journey Continues

There is still a lot to discuss regarding Kademlia. However, this post has gotten quite lengthy. We’ll save the remainder for next time.

‍