raft

Documentation

Index

• Constants
• func DPrintf(format string, a ...interface{}) (n int, err error)
• func StateToString(state State) string
• type AppendEntriesArgs
• type AppendEntriesReply
• type ApplyMsg
• type InstallSnapshotArgs
• type InstallSnapshotReply
• type LogEntry
• type Persister
  • func MakePersister() *Persister
  • func MakePersisterWithFile(me int) *Persister
  • func (ps *Persister) Close()
  • func (ps *Persister) Copy() *Persister
  • func (ps *Persister) RaftStateSize() int
  • func (ps *Persister) ReadRaftState() []byte
  • func (ps *Persister) ReadSnapshot() []byte
  • func (ps *Persister) SaveRaftState(state []byte)
  • func (ps *Persister) SaveStateAndSnapshot(state []byte, snapshot []byte)
  • func (ps *Persister) SnapshotSize() int
• type Raft
  • func Make(peers []*labrpc.ClientEnd, me int, persister *Persister, applyCh chan ApplyMsg) *Raft
  • func (rf *Raft) GetState() (int, bool)
  • func (rf *Raft) Kill()
  • func (rf *Raft) RPC_CALLEE_AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply)
  • func (rf *Raft) RPC_CALLEE_InstallSnapshot(args *InstallSnapshotArgs, reply *InstallSnapshotReply)
  • func (rf *Raft) RPC_CALLEE_RequestVote(args *RequestVoteArgs, reply *RequestVoteReply)
  • func (rf *Raft) RPC_CALLER_AppendEntriesToPeer(peerIdx int, args *AppendEntriesArgs, reply *AppendEntriesReply) bool
  • func (rf *Raft) RPC_CALLER_InstallSnapshot(peerIdx int, args *InstallSnapshotArgs, reply *InstallSnapshotReply) bool
  • func (rf *Raft) RPC_CALLER_SendRequestVote(peerIdx int, args *RequestVoteArgs, reply *RequestVoteReply) bool
  • func (rf *Raft) SavePersistAndSnapshot(index int, snapshot []byte)
  • func (rf *Raft) Start(command interface{}) (int, int, bool)
• type RequestVoteArgs
• type RequestVoteReply
• type State

Constants

const (
	//1. ElectionTimeout is chose randomly in [ElectionTimeoutMin, ElectionTimeoutMax)
	//2. Min should be not smaller than 2 * HeartBeatTimeout
	//3. (Max - Min)/2 should be enough for collecting votes
	//4. Max should not be too big, otherwise it may cause too long time to elect a new leader
	ElectionTimeoutMin = time.Millisecond * 300 // election(both election-check interval and election timeout), min
	ElectionTimeoutMax = time.Millisecond * 600 // election(both election-check interval and election timeout), max

	HeartBeatTimeout = time.Millisecond * 150 // leader heartbeat

	ApplyTimeout = time.Millisecond * 100 // apply log

	// RPCSingleTimeout: may cause too long time to wait for a single RPC response if too big
	// RPCSingleTimeout: may canuse too many RPC Calls if too small
	RPCSingleTimeout = time.Millisecond * 100
	// RPCBatchTimeout: may ignore all RPC with long latency if too small
	// RPCBatchTimeout: may cause more RPC Calls and too long time to wait for a batch RPC response(in a RPC Caller) if too big,
	// which can be replaced by retry in the new RPC Caller of a new HeartBeat
	RPCBatchTimeout = time.Millisecond * 3000
	RPCInterval     = time.Millisecond * 20 // RPCInterval: may cause busy loop for RPC retry if too small

	HitTinyInterval = time.Millisecond * 5 // hit timer will reset it by this value

	InvalidTerm    = -1
	InvalidVoteFor = -1
)

const Debug = 0

Debugging

Functions

func DPrintf

func DPrintf(format string, a ...interface{}) (n int, err error)

func StateToString

func StateToString(state State) string

Types

type AppendEntriesArgs

type AppendEntriesArgs struct {
	Term         int
	LeaderId     int
	PrevLogIndex int // index of log entry immediately preceding new ones
	PrevLogTerm  int // term of prevLogIndex entry
	Entries      []LogEntry
	LeaderCommit int // leader's commitIndex
}

type AppendEntriesReply

type AppendEntriesReply struct {
	Term    int
	Success bool
}

type ApplyMsg

type ApplyMsg struct {
	CommandValid bool
	Command      interface{}
	CommandIndex int
}

as each Raft peer becomes aware that successive log entries are committed, the peer should send an ApplyMsg to the service (or tester) on the same server, via the applyCh passed to Make(). set CommandValid to true to indicate that the ApplyMsg contains a newly committed log entry.

in Lab 3 you'll want to send other kinds of messages (e.g., snapshots) on the applyCh; at that point you can add fields to ApplyMsg, but set CommandValid to false for these other uses.

type InstallSnapshotArgs

type InstallSnapshotArgs struct {
	Term              int
	LeaderId          int    //so follower can redirect clients
	LastIncludedIndex int    //the snapshot replaces all entries up through and including this index
	LastIncludedTerm  int    //term of lastIncludedIndex
	Data              []byte //raw bytes of the snapshot chunk, starting at offset

	//chunk related
	Offset int  //byte offset where chunk is positioned in the snapshot file, not used yet
	Done   bool //true if this is the last chunk, not used yet
}

type InstallSnapshotReply

type InstallSnapshotReply struct {
	Term int //currentTerm, for leader to update itself
}

type LogEntry

type LogEntry struct {
	Term    int
	Command interface{}
}

type Persister

type Persister struct {
	// contains filtered or unexported fields
}

func MakePersister

