Building a Distributed Key-Value Store in C++ (Final)

This is the final post in the series. If you are arriving here for the first time, Part 1 is the right starting point - it covers the in-memory store and the overall roadmap.

Parts 2, 3, and 4 added persistence, TCP networking, and multi-node replication. The remaining gap is coordination: without a leader, any node can accept writes and the cluster can diverge. The Bully algorithm closes that gap.

Why the Bully algorithm?

The Bully algorithm elects a leader deterministically: the node with the highest numeric ID wins. When a node suspects the leader is gone, it sends ELECTION messages to all peers with a higher ID. If any peer responds, it backs off and waits. If none respond, it declares itself leader and broadcasts COORDINATOR.

Election flow

Triggering an election

if (leader_id == -1 && !election_in_progress.exchange(true)) {
    start_election();
}

The atomic exchange ensures only one election runs at a time on a given node.

The election itself

void KVServer::start_election() {
  // sends ELECTION to peers with higher ID
  // if any respond OK, backs off; otherwise declares self leader
  for (peer : peers with higher ID) {
    if response == OK:
      higher_responded = true
  }
  if (!higher_responded) {
    declare_leader(node_id);
  }
}

Responding to an incoming ELECTION message

else if (cmd == "ELECTION") {
  if (node_id > sender_id && !election_in_progress.exchange(true)) {
    start_election();
  }
}

A node with a higher ID immediately starts its own election - this is the "bully" behaviour.

Declaring and broadcasting the new leader

void KVServer::declare_leader(int new_leader_id) {
  leader_id = new_leader_id;
  forward_to_peers("COORDINATOR " + std::to_string(new_leader_id));
}

else if (cmd == "COORDINATOR") {
  leader_id = new_leader_id;
  election_in_progress = false;
}

Every node records the new leader_id and clears the election flag.

Leader-only writes

if (leader_id != node_id) {
  response << "NOT_LEADER " << leader_id << "\n";
}

Non-leader nodes reject writes and return the current leader's ID so the client can retry against the right node.

Heartbeat loop

void KVServer::heartbeat_loop() {
  while (true) {
    sleep(3);
    check_leader_health();
  }
}

check_leader_health() sends a lightweight ping to the current leader. If it fails, leader_id is reset to -1, which triggers a new election on the next write attempt.

Roadmap - all phases

• Phase 1 - Local store - done
• Phase 2 - Persistence & testing - done
• Phase 3 - Networking - done
• Phase 4 - Multi-node architecture - done
• Phase 5 - Consensus / leader election - done (this post)
• Phase 6 - Testing & resilience - cancelled in favour of shipping

Closing thoughts

The full source is on GitHub. Each phase lives in its own branch so you can follow the progression from a 60-line std::unordered_map wrapper to a multi-node cluster with leader election.

The project left a lot on the table - compaction, snapshotting, proper linearisability, TLS - but building it phase by phase made each distributed systems concept concrete in a way that reading papers alone never quite did.