Ceph剖析：Leader选举

作者：吴香伟 发表于 2014/09/11
版权声明：可以任意转载，转载时务必以超链接形式标明文章原始出处和作者信息以及版权声明

Paxos算法存在活锁问题。从节点中选出Leader，然后将所有对数据的修改都通过Leader作为提案提出，可以让算法快速收敛。Leader的选举规则是，由当前活动的Monitor节点中rank值最小的节点当选。选举不仅会产生Leader还将确定Quorum成员，Quorum成员就是那些支持新Leader节点当选Leader的节点。因此，虽然不能保证Leader的rank值是所有节点中最小的，但是可以保证它的值在Quorum中是最小的。Quorum是Monitor中的多数派，也就是说它的成员数目必须大于N/2+1，N为Monitor节点数目。

Leader选举过程大致可以分成以下3个步骤：首先，Proposer提出提案，发送propose消息给所有的Monitor节点。其次，Monitor节点(Acceptor)接收到proposer消息，如果接受提案则回复ack消息。最后，Proposer统计接收到的ack消息，向其它节点发送victory消息宣布赢得Leader选举并同步数据。

提出propose消息

在选举Leader过程中，epoch担当非常重要的角色。它有以下几个方面的作用：

1) 代表逻辑时间。正常情况下，Quorum中各个节点的epoch值应该是相等的。当节点离线后，它的epoch值被保存在数据库中，重新上线后它的epoch值比其它节点的小。在处理propose消息时，Acceptor节点根据epoch值来判断消息是不是最新的。
2) 用于判断当前节点是否处于Leader选举状态。当epoch为奇数时，说明节点处于选举状态；选举结束后，epoch值会递增为偶数并同步到所有的Quorum成员。

Proposer提出选举提案前，先从数据库中读取epoch值，并将其递增到奇数。

处理propose消息

Acceptor处理propose消息时，主要考虑epoch(代表时间)和rank两个因素：首先，判断propose消息是否是由于网络延迟导致的旧提案，若是则拒绝提案；其次，判断proposer的rank值是否是它知道的rank中最小的，若是则接受并且承诺不接受rank值比提案的rank值更大的提案。

处理ack消息

Ack消息对应Paxos的Accept消息。

Ack消息有两个作用：一种情况是通知Proposer它的提案被发送ack消息的Acceptor接受了；另一种情况是，Acceptor已经接受了提案(因为它的rank值小于Acceptor)，但是存在提案号更高的提案，Proposer应该放弃当前的提案，使用更高的提案号重新提出提案。

例子

假设原来已经存在两个节点A和B，现在加入新节点C，并且节点C的rank值是三者中最小的。节点C加入时，将引发选举：

1) 节点C向其余两个节点发送propose消息，将自己设置为Leader。由于节点C是新加入的，所以它的epoch值从0开始递增；
2) 节点A、B接受到消息后，发现节点C的epoch值比较旧。但由于节点C不在Quorum中，说明这个提案不是由于网络延迟导致的旧提案。并且节点C的rank值比自己小，所以接受提案并提醒对方更新epoch值。
3) 节点C接收到节点A和B的ack消息，发现自己的epoch值比它们都小，所以用它们的epoch更新自己，并重新发送propose消息，提出提案。
4) 节点A、B接受到新propose消息，发现节点C的epoch值比自己的新，于是更新自己的epoch值（持久化到磁盘）。另外，节点C的rank值也比自己的小，所以接受提案。
5) 节点C接收到节点A和B对新提案的Ack消息，赢得选举。
6) 节点C向其余节点发送victory消息，更新Quorum以及Leaders角色。

如果新加入节点的rank值的不是最小的，那么当它的proposer消息发送到rank值比自己更小的节点时，会引发节点提出提案参加候选。这种情况下，新节点虽然不会赢得选举，但是能够让自己加入到Quorum多数派。

疑问：多Leader情况

假设有A到E共5个节点，它们的rank值是依次递增的。另外，A和B之间相互不通。当5个节点的epoch都相同，节点A和B同时提出提案（此时提案的epoch也相同）。

-----------------------
     A   B   C  D  E  
A    +   -   +  +  +
B    -   +   +  +  +
-----------------------

如果B的propose先达到C、D和E节点，那么这三个节点都会接受B节点的提案。这样，节点B就获得了多数派的支持，选举超时后它将赢得选举。当节点A的propose消息到达C、D和E节点时，由于A节点的rank值要比它们已经接受的B节点的rank值小，所以这三个节点将接受A节点的提案。

这样，节点A和节点B都认为赢得了选举，都将自己初始化为Leader，都可以接受来自客户端对Cluster map的修改。

这种情况下，如果节点A的propose消息早于B节点的消息到达C、D、E中两个或两个以上的节点时，B节点将不能赢得选举。因为Acceptor承诺不接受rank值更大的提案，B节点后达到时将被拒绝。

其它

变量说明

start_stamp: 提出提案的时间戳 acked_me: 回复ack消息的节点集合 electing_me: “选我”，标记自己为候选人 leader_acked: 接受的提案的内容，没接受提案时该值默认为-1；

接口说明

1、选举的入口函数为Monitor::start_election()，进入该函数时将Monitor的状态更改为STATE_ELECTING。Elector::start()为private方法，必须经过Elector::call_election()方法调用;
2、选举成功后进入Monitor::win_election()函数将Monitor状态修改为STATE_LEADER，选举失败的节点进入Monitor::lose_election()函数将Monitor的状态修改为STATE_PEON;

参考资料

1、ceph work flow
2、