Elasticsearch选举原理之Bully算法

Elasticsearch采用了master-slave模式， ES会在集群中选取一个节点成为主节点，只有Master节点有资格维护全局的集群状态，在有节点加入或者退出集群的时候，它会重新分配分片，并将集群新状态发送给集群中其它节点，主节点会以周期性ping的方式以验证其它节点是否存活。Elasticsearch的选举算法基于Bully选举算法，简单的说，在bully算法中，每个节点都有一个编号，只有编号大的存活节点才能成为master节点。

1. 选举时间点

选举的时间点有两个

1. 某个新节点加入了集群或者某个节点从宕机中恢复
2. 集群中的某个节点检测到leader崩溃

2. 选举流程

选举的流程说明如下

1. 节点node向所有比自己大的节点发送选举消息(选举为election消息)
2. 如果节点node得不到任何回复(回复为alive消息)，那么节点node成为master，并向所有的其它节点宣布自己是master(宣布为Victory消息)
3. 如果node得到了任何回复，node节点就一定不是master，同时等待Victory消息，如果等待Victory超时那么重新发起选举

笔者借助网上的一组图片详细阐述Bully的选举流程，图片来自于

假设有如下6节点组成的集群，每个节点都会维护和其它节点的联系，p6节点是当前集群的master节点

3. Elasticsearch编号比较

Elasticsearch编号比较的判断依据有两个，首先是ClusterState版本号的比较，版本号越大优先级越高，然后是节点id的比较，id越小优先级越高。ClusterState是Master向集群中各个节点发送的集群状态，这个状态有一个版本号码，如果集群状态发生了变化，比如集群新增了节点成员或者有节点成员退出了，那么这个版本号就会加一，比对这个版本号的目的是让拥有新状态的节点成为Master的优先级高。

4. Bully算法缺陷

4.1 Master假死

Master节点承担的职责负载过重的情况下，可能无法即时对组内成员作出响应，这种便是假死。如果上图中的P6节点假死，于是P5节点成为了Master节点，但是在P6节点负载减轻之后，P6节点又对组内成员作出了响应，P6节点又会成为Master节点，如此反复，整个集群状态就会非常不可靠。

Elasticsearch是如何解决这个问题的呢？在Bully算法中，Master节点P6因为负载重，来不及对P3节点作出响应，所以P3节点通知P4,P5节点进行选举。在Elasticsearch中，P3节点发现Master P6对自己长时间不作出响应，P3节点会请求其它节点判断P6节点是否存活，如果有1/2以上节点都认定P6存活，那么P3就会放弃发起选举

4.2 脑裂问题

脑裂问题指的是一个集群中出现了两个及以上的Master节点。

比如上图中集群因为网络原因分成了两个部分，一个部分称为partition1包含P3,P5,P6节点，另一部分称为partition2包含P2,P1,P4节点，这两个partition因为网络原因比如路由器短时故障造成不能相互通信的问题。

那么网络分区一根据Bully算法选举出了P6作为master，而网络分区二选举出了P4作为master，这就是脑裂问题。

Elasticsearch脑裂解决方案

Quorum算法

脑裂问题是所有集群选举算法都要面对的一个问题，Elasticsearch集群机制采用了小参与节点的方案解决的。假设elasticsearch集群中有资格投票的实例个数是n，节点想要成为master必须要得到n/2 +1票数(在本示例中是4)。上图中的分区一P6和分区二中的P4，任何一个master节点所在的分区集群的候选节点数目都小于4，更不可能得到4个选票，所以整个Elasticsearch集群处于瘫痪状态

我们也可以强制指定elasticsearch节点在有M个候选节点的情况下能选举出一个主节点，但是如果配置数小于上文提到的 n/2 +1 那么会出现脑裂的情况，M的配置参数如下

discovery.zen.minimum_master_nodes