Ceph剖析：Leader选举

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担当非常重要的角色。它有以下几个方面的作用：

代表逻辑时间。正常情况下，Quorum中各个节点的epoch值应该是相等的。当节点离线后，它的epoch值被保存在数据库中，重新上线后它的epoch值比其它节点的小。在处理propose消息时，Acceptor节点根据epoch值来判断消息是不是最新的。

用于判断当前节点是否处于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加入时，将引发选举：

节点C向其余两个节点发送propose消息，将自己设置为Leader。由于节点C是新加入的，所以它的epoch值从0开始递增；

节点A、B接受到消息后，发现节点C的epoch值比较旧。但由于节点C不在Quorum中，说明这个提案不是由于网络延迟导致的旧提案。

并且节点C的rank值比自己小，所以接受提案并提醒对方更新epoch值。

节点C接收到节点A和B的ack消息，发现自己的epoch值比它们都小，所以用它们的epoch更新自己，并重新发送propose消息，提出提案。

节点A、B接受到新propose消息，发现节点C的epoch值比自己的新，于是更新自己的epoch值（持久化到磁盘）。另外，节点C的rank值也比自己的小，所以接受提案。

节点C接收到节点A和B对新提案的Ack消息，赢得选举。

节点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;

※部分文章来源于网络，如有侵权请联系删除；更多文章和资料|点击后方文字直达 ↓↓↓ 100GPython自学资料包 阿里云K8s实战手册 [阿里云CDN排坑指南]CDN ECS运维指南 DevOps实践手册 Hadoop大数据实战手册 Knative云原生应用开发指南 OSS 运维实战手册 云原生架构白皮书 Zabbix企业级分布式监控系统源码文档 10G大厂面试题戳领