A full implementation of the Chord distributed hash table protocol in C, built from the ground up. Each process acts as a peer node in a self-organizing ring network, capable of joining an existing cluster or bootstrapping a new one, and answering key-lookup queries in O(log N) hops.
Each node derives its position on the 64-bit identifier ring by computing a SHA-1 hash over its IP:port string and taking the most significant 64 bits. This is the core of consistent hashing: nodes and keys share the same address space, and a key is owned by the first node whose ID is greater than or equal to the key's hash (its successor). Adding or removing a node only affects its immediate neighbors on the ring — not the entire key space.
Every node maintains a finger table of 64 entries. Entry i points to the node responsible for the key at position self_id + 2^(i-1) on the ring. This lets local_find_successor skip exponentially ahead rather than walking the ring one hop at a time, achieving O(log N) lookup across a network of N nodes. The closest_preceding_node function searches both the finger table and the successor list to always forward queries to the best-known intermediate node.
Each node maintains a successor list of up to r entries (configurable, max 32). This provides resilience against node failures: if the primary successor goes down, the node can fall back to the next live entry in the list rather than losing its position in the ring. During stabilization, the successor list is reconciled with the live successor's own list to stay consistent.
Three daemon threads run concurrently to keep the ring healthy as nodes join and leave:
- Stabilize (
--sp): Contacts the current successor to verify and update the predecessor pointer. Rebuilds the successor list from the live successor's view. Notifies the successor of this node's presence. - Fix Fingers (
--ffp): Iterates through all 64 finger table entries and refreshes each by running afind_successorlookup for the corresponding ring position. - Check Predecessor (
--cpp): Pings the predecessor node; if it is unreachable, clears the predecessor pointer so the ring can heal.
All periods are independently configurable in deciseconds.
Rather than proactively pinging every node in the tables, failures are detected opportunistically during real RPC traffic. When a remote call fails, evict_dead_node is called to atomically remove that node from both the finger table and the successor list, and to clear the predecessor if it matches.
All inter-node communication happens over UDP using length-prefixed frames (8-byte big-endian length header followed by the serialized message body). Messages are defined in chord.proto and compiled with protoc-c. The RPC layer includes a configurable timeout (default 1 second) on all calls. Each incoming packet is dispatched to a dedicated thread, so the server loop is never blocked by slow handlers.
| Message | Purpose |
|---|---|
FindSuccessor |
Core Chord lookup: find the node responsible for a given key |
GetPredecessor |
Return this node's current predecessor |
Notify |
Inform a node that the sender might be its predecessor |
CheckPredecessor |
Liveness ping |
GetSuccessorList |
Return this node's full successor list |
While running, a node accepts commands on stdin:
Lookup <key>— Hashes the key string and traverses the ring to find its responsible node, printing the node's ID, IP, and port.PrintState— Prints the node's own identity, all successor list entries, and all 64 finger table entries.
Dependencies: gcc, protobuf-c, libssl (OpenSSL), libpthread.
makeThis runs protoc-c to generate chord.pb-c.c / chord.pb-c.h from chord.proto, then compiles the final chord binary.
To clean build artifacts:
make clean./chord -p <port> --sp <deciseconds> --ffp <deciseconds> --cpp <deciseconds> -r <successor-list-size>./chord -p <port> --sp <ds> --ffp <ds> --cpp <ds> -r <n> --ja <existing-node-ip> --jp <existing-node-port># Terminal 1 — bootstrap node
./chord -p 9000 --sp 5 --ffp 6 --cpp 7 -r 3
# Terminal 2 — join via node 1
./chord -p 9001 --sp 5 --ffp 6 --cpp 7 -r 3 --ja 127.0.0.1 --jp 9000
# Terminal 3 — join via node 1
./chord -p 9002 --sp 5 --ffp 6 --cpp 7 -r 3 --ja 127.0.0.1 --jp 9000Once the ring has stabilized (a few stabilization periods), you can query any node:
> Lookup myfile.txt
> PrintState
The consistent hashing technique at the core of Chord is not just academic — it is the direct ancestor of the partitioning strategies used by several major distributed databases.
Cassandra places each node on a token ring using a hash of its address, exactly as Chord does with SHA-1(IP:port). Incoming writes are routed to the node responsible for the token range covering the partition key's hash. When nodes are added or removed, only the adjacent token ranges are affected, minimizing data movement — the same property that makes Chord's ring efficient.
The original Dynamo paper (Amazon, 2007) explicitly builds on Chord's consistent hashing and successor-list ideas. Each storage node owns a range of the hash ring; replicas are placed on the next N nodes clockwise, mirroring the successor list maintained here. The paper's "virtual nodes" extension maps multiple ring positions to one physical machine to improve load balance — an evolution of the same ring arithmetic implemented in in_open and in_half_open.
Riak is a direct implementation of the Dynamo architecture and therefore inherits the same Chord lineage. Its ring is divided into a fixed number of partitions (default 64, matching this implementation's NUM_FINGERS), and each physical node is responsible for a contiguous slice of that ring. Riak's gossip-based ring state propagation serves the same role as Chord's stabilize and fix-fingers maintenance loops.
- Thread safety: all reads and writes to
self_node,predecessor,succ_list, andfingerare protected by a singlepthread_mutex_t. This keeps the implementation straightforward at the cost of some contention on the hot path. - No persistent storage: this is a pure routing layer. It resolves which node owns a key; storing the actual data is left to the application layer above it.
- Protocol version: all messages carry version
417as a sanity check; mismatched-version packets are discarded.