Raft Hints

CS1380 S22

When in doubt, read the raft cheat sheet.

https://raft.github.io/raft.pdf

Play around with a Raft simulation here: https://raft.github.io/ (does not cover network partitions)

System Components

• StableStore: Storage engine for Raft logs. Logs contain the history of changes to the cluster and its contents. Includes leader changes + record of client messages. Replicated consistently across majority of nodes.
• Implemented as an interface - BoltStore and MemoryStore are two physical storage engines (disk-based and memory-based respectively) that implement StableStore.�
• StateMachine: The actual data that clients want to store on nodes. This is basically a key-value store. When logs from StableStore are replayed on a node, they update the physical contents of StateMachine. �
• Node: A server that can exist in follower state, leader state and candidate state respectively.

Node Anatomy

All of these variables are already initialized for you

​

currentTerm and votedFor are stored in StableStore. Use the provided helper functions GetCurrentTerm, SetCurrentTerm, etc. to access it.

​

commitIndex, nextIndex, matchIndex and lastApplied are kept inside the Node struct definition.

​

Remember to update these where appropriate in your implementation.

Node Anatomy

type Config struct {

ElectionTimeout time.Duration

HeartbeatTimeout time.Duration

ClusterSize int

NodeIDSize int

LogPath string

InMemory bool

}

​

(Nodes have access to this Config under the Config struct variable)

Node Anatomy

We’ve created four Go channels for you to read from:

​

n.appendEntries = make(chan AppendEntriesMsg) // AppendEntries RPC

n.requestVote = make(chan RequestVoteMsg) // RequestVote RPC

n.clientRequest = make(chan ClientRequestMsg) // client requests

n.gracefulExit = make(chan bool) // if true, shutdown right away

​

You are required to handle messages from any of these channels in any node state. For example, if you are in doFollower state, you should be able to handle clientRequest messages appropriately.

How State Transitions Work

Example of how to do a transition from Follower -> Candidate

// anywhere inside doFollower()

-> return doCandidate // return a function pointer to doCandidate function

​

Example of how to do a transition from Follower to shutdown state

// anywhere inside doFollower()

-> return nil // triggers a shutdown of the node

​

(you can generalize this transition logic to doLeader, doCandidate and doFollower respectively)

​

What You Are Expected to Do

1. Implement the Leader state:
1. Implement sendHeartbeats
2. Implement listening on all four channels in an infinite loop
3. Edge case handling

​

1. Implement the Follower state:
2. Implement handleAppendEntries
3. Implement listening on all four channels in an infinite loop
4. Edge case handling (no need to modify appendEntries for this, but consider e.g. requestVotes edge case handling, etc.)�
2. Implement the Candidate state:
• Implement requestVotes
• Implement listening on all four channels in an infinite loop
• Edge case handling

Test Requirement

Coverage on the following files should all be >= 90% coverage.

• Node_candidate_state.go
• Node_leader_state.go
• node_follower_state.go

​

Suggested testing scenarios: Leader election, log replication, log commitment, client interaction, and all of the above but during network partition

​

There is no coverage requirement for other files. Document your tests!

​

To check per-file coverage,

​

​

​

​

Test Helpers

1. We have a way to simulate network partitions for you!
1. network_policy.go
2. See examples of use in example_partition_test.go�
2. Create a pre-existing Raft cluster with CreateDefinedLocalCluster
• test_utils.go
• See examples of use in example_client_test.go�
3. Find the leader in any list of nodes with findLeader
• See test_utils.go
• See examples of use in example_*_test.go

Provided Helper Functions

Logging helpers

• Out
• Debug
• Error
• String
• FormatState
• FormatLogCache
• FormatNodeListIds

​

Applies a single log entry to the finite state machine

• processLogEntry

​

High Level APIs for StableStore (persistent state on all servers)

• setCurrentTerm
• GetCurrentTerm
• setVotedFor
• GetVotedFor
• CacheClientReply
• GetCachedReply
• LastLogIndex
• StoreLog
• GetLog
• TruncateLog
• RemoveLogs

​

Client Registration

1. Reject if not a leader. LeaderHint should be n.Self if no leader known.
2. Create a log entry of type CommandType_CLIENT_REGISTRATION
3. Wait for the regular heartbeats process in sendHeartbeats to commit this to everyone. Put the pending response channel into a queue (hint: see requestsByCacheId data structure) so leader can do other work.
4. Once committed, processLogEntry will respond to the pending client request.

​

​

​

← What field of the newly created log can be used as a unique client id?

type RegisterClientMsg struct {

request *RegisterClientRequest

reply chan RegisterClientReply

}

Client Requests (Concepts)

1. A Client sends a request to the leader with a unique client ID and a unique sequence num. Duplicate requests are possible. Caching is necessary.
2. The leader creates a log entry and stores it. Get a cache ID with createCacheID. The reply channel is stored in n.requestsByCacheID[cacheID].
3. processLogEntry will put the reply from the state machine in the reply channel found at n.requestsByCacheID[entry.CacheId]

4. If a duplicate request comes before processLogEntry is called, make sure when the reply is available, both old and new reply channels are replied to.

5. If a duplicate request comes after processLogEntry is called, call n.GetCachedReply.

type ClientRequestMsg struct {

request *ClientRequest

reply chan ClientReply

}

Client Requests (Implement)

1. Reject if not a leader. LeaderHint should be n.Self if no leader known.
2. If n.GetCachedReply succeeds, reply with the cached reply.
3. If an entry in n.requestsByCacheId corresponding to the cache ID already exists, append the reply channel of the newly received request to the existing array. Otherwise, just add the reply channel to n.requestsByCacheId. This ensures when the reply is available, both old and new reply channels are replied to.
4. If not cached anywhere, store a new log entry.

← GetCachedReply caches replies that are already sent back to the user.

← requestsByCacheID caches requests that are in the log but not yet processed.

​

​

​

type ClientRequestMsg struct {

request *ClientRequest

reply chan ClientReply

}

Other Things

• “Each leader stores a blank no-op entry into the log at the start of its term”
• Unlike what the paper does, we try to bring the followers' log up to date in each heartbeat. We don’t send empty AppendEntriesRPC as heartbeats (unless nextIndex already exceeds lastLogIndedx).
• There is a race condition in part of the stencil code. You can ignore race conditions.

​

• Commit log by calling `processLogEntry`.
• Make sure your code is robust against hanging RPCs.
• A follower can reset election timeout after granting a vote.
• Check index out of range error.

FAQ

• Use goroutine for performance reason.
• Ex, SendHeartbeats should be fired asynchronously
• Everything in elections is done in the paper's way or its equivalent. Please read figure 1 carefully when you have questions. (ex, Why a candidate and a leader rejects equal term in requestVote)
• Do not change the proto definition
• nextIndex and matchIndex use node ID as the key. You may also use ID for comparison.
• For updating commitIndex, do not wait for all responses. Commit in sendHeartbeats() if a majority of AppendEntriesRPC calls succeed. Call processLogEntry when you are ready to commit it
• Timeout time to retry RPCs
• The paper mentioned we should retry RPCs indefinitely if no response is received in a timely manner. But for our implementation, we only need to try once at each heartbeat.
• How to handle gracefulexit? Just return nil.

​

​

​