Distributed Hash Tables

A DHT is a distributed index: put(key, value) and get(key) without a single machine that knows every mapping. Nodes pick IDs in the same key space as hashed keys. Ownership is a deterministic function of those IDs, so any correct peer can start a lookup and eventually reach a responsible node.

Two classic families dominate interview and paper vocabulary. Chord places IDs on a ring and walks (with logarithmic shortcuts) to the successor. Kademlia uses XOR distance and k-buckets so lookups iteratively ask the closest known peers. Both aim for about O(log N) messages under healthy tables; both spend continuous bandwidth on membership repair.

Production key-value clusters often keep the placement idea (hash → preference list) while replacing pure P2P lookup with a membership gossip layer and coordinator-driven quorums. Understanding the DHT still matters: it explains why adding a node remaps a slice of keys, why replica sets are “next N along the metric,” and why stale routing is a first-class failure mode.

With m-bit IDs, the space is 0…2^m − 1 arranged as a circle. Node n's successor is the next live ID clockwise. Key k belongs to successor(k). If nodes are sparse, arcs are uneven; virtual nodes (multiple IDs per host) or careful ID assignment smooth load the same way consistent hashing does for caches.

Correctness of a lookup does not require every finger to be perfect. Chord's proofs lean on successor correctness: as long as the predecessor/successor linked list is connected, you can crawl slowly around the ring. Fingers only make that crawl logarithmic. That is why stabilization prioritizes successor repair over fancy long-range links.

m-bit circular space: 0 .. 2^m - 1

successor(k) = first live node with id ≥ k (mod 2^m)

Naive lookup from any node:
  while not responsible for k:
    ask local successor
  // O(N) hops — correct but useless at scale

With fingers:
  each hop jumps to the farthest known node still ≤ k
  expected O(log N) hops when fingers are fresh

Node n's ith finger ideally points at successor(n + 2ⁱ⁻¹). Early fingers cover local neighborhood; later fingers jump halfway across the ring. A lookup always chooses the finger that gets closest to the key without overshooting in the Chord “still ≤ key” sense, then continues.

sequenceDiagram
    participant C as Client / requester
    participant N as Node n
    participant F as Distant finger
    participant S as Successor of key
    C->>N: find_successor(key)
    N->>F: key is far; ask finger closer to key
    F->>S: remaining distance small; ask near node
    S-->>F: I own key (or hold replica)
    F-->>N: successor reply
    N-->>C: owner address + optional value

Stale fingers are expected. A finger that points at a dead node is replaced after a failed RPC and a refresh. A finger that points slightly farther than ideal only costs an extra hop. The dangerous case is believing a wrong successor: then you may declare “not found” for keys that still live one hop away, or hand writes to the wrong owner until stabilization heals the ring.

Join: contact any bootstrap peer, learn your successor, initialize fingers, then notify so the predecessor pointer updates. Key transfer moves only the keys you now own—about 1/(N+1) of the space in expectation under uniform hashing—same intuition as consistent hashing.

Leave or crash: neighbors notice timeouts. Successor lists of length r let you skip dead nodes. Keys that lived only on the dead node are lost unless you kept a replication factor ≥ 2 and repaired promptly. DHT papers often assume soft-state republish: publishers refresh puts on a timer so lost replicas regenerate after churn.

stabilize() periodically:
  x = successor.predecessor
  if x is between me and successor:
    successor = x          // someone joined in the middle
  successor.notify(me)

notify(n):
  if predecessor is nil or n is between predecessor and me:
    predecessor = n

// Concurrent joins need these loops; a single atomic “insert on ring”
// does not exist across failure-prone peers.

Kademlia drops the ring metaphor. Distance(a, b) = a ⊕ b. Lookups are iterative: ask α parallel peers closest to the target, learn closer contacts, repeat until the closest k peers stop improving. Values are stored on the k nodes closest to the key.

Each node keeps one k-bucket per bit-prefix distance. Buckets for nearby IDs stay small and specific; distant buckets cover huge ranges with only k contacts. Under churn, preferring long-lived peers (ping before eviction) keeps routing resilient—important for open P2P overlays where median session length is short.

Example (toy 4-bit IDs):
  me = 0b0101 (5)
  peer = 0b0111 (7)  → distance 0b0010 = 2  (close)
  peer = 0b1101 (13) → distance 0b1000 = 8  (farther)

Lookup for key 0b0110:
  start with α contacts from the bucket covering that prefix
  each round replace with closer contacts from replies
  stop when k closest known peers have been queried

Soft-state DHTs often expire values unless republished. That matches content announcement (torrent peer lists) better than durable databases. Durable DHTs add disk on each node, anti-entropy between replica sets, and explicit delete tombstones with retention windows—at which point you have reinvented much of a distributed KV store.

Concurrent puts to the same key during a partition produce divergent replicas. The overlay can deliver you the set of holders; choosing LWW, vector clocks, or CRDTs is an application or storage-layer decision sitting above the DHT routing plane.

Datacenter:
  N = 1e6, hops ≈ 20, RTT = 0.5 ms
  iterative serial ≈ 10 ms  (borderline for tight APIs)
  with α-parallel + owner cache: often 1–2 RTTs after warm-up

WAN / P2P:
  RTT = 50–150 ms, hops ≈ 10–20
  multi-second gets unless values are cached near the edge

Design consequence:
  user-facing get → cache preference list / full membership locally
  DHT walk → background discovery, rare miss path, or open overlays

This is why managed stores advertise “consistent hashing” while implementing local membership views: they keep the remap math and drop the multi-hop tax on the hot path.

BitTorrent's distributed tracker, IPFS-style content routing, and some service-discovery overlays are literal DHTs. Datacenter stores often keep only the hash-ring placement fragment and replace multi-hop get with local membership maps—still “DHT-inspired,” not a full Chord deployment.

Interview framing that stays accurate:

"We place keys with consistent hashing / DHT-style ownership so
adding a node remaps ~1/N of keys. Clients (or coordinators) know
membership via gossip, so a get is one RPC to the preference list,
not a multi-hop Chord walk. Replication uses the next N owners on
the ring. Routing-table churn is managed by the membership layer."