raft

package
v0.0.0-...-67a7720 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 4, 2019 License: MIT Imports: 13 Imported by: 0

Documentation

Index

Examples

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 

func ResolveAllPeers(hosts HostMap, clients ClientMap, hostfile string, amHost bool) (int, int)

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 

func ResolvePeersOnce(hosts HostMap, clients ClientMap, h hostStringMap, c clientStringMap) bool

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 ClientID 

type ClientID int

ClientID is the integer ID of a client node

type ClientMap 

type ClientMap map[ClientID]Peer

ClientMap associates a raft client's ID with their net info

func (ClientMap) String 

func (m ClientMap) String() string

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 HostID 

type HostID int

HostID is the integer ID of a raft host node

type HostMap 

type HostMap map[HostID]Peer

HostMap associates a raft host's ID with their net info

func (HostMap) String 

func (m HostMap) String() string

type Log 

type Log []LogEntry

Log holds LogEntries and

func (Log) String 

func (l Log) String() string

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

func (LogEntry) String 

func (le LogEntry) String() string

type LogIndex 

type LogIndex int

LogIndex is a position in the log

type Peer 

type Peer struct {
	IP       net.IP
	Port     int
	Hostname string
}

Peer represents the network information for a RaftNode

func (Peer) String 

func (p Peer) String() string

type RPCResponse 

type RPCResponse struct {
	Term     Term
	Success  bool
	LeaderID HostID
}

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 

func (r *RaftNode) CandidateLooksEligible(candLastLogIdx LogIndex, candLastLogTerm Term) bool

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) QuitChan 

func (r *RaftNode) QuitChan() chan bool

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) String 

func (r *RaftNode) String() string

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:

  1. If we get a requestVoteRPC from a future term, we immediately jump to that term and send our vote
  2. 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!)
  3. 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 

type RequestVoteStruct struct {
	Term        Term
	CandidateID HostID
	LastLogIdx  LogIndex
	LastLogTerm Term
}

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

type Term 

type Term int

Term is a monotonically increasing integer identifying the current leader's term

func (Term) String 

func (t Term) String() string

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.