HW: Fault-Tolerant Key-Value Service (C)

In this assignment, which is based on labs from MIT 6.5840, you will build a fault-tolerant key-value storage service from the ground up. You will start with a single-server key/value store, then implement the Raft consensus algorithm, and finally combine them into a replicated service that continues operating even when servers crash or become partitioned.

This assignment has four parts:

1. Simple Key-Value Server
   Implement a single-server KV store with versioned puts and a client that communicates via RPC.
2. Distributed Lock
   Build a lock service on top of your KV store.
3. Raft
   Implement the Raft consensus algorithm with leader election, log replication, and persistence.
4. Fault-Tolerant KV Store
   Combine Raft with the KV store to build a replicated state machine, and adapt your client and lock to work with the cluster.

Getting started

Pull the starter code. Build and verify the project compiles.

cd ~/code/personal
git pull staff main
cd kvsrv-c-starter

make

You will see compiler warnings about unused variables and unused parameters. Don’t worry, these are expected as long as you do not see any errors.

The build produces five binaries: kv_server, raft_server, and the three test binaries below.

Testing

Each test binary forks child processes for isolation, so run them one at a time:

# Parts 1-2: Single-server KV and Distributed Lock
./test_kvsrv

# Part 3: Raft
./test_raft

# Part 4: Fault-tolerant KV
./test_kvraft

The tests execute sequentially in a fixed order inside each binary. To run a subset, edit main() in the corresponding tests/*.c file (or just scroll the output).

Resources

• Raft paper (extended version) — Read this. Sections 5 and 6 along with Figure 2 are most important.
• Raft visualization — Interactive demo of leader election and log replication.
• MIT 6.5840 Raft guide — Practical tips for implementing Raft.