一.State
①Persistent state on all server(所有server的持久化的状态):(Updated on stable storage before responding to RPCs)
currentTerm:自己已知的最新Term,初始化时是0,单调增加
votedFor:在currentTerm内,票投给了哪个candidateId
log[]:log entries;每一个entry 包含了针对状态机的命令,还有这个entry是在哪个term的leader接到的.
②Volatile State on all server
commitIndex:已知的最后一个commited entry index(基0,单调递增)
lastApplied:本server最后一个已经applied到状态机的entry index(基0,单调递增)
③Volatile State on leader:在选举后重新初始化
nextIndex[]:针对每个server的下一个待发送的entry index
matchIndex[]:已经和leader对齐的index
二.AppendEntries RPC:invoked by leader to replicated log entries;also used as heartbeat.
①Arguments:
term: leader's term
leaderId:so follower can redirect clients 所以follower可以重定向客户端
prevLogIndex:(index of previous log)index of log entry immediately preceding new ones 新entry的前一个index.
leaderCommit:leader's commitIndex
②Results:
term:currentTerm,用于让leader检查自己
success:当follower的匹配到了arguments里的prevLogIndex和term,为true
③Receiver implementation:
1.如果term < currentTerm 返回false(告诉leader,老铁你过期了) §5.1
2.如果term和prevLogTerm匹配,但是log中不包含prevLogIndex,返回false. §5.3
3.如果存在entryIndex,但是这条entry的term与AppendEntries RPC中的term冲突.则把这条冲突的entry和以后的全部删掉. §5.3
4.追加没有出现在log中的新entry
5.if leaderCommit > commiteIndex,set commitIndex =min(leaderCommit, index of last new entry)
三.RequestVote RPC :Invoked by candidates to gather votes (§5.2).
①Arguments:
term:candidate's term
candidateId:candidate requesting vote
lastLogIndex:index of candidate's last log entry. §5.4
lastLogTerm:term of candidate's last log entry. §5.4
②Results:
term:currentTerm, for candidate to update itself
voteGranted:true means candidate received vote
③Receiver implementation:
1.如果term < currentTerm 返回false §5.1
2.votedFor is null or candidateId, and candidate’s log is at least as up-to-date as receiver’s log, grant vote (§5.2, §5.4)
voteFor是null或者就是这个candidateId,并且lastLogIndex至少比接收者的log新,投票
四.Rules for Servers
①All Servers:
1.If commitIndex > lastApplied: increment lastApplied, apply log[lastApplied] to state machine (§5.3) 先增加lastApplied,然后apply
2.If RPC request or response contains term T > currentTerm:set currentTerm = T, convert to follower (§5.1)(只要有别人告诉你,你的term过期了,就更新term并变成follower)
②Followers(§5.2):
1.回复candidate和leader的RPC
2.如果没有收到任何leader的AppendEntries或者投票给某个candidate而选举超时,转变自己成为candidate.
③Candidates(§5.2):
1.在转变成Candidate时,发起投票
-增加currentTerm
-Vote for self
-Reset election timer
-Sent RequestVote RPC to all other servers
2.If votes recieved majority of servers:become leader.
3.如果收到新leader的AppendEntries RPC,convert to Follower
4.如果选举超时,重新再来一次选举
④Leaders
1.当选时:发送初始化空的AppendEntries RPCs(heartbeat) 给每一个server;在空闲期间一直重复,以阻止election timer timeout
2.如果收到client的命令:追加entry到本地的log,在entry被应用到状态机后回复.
3.If last log index ≥ nextIndex for a follower:从nextIndex开始发送带着log entries 的AppendEntries RPC.
-If successful: update nextIndex and matchIndex for follower (§5.3)
-If AppendEntries fails because of log inconsistency:decrement nextIndex and retry (§5.3) -- 上一任leader的entry还没提交,leader就挂了
-If there exists an N such that N > commitIndex, a majority of matchIndex[i] ≥ N, and log[N].term == currentTerm:set commitIndex = N (§5.3, §5.4). 此条规则说明commitIndex如何根据matchIndex得到.
