Chord: Finding Any Key in a Peer-to-Peer Network in O(log n) Hops

The problem: find one key among a million peers, with no directory

A peer-to-peer network has no central server to ask “who has key X?” — that would just recreate the single point of failure P2P is trying to avoid. A Distributed Hash Table solves this by giving every node and every key a position in the same address space and a deterministic rule for who is responsible for which keys, so that any node can find the owner of any key without a directory, using only local knowledge and a bounded number of hops.

Chord, published by Stoica, Morris, Karger, Kaashoek and Balakrishnan at MIT in 2001, is the cleanest of the classic DHT designs (alongside Pastry, Kademlia and CAN). Its entire structure rests on one idea: hash everything — node IP addresses and key names alike — with a consistent hash function (SHA-1 in the original paper) onto the same circular identifier ring of size 2^m.

The ring and the successor rule

Once every node and key has an m-bit identifier on the ring 0..2^m-1, ownership follows one rule: a key k belongs to the first node whose identifier is equal to or comes immediately after k, walking clockwise — called k's successor, written successor(k). That single deterministic rule is the entire specification of “who owns what”; there is nothing to negotiate or agree on.

ring size = 2^m               (m = 160 with SHA-1, in the original paper)
nodeID    = hash(IP address)
keyID     = hash(key name)
owner(key) = the first node whose ID >= keyID, walking clockwise around the ring
             (wrapping past 2^m-1 back to 0 if necessary)

Naive routing is correct but slow

If every node only knew its immediate successor on the ring, you could still find any key — just walk clockwise node by node asking “do you own this key?” — but that is O(n) hops for n nodes, which is useless at any real scale: a million-node network would need up to a million message hops to resolve one lookup.

Finger tables: the O(log n) trick

Chord's contribution is the finger table: each node keeps up to m pointers, where the i-th finger points to the successor of (nodeID + 2^(i-1)) mod 2^m. In plain terms, a node keeps a shortcut to roughly a quarter of the way around the ring, an eighth of the way, a sixteenth, and so on down to its immediate neighbour — doubling distances, exactly like the pointers in a skip list or the levels of binary search.

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

// lookup(key) at node n:
if key is between n and n.successor:  return n.successor        // found it
else:  forward the query to the finger farthest before key      // biggest jump that doesn't overshoot
        (that node repeats the same rule)

Each hop at least halves the remaining distance around the ring to the target key, because the chosen finger is the closest preceding node to the target among all O(log n) candidates — so the number of hops to resolve any lookup is O(log n), and each node only needs to store O(log n) routing state rather than knowing about every other node in the network. For a million-node network that is roughly 20 hops instead of up to a million — the difference between a lookup that resolves in tens of milliseconds and one that does not resolve in a human lifetime.

Nodes join and leave constantly — that is the normal case, not the exception

Peer-to-peer networks experience constant churn: nodes join, leave, and crash without warning, far more often than servers in a datacenter do. Chord handles this with two mechanisms working together. First, each node keeps a small successor list (not just a single successor) so that if its immediate successor dies, it can fail over to the next-best one without the ring breaking. Second, a periodic stabilization protocol runs continuously in the background: every node occasionally checks whether its successor's predecessor pointer is more accurate than its own, and notifies its successor of its own existence, gradually repairing the ring and refreshing finger tables even while nodes are joining and leaving.

Because stabilization is continuous rather than instantaneous, the ring can be briefly inconsistent right after a burst of churn — a lookup mid-repair might take a few extra hops, or in rare cases briefly fail — but the original Chord paper proves that as long as the rate of churn is not faster than the stabilization rate, the ring self-heals and correctness is preserved, only with a temporary, bounded hit to lookup speed.

Consistent hashing: why only O(1/n) of the keys move when a node joins

The property that makes Chord (and consistent hashing generally) attractive over a plain hash table sharded across n servers is what happens when n changes. With an ordinary modulo hash — server = hash(key) mod n — adding or removing a single server changes the target of almost every key, because n changed in the denominator. On a consistent-hash ring, a node joining only takes over the contiguous arc of keys between itself and its new predecessor — everyone else's ownership is completely untouched. Expected key movement on a join or leave is O(1/n) of the total keyspace, not O(all of it), which is the entire reason DHTs are viable for systems that add and remove capacity routinely.

Where this shows up beyond file sharing

Chord's ideas are the direct ancestor of production systems most engineers use without thinking about DHTs at all: Amazon's Dynamo (and by extension Cassandra and Riak) uses consistent hashing on a ring for data partitioning; memcached client libraries use consistent hashing to decide which cache server owns which key; BitTorrent's trackerless mode runs on Kademlia, a sibling DHT with a slightly different (XOR) distance metric but the same O(log n) routing idea. The specific ring-and-finger-table mechanics vary, but the underlying trade — bounded routing state, logarithmic hops, minimal disruption on membership change — is the same problem Chord solved first and cleanly.

Frequently asked questions

Try it live

Everything above runs in your browser — open P2P Chord DHT and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.