Page 193 - 《软件学报》2021年第6期

谷晓松 等:支持乱序执行的 Raft 协议 1767

LET j==m.msource
syncOK==/\m.msync\geq sync[i]
grant==/\syncOK
/\votedFor[i]\in {Nil,j}
/\currentTerm[i]=m.mterm
IN
/\m.mterm\leq currentTerm[i]
/\m.mtype=RequestVoteRequest
/\\/grant/\votedFor′=[votedFor EXCEPT ![i]=j]
\/\neg grant/\UNCHANGED votedFor
/\Send([mtype6RequestVoteResponse,
mterm6currentTerm[i],
mvoteGranted6grant,
mlog6LET C=={n\in Index:log[i][n].term=sync[i]}
IN {〈〈n,log[i][n]〉〉:n\in C},
mend6end[i][m.msync],
msource6i,
mdest6j])
/\UNCHANGED 〈〈currentTerm,currentState,sync,log,syncTrack,
electionVars,end〉〉
--------------------------------------------------------------------------------------------------------
• BecomeLeaderCandidate(i):若候选节点 i 从一个多数派(voteGranted)的节点收到同意选举的消息,i 转
变为主节点候选者.i 要恢复任期等于自己同步号(sync[i])的日志项,因此,i 首先确定能接受的任期为
sync[i]的日志项的最大编号,将它保存在 end[i][sync[i]]中.方法为:在收到的消息的 m.mend 中选择最新
的.之后对每个可接受的编号,i 在收到的对应编号的日志项中选择最新的,并写入日志.对每个节点 p,i
初始化 syncTrack[i][p]=sync[i].
-----------------------------------------------------------------------------------------------------------
Merge(entries,term,date)==
IF entries={⋅} THEN [term6term,
date6date,
value6Nil,
committed6FALSE]
ELSE
LET
committed=={e\in entries:e.committed=TRUE}
chosen==
CASE committed={⋅}→CHOOSE x\in entries:
\A y\in entries:x.date\geq y.date
[⋅] committed/={⋅}→CHOOSE x\in committed:TRUE
IN
[term6chosen.term,