继续上一篇文末提到的paxos，这一篇谈谈如何通过选主来解决paxos的活性问题。

问题

basic paxos存在一个活性（liveness）问题，如图： 首先注意每个proposer都只需要给超过半数的acceptor发起请求并取得一致即可，这里的例子共有5个server，所以这个数是3。

  • 首先Server1 发起epoch值为3的prepare请求（P 3.1）到server1，server2和server3并均获取到访问权
  • 在Server1继续发起accept请求（A 3.1 X）试图将取值设置为X之前，Server 5 发起epoch值为5的prepare请求（P 3.5）到serve3，server4和server5并抢占到了访问权
  • Server1 发起epoch值为3的accept请求，S1，S2均返回OK，但是S3由于被Server 5发来的（P 3.5）抢占了访问权，返回fail，由于只收到2个OK（不超过半数），所以并未取得确定性取值
  • 依次类推，每个accept请求到达之前都被更新的epoch抢占了访问权，就会导致集群陷入活锁，无法获得一个确定性取值。

绕过

有一个简单的方法来绕过这个问题：在每次使用更大的epoch值重新发起prepare请求之前随机等待一小段时间，使得其他proposer有机会完成accept过程。

不过这个方法只能一定程度缓解问题，没有从根本上解决问题。

Lamport建议通过选主的方式选定一个leader承担proposer的角色，集群中的其他server承担acceptor的角色，从而避免由于多个proposer抢夺访问权出现的活锁问题。

选主

假定每个server都拥有一个唯一的ID，如上图中的 S1，S2 等等，所以可以采用以下简单的策略：使得拥有最大ID值的server成为leader。 具体步骤：

  • 每台server每隔时间间隔T给其他所有server发送心跳，心跳中携带自己的ID
  • 如果某台server在2T时间内（考虑网络时延）没有接收到高于自己ID的server发来的心跳，则自己充当leader角色
  • 负责接收client传来的请求
  • 承担proposer和acceptor
  • 如果某台server认识到自己不是leader
  • 将client传来的请求转发给leader
  • 承担acceptor

这是一个简单而且有效的选主策略，但是我们不得不考虑一下分布式中的经典情况：脑裂。 因为网络分区的关系，同时可能有多个自认为的leader存在，是不是又有可能出现活锁？

答案是不会。

如果某几个proposer由于出现活锁导致client请求超时，client会寻求其他server，重新进行一次选主，而acceptor抢占式访问的设计不会受到先前的prepare请求影响，重新洗牌后重新陷入活锁的概率就大大降低了。 这个方法也被称为PaxosLease或者lease相关的描述。

工程实践