A Kademlia-style distributed hash table in Go: a k-bucket routing table and a networked node that stores and finds values by iterative XOR-distance lookup.
Each node has a 160-bit ID and keeps a routing table of other nodes it has heard from, organised into k-buckets by XOR distance. Values are stored under the SHA-1 of their contents on the k nodes closest to that key, and any node can find a value by walking the network toward the key a few nodes at a time. Nodes talk to each other over TCP using protobuf messages, and the routing table and value store are safe for concurrent use.
Keys and distance. Node IDs and value keys are 20-byte SHA-1 digests. The distance between two keys is their bitwise XOR, treated as a big-endian integer. The keys package provides the hash, per-bit access, XOR distance, and the mapping from a distance to its bucket index (the position of the highest set bit).
Routing table. The table starts as a single bucket holding the local node. Each bucket covers a range of the key space described by a bit prefix and holds at most k nodes. When a bucket fills up, it is split into two only if it contains the local node's own ID; otherwise the new node is dropped. This keeps detailed knowledge of the neighbourhood around the local ID and coarse knowledge of everything else, which is what makes lookups converge in O(log n) hops. ClosestK gathers all known nodes, sorts them by XOR distance to the target, and returns the nearest k.
Wire protocol. Five RPCs are defined: PING, STORE, GET, FIND_NODE and FIND_VALUE, with ACK, NODES and VALUE as replies. Every RPC uses one Message protobuf envelope carrying the sender's ID and address, so every incoming message also serves as an opportunity to learn about a peer. Messages are framed on TCP with a 2-byte big-endian length prefix followed by the serialised protobuf. Each request opens a connection, sends one message, reads one reply, and closes.
Iterative lookup. FindNode and FindValue start from the k closest nodes in the local table and repeatedly query up to alpha unvisited nodes from the candidate set. Each reply's nodes are merged into the candidate set (and into the routing table), which is re-sorted and trimmed to k. The loop stops when a round produces no node closer than the current k-th best. FindValue short-circuits as soon as any node answers with the value.
Bootstrapping. NewNode returns as soon as the listening socket is open. In the background it pings each configured neighbour, inserts those that answer, and asks each for the nodes closest to its own ID, pinging and inserting those as well.
Store. Store hashes the value to get its key, runs FindNode on that key, and sends STORE to each result (storing locally if the local node is among them). If fewer than k nodes end up holding the value, StorageError is returned so the caller knows replication is incomplete.
Shutdown. Shutdown sends each neighbour a PING whose sender has an empty address, which peers interpret as "remove me", then closes the listening socket and marks the node dead. Subsequent calls on the node return ShutdownError.
Concurrency. The routing table is guarded by a mutex, the value store by a read-write mutex, and shutdown state by its own mutex plus a closed-channel signal that the accept loop watches.
| Path | Contents |
|---|---|
api/kdht/ |
Public interfaces (Node, RoutingTable), sentinel errors, key size constants, and the protobuf schema plus generated code |
keys/ |
SHA-1 hashing, bit access, XOR distance and bucket index helpers |
dht/ |
The routing table (routing.go) and the network node (node.go) |
tests/ |
Black-box tests against the public API |
go build ./...
There is no standalone binary; the package is used as a library. A minimal two-node network:
package main
import (
"fmt"
"github.com/rao/kademlia-dht/dht"
"github.com/rao/kademlia-dht/keys"
)
func main() {
a, _ := dht.NewNode(keys.Compute([]byte("a")), "localhost:9001", 2, 3, nil)
b, _ := dht.NewNode(keys.Compute([]byte("b")), "localhost:9002", 2, 3, []string{"localhost:9001"})
defer a.Shutdown()
defer b.Shutdown()
value := []byte("hello, dht")
if err := a.Store(value); err != nil {
panic(err)
}
got, from, err := b.FindValue(keys.Compute(value))
fmt.Printf("%q from %s (err=%v)\n", got, from.Address, err)
}The third and fourth arguments to NewNode are k (bucket size and replication factor) and alpha (lookup parallelism). Store needs at least k reachable nodes, so k must not exceed the network size.
go test ./...
keys/ has unit tests for hashing, bit access, distance and bucket indexing. tests/ exercises the routing table (bucket splitting, capacity, dropping when full, lookup and removal) and the node end to end (ping, store, find node, find value, shutdown semantics, neighbour discovery, and the under-replication error). The node tests bind ports in the 12345 to 12360 range on localhost.
- Buckets are not refreshed and there is no least-recently-seen eviction; a full bucket simply drops newcomers.
- Values are never republished or expired, and nothing is persisted to disk.
- Each RPC opens a fresh TCP connection rather than reusing one per peer.
- Lookups are sequential within a round; alpha bounds how many nodes are contacted per round, not how many are in flight at once.
Originally built for a university distributed-systems course; the wire protocol and interfaces were specified by the course, the implementation is my own.