func MakePersister() *Persister

func MakePersisterWithFile

func MakePersisterWithFile(me int) *Persister

func (*Persister) Close

func (ps *Persister) Close()

func (*Persister) Copy

func (ps *Persister) Copy() *Persister

func (*Persister) RaftStateSize

func (ps *Persister) RaftStateSize() int

func (*Persister) ReadRaftState

func (ps *Persister) ReadRaftState() []byte

func (*Persister) ReadSnapshot

func (ps *Persister) ReadSnapshot() []byte

func (*Persister) SaveRaftState

func (ps *Persister) SaveRaftState(state []byte)

func (*Persister) SaveStateAndSnapshot

func (ps *Persister) SaveStateAndSnapshot(state []byte, snapshot []byte)

Save both Raft state and K/V snapshot as a single atomic action, to help avoid them getting out of sync.

func (*Persister) SnapshotSize

func (ps *Persister) SnapshotSize() int

type Raft

type Raft struct {
	// contains filtered or unexported fields
}

A Go object implementing a single Raft peer.

func Make

func Make(peers []*labrpc.ClientEnd, me int,
	persister *Persister, applyCh chan ApplyMsg) *Raft

the service or tester wants to create a Raft server. the ports of all the Raft servers (including this one) are in peers[]. this server's port is peers[me]. all the servers' peers[] arrays have the same order. persister is a place for this server to save its persistent state, and also initially holds the most recent saved state, if any. applyCh is a channel on which the tester or service expects Raft to send ApplyMsg messages. Make() must return quickly, so it should start goroutines for any long-running work.

func (*Raft) GetState

func (rf *Raft) GetState() (int, bool)

return currentTerm and whether this server believes it is the leader.

func (*Raft) Kill

func (rf *Raft) Kill()

the tester doesn't halt goroutines created by Raft after each test, but it does call the Kill() method. your code can use killed() to check whether Kill() has been called. the use of atomic avoids the need for a lock.

the issue is that long-running goroutines use memory and may chew up CPU time, perhaps causing later tests to fail and generating confusing debug output. any goroutine with a long-running loop should call killed() to check whether it should stop.

func (*Raft) RPC_CALLEE_AppendEntries

func (rf *Raft) RPC_CALLEE_AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply)

func (*Raft) RPC_CALLEE_InstallSnapshot

func (rf *Raft) RPC_CALLEE_InstallSnapshot(args *InstallSnapshotArgs, reply *InstallSnapshotReply)

func (*Raft) RPC_CALLEE_RequestVote

func (rf *Raft) RPC_CALLEE_RequestVote(args *RequestVoteArgs, reply *RequestVoteReply)

example RequestVote RPC handler.

func (*Raft) RPC_CALLER_AppendEntriesToPeer

func (rf *Raft) RPC_CALLER_AppendEntriesToPeer(peerIdx int, args *AppendEntriesArgs, reply *AppendEntriesReply) bool

func (*Raft) RPC_CALLER_InstallSnapshot

func (rf *Raft) RPC_CALLER_InstallSnapshot(peerIdx int, args *InstallSnapshotArgs, reply *InstallSnapshotReply) bool

func (*Raft) RPC_CALLER_SendRequestVote

func (rf *Raft) RPC_CALLER_SendRequestVote(peerIdx int, args *RequestVoteArgs, reply *RequestVoteReply) bool

example code to send a RequestVote RPC to a server. server is the index of the target server in rf.peers[]. expects RPC arguments in args. fills in *reply with RPC reply, so caller should pass &reply. the types of the args and reply passed to Call() must be the same as the types of the arguments declared in the handler function (including whether they are pointers).

The labrpc package simulates a lossy network, in which servers may be unreachable, and in which requests and replies may be lost. Call() sends a request and waits for a reply. If a reply arrives within a timeout interval, Call() returns true; otherwise Call() returns false. Thus Call() may not return for a while. A false return can be caused by a dead server, a live server that can't be reached, a lost request, or a lost reply.

Call() is guaranteed to return (perhaps after a delay) *except* if the handler function on the server side does not return. Thus there is no need to implement your own timeouts around Call().

look at the comments in ../labrpc/labrpc.go for more details.

if you're having trouble getting RPC to work, check that you've capitalized all field names in structs passed over RPC, and that the caller passes the address of the reply struct with &, not the struct itself.

func (*Raft) SavePersistAndSnapshot

func (rf *Raft) SavePersistAndSnapshot(index int, snapshot []byte)

this function may be called directly by the server

func (*Raft) Start

func (rf *Raft) Start(command interface{}) (int, int, bool)

the service using Raft (e.g. a k/v server) wants to start agreement on the next command to be appended to Raft's log. if this server isn't the leader, returns false. otherwise start the agreement and return immediately. there is no guarantee that this command will ever be committed to the Raft log, since the leader may fail or lose an election. even if the Raft instance has been killed, this function should return gracefully.

the first return value is the index that the command will appear at if it's ever committed. the second return value is the current term. the third return value is true if this server believes it is the leader.

type RequestVoteArgs

type RequestVoteArgs struct {
	// Your data here (2A, 2B).
	Term         int
	CandidateId  int
	LastLogIndex int //index of candidate's last log entry
	LastLogTerm  int //term of candidate's last log entry
}

example RequestVote RPC arguments structure. field names must start with capital letters!

type RequestVoteReply

type RequestVoteReply struct {
	// Your data here (2A).
	Term        int
	VoteGranted bool
}

example RequestVote RPC reply structure. field names must start with capital letters!

type State

type State int

const (
	Follower  State = 0
	Candidate State = 1
	Leader    State = 2
)