一.State
①Persistent state on all server(所有server的持久化的狀態(tài)):(Updated on stable storage before responding to RPCs)
currentTerm:自己已知的最新Term,初始化時是0,單調(diào)增加
votedFor:在currentTerm內(nèi),票投給了哪個candidateId
log[]:log entries;每一個entry 包含了針對狀態(tài)機的命令,還有這個entry是在哪個term的leader接到的.
②Volatile State on all server
commitIndex:已知的最后一個commited entry index(基0,單調(diào)遞增)
lastApplied:本server最后一個已經(jīng)applied到狀態(tài)機的entry index(基0,單調(diào)遞增)
③Volatile State on leader:在選舉后重新初始化
nextIndex[]:針對每個server的下一個待發(fā)送的entry index
matchIndex[]:已經(jīng)和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.追加沒有出現(xiàn)在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時,發(fā)起投票
-增加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.當選時:發(fā)送初始化空的AppendEntries RPCs(heartbeat) 給每一個server;在空閑期間一直重復,以阻止election timer timeout
2.如果收到client的命令:追加entry到本地的log,在entry被應用到狀態(tài)機后回復.
3.If last log index ≥ nextIndex for a follower:從nextIndex開始發(fā)送帶著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).? 此條規(guī)則說明commitIndex如何根據(jù)matchIndex得到.
