dkvs — Distributed Key-Value Store

A fault-tolerant distributed key-value store with Raft-style consensus. Written in C++20 with standalone Asio and a hand-rolled wire protocol.

Status: phases 1–6 complete. Leader election, log replication, on-disk WAL, recovery from restart, and idempotent client retries all land tests. Throughput / latency benchmarks + a fault-injection harness are next.

---

Build

Requires CMake ≥ 3.20 and a C++20 compiler (Apple Clang 17, GCC 11+, Clang 14+). Asio and GoogleTest are fetched automatically via FetchContent.

cmake -S . -B build -G Ninja
cmake --build build -j

Run a 3-node cluster locally

./build/dkvs_node --id 1 --listen 19101 \
  --peers 2@127.0.0.1:19102,3@127.0.0.1:19103 --data-dir ./data/n1 &
./build/dkvs_node --id 2 --listen 19102 \
  --peers 1@127.0.0.1:19101,3@127.0.0.1:19103 --data-dir ./data/n2 &
./build/dkvs_node --id 3 --listen 19103 \
  --peers 1@127.0.0.1:19101,2@127.0.0.1:19102 --data-dir ./data/n3 &

Logs print role transitions: Follower → Candidate → Leader. Kill the leader (kill <pid>) and watch one of the followers win the next election.

Test

ctest --test-dir build --output-on-failure
# or
./build/tests/dkvs_unit_tests

The test suite includes:

• Frame codec round-trip + truncation/magic checks
• Raft log append, query, and the Figure-7-style merge-with-conflict logic
• 3-node election convergence (~250 ms wall time)
• Leader failover after the leader is stopped
• 3-node end-to-end PUT/GET/DELETE through the real wire protocol with a sync client
• WAL: state + entries round-trip, file rewrite on truncate, tail-truncated record tolerated on replay
• Single-node restart: write 3 keys, kill the process, restart, read all 3 back

---

Architecture

┌──────────── node ────────────┐
│   ┌───────────────────────┐  │
│   │       RaftNode        │  │  state machine (single strand)
│   │  Follower│Candidate│  │
│   │           │Leader      │  │
│   └────┬───────┬───────────┘  │
│        │       │              │
│   ┌────▼───┐ ┌─▼────────┐     │
│   │ Server │ │ PeerLink │×N   │  Asio TCP
│   │(accept)│ │ (dial+RC)│     │
│   └────┬───┘ └────┬─────┘     │
│        │          │            │
│        └────┬─────┘            │
│         ┌───▼────┐             │
│         │Session │ framed I/O  │
│         └────────┘             │
└────────────────────────────────┘

• One io_context, one worker thread. All Raft state mutations are posted to a strand inside RaftNode. The two-thread Raft footgun (election timer racing AppendEntries) is avoided by construction. Adding more I/O threads later only requires moving the strand off io.get_executor().
• Hand-rolled wire format. 20-byte header (magic | version | type | corr_id | length) + little-endian payload, with a length cap. No protobuf, no gRPC.
• Persistence is a real append-only WAL. Each record is [magic | crc32 | length | encoded LogEntry], fsynced after every append. State (current_term, voted_for) goes in state.dat via write-tmp + atomic rename + fsync of the directory. Tail-truncated records (crash mid-fsync) are detected by CRC and discarded on replay.
• Linearizable reads via the log. Get is appended as a no-op log entry and the reply waits for that entry to commit. Slower than a ReadIndex optimization but obviously correct under leader change.
• Idempotent retries. Each client tags requests with (client_id, request_id). The leader keeps the most recent reply per client in a session table, so a retried Put after a crash mid-reply doesn't apply twice.
• Linearization point on leader change. A new leader appends a no-op in its term so that prior-term entries can be committed (Raft §5.4.2). This is also what makes single-node restart recover its state machine.

Wire format

 0       4   6   8       16          20
 ├───────┼───┼───┼───────┼───────────┤
 │ magic │ver│typ│corr_id│payload_len│ payload bytes...
 │ 'DKV1'│ 1 │   │       │           │

All multi-byte integers little-endian. Strings & byte blobs are length-prefixed (u32). See src/net/frame.hpp for the codec.

Raft phases

Phase	Status	Module
1. Scaffold + RPC framing	✅	src/net/
2. Asio session / server / peer link	✅	src/net/
3. Leader election + heartbeats	✅	src/raft/node.cpp
4. Log replication + commit + apply	✅	src/raft/node.cpp, src/kv/
5. Persistence: on-disk WAL + replay	✅	src/storage/wal.cpp
6. Client lib + idempotent retries	✅	src/client/, session-table dedup in RaftNode
7. Fault-injection harness	⏳	sim/
8. Throughput / latency benchmarks	⏳	bench/

Layout

src/
  common/   types, logging
  net/      frame codec, Asio session/server/peer link
  raft/     RaftLog, RaftNode (election + heartbeat)
  storage/  on-disk WAL (CRC32 + fsync + atomic state rename)
  kv/       KV state machine (mutex-guarded hashmap)
  client/   sync client (NotLeader redirect, RPC timeout)
  node/     main() — config parsing, signal handling
tests/      gtest unit + integration
sim/        fault-injection harness (TODO)
bench/      workload driver (TODO)