Skip to content
raoPublic

About

A Raft consensus implementation in Go that replicates a key-value store across a cluster of UDP peers.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

1 Commit

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

raft-kv

A Raft consensus implementation in Go that replicates a key-value store across a cluster of UDP peers.

Overview

Each member of the cluster runs one raft.Server. Members elect a leader with randomized timeouts, the leader accepts client writes and replicates them as log entries, and an entry is applied to the key-value state once a quorum of members has stored it. Clients can talk to any member: followers answer with a redirect to the leader they last heard from. Everything is in the standard library plus protobuf for encoding; there are no external Raft or networking dependencies.

How it works

Roles and elections. Every server starts as a follower. A background timer checks every 50ms whether a heartbeat has arrived within the server's election timeout, drawn uniformly from [MinTimeout, MaxTimeout). If not, the server increments its term, votes for itself, and sends VOTE_REQUEST to every peer. A peer grants the vote if it has not voted in that term and the candidate's log is at least as up to date as its own (last term, then last index). Reaching Quorum votes makes the candidate leader; seeing a higher term in any message drops it back to follower.

Replication. The leader appends a no-op entry when it wins, then sends APPEND messages to every peer every Interval. Each APPEND carries prevIndex/prevTerm for the consistency check and up to MaxEntries entries from that peer's nextIndex onward. A follower whose log disagrees truncates and replies with its current log length, and the leader walks nextIndex back until the logs line up.

Commit. The leader tracks matchIndex per peer from APPEND_REPLY messages. The newest entry from the current term that a quorum has stored becomes the commit index; followers learn it from the committed field on the next heartbeat. Committed entries are applied in order to an in-memory map[string][]byte.

Clients. SET_VALUE on the leader appends an entry and parks the request until that entry commits, then replies ACK with success = true. GET_VALUE reads the committed state directly. Either request sent to a follower returns REDIRECT with the leader's address, and the client library retries there. A client-chosen sequence number is echoed in every reply so stale UDP datagrams can be skipped.

Concurrency. One goroutine per server drains the UDP socket and dispatches on message type; every handler takes the server's single mutex. The leader's heartbeat loop and the election timer run as separate goroutines and check state under the same lock.

Wire format. A single protobuf envelope, RaftMessage, serves both cluster traffic and client traffic. Datagrams are capped at 65,000 bytes.

Layout

Path Contents
raft/ The consensus server: state machine, elections, replication, commit, client handling
api/ ClusterConfig parsing, the Server interface, and the protobuf message definitions
transport/ UDP socket wrapper that decodes datagrams onto a channel
client/ One-shot request/reply client with redirect handling
cmd/ server, client_set, client_get, checkconfig executables
configs/ Example two- and three-member cluster configurations
tests/ End-to-end tests that run real clusters on localhost

Build and run

Requires Go 1.21 or newer. Regenerating the protobuf code additionally needs protoc and protoc-gen-go.

make build          # builds the four commands into their cmd/ directories
make test           # go test ./...
make proto          # regenerate api/messages.pb.go from api/messages.proto

A cluster is described by a JSON file:

{
    "Interval": "100ms",
    "MinTimeout": "250ms",
    "MaxTimeout": "350ms",
    "Quorum": 2,
    "Servers": [ "127.0.0.1:6800", "127.0.0.1:6809" ]
}

Start one server process per entry, giving each its index. A server runs until its standard input closes, so run each in its own terminal:

cmd/server/server 0 configs/two_servers.json
cmd/server/server 1 configs/two_servers.json

Then write and read through any member. The clients follow redirects to the leader on their own:

$ cmd/client_set/client_set 127.0.0.1:6809 colour blue
redirected to 127.0.0.1:6800
$ cmd/client_get/client_get 127.0.0.1:6800 colour
blue

Servers log every message they receive to standard error, which is handy for watching an election happen. Use IP addresses rather than localhost in configs so that clients and servers agree on IPv4.

Testing

go test ./...

The tests package brings up real servers on localhost UDP ports in the 20000 range and checks that:

  • a lone follower times out and sends a vote request;
  • two of three members are enough to elect a leader that starts heartbeating;
  • a client write is committed and visible on every member;
  • a write submitted before quorum exists stalls, then commits once a second member joins.

api has unit tests for configuration parsing and the timeout distribution. The suite passes under go test -race.

Limitations

  • State is in memory only; there is no persistence or recovery across restarts.
  • No log compaction or snapshots, so the log grows without bound.
  • Cluster membership is fixed by the configuration file.
  • Reads are served by the leader without a read-index round trip, so a deposed leader that has not yet noticed could serve a stale value.
  • While no leader is known, followers redirect clients to themselves and the client library retries immediately, so a client started before the first election busy-loops until a leader emerges.

Originally built for a university distributed-systems course; the wire protocol and interfaces were specified by the course, the implementation is my own.

About

A Raft consensus implementation in Go that replicates a key-value store across a cluster of UDP peers.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages