Paxos可容错的一致性协议

时间：2022-09-27 20:03:51

一致性问题要求多个process对一个值达成一致。基于消息传递的分布式系统中，在不考虑消息篡改等拜占庭错误的情况下，Paxos可以解决在进程退出，消息延迟，丢失，重复等异常发生的环境中对某个值达成一致的问题。

考虑Paxos最基本的形式：

两个角色：Proposer和Acceptor，Proposer提出Value(决议值)，Acceptor处理是否Accept Value

两个阶段：Prepare和Propose，第一阶段Prepare用于确认第二阶段的Value，第二个阶段Proposer请求Acceptor Accept Value

每个参与Paxos协议的server可以同时担任两个角色。当一个Value被majority的server Accept，则这个Value达成一致。

Acceptor的状态：MaxAcceptRoundNumber，Accept的最大的轮次号，MaxPrepareRoundNumber，Promise(回复PrepareReq OK)的最大的轮次号

RoundNumber全局唯一。轮和轮之间是并行的。每一轮都有一个coordinator，即发送proposal的server。

算法

Prepare阶段：

Proposer给所有Acceptor发送PrepareReq(RoundNumber)请求，

如果Acceptor的max(MaxAcceptRoundNumber, MaxPrepareRoundNumber)大于RoundNumber，则拒绝PrepareReq(RoundNumber)。Proposer接收到拒绝请求，直接选择一个新的round number，进入下一轮的Prepare阶段。

如果Acceptor的max(MaxAcceptRoundNumber, MaxPrepareRoundNumber)小于RoundNumber，则Promise该PrepareReq(RoundNumber)，更新本地的MaxPrepareRoundNumber为RoundNumber，并且发送PrepareRes(MaxAcceptRoundNumber,Value)给Proposer。

Accept阶段：

Proposer接收到了majority的Acceptor的PrepareRes(MaxAcceptRoundNumber,Value)后，从所有接收到的PrepareRes中选出最大的MaxAcceptRoundNumber对应的Value，然后发送AcceptReq(RoundNumber,Value)给所有的Acceptor。Accept接收到AcceptReq (RoundNumber,Value)后，如果max(MaxAcceptRoundNumber, MaxPrepareRoundNumber) 大于RoundNumber，则拒绝AcceptReq(RoundNumber,Value)，否则更新本地的MaxAcceptRoundNumber为RoundNumber，并且Accept AcceptReq(RoundNumber,Value)。如果Proposer接收到majority的Acceptor回复没有Accept过任何AcceptReq，则Proposer任意选择一个Value，并且给所有的Acceptor发送AcceptReq(RoundNumber,Value)。收到majority的AcceptRes后，给所有的Acceptor发commit消息。

算法的正确性的证明关键在于证明：

如果有AcceptReq(m,Vm) 第一次被majority的Acceptor Accept，则对于AcceptReq(j, Vj)，j > m -> Vj=Vm

证明

数学归纳法：

  1. 对于j = m, 显然Vj=Vm
  2. 假设j = k, k > m，有Vk = Vm，即第[m,k]轮AcceptReq(j, Vj) 都有Vj=Vm 。只需要证明j = k+1,有Vk+1=Vm

i用来索引Acceptor

显然第k+1轮能够发出AcceptReq(k+1,Vk+1)，说明第k+1轮成功的收到了majority的PrepareRes(Xi, Vxi)，由于Prepare阶段的限制，显然xi < k+1,即xi <= k，从而max(Xi) <= k。由于Accept阶段的限制，只能Accept比本地已经Accept的Req更大的，由于m已经被majority Accept了，故至少有一个PrepareRes(Xi,Vxi)中的Xi >= m, 从而max(Xi) >=m

综上所述有,对于第k+1轮来说，有 m <= max(Xi)<= k，又由于h ∈[m,k]轮的所有的AcceptReq(h,Vh)都有Vh=m(数学归纳法的假设)，即第h轮收集到的PrepareRes中最大的AcceptRoundNumber对应的value(即 Vh)是m，故AcceptReq(k+1, Vk+1)的Vk+1=Vm ,得证。

参考文献

Paxos made simple

Fast Paxos

相关文章