分布式系统设计迷思(二)

继续上一篇文末提到的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相关的描述。

工程实践