Kademlia DHT: Implementing Peer Discovery in Go

Centralized discovery is a single point of failure. When you’re building a distributed storage system, you eventually need a way for nodes to find each other without a registry that can go down.

Kademlia DHT (Distributed Hash Table) is the standard solution. It’s what BitTorrent, IPFS, and Ethereum use. The key insight is elegant: organize nodes in a logical space defined by XOR distance, so lookups converge in O(log n) network hops regardless of cluster size.

The XOR Metric

Every node has a 160-bit (or 256-bit) ID. The distance between two nodes is the XOR of their IDs:

type NodeID [20]byte

func Distance(a, b NodeID) NodeID {
    var d NodeID
    for i := range a {
        d[i] = a[i] ^ b[i]
    }
    return d
}

This metric has two useful properties: it’s symmetric (distance(a,b) == distance(b,a)) and it forms a tree structure where each bit narrows the search space by half.

The Routing Table

Each node maintains a routing table of k-buckets — one bucket per bit position in the ID space. Each bucket holds up to k contacts (typically k=20).

type RoutingTable struct {
    self    NodeID
    buckets [160]*KBucket
    mu      sync.RWMutex
}

func (rt *RoutingTable) BucketIndex(id NodeID) int {
    d := Distance(rt.self, id)
    for i := 0; i < 160; i++ {
        byteIdx, bitIdx := i/8, 7-(i%8)
        if (d[byteIdx]>>bitIdx)&1 == 1 {
            return 159 - i
        }
    }
    return 0
}

The bucket index is the position of the highest set bit in the XOR distance — the further a node is, the fewer contacts you keep about it. This is by design: you need fine-grained knowledge of nearby nodes, not distant ones.

The Four RPCs

Kademlia defines four operations:

RPC	Purpose
PING	Check if a node is alive
STORE	Ask a node to store a key-value pair
FIND_NODE	Return the k closest nodes to a given ID
FIND_VALUE	Return a stored value, or the k closest nodes if not found

The FIND_NODE lookup drives peer discovery. You start with the k closest contacts you already know, ask them for their k closest contacts to the target ID, and repeat until the set stops changing.

func (n *Node) LookupNode(ctx context.Context, target NodeID) ([]Contact, error) {
    seen := make(map[NodeID]bool)
    closest := n.table.ClosestContacts(target, Alpha) // Alpha = 3 parallel queries

    for {
        candidates := filterUnseen(closest, seen)
        if len(candidates) == 0 {
            break
        }

        results := n.parallelFindNode(ctx, candidates[:min(Alpha, len(candidates))], target)
        for _, c := range results {
            seen[c.ID] = true
            closest = mergeAndSort(closest, results, target)
        }

        if !improved(closest) {
            break
        }
    }

    return closest[:min(K, len(closest))], nil
}

The SQLite Persistence Layer

Pure in-memory routing tables mean every node restart requires a full re-bootstrap. Persisting to SQLite gives you warm restarts:

const schema = `
CREATE TABLE IF NOT EXISTS contacts (
    id        BLOB PRIMARY KEY,
    addr      TEXT NOT NULL,
    last_seen INTEGER NOT NULL
);`

func (rt *RoutingTable) Persist(db *sql.DB) error {
    tx, _ := db.Begin()
    stmt, _ := tx.Prepare(`
        INSERT OR REPLACE INTO contacts(id, addr, last_seen)
        VALUES (?, ?, ?)`)
    defer stmt.Close()

    for _, bucket := range rt.buckets {
        for _, c := range bucket.Contacts() {
            stmt.Exec(c.ID[:], c.Addr, time.Now().Unix())
        }
    }
    return tx.Commit()
}

Tradeoffs to Know Before You Ship

• Churn handling: Kademlia prefers long-lived contacts. In a high-churn environment (cloud instances coming and going), your k-buckets go stale faster than the refresh interval can compensate.
• Sybil attacks: Kademlia has no identity verification by default. Malicious nodes can flood a region of the ID space. Mitigate with signed node IDs tied to cryptographic keypairs.
• Bootstrap paradox: A node with an empty routing table needs at least one known peer to join the network. Ship a list of hardcoded bootstrap nodes.