Paxos与Raft的简明比较

abun 2019-06-27

基本术语和操作对应

Paxos术语/操作Raft术语/操作备注
Proposal Number (PN)TermPaxos建议每个 Proposer 可用的 PN 集合不相交(disjoint sets); Raft 允许各个 Follower 竞选 Leader 时用相同的Term,Voter结合Term和VotedFor,区分到底支持了谁。
Value is Chosen (值被选定/形成决议)Commit下面有解释,二者独立性不同
实例(Paxos Instance)Log Entry一系列ID递增的Instance对应一系列Log Entry
Phase 2AppendEntryAppendEntry是对前面一个Entry有依赖的

主要过程比较

比较项基于Paxos的RSMRaft State Machine
一个实例形成决议的必要条件接受该提议 Acceptor 形成多数派;1) 直接 Commit: Term 等于currentTer m的log entry,形成多数派; 2) 间接Commit: 在新 Leader 当选后,对于非当前 Term 的Entry,形成多数派不代表表示已经 Commit。而是通过一个直接 commit,让更早的 entry 被间接 commit (一次性Commit了 commitIndex 及之前所有的 entry)。
各个实例的决议过程,是否独立?独立,无顺序关系有顺序依赖关系: 1) Accept 时的前向依赖:Follower 接受 entry 时,需要按照 PrevLogIndex 和 PrevLogTerm 匹配。2) Commit 时的后向依赖:leader 当选后,直到有 currentTerm 的 log 被 commit,才会让其当选前未 commit 的 entry 变为committed。
Leader 选举1)必须有过半的 Voter 接受其PN(Term);2)竞选 Leader 时,PN 大的当选; 3)每个提议者可使用的 PN 集合不相交。1) 必须有过半的 Voter 接受其 PN(Term);2) 竞选 Leader 时,PN/Term 大的当选; 3) 允许不同的 Proposer 在竞选 Leader 时用相同的 Term; 4) Leader 的 log 不能比其他 Voter的log旧(通过比较 Term 和 Log 长度);
Leader 当选后如何处理当选之前尚未形成决议的实例?使用自己的新 PN,对所有未形成决议的实例执行phase 1( Follower 不需要对每个实例都回复,只需要将那些已经执行到 Phase 2的实例的 Value 返回即可)。然后使用最大的 value 或者 no-op 进行 phase 2,以尽快解决空洞问题。Leader 采用推送的方式,将自己已经持久化的 log 推送出去。推送的 log 的 term 不变。只有自己当选后发起的 AppendEntry,才会用新Term。
Leader刚当选后执行的Phase 1Leader选举过程中的log新旧比较更换Leader都需要代价的,但是付出代价的时机有差异。
无 Leader 如何运行?仍然能保证单个实例的 Consensus没法进行读写
持久化的值MaxAccepted PN、各个 LogEntrycurrentTerm、 VotedFor(与 currentTerm对应)、 各个Log Entry

相关推荐