朝花夕拾

Paxos

2019/09/24 Paxos 分布式协议 技术

2PC(两阶段提交)

2PC协议有两个阶段：Propose和Commit

无faliure情况下

image-20190909183040036

如果有一个voter在propose投了反对票，则通过失败，coordinator会在告诉所有voter放弃这个propose

image-20190909200954861

缺陷

在commit阶段，如果coordinator和voter3都失联了，那么其他voter无法判断现在处于两种场景中的哪一种：

  1. 上轮全票通过然后voter3第一个收到commit的消息然后commit后crash了
  2. voter3反对所以干脆没通过。

image-20190909205531501

2PC 无法处理这种情况的原因是voter收到propose后，直接就commit，而没有在commit前通知其他节点已经收到propose的结果（commit or not），从而导致在coordinator和voter都掉线的情况下，无法知道当前是应该commit还是abort。为了解决这个问题，3PC了解一下。

3PC（三阶段提交）

介绍

​ 简单来说，3PC就是把2PC的commit阶段拆分为了PreCommit和Commit阶段。通过新增的PreCommit阶段，voter可以知道上一阶段Propose的结果，但不会commit，而进入commit阶段，voter就可以知道其他voter都要commit，所以就能安心commit了。

​ 相当于加了一个barrier，在这个barrier之前（PreCommit之前），如果coordinator挂掉，则大家都知道不需要commit，会放弃掉当前的propose然后重新选一个coordinator出来；如果在barrier之后（PreCommit之后）coordinator挂掉，voter知道这是需要commit的，所以也就能安心commit。

image-20190909211636589

缺点

  1. 不能处理网络分区的情况。
    1. 假设在PreCommit阶段所有节点被一分为二 （图示为3个voter，实际上需要两边的voter相等时才会出现这种情况），收到preCommit 消息的voter在一边，而没有收到这个消息的在另一边，在这种情况下，两边就可能会选出新的coordinator而做出不同的决定
    2. image-20190924142101074
  2. 3PC也不能处理fail-recover 的错误情况。简单来说，当coordinator收到preCommit的确认前crash了，于是voter重新选举一个新的coordinator 出来，当源coordinator重启之后，会向所有voter发送abort，因为它没有收到全部的preCommit 回复，此时可能会出现原coordinator 和 继任 coordinator 发送相矛盾的指令，从而出现节点的状态分歧。

Paxos

简介

从整体上来说，Paxos 算法的目标就是要保证最终有一个提案会被选定，当提案被选定后，进程最终也能获取到被选定的提案。

Prepare 阶段

  1. leader节点给所有其他acceptor节点发送消息“proposal(n)”——n 是该节点为这个提议选择的一个数字，姑且理解为一个方案编号，并期待该提议获得所有节点中的简单多数（Paxos的Quorum）许可

  2. 每一个接收到proposal的acceptor节点：

    1. 如果这是它接收到的第一个proposal，回答“promise”.代表该节点许诺将会保持承认该proposal发送方为leader，除非收到其他优先级更高的proposal；

      如果已经有接收并accepted（注意：这是下一阶段可能会发生的动作）其他的proposal(n’,v’)——n’是该proposal的方案号而v’是提议的公式

      1. 如果n < n’ ，之前accept的提议有更高优先级，对新接受的提议回答“reject”，以兑现之前的许诺
      2. 如果n > n’，回答“promise”并同时附上旧的提议，proposal(n’,v’)。这样在认可新的leader身份的同时，也告诉了新的leader过去的被简单多数认可过的提议

    2. prepare结果（reject）：如果proposer的提议受到了简单多数的“reject”，竞争leader宣告失败，可以放弃这一提议。

    3. prepare结果（promise）：如果接收到了简单多数的“promise”，则该proposer成为leader，它需要从收到的promise里附带的之前accepted的提议中选取方案号（n值）最高的对应的共识；如果历史上没有被accept过的提议，leader可以自己选取一个共识v。

Accept 阶段

  1. leader会多所有acceptor发送“accept-request(n,v)”，请求acceptor接受编号为n的共识v的提议。
  2. 每一个接收到该提议的acceptor节点：如果没有接受过编号比n更高的提议，则返回“accept”标识接受这一共识提议，否则返回“reject”
  3. 如果简单多数的acceptor返回了“accept”，则共识达成；否则共识失败，重启paxos协议。

注意

  1. 第一阶段竞争的并不是共识本身，而是在争取坐实leader身份获得简单多数的认可（编号越高代表优先级越高，但是并不代表优先级高的一定能抢到leader）
  2. 方案编号n本身并不是共识，而是提议的一个优先级，在多个节点竞争leader身份时可以区分优先顺序。共识本身（v）会在下一阶段leader身份确认后由leader添加进提议。
  3. 虽然这一轮只会有一个leader获得简单多数的认可，但可能有多个“糊涂”节点认为自己应该做leader。

Paxos对2PC和3PC有几点重要的改进

  1. 分离共识的提议者proposer以及帮助提议最终通过的leader这两个角色
    1. 即使一个leader身份被批准，它也需要尊重历史上其他被统一过的提议
  2. 对简单多数的巧妙应用
    1. 第一阶段里选举leader要求的简单多数保证了选举出来的leader一定不会错过之前被accept过的提议——所以就算那个提议最初的proposer挂了，也会至少被一个acceptor发给新的leader来继承。
    2. 第二阶段里要求的达成共识的简单多数保证了有多个“自以为是”的leader出现时（比如一个leader掉线，新leader选出，旧leader重新上线），一定只会有一个最后通过。

Paxos与2PC/3PC 的关系

Paxos如何克服2PC的问题：

  1. 2PC中coordinator是唯一而固定的，如果coordinator宕机，那么就会有情形导致coordinator之前propose的提议的投票结果丢失。就算启动新的后背coordinator，没有机制可以学习以前的投票结果。
  2. Paxos因为分离了协议和leader，从算法上保证总可以选举出后备leader并接替前任leader的工作。

Paxos 如何克服3PC的问题：

  1. 3PC发生的问题在于当有多个“自认的leader”出现时，并不能有效解决coordinator之间的竞争——谁是真正的coordinator
  2. 而Paxos通过Quorum的运用，保证了多个leader之间可以互相发现。

Paxos的局限性

  1. 活锁问题

Paxos理论上存在一个不能终结协议的活锁竞争问题。比如一个proposer提交的提议因为编号过低被拒绝时，此proposer可能重启Paxos而提高编号重新提交。如果同时有两个proposer都发现自己的方案编号过低，从而轮流提出更高编号的proposal而导致对方被拒，可能会导致死循环（或活锁）

image-20190924183619683

image-20190924183635199

为了保证Paxos算法流程的可持续性，以避免陷入“死循环“，就必须选择一个主proposer，并规定只有主proposer才能提出提案。

  1. 恶意节点

目前为止2PC、3PC、Paxos均是假设所有节点都遵守协议的规定。当存在恶意的，可能发送任何导致协议停止或出错的消息的节点存在时，就需要有更强的共识算法在”守法节点“间达成共识。（拜占庭将军问题）

Search

    Table of Contents