Day 01: Distributed Hash Tables & Kademlia

The XOR metric that quietly organizes every modern swarm.

⏱ ~90 min · theory 45 / lab 45

Almost everything else in this manual sits on top of one idea: a distributed hash table.
A DHT lets thousands of machines, none of which trust or even know each other, collectively behave like
one giant key–value store — with no server, no central index, and no single point of failure. When you
ask the network "who has the data for key K?", the lookup converges on the answer in roughly
log₂(N) hops even across millions of nodes. Kademlia is the design that made this practical,
and it is the ancestor of the BitTorrent DHT, IPFS, Ethereum's discovery layer, and Holepunch's
hyperdht.

1.1 The problem a DHT solves

Imagine you want to store a billion key–value pairs across a fluctuating set of peers. A naive approach
puts everything on one coordinator — but that coordinator is a bottleneck and a kill switch. The DHT insight
is to give every node and every key an ID drawn from the same address space (say, 256-bit
numbers), then define a rule: a key lives on the node(s) whose ID is "closest" to the key's ID.
Now any node can independently figure out where a key should be, without asking a server.

Two questions fall out of that: (1) what does "closest" mean, and (2) how does a node that knows only a
handful of peers route a query to the right corner of the network? Kademlia answers both elegantly.

1.2 XOR as a distance metric

Kademlia measures distance between two IDs as their bitwise XOR, interpreted as an integer:
distance(a,b) = a XOR b. This looks strange the first time you see it, but it has exactly the
properties a metric needs:

Identity: d(a,a) = 0 — a node is distance zero from itself.
Symmetry: d(a,b) = d(b,a) — if I am close to you, you are equally close to me. (This is the property the older Chord ring lacked, and why Kademlia routing tables self-reinforce.)
Triangle inequality: d(a,c) ≤ d(a,b) ⊕ d(b,c) holds.
Unidirectionality: for any point a and distance Δ, there is exactly one point b with d(a,b)=Δ. This means all lookups for the same key converge along the same path, which is what makes caching and routing-table convergence work.

The magic is that XOR distance is prefix-sensitive: two IDs that share a long leading bit-prefix are
numerically close. So "getting closer to the target" is the same as "matching more of its high bits," and that
turns routing into a binary-search-like descent through the ID space.

Intuition
Think of IDs as leaves of a binary tree. Each step of a lookup lets you correct one more bit, halving the
remaining search space. Halving repeatedly across N nodes is why lookups take O(log N) hops.

1.3 k-buckets: the routing table

A node can't remember every peer, so Kademlia keeps a structured, partial view. For each bit-distance band
i (peers whose ID differs from mine starting at bit i), the node keeps a
k-bucket: a list of up to k contacts (commonly k = 20). The result is a
routing table that is dense for nearby IDs and sparse for far ones — you know your immediate neighborhood
in fine detail and the rest of the universe only coarsely. That asymmetry is exactly what you need: to route, you
only ever need a peer that is closer than you to the target, and the table guarantees you have one.

k-buckets also encode a liveness policy. When a bucket is full and a new node appears, Kademlia pings the
least-recently-seen contact; if it still answers, the newcomer is discarded. This deliberately favors
long-lived nodes, because empirically a node that has been up for an hour is likely to stay up another hour. It
also makes the table naturally resistant to flooding attacks.

1.4 The four RPCs

RPC	Purpose
`PING`	Liveness check; the heartbeat behind bucket maintenance.
`STORE`	Tell a node to hold a `(key, value)` pair.
`FIND_NODE`	"Give me the `k` closest contacts you know to this ID." The workhorse of routing.
`FIND_VALUE`	Like `FIND_NODE`, but if the node holds the value it returns it directly.

1.5 Iterative lookup and the α parameter

To find a target, a node starts with the closest contacts it knows and sends them FIND_NODE in
parallel. Each response returns contacts that are (hopefully) closer; the node keeps the best results it has seen,
picks the closest un-queried ones, and repeats. Lookups are iterative — the searcher drives every
step and stays in control — rather than recursive, which improves resilience to misbehaving nodes.

The concurrency factor α (typically 3) controls how many queries are in flight at once. It
trades latency against redundant traffic: higher α tolerates slow or dead peers without stalling
the descent, at the cost of extra packets.

Holepunch note
hyperdht is Kademlia-derived but tuned for a different job: instead of storing arbitrary blobs, its
primary role is peer discovery and connection bootstrapping. It stores small mutable/immutable records
(signed announcements of "I am reachable at this address") and integrates UDP hole-punching directly into the
lookup. Same routing skeleton, different payload. Keep this contrast ready — it is a likely interview question.

1.6 Lab — build a minimal Kademlia routing core

Goal

Implement XOR distance, a k-bucket routing table, and a simulated iterative lookup over an in-memory network
of nodes. You will see the log N convergence with your own eyes by printing each hop.

Setup

# no dependencies — pure Node
mkdir kad-lab && cd kad-lab
node --version   # v18+ recommended

