After a few years of taking it easy while writing business code on AWS, I felt it was still necessary to deepen my craft as a programmer and properly learn how distributed systems actually work. So after finishing MIT 6.828, I continued down the rabbit hole into the famous 6.824 (now 6.5840) — implementing Raft from scratch in golang, and then building a distributed K/V storage system on top of it. After finishing, I could only sigh: having undergrads do this lab is just absurdly hard; debugging distributed systems bugs is genuinely life-shortening... In the end, I still completed the three Raft-based labs. All tests passed, including 10k parallel stress runs of the full test suite, but due to course requirements the code cannot be made public, so I’m writing this blog post to record some takeaways.
This article is divided into three parts: no spoilers, light spoilers, and heavy spoilers. The first part has no spoilers and focuses on experience, pitfalls, and debugging techniques, so feel free to read it.
Reflections on Getting Through
- Years of work experience taught me one thing: the core difficulty of programming is that you don’t know where you’ll step into a pitfall. The biggest benefit of a carefully designed lab like this is that the authors (try to) help you avoid pitfalls, so before writing code, read all the advice carefully and make sure it aligns with your own thinking. Don’t design some fancy structure on a whim and then discover you’ve planted a giant mine for yourself.
- Even experienced programmers still miss details that lead to racing conditions... If there is any subtle bad taste in the code, trust me, it will make you suffer through debugging.
- The lifecycle of a goroutine is sometimes not what you think. If you have a leak, it may affect the system in almost incomprehensible ways — for example, timers (
time.Sleep) no longer firing accurately, causing frequent election timeouts and preventing consensus. If you suspect this, you can use the method provided here to dump all running goroutines at a moment in time and inspect them (note to setdebug=2to get a more readable stack trace). In short, once a Raft instance isKill()ed, it’s best to ensure its corresponding goroutines can finish within a bounded time, even if the lab doesn’t require it. - The TA-provided
dtestscript makes it easy to stress test the system with high concurrency, but under high CPU load the golang runtime can also have inaccurate timers, making Raft run inefficiently and causing some test cases to fail. This is normal; don’t obsess over it. For example, lab4’sTestJoinLeavecase will directly sleep for one second to wait for a replica group to send out shard data, and then disconnect its network. It does not consider that under high load the send may not finish in time, ultimately causing a deadlock timeout. - Be extra careful when using channels: this type cannot be serialized by RPC. After deserialization you will get
nil, and writing tonilwill directly block! This is a huge pitfall — shouldn’t it be a runtime error...
Debug Logs and Visualization
The labs in 6.824 essentially force you to learn debugging techniques for distributed systems, so how to log efficiently is a critical part. The TA even wrote a dedicated blog post to introduce related tips; note that it provides a script named dtest that is very useful. Based on past work experience, I chose to use the Chromium project’s performance visualization tool Perfetto to assist in debugging Raft, and in practice the fit felt quite good. This visualization tool still supports Chromium’s early Trace Event Format data format: you just write key system data into JSON using the required fields, then load the file from the web UI for visualization, with useful features like timeline zooming and markers.
Each thread in the figure can correspond to a Raft server node, and each process can correspond to a replica group in lab4, so this existing hierarchy fits well for showing Raft execution details. I actually used only two event types: Duration Events to visualize each server’s role state on the timeline, and Instant Events to annotate occurring events while recording detailed internal state (after the event) in JSON format, which is very helpful for debugging.
You can pass the JSON output filename via an environment variable, and modify the TA-provided dtest script so that when a test fails it also saves the corresponding JSON file for later analysis. If you record too many event types, you can quickly hack a simple Python script to filter the JSON content, or provide switches in code, etc. The implementation can be quite flexible. A rough example of event recording code is as follows (this is somewhat quick-and-dirty using global variables):
func TraceInstant(name string, server int, group int, timestamp int64, args map[string]any) {
if !FlagTrace {
return
}
gMutex.Lock()
defer gMutex.Unlock()
if gFile == nil {
return
}
logitem := map[string]any{
"name": name,
"ph": "i",
"pid": group,
"tid": server,
"ts": timestamp - gStart,
"args": args,
}
data, _ := json.Marshal(logitem)
gFile.Write(data)
gFile.WriteString(",\n")
}
Since we need frequent access to Raft internal state, we should also wrap it in a method:
func merge(maps ...map[string]any) map[string]any {
merged := make(map[string]any)
for _, m := range maps {
for k, v := range m {
merged[k] = v
}
}
return merged
}
func (rf *Raft) GetTraceState() map[string]any {
return merge(rf.log.GetTraceState(), map[string]any{
"GID": rf.getGID(),
"raft.currentTerm": rf.currentTerm,
"raft.commitIndex": rf.commitIndex,
"raft.lastApplied": rf.lastApplied,
"raft.nextIndex": fmt.Sprintf("%v", rf.nextIndex),
})
}
// when recording events:
TraceInstant("NewElection", rf.me, rf.getGID(), time.Now().UnixMicro(), rf.GetTraceState())
Many times tests get stuck on a panic in our code. It’s best to wrap that too, so you can find the corresponding event in the visualized logs and inspect what happened before and after:
func (rf *Raft) TracePanic(msg string, context map[string]any) {
TraceInstant("Panic", rf.me, rf.getGID(), time.Now().UnixMicro(), merge(rf.GetTraceState(), context))
panic(msg)
}
On the other hand, we should create Duration Events to record which role each server is in on the timeline, based on the paper’s Figure 4 state transition diagram, which makes the visualization much clearer. Example:
func (rf *Raft) SwitchToCandidate() {
now := time.Now().UnixMicro()
if rf.role == Leader {
panic("Leader can not become candidate")
}
if rf.role == Follower {
TraceEventEnd(Follower.String(), rf.me, rf.getGID(), now, nil)
}
if rf.role != Candidate {
TraceEventBegin(Candidate.String(), rf.me, rf.getGID(), now, rf.GetTraceState())
}
rf.role = Candidate
// ...
}
func (rf *Raft) SwitchToFollower() { /* ... */ }
func (rf *Raft) SwitchToLeader() { /* ... */ }
Note: when initializing the JSON file, you need to record an initial event with ts=0 (SystemStart). Otherwise, the web UI will shift the first event to time zero, and all subsequent timestamps will have an offset added, making it inconvenient to locate events by timestamp in the UI.
Below are the debug-friendly events I printed in code after completing all labs. If file size allows, it’s best to record as much state context as possible:
- SystemStart
- StartCommand
- NewElection
- Vote/GotVote
- Commit/Apply
- Snapshot/StateMachineSnapshot
- Heartbeat/AppendEntries
- InstallSnapshot
- SendShard/SendShardFailed
In practice, this debugging setup still has the following drawbacks:
- You can’t quickly search for events at a specific timestamp or matching certain conditions; you need to zoom and hunt manually
- There’s no way to link events together or jump quickly between related events
⚠️ Light spoilers begin below, mainly covering implementation ideas for parts that are not clearly spelled out in the Raft paper and the lab guidance, plus some points to watch out for.
Approach and Details
Lab2: Raft Protocol
Election Timeout
If a follower receives no communication over a period of time called the election timeout, then it assumes there is no viable leader and begins an election to choose a new leader.
A key point here is that when a follower receives any kind of RPC, it resets the election timeout timer. If you don’t do this, you can end up in a situation where a leader has just been elected, but some follower times out and starts a new election, hurting stability.
Also note that the election timeout provided in the initial code is on the low side. In TestFigure8Unreliable2C, because the network delay jitter is configured relatively high, under concurrent stress there can be a small probability of timeout errors. Since the network itself is unstable, a low timeout makes it easy for followers to miss heartbeats even after a leader has been elected, triggering new elections repeatedly and preventing log entries from being committed. This issue bothered me for quite a while; I analyzed logs for a long time and eventually confirmed it was not an implementation bug. After referencing others’ blogs, I found that simply setting the election timeout to 400–800ms fixes it...
PS: The pitfall here essentially comes from insufficient theoretical grounding. If I've ever read Designing Data-Intensive Applications, I should have recognized that Raft’s liveness property relies on assuming bounded message-processing latency. When this bound is chosen incorrectly, the system can fail to make forward progress.
How should voteFor be updated?
From the paper’s Figure 4 state transitions we know that when a node is a leader, this field is meaningless; when the node is a candidate, voteFor is obviously set to itself. So only when the node becomes a follower does it need to be set to null, because at that moment it does not yet know whom to vote for. At initialization, all nodes are followers, so all voteFor values are also null.
Commit Policy
Only log entries from the leader’s current term are committed by counting replicas.
Intuitively, we want to commit an entry once it has been replicated to a majority, but what if the leader crashes before committing? Can the new leader just “finish committing” an entry from the previous leader? The paper tells us this policy is flawed; the counterexample is Figure 8 — even if a log entry has been replicated to a majority, a new leader may still overwrite it. The correct approach adds a condition: if you want to commit, you must commit through the current term in one go, which naturally includes uncommitted entries from earlier terms; but if you can’t do that, you must not commit only replicated entries from previous terms.
Because of this policy, during debugging you must also note that after a term change, if no new commands arrive, then even fully replicated commands may not be committed. This is expected behavior.
Snapshot Implementation Details
When you wrap the log array into a data structure, it’s very easy to miss boundary conditions. So you should add panics (with concrete printed info) anywhere an out-of-bounds access might occur, which helps fix these bugs.
Avoid state machine rollback
Take care that these snapshots only advance the service's state, and don't cause it to move backwards.
This sentence in the lab highlights a detail that can cause bugs in lab3: when receiving an InstallSnapshot RPC, if the snapshot contains fewer log entries than the local log length but is still newer than the previous snapshot, we will save the snapshot, but we do not necessarily need to apply it to the service (state machine). In this case it’s possible that rf.commitIndex >= args.LastIncludedIndex; applying the snapshot would cause the service state to move backwards. We can maintain a lastAppliedIndex in the KV service to avoid this and still pass tests, but that is not the correct implementation. We should instead ensure at the source that the Raft protocol never emits an incorrect apply snapshot.
Correctly backing off nextIndex
This is another easy pitfall. After implementing the nextIndex backoff optimization in lab 2C, you might write logic like this in the AppendEntries RPC:
if rf.log.IsTermValidAt(args.PrevLogIndex) {
// ...
} else {
reply.XLen = rf.log.Length()
reply.XTerm = -1
reply.XIndex = -1
reply.Success = false
return
}
But once log compaction is introduced in lab 2D, failing to find the term at PrevLogIndex can have two causes: the follower’s log is too short, or the entry at that position has been compacted. In the latter case, we need to return the first log entry index that is not yet in the snapshot, so the leader can start sending AppendEntries from there. Otherwise, the leader may never be able to replicate logs to this follower. I only triggered an error from this bug at the end of lab4 — it is extremely subtle.
Apply messages in order
After updating commitIndex, how to send ApplyMsg to applyCh is slightly tricky, especially after implementing Snapshot you may find the system deadlocking due to failing to acquire locks. It’s best to send asynchronously to prevent applyCh from blocking and holding Raft locks, freezing the whole system. Also, you cannot just start a new goroutine every time, because then you can’t guarantee command index order when writing to the channel. Instead, you should use a buffered queue. ApplyMsg produced by InstallSnapshot RPC should also go into the same buffer to ensure correct ordering when delivering to the state machine.
Lab2 took me the longest, and I only managed to make all cases pass stably after finishing lab4:
⛔️ Heavy spoilers begin below, including many implementation details that require your own design and reasoning. Reading the content below will reduce the depth of your own thinking about these problems!
Lab 3: K/V Server
After implementing the core Raft protocol, the next step is to understand how to use it. Essentially, it is used to linearly commit concurrent modifications (and reads) to a state machine in order to achieve strong consistency. This lab requires thinking through several key questions:
- How can client RPCs synchronously and cleanly obtain execution results from the state machine thread?
- Understand how request deduplication actually works, and how to optimize space complexity
- After a client operation is successfully submitted through
rf.Start(), it will sleep and wait, but not every successfully submitted operation will ultimately be committed. From Figure 8 in the paper we know that different operations may end up being committed at the same index; how do we gracefully fail the requests that are still waiting?
For the first point, here is my implementation idea: just store a buffered string channel in the Op struct, used to receive the result sent back from the state machine thread during execution.
type Op struct {
Key string
Value string
Op string
ResultCh chan string
From int
// ...
}
func (kv *KVServer) Get(args *GetArgs, reply *GetReply) {
// ...
resultCh := make(chan string, 1)
index, _, isLeader := kv.rf.Start(Op{
Op: GetOp,
Key: args.Key,
ResultCh: resultCh,
From: kv.me,
// ...
})
if isLeader {
select {
case result := <-resultCh:
reply.Value = result
reply.Err = OK
}
// ...
} else {
reply.Err = ErrWrongLeader
}
}
// goroutine StateMachineExecutor
// ...
if op.From == kv.me && op.ResultCh != nil {
op.ResultCh <- result
}
Since ResultCh is automatically converted to nil during serialization, it will not be replicated to followers via AppendEntries. This ensures that only the server node that received the client RPC and is blocked waiting needs its state machine thread to write to the channel to unblock.
After unavoidable debugging, I finally passed:
Lab 4: Shard K/V Server
This lab basically only states requirements and asks you to figure out how to implement them; the degree of freedom is far higher than in earlier labs.
A few tips:
- Before starting Shard K/V Server, be sure to stress test the Shard Controller module with
dtestand make sure it is correct. - Read the lab guide thoroughly and include the challenge problems in the design from the beginning; there is no need to do them separately.
Implementing Re-configuration
The first point that stuck me was: after a config update, how do we synchronously propagate information to all replica groups? From lab3 we learned that distributed systems are essentially about linearly committing all concurrent modifications to the state machine through Raft, so there must be a thread continuously pulling from the shard controller. The next question is how to apply the received config changes to Raft. Here is a crucial point: can we skip one or several config versions and directly apply the next one? The answer is no. If we allow this, each server node cannot ensure its config update history matches others, which will inevitably lead to some form of deadlock. For example, a replica group might wait for shard data from other groups, but the corresponding group skipped this config, so the system state can never move forward.
Therefore, while handling re-configuration, all server nodes within the same replica group must reach consensus on config changes, so they can send out shard data with consistent state. This means we need to submit ConfigChange itself as a log entry to the underlying Raft protocol, and when the state machine processes this command, it must require the config num to increase in order; otherwise it ignores it. Pseudocode for the config puller thread is:
func (kv *ShardKV) configPuller() {
for !kv.killed() {
newConfig := kv.mck.Query(-1)
activeConfig := kv.config.Load()
if newConfig.Num != activeConfig.Num {
for num := activeConfig.Num + 1; num <= newConfig.Num && !kv.killed(); num += 1 {
cfg := kv.mck.Query(num)
kv.rf.Start(Op{
Op: ConfigChange,
NewConfig: &cfg,
// ...
})
}
}
time.Sleep(time.Millisecond * 100)
}
}
Note that in the code above we call kv.rf.Start() directly. Intuitively it seems this ensures the operation enters Raft and gets replicated to followers by the current leader, but it does not! The reason is that the server node may not be the leader when it starts the operation, so the operation gets dropped. Only when a call returns isLeader=true can we guarantee that the operation enters Raft, but even then it still cannot guarantee it will be executed; only when the operation appears on applyCh can we truly guarantee it has been executed. Because the puller logic reads the current config num and keeps retrying, it won’t affect overall correctness. In other words, I just keep sending; whether your state machine executes it is another matter, but it won’t be missed.
Request Deduplication
The dedup logic in lab4 is mostly similar to lab3, but you must note that when sending shard data to other replica groups, you also need to send the corresponding elements in the dedup table, so that the new replica group can avoid accepting duplicate requests from the same client. One might make a simple modification to the lab3 logic: still use client ID as the key, put shard ID into the value, then iterate the dedup table to find and delete entries for shards being sent to another replica group. This looks fine, but it ignores an important detail: after deleting a client ID, if the current replica group later receives another request from that client, what will it use for dedup? So what we need is not a simple deletion but more like a “rollback”. The solution is also simple — combine client ID and shard ID as the key:
type DedupKey struct {
ClientId int64
ShardId int
}
type DedupEntry struct {
SeqNumber int32
Value string
}
type ShardKV struct {
//...
dedup map[DedupKey]DedupEntry
}
// when sending shards to other replica group:
for key, entry := range kv.dedup {
for _, shard := range shards {
if key.Shard == shard {
// copy the entry into send shard request
// ...
delete(kv.dedup, key)
}
}
}
This expands the size of the dedup table, but when we delete a particular (ClientId, ShardId), we still keep keys formed by the same client ID and the remaining shards, so we can correctly dedup future requests from that client. If this is not implemented correctly, you will fail the linearizability tests, and it is extremely hard to debug.
After painful debugging, I finally passed all lab4 tests stably:
Challenge 1 Garbage collection
The key point here is: when sending shard data, you must ensure that the data has been persisted to the target replica group before it is safe to delete locally. I chose to, after handling ConfigChange, store shard data in a buffer and send it asynchronously, and also persist that buffer as part of persistent state. But in this challenge you run into a problem: right after executing ConfigChange, a snapshot may be triggered, and before shard data in each server node’s buffer has been sent, it gets saved, creating redundancy. Some mechanism is needed to ensure that once shard sending completes, you take another snapshot. To pass this test case 100%, I used a tricky workaround: after each async shard send completes, send a special NOP command via applyCh with index set to -1, forcing a snapshot so that redundant data written into the previous snapshot gets overwritten. The logic is roughly like this:
// goroutine SendShards
// ...
if allShardsSent {
kv.applyCh <- raft.ApplyMsg{CommandValid: true, CommandIndex: -1, Command: Op{
Op: Nop,
}}
}
// goroutine CommandExecutor
// ...
if kv.maxraftstate > 0 && kv.persister.RaftStateSize() >= kv.maxraftstate {
if cmd.CommandIndex != -1 {
kv.Snapshot(cmd.CommandIndex)
} else {
kv.Snapshot(kv.lastAppliedIndex)
}
}
Although this implementation is not pretty and reduces efficiency, it passes the Challenge 1 test case stably.
What's Next?
- Implement linearizable read: you will find that the read path can also be optimized to support high throughput, which helps further clarify the tradeoff between synchronous replication vs consensus replication
- Support distributed transactions: gain a more essential understanding of 2PC, and you will realize that it shines behind every guarantee of “atomicity” in various distributed systems
(End of article)
PS: If you were patient enough to read this far and are interested in my implementation, you can email me to request the code. For reference and learning only; please do not publish it publicly.