Distributed Hash Table

A Chord-inspired distributed hash table implementation in C++ using TCP sockets. Multiple name server nodes form a ring topology, partitioning a key space of 0--1024 and supporting dynamic node entry/exit with automatic data migration.

Features

• Chord-like ring topology: Nodes are organized in a logical ring ordered by ID
• Key range partitioning: Key space [0, 1024] is divided among active nodes
• Insert, lookup, and delete: Operations are routed around the ring to the responsible node
• Dynamic node entry/exit: Nodes can join or leave at runtime with automatic key range rebalancing and data migration
• Ring traversal tracking: Reports which nodes were traversed during operations
• Thread pool concurrency: Background threads handle incoming messages while the main thread processes user commands
• Thread-safe message queue: Producer-consumer queue for inter-thread communication

Architecture

• bnserver (Bootstrap Name Server) -- The initial node that owns the full key range [0, 1024]. Serves as the entry point for new nodes joining the ring. Also handles user commands (insert, lookup, delete) and forwards them around the ring as needed.
• nameserver -- A regular name server node. Joins the ring via the bootstrap server, receives its key range and migrated data, then participates in routing and storage.

Message Protocol

Nodes communicate using #-delimited text messages over TCP sockets. Message types include: entry, exit, insert, lookup, delete, traversal, pass_back, and handshake messages for ring restructuring (successor_entry, predecessor_exit, etc.).

Building

make        # builds both nameserver and bnserver
make clean  # removes binaries

Requires a C++ compiler with C++17 and pthread support.

Usage

1. Start the bootstrap server with its config file:

   ./bnserver config/bsconfig.txt

2. In separate terminals, start name server nodes:

   ./nameserver config/ns1config.txt
   ./nameserver config/ns2config.txt

3. On each name server, type entry to join the ring.

4. On the bootstrap server, issue commands:

   • insert <key> <value> -- Insert a key-value pair
   • lookup <key> -- Look up a value by key
   • delete <key> -- Delete a key-value pair
   • info -- Display this node's range, neighbors, and stored data

5. On a name server, type exit to leave the ring (data is migrated to successor).

Configuration Files

Bootstrap config (config/bsconfig.txt):

<id>
<port>
<key> <value>
<key> <value>
...

Name server config (config/ns1config.txt):

<id>
<port>
<bootstrap_ip> <bootstrap_port>