Step 1 — IDs and XOR distance

We use 16-bit IDs (a Buffer of 2 bytes) so the numbers stay small and printable. Real systems use
160 or 256 bits, but the math is identical.

// kad.js
const ID_BITS = 16;
const ID_BYTES = ID_BITS / 8;

function randomId() {
  const b = Buffer.allocUnsafe(ID_BYTES);
  for (let i = 0; i < ID_BYTES; i++) b[i] = (Math.random() * 256) | 0;
  return b;
}

// XOR distance as a BigInt so it is directly comparable
function distance(a, b) {
  let d = 0n;
  for (let i = 0; i < ID_BYTES; i++) d = (d << 8n) | BigInt(a[i] ^ b[i]);
  return d;
}

// index of the most-significant differing bit -> which bucket a peer belongs in
function bucketIndex(self, other) {
  for (let i = 0; i < ID_BYTES; i++) {
    const x = self[i] ^ other[i];
    if (x !== 0) return i * 8 + Math.clz32(x) - 24; // clz32 on a byte
  }
  return ID_BITS; // identical
}

Step 2 — the k-bucket routing table

const K = 4; // small k so buckets fill up visibly

class RoutingTable {
  constructor(selfId) {
    this.self = selfId;
    this.buckets = Array.from({ length: ID_BITS + 1 }, () => []);
  }
  add(node) {
    if (node.id.equals(this.self)) return;
    const b = bucketIndex(this.self, node.id);
    const bucket = this.buckets[b];
    if (bucket.find(n => n.id.equals(node.id))) return;
    if (bucket.length < K) bucket.push(node);
    // (real impl: ping least-recently-seen before evicting)
  }
  // return the n contacts closest to a target id
  closest(target, n = K) {
    return this.buckets.flat()
      .sort((x, y) => (distance(x.id, target) < distance(y.id, target) ? -1 : 1))
      .slice(0, n);
  }
}

Step 3 — a simulated network + iterative lookup

const ALPHA = 3;

class Node {
  constructor(id) { this.id = id; this.table = new RoutingTable(id); }
  // the FIND_NODE RPC: just answer with my closest known contacts
  findNode(target) { return this.table.closest(target); }
}

function buildNetwork(count) {
  const nodes = Array.from({ length: count }, () => new Node(randomId()));
  // seed each node's table with random acquaintances (bootstrap gossip)
  for (const n of nodes)
    for (let i = 0; i < 20; i++)
      n.table.add(nodes[(Math.random() * count) | 0]);
  return nodes;
}

// iterative lookup driven by one starting node
function lookup(start, target) {
  let shortlist = start.table.closest(target, ALPHA);
  const queried = new Set();
  let hops = 0, best = distance(start.id, target);

  while (true) {
    const batch = shortlist.filter(n => !queried.has(n.id.toString('hex'))).slice(0, ALPHA);
    if (batch.length === 0) break;
    hops++;
    let found = [];
    for (const peer of batch) {
      queried.add(peer.id.toString('hex'));
      found = found.concat(peer.findNode(target));
    }
    // merge, dedupe, keep K closest overall
    const seen = new Map();
    for (const n of shortlist.concat(found)) seen.set(n.id.toString('hex'), n);
    shortlist = [...seen.values()]
      .sort((x, y) => (distance(x.id, target) < distance(y.id, target) ? -1 : 1))
      .slice(0, K);
    const closest = distance(shortlist[0].id, target);
    if (closest >= best) break; // no improvement -> converged
    best = closest;
  }
  return { hops, winner: shortlist[0], best };
}

// --- run it ---
const N = 5000;
const net = buildNetwork(N);
const target = randomId();
const start = net[0];
const r = lookup(start, target);
console.log(`network size  : ${N}`);
console.log(`target        : ${target.toString('hex')}`);
console.log(`hops to find  : ${r.hops}`);
console.log(`log2(N)       : ${Math.log2(N).toFixed(1)}`);
console.log(`closest found : ${r.winner.id.toString('hex')}`);

Run & expected output

node kad.js
// network size  : 5000
// target        : 9c41
// hops to find  : 4         <- compare to log2(5000) ≈ 12.3
// closest found : 9c2f      <- shares the 9c.. prefix

Experiments to try

Sweep N from 100 to 100000 and plot hops vs N. The curve is logarithmic — this is the headline property of every DHT.
Set ALPHA = 1 and re-run. Lookups still work but take more rounds and are fragile if a queried node is "dead." Then try ALPHA = 8 and watch redundant queries climb.
Reduce the bootstrap acquaintance count from 20 to 3. Lookups degrade or fail — the routing table is too sparse. This is why real DHTs run periodic bucket-refresh lookups.

1.7 Self-check & interview drill

I can define XOR distance and name its four metric properties.
I can explain what a k-bucket stores and why eviction favors old nodes.
I can walk through an iterative lookup and the role of α.
My lab prints hop counts that grow logarithmically with network size.