Distributed systems · 2026 · in progress

Capstan

A Raft consensus implementation, built test-first with a failure-injection harness.

No one turns it alone — it takes a crew, pushing together. A capstan is a ship’s winch that needs several sailors on the bar, moving in step, to turn at all. This project applies that same principle to a cluster of machines — getting them to agree on one truth even when parts of it crash, stall, or drop off the network, built up test by test rather than pulled in as a library. A coordinator already reassigns work when a machine goes quiet and writes output so a crash mid-task never leaves a partial result behind, and a versioned key-value store rejects any write that’s racing an unseen change, with a small lock built on nothing but that guarantee. The cluster picks its own leader — no fixed one, no external coordinator, just randomized timers and term numbers — and it recovers when that leader is cut off. It now agrees on a log as well as a leader: followers refuse entries that don’t line up behind what they already hold, and nothing counts as committed until a majority carries it, which holds through leaders failing, followers dropping out, and partitioned machines rejoining.

The instrument

A coordinator that outlives a dead worker

Tasks go out over plain Go RPC and get reassigned if a worker goes quiet for 10 seconds; output lands via temp-file-then-rename so a crash mid-task never leaves a partial result behind.

The tests exist before the implementation does

A failure-injection harness — elections, replication, crash persistence, snapshots — drives the target design, written before the code it's meant to catch.

The movement

The engineering underneath

A capstan needs a majority of hands, not all of them — that's the whole mechanism, not just the metaphor.

Output lands by rename, not by write

A worker writes each finished bucket to a fresh temp file and only renames it into place once every record is flushed — a crash mid-write leaves an orphaned temp file, never a half-written result the coordinator could mistake for done.

worker.go

for y, bucket := range buckets {
    tmpfile, err := os.CreateTemp(".", "mr-tmp-*")
    if err != nil {
        log.Fatalf("cannot create temp file: %v", err)
    }
    enc := json.NewEncoder(tmpfile)
    for _, kv := range bucket {
        if err := enc.Encode(&kv); err != nil {
            log.Fatalf("cannot encode kv: %v", err)
        }
    }
    tmpfile.Close()

    oname := fmt.Sprintf("mr-%d-%d", reply.TaskId, y)
    os.Rename(tmpfile.Name(), oname)
}

A Put that carries its own compare-and-swap

Before machines can agree with each other, one needs a store that doesn't let concurrent writers clobber each other silently. Every Put carries the version it last read; the server rejects it if that version has moved. A lock (Acquire, Release, nothing else) rides on top of exactly that guarantee.

server.go

func (kv *KVServer) Put(args *rpc.PutArgs, reply *rpc.PutReply) {
    kv.mu.Lock()
    defer kv.mu.Unlock()

    entry, ok := kv.data[args.Key]
    if !ok {
        if args.Version != 0 {
            reply.Err = rpc.ErrNoKey
            return
        }
        kv.data[args.Key] = valueEntry{value: args.Value, version: 1}
        reply.Err = rpc.OK
        return
    }

    if entry.version != args.Version {
        reply.Err = rpc.ErrVersion
        return
    }

    kv.data[args.Key] = valueEntry{value: args.Value, version: entry.version + 1}
    reply.Err = rpc.OK
}

A leader with no one to appoint it

Each server waits out a randomized timeout and calls an election if no heartbeat arrives in time; the randomness is what keeps split votes from repeating forever. No fixed leader, no external coordinator — just timers and term numbers deciding who's in charge. A candidate fans its request out in parallel and stops counting the moment the term it was elected under has moved on — a vote that arrives late belongs to an election that's already over.

raft.go

go func(server int) {
    reply := RequestVoteReply{}
    if !rf.sendRequestVote(server, &args, &reply) {
        return
    }

    rf.mu.Lock()
    defer rf.mu.Unlock()

    if reply.Term > rf.currentTerm {
        rf.currentTerm = reply.Term
        rf.state = follower
        rf.votedFor = -1
        return
    }

    if rf.state != candidate || rf.currentTerm != term {
        return
    }

    if reply.VoteGranted {
        voteMu.Lock()
        votes++
        count := votes
        voteMu.Unlock()

        if count > len(rf.peers)/2 && rf.state == candidate {
            rf.state = leader
            go rf.sendHeartbeats(term)
        }
    }
}(i)

The follower is the one who says no

A leader can't simply announce the log — it has to prove it lines up. Every batch names the entry that should come just before it, and a follower that doesn't have that exact index and term refuses outright; the leader walks its guess backward until the two agree. Where they diverge, the follower truncates its own tail rather than keeping a record nobody else has.

raft.go

if args.PrevLogIndex >= len(rf.log) ||
   rf.log[args.PrevLogIndex].Term != args.PrevLogTerm {
    reply.Term = rf.currentTerm
    reply.Success = false
    return
}

for i, entry := range args.Entries {
    idx := args.PrevLogIndex + 1 + i
    if idx < len(rf.log) {
        if rf.log[idx].Term != entry.Term {
            rf.log = rf.log[:idx]
            rf.log = append(rf.log, args.Entries[i:]...)
            break
        }
    } else {
        rf.log = append(rf.log, args.Entries[i:]...)
        break
    }
}

Committed means "on a majority," not "on everyone"

Electing a leader settles who speaks; the log settles what was said. An entry becomes safe to apply once it sits at the same index on more than half the cluster — the leader scans backward for the highest such index and moves the commit line there. The extra condition is the one that's easy to miss: only entries from the leader's own term count. Counting an inherited entry into a majority is how a committed record can still be lost. Stragglers catch up later; the majority is what makes it durable now.

raft.go

func (rf *Raft) updateCommitIndex() {
    for n := len(rf.log) - 1; n > rf.commitIndex; n-- {
        if rf.log[n].Term != rf.currentTerm {
            continue
        }
        count := 1

        for i := range rf.peers {
            if i != rf.me && rf.matchIndex[i] >= n {
                count++
            }
        }

        if count > len(rf.peers)/2 {
            rf.commitIndex = n
            break
        }
    }
}

Specification

Language: Go
Paper: Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (2014)
Consensus target: Raft — election, replication, snapshots
Testing: Failure-injection harness — elections, replication, crash persistence, snapshots
Basis: MIT 6.5840 (Distributed Systems), self-study