This document outlines the design for adding real network connectivity to the Chord DHT implementation using the nng (nanomsg-next-generation) library.
Current State: Pure in-memory simulation with direct pointer access between nodes
Target State: Distributed system with network RPC communication
Estimated Effort: 7-11 days of development
Think of this codebase the same way you would think of a debugger or game engine:
-
Layer correctness over cleverness.
Network code lives insrc/net, core Chord logic lives insrc/core, UI lives insrc/app. Violations will be rejected. -
Data structures first, API second.
The ring, finger tables, and node state representations must be explicit and easy to inspect. APIs are built around these structures, not the other way around. -
Observability is not optional.
Logging and tracing hooks must be designed into the system. You should be able to trace a lookup from CLI command, through the node state machine, across the network, and back. -
Tests are the spec.
Behavior is defined by tests. When behavior is ambiguous, write/adjust a test first, then adjust the code. -
No dead code, no speculative abstractions.
If an abstraction is not clearly used, it should not exist. Keep the design focused on the Chord protocol and its immediate needs.
During code review, changes will be evaluated primarily against:
- Does this respect the layer boundaries?
- Does this make the system easier to debug and test?
- Is the behavior covered by unit and/or integration tests?
The repository is structured into layers and subsystems. The goal is:
- clear separation of concerns
- testable units
- explicit boundaries between transport, protocol, and application
Target layout:
src/core/chord_types.h– core type definitions, IDs, configurationhash.c,hash.h– consistent hashing, key space operationskey.c,key.h– key representation, parsing, formattingring.c,ring.h– Chord ring operations (join, stabilize, lookup)finger.c,finger.h– finger table maintenance and selectionnode.c,node.h– node life‑cycle, state machine, timers
net/net_transport.c,net_transport.h– raw network I/O (sockets or NNG)net_protocol.c,net_protocol.h– wire format, message encode/decodenet_peer.c,net_peer.h– high‑level peer abstraction wrapping transport
app/app_driver.c– CLI / TUI / test harness entry pointapp_commands.c,app_commands.h– user commands to interact with the ring
util/util.c,util.h– shared utilities (logging, time, random IDs, etc.)
include/- Public headers, if we export an API (e.g.
chord.h).
- Public headers, if we export an API (e.g.
tests/unit/– small unit tests forsrc/coreandsrc/utilintegration/– multi‑node network tests using the test harness
build/- Out‑of‑tree build artifacts (optional, but recommended).
scripts/- Helper scripts for running test clusters, benchmarks, etc.
vendor/nng/– nng library as git submodule
Existing source files (e.g. ring.c, node.c) are moved into these directories without changing their responsibilities initially. Follow‑up refactors will split them further along these boundaries.
File migration map:
chord_types.h→src/core/chord_types.hhash.c,hash.h→src/core/hash.c,src/core/hash.hkey.c,key.h→src/core/key.c,src/core/key.hring.c,ring.h→src/core/ring.c,src/core/ring.hfinger.c,finger.h→src/core/finger.c,src/core/finger.hnode.c,node.h→src/core/node.c,src/core/node.hutil.c,util.h→src/util/util.c,src/util/util.happ_driver.c→src/app/app_driver.ctest_hash.c→tests/unit/test_hash.c
- Type: In-memory simulation (no actual network calls)
- Method: Direct pointer dereferencing between nodes
- Storage: All nodes in global
Ringstructure withNode *nodes[500]array - Limitation: All nodes must exist in same process memory space
node_find_successor()- Recursive key lookupnode_closest_preceding_node()- Finger table querynode_stabilise()- Periodic stabilizationnode_notify()- Predecessor notificationnode_fix_fingers()- Finger table maintenancenode_join()- Bootstrap into networknode_document_add()- Store documentnode_document_query()- Retrieve document
The project targets a modern C toolchain:
- C standard: C23 preferred, minimum C20.
- We expect a conforming libc implementation (e.g. glibc, musl, modern Windows CRT).
- The code must compile cleanly with:
clangandgccon Linux/macOSclang-clorclon Windows (where feasible)
Recommended baseline compiler flags:
# Development build
cc -std=c2x -Wall -Wextra -Wpedantic -Werror \
-Wshadow -Wconversion -Wdouble-promotion -Wformat=2 \
-fno-common -fstrict-aliasing -g -O0 \
-fsanitize=address,undefined \
-o build/chord src/app/app_driver.c ...
# Release build
cc -std=c2x -Wall -Wextra -Wpedantic \
-O3 -DNDEBUG \
-o build/chord src/app/app_driver.c ...The existing makefile will be replaced with:
- A minimal
Makefilethat:- builds
build/chordfromsrc/** - builds unit tests under
build/tests/* - exposes targets:
all– default builddebug– debug build with sanitizersrelease– optimized buildtest– build and run the full test suiteclean– remove build artifacts
- builds
- Optionally, a small CMake configuration if IDE support is desired; the
Makefileremains the authoritative reference.
The Chord implementation is organized into directional layers. Dependencies flow upwards only:
- Files:
src/util/*,src/net/net_transport.* - Responsibilities:
- OS and libc abstractions: time, random IDs, logging, error handling.
- Network transport primitives: sockets or NNG endpoints, connection management.
- May depend on system headers and external libraries (e.g.
nng), but not on Chord concepts (keys, rings, nodes).
- Files:
src/core/chord_types.h,src/core/hash.*,src/core/key.*,src/core/ring.*,src/core/finger.*,src/core/node.* - Responsibilities:
- Key space definition (identifier size, hash function).
- Ring topology and invariants.
- Node state machine and stabilization algorithm.
- Lookup protocol (find successor/predecessor) abstracted over a generic messaging API.
- Depends only on the foundation layer for utilities (time, randomness) and on
net_protocolinterfaces, not on any UI or CLI.
- Files:
src/net/net_protocol.*,src/net/net_peer.* - Responsibilities:
- Encode/decode of protocol messages (join, stabilize, notify, lookup, data transfer).
- Framing, versioning, and error codes.
- Mapping between Chord core requests and low‑level transport messages.
- Depends on foundation (transport) and Chord core (types and commands), but is decoupled through stable interfaces:
net_protocol.hdefines the wire types.net_peer.hexposes async operations (connect, send_request, receive_response, close).
- Files:
src/app/app_driver.*,src/app/app_commands.* - Responsibilities:
- Start and stop a node.
- Configure the node (ports, join addresses, logging).
- Provide a CLI interface and simple scripts for integration tests.
- Depends on Chord core and network protocol layers, but not vice versa.
src/core/*must not includesrc/app/*.src/core/*may depend on narrow interfaces insrc/net/net_protocol.horsrc/net/net_peer.h, but not on raw sockets.src/app/*is allowed to know about everything below, but must not contain algorithmic logic that belongs insrc/core/*.
The codebase targets modern C:
- Compile with
-std=c2x(or-std=c20where C23 is not yet available). - Assume a modern libc (POSIX‑like APIs on Unix, Winsock + CRT on Windows).
Allowed features:
- Designated initializers and compound literals for structs.
- Fixed‑width integer types (
uint32_t,uint64_t, etc.) from<stdint.h>. _Static_assertfor invariants that must hold at compile time.- Inline functions in headers for small, performance‑critical helpers.
- Flexible array members where appropriate, coupled with explicit length tracking.
Memory and safety:
- No naked
malloc/freecalls scattered through the code. All allocations go through narrow utility functions insrc/util/memory.*. - All public APIs define clear ownership rules for allocations, and these rules are documented in header comments.
- Use
size_tfor sizes and counts, avoid mixing signed and unsigned types; use casts consciously and locally.
Error handling:
- No silent error ignoring. Every call that can fail must return an error code or log explicitly.
- Use a simple
enum chord_err(or reusenng_errstyle) for domain‑specific error codes. - Functions that can fail return an error code; out‑parameters are only written on success.
Standard library usage:
- Prefer standard functions (
memcpy,memmove,snprintf,strtoul,clock_gettimeor equivalent) over custom re‑implementations, unless there is a clear portability or performance reason. - Wrap non‑portable system calls behind small adapters in
src/utilorsrc/net.
When writing C for this project, follow these rules:
- Every
.cfile has exactly one corresponding.hfile for its public interface, except pure implementation files used only by a single translation unit. - Header files declare types and functions; they do not define storage except for
staticorinlinehelpers.
- Functions that are part of a module's public API are prefixed with the module name (
chord_ring_,chord_node_,net_peer_, etc.). - Internal helpers are declared
staticand live near their only call sites.
- Keep functions small and single‑purpose. If it does more than one conceptual task, split it.
- All functions that can fail return an error code; do not mix return codes and
errno. - Avoid global mutable state. When state is necessary (e.g. a node's state), keep it in explicit context structs passed around.
- Use K&R brace style consistently.
- No trailing whitespace, use spaces (not tabs), 4-space indentation.
- Use descriptive names:
node,finger_table,successor, notn,ft,s.
- Document the contract of each public function in the header: inputs, outputs, ownership, error conditions.
- Avoid redundant comments. The code should be readable without comments; comments explain why, not what.
- For new functionality, write tests before or alongside implementation:
- unit tests for pure logic (hashing, ring operations)
- integration tests for network behavior and multi‑node scenarios
The test suite is split into unit tests and integration tests. We aim for a TDD workflow:
- Write tests that describe the desired behavior.
- Implement the minimal code to make them pass.
- Refactor while keeping tests green.
- Located under
tests/unit/. - Focus: deterministic, in‑process tests for:
hash.*– consistent hashing, ring size constraints.key.*– key parsing/formatting, comparison.ring.*– successor/predecessor logic, interval arithmetic.finger.*– finger table index calculation and updates.node.*– state transitions; use fake timers and fake network peers.
- Should not use real sockets. Instead:
- Introduce a
net_peer_ifacethat can be implemented by a fake. - Unit tests inject fake peers to validate protocol logic.
- Introduce a
Example unit test layout:
tests/unit/test_hash.ctests/unit/test_ring.ctests/unit/test_node_state.c
Each test file follows a simple test framework (e.g. acutest‑style or a small in‑house equivalent) for consistency.
- Located under
tests/integration/. - Focus: real network behavior and multi‑node scenarios.
- Use a small test harness inspired by NNG's
nuts.h:- Helpers to create temporary addresses (
chord_test_scratch_addr()). - Helpers to start and stop nodes (
chord_test_spawn_node()/chord_test_kill_node()). - Macros to connect nodes and verify connectivity (
CHORD_TEST_MARRY()equivalent). - Utilities to wait for stabilization and check invariants (
CHORD_TEST_WAIT_STABLE()).
- Helpers to create temporary addresses (
The test harness should:
- Allow running multiple integration tests in a single process without resource leaks (similar spirit to
TEST_INIT/TEST_FINIinnuts.h). - Provide
CHORD_TEST_PASS/CHORD_TEST_FAILmacros mirroringNUTS_PASS/NUTS_FAIL, wrapping the project's error codes. - Provide short, readable macros for common patterns:
CHORD_TEST_SEND_LOOKUP(node, key, expected_successor)CHORD_TEST_RING_INVARIANTS(nodes[], count)
Integration test examples:
tests/integration/test_two_node_join.ctests/integration/test_stabilization_under_churn.ctests/integration/test_key_distribution.c
- A single
testtarget in theMakefile:- builds all tests to
build/tests/* - runs unit tests first, then integration tests
- builds all tests to
- On failure, tests must print enough logging (using the project's logging facilities) to diagnose the issue without reruns.
- Lightweight: Broker-less messaging library
- Protocols: REQ/REP (request-reply), PUB/SUB, PUSH/PULL, etc.
- Transports: TCP, IPC, inproc, TLS, WebSocket
- Async I/O: Built-in asynchronous operations
- License: MIT (compatible with this project)
- REQ/REP pattern perfect for RPC-style Chord operations
- Async I/O enables concurrent request handling
- Multiple transports (TCP for distributed, IPC for local testing)
- TLS support for secure production deployments
- Simple API minimizes integration complexity
┌─────────────────────────────────────────────────────────┐
│ Application Layer │
│ (app_driver.c - user interface) │
└─────────────────────────────────────────────────────────┘
│
┌─────────────────────────────────────────────────────────┐
│ Chord Protocol Layer │
│ (node.c, ring.c - modified to use network calls) │
└─────────────────────────────────────────────────────────┘
│
┌─────────────────────────────────────────────────────────┐
│ Network Abstraction Layer │
│ (network.c - RPC client functions) │
│ ┌──────────────────────────────────────────────────┐ │
│ │ RPC Server (rpc_server.c - request handlers) │ │
│ └──────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────┘
│
┌─────────────────────────────────────────────────────────┐
│ NNG Library │
│ (REQ/REP sockets over TCP/IPC) │
└─────────────────────────────────────────────────────────┘
typedef struct NodeAddress {
char id[NODE_ID_LENGTH + 1];
int key;
char url[256]; /* e.g., "tcp://192.168.1.1:5555" */
} NodeAddress;typedef struct Node {
char *id;
int key;
NodeAddress *predecessor; /* Was: Node* */
NodeAddress *successor; /* Was: Node* */
FingerTable *finger_table;
int state;
Document **documents;
int num_documents;
NodeAddress *successors[SUCCESSOR_LIST_SIZE];
/* NEW: Network components */
char bind_url[256];
nng_socket rep_socket; /* Server socket for incoming RPCs */
nng_thread *rpc_thread; /* RPC server thread */
} Node;{
"type": "FIND_SUCCESSOR",
"request_id": "uuid",
"params": {
"key": 42
}
}
{
"type": "FIND_SUCCESSOR_RESPONSE",
"request_id": "uuid",
"result": {
"id": "node1",
"key": 42,
"url": "tcp://192.168.1.1:5555"
}
}FIND_SUCCESSOR- Find successor for keyGET_PREDECESSOR- Get predecessor nodeGET_SUCCESSOR- Get successor nodeNOTIFY- Notify of potential predecessorCLOSEST_PRECEDING- Get closest preceding nodeSTORE_DOCUMENT- Store documentQUERY_DOCUMENT- Query documentPING- Health check
Files: network.h, network.c, serialize.h, serialize.c
- Create NodeAddress structure
- Implement JSON serialization/deserialization
- Create network initialization functions
- Implement basic RPC client (REQ socket)
- Add timeout and error handling
Files: rpc_server.h, rpc_server.c
- Create RPC server thread
- Implement REP socket listener
- Add request dispatcher
- Implement handlers for 8 RPC types
- Add thread-safe access to local node state
Files: Modify node.c, ring.c, chord_types.h
- Update Node structure with network fields
- Replace Node* with NodeAddress* in function signatures
- Replace direct pointer access with network_* calls
- Update node_init() to start RPC server
- Add node cleanup to stop RPC server
Files: test_network.c, update makefile
- Create unit tests for network layer
- Test single-node operation
- Test two-node operation
- Test multi-node ring formation
- Test document storage/retrieval
- Test node failure scenarios
- Performance testing and optimization
Decision: Start with synchronous, add async optimization later
- Rationale: Simpler to implement and debug
- Future: Use nng_aio for async operations to improve throughput
Decision: JSON for initial implementation
- Pros: Human-readable, easy to debug, standard libraries available
- Cons: Larger message size, slower parsing
- Future: Consider Protocol Buffers or MessagePack for production
Decision: TCP for distributed nodes, IPC for local testing
- TCP:
tcp://0.0.0.0:5555for production - IPC:
ipc:///tmp/chord_node_1for local multi-node testing - Future: Add TLS transport for secure deployments
Decision: Use nng's built-in thread safety + minimal locking
- Each node has dedicated RPC server thread
- Use mutex for document storage access
- Node state reads are atomic (int fields)
Decision: Comprehensive timeout and retry logic
- All RPC calls have 5-second timeout
- Failed RPCs return NULL/error code
- Caller decides retry strategy (e.g., try successor list)
int network_init(Node *node, const char *bind_url) {
int rv;
/* Create REP socket for incoming requests */
if ((rv = nng_rep0_open(&node->rep_socket)) != 0) {
return rv;
}
/* Bind to address */
if ((rv = nng_listen(node->rep_socket, bind_url, NULL, 0)) != 0) {
nng_close(node->rep_socket);
return rv;
}
/* Store bind URL */
strncpy(node->bind_url, bind_url, sizeof(node->bind_url) - 1);
/* Start RPC server thread */
if ((rv = nng_thread_create(&node->rpc_thread, rpc_server_loop, node)) != 0) {
nng_close(node->rep_socket);
return rv;
}
return 0;
}NodeAddress* network_find_successor(NodeAddress *remote, int key) {
nng_socket sock;
nng_msg *msg;
char request[512];
char *response;
NodeAddress *result = NULL;
int rv;
/* Create REQ socket */
if ((rv = nng_req0_open(&sock)) != 0) {
return NULL;
}
/* Set timeout */
nng_socket_set_ms(sock, NNG_OPT_RECVTIMEO, 5000);
/* Connect to remote node */
if ((rv = nng_dial(sock, remote->url, NULL, 0)) != 0) {
nng_close(sock);
return NULL;
}
/* Build request */
snprintf(request, sizeof(request),
"{\"type\":\"FIND_SUCCESSOR\",\"params\":{\"key\":%d}}", key);
/* Send request */
if ((rv = nng_msg_alloc(&msg, 0)) != 0 ||
(rv = nng_msg_append(msg, request, strlen(request))) != 0 ||
(rv = nng_sendmsg(sock, msg, 0)) != 0) {
nng_close(sock);
return NULL;
}
/* Receive response */
if ((rv = nng_recvmsg(sock, &msg, 0)) == 0) {
response = (char*)nng_msg_body(msg);
result = deserialize_node_address(response);
nng_msg_free(msg);
}
nng_close(sock);
return result;
}void handle_find_successor_rpc(Node *local, nng_msg *request) {
char *request_body = (char*)nng_msg_body(request);
int key;
Node *successor;
char response[512];
/* Parse request */
key = parse_find_successor_request(request_body);
/* Execute local Chord operation */
successor = node_find_successor(local, key);
/* Build response */
snprintf(response, sizeof(response),
"{\"type\":\"FIND_SUCCESSOR_RESPONSE\","
"\"result\":{\"id\":\"%s\",\"key\":%d,\"url\":\"%s\"}}",
successor->id, successor->key, successor->bind_url);
/* Send response */
nng_msg_clear(request);
nng_msg_append(request, response, strlen(response));
nng_sendmsg(local->rep_socket, request, 0);
}Keep simulation mode for testing:
#ifdef NETWORK_MODE
result = network_find_successor(remote_addr, key);
#else
result = node_find_successor(remote_node, key);
#endif- Week 1: Implement network layer, test with 2 nodes
- Week 2: Full integration, test with 5-10 nodes
- Week 3: Stress testing, optimization, documentation
- Serialization/deserialization correctness
- RPC timeout handling
- Error condition handling
- Two-node ring formation
- Multi-node ring formation (5, 10, 20 nodes)
- Document storage and retrieval
- Node join/leave operations
- Stabilization convergence
- Lookup latency (average, p95, p99)
- Throughput (requests/second)
- Scalability (10, 50, 100 nodes)
- TLS Transport: Secure communication for production
- Async I/O: Use nng_aio for better concurrency
- Compression: Reduce message size for large documents
- Monitoring: Add metrics and observability
- NAT Traversal: Support nodes behind firewalls
- IPv6 Support: Modern network compatibility
CC=clang
CFLAGS=-std=c2x -Wall -Wextra -Wpedantic -Werror \
-Wshadow -Wconversion -Wdouble-promotion -Wformat=2 \
-fno-common -fstrict-aliasing
CFLAGS_DEBUG=-g -O0 -fsanitize=address,undefined
CFLAGS_RELEASE=-O3 -DNDEBUG
LDFLAGS=-lm -Lvendor/nng/build -lnng -lpthread
INCLUDES=-Iinclude -Ivendor/nng/include
SRC_CORE=src/core/hash.c src/core/key.c src/core/ring.c \
src/core/finger.c src/core/node.c
SRC_NET=src/net/net_transport.c src/net/net_protocol.c src/net/net_peer.c
SRC_UTIL=src/util/util.c
SRC_APP=src/app/app_driver.c src/app/app_commands.c
OBJS=$(SRC_CORE:.c=.o) $(SRC_NET:.c=.o) $(SRC_UTIL:.c=.o) $(SRC_APP:.c=.o)
all: build/chord
debug: CFLAGS += $(CFLAGS_DEBUG)
debug: build/chord
release: CFLAGS += $(CFLAGS_RELEASE)
release: build/chord
build/chord: $(OBJS)
@mkdir -p build
$(CC) $(CFLAGS) $(OBJS) $(LDFLAGS) -o $@
%.o: %.c
$(CC) $(CFLAGS) $(INCLUDES) -c $< -o $@
test: build/tests/unit/test_hash
./build/tests/unit/test_hash
build/tests/unit/test_hash: tests/unit/test_hash.c src/core/hash.o src/core/ring.o
@mkdir -p build/tests/unit
$(CC) $(CFLAGS) $(INCLUDES) $^ $(LDFLAGS) -o $@
clean:
rm -rf build/ $(OBJS)
.PHONY: all debug release test clean- nng: Install via package manager or build from source
- Ubuntu/Debian:
apt-get install libnng-dev - macOS:
brew install nng - From source:
git clone https://github.com/nanomsg/nng && cd nng && mkdir build && cd build && cmake .. && make && sudo make install
- Ubuntu/Debian:
This design provides a clear path to transform the Chord simulation into a real distributed system. The nng library offers the perfect balance of simplicity and power for implementing the required RPC communication patterns.
Next Steps:
- Install nng library
- Create network.c with basic RPC client
- Create rpc_server.c with request handlers
- Modify node.c to use network calls
- Test with 2-node setup
- Expand to multi-node testing
Estimated Timeline: 7-11 days for full implementation and testing