The Chord Distributed Hash Table

Why Chord matters

Before structured overlays, peer-to-peer systems either kept a central index (Napster — one lawsuit away from oblivion) or flooded queries to every neighbor (Gnutella — O(n) messages per search, and no guarantee of finding a key that exists). Chord solved the routing problem cleanly: give every node and every key a place on a shared ring, hand each node a small routing table, and any node can find the machine responsible for any key in a logarithmic number of hops. No central server, no flooding, and a provable bound.

The four properties Chord provides are the checklist every DHT since has been measured against:

• Load balance. Consistent hashing spreads keys roughly evenly — each of n nodes owns about K/n of the K keys.
• Decentralization. No node is special; the protocol is fully symmetric.
• Scalability. Lookup cost grows as O(log n), so a ring can grow from 10 to 10 million nodes and a query still finishes in a couple dozen hops.
• Availability. The ring self-heals under churn — nodes constantly joining and leaving — through periodic stabilization.

The ideas underneath Chord — hash keys and servers onto the same ring, own the arc up to your predecessor, replicate onto the next few successors — are exactly the ideas that reappear in Amazon's Dynamo, Apache Cassandra, and Riak. Chord is where most engineers first meet them in a form small enough to prove correct.

How Chord works, step by step

Everything sits on a circle of 2^m identifiers, called the identifier ring. Positions wrap around modulo 2^m, so identifier 2^m − 1 is immediately followed by 0.

• Node identifiers. Each node hashes its IP address (or a node key) with a consistent hash — SHA-1 in the original paper, giving m = 160 bits — to land at a point on the ring.
• Key identifiers. Each key is hashed with the same function to a point on the same ring.
• Ownership rule. Key k is stored on successor(k) — the first node whose identifier is equal to or clockwise-follows k. Equivalently, a node owns every key in the half-open arc from just after its predecessor up to and including itself.

If every node knew only its immediate successor, you could still find any key: hop clockwise, one node at a time, until you reach the key's owner. That is correct but slow — O(n) hops. Chord fixes the speed with the finger table.

The finger table — O(log n) routing

Each node n keeps a table of m fingers. The i-th finger (for i = 1 … m) points to:

finger[i].node = successor( (n + 2^(i-1)) mod 2^m )

So finger 1 points to the node at least 1 position clockwise, finger 2 at least 2 away, finger 3 at least 4, and so on — each finger reaches exponentially farther around the ring, the last one reaching halfway across. A lookup walks these shortcuts: from wherever it currently stands, it jumps to the finger that lands closest to the target without overshooting it. Because each such jump lands in the half of the remaining arc nearer the target, the distance to the key at least halves every hop. Halving a 2^m-wide interval down to a single node takes at most about log₂ n steps — hence O(log n) hops with high probability.

Note the asymmetry that trips people up: only the successor pointer is required for correctness. If every finger were stale but successors were right, lookups would still return the correct owner — just slowly. The finger table is pure performance; the successor pointer is the invariant.

Joins, leaves, and stabilization

Nodes come and go constantly ("churn"), so Chord cannot assume a static ring. It maintains correctness with three periodic routines rather than a global lock:

• join(n′). A new node n asks any existing node n′ to look up successor(n). It sets that as its successor and inserts itself, but does not yet touch anyone else's pointers.
• stabilize(). Run periodically by every node. n asks its successor for the successor's predecessor x. If x falls between n and its current successor, then x is a better successor, so n adopts it and notifies it — which lets the newcomer's predecessor pointer get set. This is how a freshly joined node is woven into the ring.
• fix_fingers(). Periodically refreshes one finger-table entry at a time by re-running the lookup for n + 2^(i-1). Because fingers are only an optimization, they can lag reality without breaking correctness.

To survive failures, each node keeps a successor list of the next r ≈ O(log n) nodes. If its immediate successor dies, it skips to the next live entry and stabilization repairs the rest. Keys are replicated across these r successors so a single node death loses no data. The paper proves that if every node's successor pointer is correct, lookups are correct — and that stabilization restores that invariant after any sequence of joins, given enough time between failures.

A worked example on a 6-bit ring

Take m = 6, so the ring has 2^6 = 64 identifiers (0–63). Suppose nodes exist at identifiers 1, 8, 14, 21, 32, 38, 42, 48, 51, 56. Where does key 54 live? Walk clockwise from 54: 55 has no node, 56 does — so successor(54) = 56, and node 56 owns key 54.

Now suppose node 8 wants to look up key 54. Node 8's finger table points to successors of 8+1=9, 8+2=10, 8+4=12, 8+8=16, 8+16=24, and 8+32=40 — i.e. nodes 14, 14, 14, 21, 32, and 42. To reach 54, node 8 picks the finger that most-closely precedes 54 without passing it: that is node 42. From 42, the closest-preceding finger to 54 is node 51. From 51, the successor is 56, whose predecessor 51 confirms it owns the arc (52–56) containing 54. Three hops — 8 → 42 → 51 → 56 — versus the eight single-successor hops a naive walk would need. That gap is exactly the O(log n) versus O(n) difference, and it widens as the ring grows.

Common misconceptions and pitfalls

