For that, we'll need to define an Xor method for our Node IDs: Now that we've defined our Node ID thoroughly, we can start on the routing table implementation.
To enable efficient traversal through a DHT, a routing table needs to contain a selection of nodes both close to and far away from our own node.
Kademlia accomplishes this by breaking up the routing table into 'buckets', with each 'bucket' corresponding to a particular range of distances between the nodes stored in that bucket and ourselves.
We'll make use of this in our Update method, which takes a Contact and updates the routing table with it: This function starts by finding the appropriate bucket, then using the iterable module's Find method to locate the contact inside the bucket if it already exists.If it does, it moves the contact to the front of the bucket.This behaviour is an important part of Kademlia's robustness: Nodes that have been around for a long time are more likely to remain in the DHT than new nodes, so Kademlia has a large preference for established nodes.If the node already in the bucket, it's appended to the end if there's room. The TODO here is also important: If adding our contact to the bucket would make the bucket too full, we should asynchronously ping the least-recently-seen element in the bucket (the one at the back of the list).We're also making use of the encoding/hex and rand modules from the Go standard library.
We should also define a function to convert a Node ID back into hex, for printing and so forth: Since this function has the correct signature, our Node ID struct now implements the fmt.
Stringer interface, meaning that our String function will be used to convert our Node ID for display any time we use Printf or similar functions on it.
We should also define a couple of common operations on our Node ID - equality and ordering: Together, these methods define a well-ordering for Node IDs.
The second implication of this approach is that the number of the bucket a given node should be placed in is determined by the number of leading 0 bits in the XOR of our node ID with the target node ID, which makes for easy implementation.
Let's add a function to our Node ID struct to facilitate this: First, we define a Contact struct, which contains the data we need to store in the routing table.
Kademlia is a good example of a basic DHT, because unlike some competing algorithms, it's extremely simple.