Documentation ¶
Index ¶
- func Raft()
- func ResolveAllPeers(hosts HostMap, clients ClientMap, hostfile string, amHost bool) (int, int)
- func ResolvePeersOnce(hosts HostMap, clients ClientMap, h hostStringMap, c clientStringMap) bool
- type AppendEntriesStruct
- type ClientData
- type ClientDataStruct
- type ClientID
- type ClientMap
- type ClientResponse
- type ClientSerialNum
- type HostID
- type HostMap
- type Log
- type LogEntry
- type LogIndex
- type Peer
- type RPCResponse
- type RaftNode
- func (r *RaftNode) AppendEntries(ae AppendEntriesStruct, response *RPCResponse) error
- func (r *RaftNode) CandidateLooksEligible(candLastLogIdx LogIndex, candLastLogTerm Term) bool
- func (r *RaftNode) QuitChan() chan bool
- func (r *RaftNode) Start()
- func (r *RaftNode) StoreClientData(cd ClientDataStruct, response *ClientResponse) error
- func (r *RaftNode) String() string
- func (r *RaftNode) Vote(rv RequestVoteStruct, response *RPCResponse) error
- type RequestVoteStruct
- type StateMachine
- type Term
Examples ¶
- RaftNode (ResetTickers_notTooFast)
- RaftNode (ResetTickers_notTooSlow)
- RaftNode.AppendEntries (BadPrevLogIdxFails)
- RaftNode.AppendEntries (BadPrevLogTermFails)
- RaftNode.AppendEntries (ExtendAndDeleteSuffixSucceeds)
- RaftNode.AppendEntries (InvalidHeartbeatPrevLogIdxFails)
- RaftNode.AppendEntries (InvalidHeartbeatPrevLogTermFails)
- RaftNode.AppendEntries (OldTermFails)
- RaftNode.AppendEntries (UnusedIdxSucceeds)
- RaftNode.AppendEntries (ValidHeartbeatSucceeds)
- RaftNode.CandidateLooksEligible (BadLogIdxFails)
- RaftNode.CandidateLooksEligible (BadLogTermFails)
- RaftNode.CandidateLooksEligible (FutureLogIdxSucceeds)
- RaftNode.CandidateLooksEligible (FutureLogTermSucceeds)
- RaftNode.CandidateLooksEligible (SameLogTermLogIdxSucceeds)
- RaftNode.Vote (BadLogIdxFails)
- RaftNode.Vote (BadLogTermFails)
- RaftNode.Vote (FutureLogIdxNewLeaderSucceeds)
- RaftNode.Vote (FutureLogIdxSameLeaderSucceeds)
- RaftNode.Vote (FutureLogTermNewLeaderSucceeds)
- RaftNode.Vote (FutureLogTermSameLeaderSucceeds)
- RaftNode.Vote (FutureTermSucceedsNewLeader)
- RaftNode.Vote (FutureTermSucceedsSameLeader)
- RaftNode.Vote (PrevTermNewLeaderFails)
- RaftNode.Vote (PrevTermSameLeaderFails)
- RaftNode.Vote (SameTermNewLeaderFails)
- RaftNode.Vote (SameTermSameLeaderSucceeds)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Raft ¶
func Raft()
Raft is the entrypoint function for the raft replicated state machine protocol
func ResolveAllPeers ¶
ResolveAllPeers gets the net address of all raft hosts and clients, and stores these in the provided HostMap and ClientMap structures. Notice that all nodes must be alive to begin the protocol; thus We loop infinitely here, until we have information for all nodes. Returns our own id and our recvPort. id returned as integer. Caller (either host or client) must cast to HostID or ClientID appropriately
func ResolvePeersOnce ¶
ResolvePeersOnce makes one attempt to identify all hosts and clients in the provided maps. As they are found, peers get removed from these maps. NOTE - We do not handle the errors from LookupHost, because we are waiting for nodes to come online.
Types ¶
type AppendEntriesStruct ¶
type AppendEntriesStruct struct { Term Term LeaderID HostID PrevLogIndex LogIndex PrevLogTerm Term Entries []LogEntry LeaderCommit LogIndex }
AppendEntriesStruct holds the input arguments for the RPC AppendEntries
func (AppendEntriesStruct) String ¶
func (ae AppendEntriesStruct) String() string
type ClientData ¶
type ClientData string // NOTE - could make contents a state machine update
ClientData represents an object sent by the client for storage in the StateMachine
type ClientDataStruct ¶
type ClientDataStruct struct { ClientID ClientID Data ClientData ClientSerialNum ClientSerialNum }
ClientDataStruct holds the inputs that a client sends when they want to store information in the statemachine
type ClientResponse ¶
type ClientResponse struct { Success bool // if success == false, then client should retry using 'leader' Leader HostID }
ClientResponse carries the reply from a raft node to a client after RPC
func (ClientResponse) String ¶
func (c ClientResponse) String() string
type ClientSerialNum ¶
type ClientSerialNum int
ClientSerialNum is a unique, monotonically increasing integer that each client attaches to their requests The state machine includes a map of clients and their most recently executed serial num If a request is received with a stale ClientSerialNum, the leader can immediately reply "success"
type LogEntry ¶
type LogEntry struct { Term Term ClientData ClientData // TODO - the following 3 fields are here for convenience // They might belong to the StateMachine instead of the Log ClientID ClientID // The client who sent this data ClientSerialNum ClientSerialNum // The unique number the client used to identify this data ClientResponse ClientResponse // The response that was given to this client }
LogEntry is an entry in the log NOTE that all fields must be public for Gob encoding during RPC
func NewLogEntry ¶
func NewLogEntry(t Term, cd ClientData, cid ClientID, csn ClientSerialNum, cr ClientResponse) LogEntry
NewLogEntry is a public constructor for a LogEntry
type RPCResponse ¶
RPCResponse carries the reply between raft nodes after an RPC
func (RPCResponse) String ¶
func (r RPCResponse) String() string
type RaftNode ¶
type RaftNode struct { // Exported for persistent storage CurrentTerm Term // latest term server has seen VotedFor HostID // ID of candidate that received vote in current term (or -1 if none) Log Log StateMachine StateMachine // Convenience variables sync.Mutex // control acess from multiple goroutines. Notice we can now just do r.Lock() instead of r.mut.Lock() // contains filtered or unexported fields }
RaftNode describes a participant in the Raft protocol
Example (ResetTickers_notTooFast) ¶
r := mockRaftNode(Term(0), Term(0), 0, 0) r.timeoutUnits = time.Millisecond var result strings.Builder result.WriteString("begin.") nIteration := 5 for i := 0; i < nIteration; i++ { var electionTimeout, _ time.Duration = r.resetTickers() var half time.Duration = electionTimeout / 2 Loop: for { select { case <-time.After(half): // should always trigger first break Loop case <-r.electionTicker.C: result.WriteString("bad.") break Loop } } } result.WriteString("end") fmt.Println(result.String())
Output: begin.end
Example (ResetTickers_notTooSlow) ¶
r := mockRaftNode(Term(0), Term(0), 0, 0) r.timeoutUnits = time.Millisecond var result strings.Builder result.WriteString("begin.") nIteration := 5 for i := 0; i < nIteration; i++ { var electionTimeout, _ time.Duration = r.resetTickers() var half time.Duration = electionTimeout / 2 Loop: for { select { case <-r.electionTicker.C: // should always trigger first break Loop case <-time.After(electionTimeout + half): result.WriteString("bad.") break Loop } } } result.WriteString("end") fmt.Println(result.String())
Output: begin.end
func NewRaftNode ¶
func NewRaftNode(id HostID, recvPort int, hosts HostMap, clients ClientMap, quitChan chan bool) *RaftNode
NewRaftNode is a public constructor for RaftNode
func (*RaftNode) AppendEntries ¶
func (r *RaftNode) AppendEntries(ae AppendEntriesStruct, response *RPCResponse) error
AppendEntries is called by RPC from the leader to modify the log of a follower. TODO - some amount of duplicated logic in AppendEntries() and Vote() Returns false if entries were rejected, or true if accepted
Example (BadPrevLogIdxFails) ¶
follower, leaderLog := setupAppendEntriesTest() ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: 999, // follower does not have this position PrevLogTerm: 0, Entries: leaderLog, LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: false
Example (BadPrevLogTermFails) ¶
follower, leaderLog := setupAppendEntriesTest() ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: 0, // follower has this position PrevLogTerm: 999, // does not match follower's term at that position Entries: leaderLog, LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: false
Example (ExtendAndDeleteSuffixSucceeds) ¶
prevLogIdx := 2 follower, leaderLog, resultLog := setupAppendEntriesTestWithSplice(2) ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: LogIndex(prevLogIdx), // This time, append after position 2 PrevLogTerm: 1, // matches follower's term at that position Entries: leaderLog, LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(sameLog(follower.Log, resultLog))
Output: true
Example (InvalidHeartbeatPrevLogIdxFails) ¶
prevLogIdx := 6 follower, _, _ := setupAppendEntriesTestWithSplice(prevLogIdx) ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: LogIndex(prevLogIdx + 1), // follower has this position PrevLogTerm: 1, // does NOT match follower's term at that position Entries: make([]LogEntry, 0), LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: false
Example (InvalidHeartbeatPrevLogTermFails) ¶
prevLogIdx := 6 follower, _, _ := setupAppendEntriesTestWithSplice(prevLogIdx) ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: LogIndex(prevLogIdx), // follower has this position PrevLogTerm: 0, // does NOT match follower's term at that position Entries: make([]LogEntry, 0), LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: false
Example (OldTermFails) ¶
follower, leaderLog := setupAppendEntriesTest() ae := AppendEntriesStruct{ Term: 4, LeaderID: 2, PrevLogIndex: 0, PrevLogTerm: 1, // matches the entry of follower's log Entries: leaderLog, LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: false
Example (UnusedIdxSucceeds) ¶
prevLogIdx := 6 follower, leaderLog, resultLog := setupAppendEntriesTestWithSplice(prevLogIdx) ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: LogIndex(prevLogIdx), // follower has this position PrevLogTerm: 1, // matches follower's term at that position Entries: leaderLog, LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(sameLog(follower.Log, resultLog))
Output: true
Example (ValidHeartbeatSucceeds) ¶
prevLogIdx := 6 follower, _, _ := setupAppendEntriesTestWithSplice(prevLogIdx) ae := AppendEntriesStruct{ Term: 5, LeaderID: 2, PrevLogIndex: LogIndex(prevLogIdx), // follower has this position PrevLogTerm: 1, // matches follower's term at that position Entries: make([]LogEntry, 0), LeaderCommit: 8} response := RPCResponse{} follower.AppendEntries(ae, &response) fmt.Println(response.Success)
Output: true
func (*RaftNode) CandidateLooksEligible ¶
CandidateLooksEligible allows a raft node to decide whether another host's log is sufficiently up-to-date to become leader Returns true if the incoming RequestVote shows that the peer is at least as up-to-date as we are See paper section 5.4
Example (BadLogIdxFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 0) // voter's currentLeader candidateLastLogTerm := Term(4) candidateLastLogIdx := LogIndex(2) result := voter.CandidateLooksEligible(candidateLastLogIdx, candidateLastLogTerm) fmt.Println(result)
Output: false
Example (BadLogTermFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 0) // voter's currentLeader candidateLastLogTerm := Term(1) candidateLastLogIdx := LogIndex(9) result := voter.CandidateLooksEligible(candidateLastLogIdx, candidateLastLogTerm) fmt.Println(result)
Output: false
Example (FutureLogIdxSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 0) // voter's currentLeader candidateLastLogTerm := Term(4) candidateLastLogIdx := LogIndex(8) result := voter.CandidateLooksEligible(candidateLastLogIdx, candidateLastLogTerm) fmt.Println(result)
Output: true
Example (FutureLogTermSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 0) // voter's currentLeader candidateLastLogTerm := Term(8) candidateLastLogIdx := LogIndex(1) result := voter.CandidateLooksEligible(candidateLastLogIdx, candidateLastLogTerm) fmt.Println(result)
Output: true
Example (SameLogTermLogIdxSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 0) // voter's currentLeader candidateLastLogTerm := Term(4) candidateLastLogIdx := LogIndex(3) result := voter.CandidateLooksEligible(candidateLastLogIdx, candidateLastLogTerm) fmt.Println(result)
Output: true
func (*RaftNode) Start ¶
func (r *RaftNode) Start()
Start is the entrypoint for a raft node (constructed here or in a test) to begin the protocol
func (*RaftNode) StoreClientData ¶
func (r *RaftNode) StoreClientData(cd ClientDataStruct, response *ClientResponse) error
StoreClientData allows a client to send data to the raft cluster via RPC for storage We fill the reply struct with "success = true" if we are leader and store the data successfully. If we are not leader, we will reply with the id of another node, and the client must detect this and retry at that node. If we do not know or do not yet have a leader, we will reply with leader = -1 and client may choose to retry at us or another random node. TODO - need a version of StoreClientData that ensures some form of commitment after leader responds to a message?
func (*RaftNode) Vote ¶
func (r *RaftNode) Vote(rv RequestVoteStruct, response *RPCResponse) error
Vote is called by RPC from a candidate. We can observe the following from the raft.github.io simulation:
- If we get a requestVoteRPC from a future term, we immediately jump to that term and send our vote
- If we are already collecting votes for the next election, and simultaneously get a request from another node to vote for them, we do NOT give them our vote (we've already voted for ourselves!)
- if we've been offline, and wakeup and try to get votes: we get rejections, that also tell us the new term, and we immediately jump to that term as a follower
Example (BadLogIdxFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 4, LastLogIdx: 2, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=false, reply.Term=5
Example (BadLogTermFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 3, LastLogIdx: 3, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=false, reply.Term=5
Example (FutureLogIdxNewLeaderSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 8, LastLogIdx: 4, CandidateID: 1} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (FutureLogIdxSameLeaderSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 8, LastLogIdx: 4, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (FutureLogTermNewLeaderSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 8, LastLogIdx: 3, CandidateID: 1} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (FutureLogTermSameLeaderSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 6, LastLogTerm: 8, LastLogIdx: 3, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (FutureTermSucceedsNewLeader) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 8, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 1} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (FutureTermSucceedsSameLeader) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 8, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
Example (PrevTermNewLeaderFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 4, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 1} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=false, reply.Term=5
Example (PrevTermSameLeaderFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 4, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=false, reply.Term=5
Example (SameTermNewLeaderFails) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 5, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 1} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=false, reply.Term=5
Example (SameTermSameLeaderSucceeds) ¶
// Mock voter voter := mockRaftNode( Term(5), // voter's Term Term(4), // voter's lastLogTerm 3, // voter's lastLogIndex 2) // voter's currentLeader // Prepare inputs for the RPC args := RequestVoteStruct{ Term: 5, LastLogTerm: 4, LastLogIdx: 3, CandidateID: 2} reply := RPCResponse{} voter.commonVote(args, &reply) fmt.Printf("reply.Success=%t, reply.Term=%d", reply.Success, reply.Term)
Output: reply.Success=true, reply.Term=5
type RequestVoteStruct ¶
RequestVoteStruct holds the parameters used during the Vote() RPC
func (RequestVoteStruct) String ¶
func (rv RequestVoteStruct) String() string
type StateMachine ¶
type StateMachine struct { ClientSerialNums map[ClientID]ClientSerialNum // The most recently executed serial number for each client Contents []ClientData }
StateMachine is the core data structure whose updates we want to be resilient
func NewStateMachine ¶
func NewStateMachine() StateMachine
NewStateMachine constructs an empty StateMachine
func (StateMachine) String ¶
func (s StateMachine) String() string