• "Finger tables are required for correctness." No — correctness rides entirely on the successor pointer. Fingers only shrink the hop count. A ring with garbage fingers but valid successors still returns the right owner.
• "A key is stored on the node before it on the ring." It is the successor (first node clockwise, equal-or-after), not the predecessor. Getting the direction wrong sends every lookup to the wrong owner.
• "O(log n) is worst case." It is a high-probability bound over the random hash placement, not a guaranteed worst case. Adversarial identifier placement can degrade routing; consistent hashing's balance is an expectation, which is why real systems add virtual nodes to tighten it.
• "Chord tolerates any failures." It tolerates failures as long as they do not wipe out an entire successor list of r consecutive nodes simultaneously. Lose all r and the ring can partition.
• "Stabilization makes lookups block." Stabilization runs in the background; lookups never wait on it. Mid-churn, a lookup can transiently return a slightly stale successor, which the paper handles as an acceptable, self-correcting inconsistency rather than an error.

Chord vs other lookup approaches

	Chord	Kademlia	Pastry / Tapestry	Consistent hashing (client-side)
Lookup hops	O(log n)	O(log n)	O(log n)	O(1) (client knows whole ring)
Routing state / node	O(log n) fingers	O(log n) k-buckets	O(log n) + leaf set	O(n) at each client
Metric	Clockwise ring distance	XOR distance (symmetric)	Prefix routing + proximity	Ring position
Repair mechanism	Periodic stabilize()	Learns from any traffic	Leaf-set repair	Manual / gossiped membership
Handles churn well?	Yes, with successor list	Yes, self-healing	Yes	Needs external membership
Notable deployments	Research, teaching model	BitTorrent, IPFS, Ethereum	PAST, Scribe	Dynamo, Cassandra, memcached

Implementation — Chord lookup in Python

The core of Chord is two routines: find_successor, which resolves a key to its owning node, and closest_preceding_node, which walks the finger table to take the biggest safe jump. The interval checks are all done modulo 2^m so that arcs wrap around the ring.

M = 6                    # identifier bits -> ring of size 2**M
RING = 1 << M            # 64 identifiers

def in_interval(x, a, b, inc_a=False, inc_b=False):
    """Is x in the arc (a, b) going clockwise, mod RING?"""
    if a == b:
        return x != a or inc_a or inc_b   # whole ring
    lo = a if inc_a else (a + 1) % RING
    hi = b if inc_b else (b - 1) % RING
    if a < b:
        return lo <= x <= hi
    return x >= lo or x <= hi              # wraps past 0

class Node:
    def __init__(self, node_id, ring):
        self.id = node_id
        self.ring = ring                  # id -> Node, for lookups
        self.finger = [None] * M          # finger[i] = successor(id + 2**i)
        self.successor = self
        self.predecessor = None

    def find_successor(self, key):
        # If key is in (self, successor], its owner is our successor.
        if in_interval(key, self.id, self.successor.id, inc_b=True):
            return self.successor
        # Otherwise jump to the closest finger preceding the key and recurse.
        n = self.closest_preceding_node(key)
        return n.find_successor(key)

    def closest_preceding_node(self, key):
        for i in range(M - 1, -1, -1):    # farthest finger first
            f = self.finger[i]
            if f and in_interval(f.id, self.id, key):
                return f
        return self                        # no better hop; we are closest

def build_finger_tables(nodes):
    ids = sorted(n.id for n in nodes)
    by_id = {n.id: n for n in nodes}
    def successor_of(x):
        for i in ids:                      # first node id >= x, else wrap
            if i >= x:
                return by_id[i]
        return by_id[ids[0]]
    for n in nodes:
        n.successor = successor_of((n.id + 1) % RING)
        for i in range(M):
            start = (n.id + (1 << i)) % RING
            n.finger[i] = successor_of(start)

# --- demo: the worked example above ---
ids = [1, 8, 14, 21, 32, 38, 42, 48, 51, 56]
nodes = [Node(i, None) for i in ids]
build_finger_tables(nodes)
node8 = next(n for n in nodes if n.id == 8)
owner = node8.find_successor(54)
print(owner.id)   # -> 56, reached in O(log n) hops via the finger table

In a real deployment each find_successor hop is a network RPC to a remote node rather than a local recursion, and successor / predecessor / finger are repaired asynchronously by stabilize() and fix_fingers(). The routing logic above is exactly what runs on each hop — the distributed version just replaces the in-memory ring dictionary with message passing.

History — from MIT to every modern DHT

Chord was published as "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications" at ACM SIGCOMM 2001 by Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan at MIT. The consistent-hashing ring it builds on came from Karger's own earlier 1997 work on distributed web caching. Chord was one of four structured DHTs that appeared almost simultaneously — alongside CAN, Pastry, and Tapestry — but its ring-plus-finger-table design proved the easiest to reason about and became the standard teaching example. The extended 2003 IEEE/ACM Transactions on Networking version added the successor-list failure model and the full stabilization correctness proofs. Nearly every production DHT and consistent-hashing data store since — Dynamo, Cassandra, Riak — inherits Chord's core insight even when it swaps the routing for a gossiped, full-membership view.