Distributed hash tables: Chord

Click through the three lookups. Some resolve in 0 hops — node A already knows the answer from its own successor pointer. Others take 1 or 2 jumps. Nobody ever walks the ring node by node; each hop leaps as far around the ring as it can without overshooting.

Every node keeps a finger table: $m$ pointers, where finger $i$ points to the successor of a position exponentially further around the ring than finger $i-1$.

A lookup for key $k$ starting at node $n$ jumps to the furthest finger that still lies strictly between $n$ and $k$ — never past it — repeating until $k$ falls inside the current node's own successor arc, at which point that successor is the owner.

• $m$ — bits in the address space; $4$ here, so $16$ ring positions and $4$ fingers per node.
• $\text{finger}_i(n)$ — node $n$'s $i$-th finger: the successor of $n + 2^i$.
• $\text{successor}(x)$ — the same clockwise-successor rule as consistent hashing: the first node at or after position $x$.

1. Fingers double in reach

   • Finger $0$ reaches $1$ step ahead
   • Finger $1$ reaches $2$ steps ahead
   • Finger $2$ reaches $4$ steps ahead

   And so on — each finger roughly doubles how far around the ring it can see.

2. At most m hops

   Because each hop at least halves the remaining clockwise distance to the target, no lookup on an $m$-bit ring ever takes more than $m$ hops — $O(\log N)$ instead of walking every node.

Start from any of the 4 nodes and drag the target key all the way around the ring. Watch the path column: it never lists more than a couple of intermediate nodes, no matter how far the key sits from the start — each hop is a big leap, not a small step.

Ring size $16$ ($m=4$); nodes A@2, B@6, C@9, D@13 — the same ring the consistent-hashing chapter used:

1. Node A's finger table

   • $\text{finger}_0(2)=\text{successor}(2+2^0)=\text{successor}(3)=6$
   • $\text{finger}_1(2)=\text{successor}(2+2^1)=\text{successor}(4)=6$
   • $\text{finger}_2(2)=\text{successor}(2+2^2)=\text{successor}(6)=6$
   • $\text{finger}_3(2)=\text{successor}(2+2^3)=\text{successor}(10)=13$

   So A's fingers are $[6, 6, 6, 13]$.

2. Lookup key@5 from A — 0 hops

   Key position $5$ falls in $(2, 6]$ — exactly the arc A's own finger $0$ already covers. A answers immediately: owner is B (pos 6), no other node contacted.

3. Lookup key@12 from A — 2 hops

   1. $12$ is past B's arc, so A jumps to its furthest finger that doesn't overshoot: $6$ (node B)
   2. B's fingers are $[9, 9, 13, 2]$; $12$ is still past B's own successor ($9$), so B jumps to its furthest qualifying finger, $9$ (node C)
   3. C's fingers are $[13, 13, 13, 2]$; now $12$ falls in $(9, 13]$, C's own successor arc — so C answers directly: owner is D (pos 13)

   Path: A → B → C, 2 hops.