Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

2 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Chord DHT — Consistent Hashing over a Distributed Ring

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.


What Was Implemented

Node Identity & Consistent Hashing

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.

Finger Table & O(log N) Lookup

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.

Successor List (Fault Tolerance)

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.

Background Maintenance Threads

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 a find_successor lookup 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.

Lazy Dead-Node Eviction

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.

UDP Transport with Protobuf Framing

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.

Supported RPC Messages

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

Interactive Commands

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.

Building

Dependencies: gcc, protobuf-c, libssl (OpenSSL), libpthread.

make

This 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

Running

Start a new ring

./chord -p <port> --sp <deciseconds> --ffp <deciseconds> --cpp <deciseconds> -r <successor-list-size>

Join an existing ring

./chord -p <port> --sp <ds> --ffp <ds> --cpp <ds> -r <n> --ja <existing-node-ip> --jp <existing-node-port>

Example: three-node local cluster

# 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 9000

Once the ring has stabilized (a few stabilization periods), you can query any node:

> Lookup myfile.txt
> PrintState

How Chord Powers Consistent Hashing in Production Systems

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.

Apache Cassandra

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.

Amazon DynamoDB

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

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.


Design Notes

  • Thread safety: all reads and writes to self_node, predecessor, succ_list, and finger are protected by a single pthread_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 417 as a sanity check; mismatched-version packets are discarded.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages