高可用集群中的选举机制
一个高可用的集群里，一般都会存在主节点的选举机制。这里以elasticsearch集群为例，介绍一下集群的节点选举方法。
如果查看Elasticsearch集群里的节点信息，你会发现里面有一个节点称为master节点，而且一个集群只有一个master节点。那么，什么是master节点呢? 为什么集群一定要有一个master节点？master什么时候产生，又是怎么产生的呢？
什么是master节点？
简单的说，master节点就是集群中的leader，或者管理者。master节点知道所有其它节点的状态，集群中的一些重要的决策交由它来做。
为什么集群里一定要有一个master节点？
我们可以想象一下一个没有master节点的集群是什么样子的。假设我们有这样一个集群：集群中有5个节点，分别是A、B、C、D和E。所有的节点都是普通节点，大家的职责没有任何区别，而且每一个节点都知道其它节点的信息。我们来看看这样的“无政府”状态的集群是否可以正常运行。
在某一时刻，外部系统发来了一个条数据，这个集群要把这条数据存储起来。Elasticsearch在存储数据之前，首先要创建一个索引，而创建索引就要生成分片。那么，分片应该放在哪些节点呢？嗯，这是个问题！如果有个leader在，那么，这个决策直接交给leader决定就好了。可是现在没有，试试发扬民主精神，靠大家群策群力如何？
假设集群需要为这个索引生成2个分片。噢，等等！分片数谁说了算？万一有人认为需要3个分片，有人认为需要2个分片，怎么办？真是寸步难行啊！算了，乐观点，我们姑且认为每个节点在启动的时候都设置的是2个分片，而且一直没有变化，大家在这方面暂时没有分歧，就2个分片吧。下一步就是决定把这两个分片放到哪里。在这个乌合之众的群体中，最简单有效的方法就是投票。假设大家都认为应该存放在负载最轻的节点上。因为每个节点都知道其它节点的信息(包括负载信息)，所以大家都知道该把分片放到哪个节点。比如，这一次大家一致认为E节点最轻松，分片就放到E节点了。OK，大功告成！
事情算是搞定了，可是似乎并不轻松。我们来算一下账。这一次投票中，为了检查其它节点到状态，每个节点都和其它所有到节点进行了一次通信。5个节点累计做了4X5=20次通信。这只是一个5节点到集群，如果50个节点，一次投票则需要50X49= 2450次通信。如果每次决策都需要全民投票，那么实在是太重了。这跟现实社会是一样的，如果颁布每条法律都需要做一次全民投票，基本上这个社会就无法运转了。最好的办法是选一个管理者，然后由他来做决策。全民投票仅用于选择谁来当管理者。
另外，如果没有master，会产生脑裂(brain split)问题。
假设我们的集群结构是下面这个样子的。A和B在一个网络里，C、D和E在另一个网络里。如果两个网络之间的连接断了，这个集群就变成了两个小集群，即脑裂。这两个小集群各自处理数据。一段时间后，可能网络又联通了，但是它们之间已经产生了数据冲突，无法解决。
“无政府”状态的集群似乎问题重重，然而，我们仍然不能就此得出结论，说必须有一个master才行，也许存在某种巧妙的方法可以解决裁决问题，可以解决脑裂问题。不过，设置一个master是一个简介有效的方法。
有了master节点，集群会怎样？
假设我们的集群设定了一个master节点，比如节点A。整个集群由它负责管理，它可以决定创建多少分片、在哪里创建分片。
集群中的B节点收到一条数据。B节点先问一下A：“需要创建几个分片？在哪里创建？” A节点扫描一下集群的负载（也可以定时扫描，把集群状态存起来），发现E节点负载最小。然后告诉B：“创建2个分片，在E节点”。就这么简单。
光靠master节点解决不了脑裂问题，还需要引入一个称为法定人数(quorum)的概念。法定人数表示一个集群最少需要几个节点数。比如，设置前面集群的法定人数是3， 那么，当两个交换机的网络断开时，就不会出现问题。左侧两个节点组成的网达不到法定人数，因此A节点这个master必须退休，B也要停止工作。右侧有三个节点，满足法定人数要求，则可以选举master。比如，选举C节点为master，那么右侧3个节点可以继续正常工作。当交换机之间的连接通了以后，A和B会重新加入以C为master的集群。整个集群跟之前一样，只是master从A变成了C。
在交换机断开的那段时间，由于A和B两个节点不满足法定人数，所以它们不做任何数据处理。当它们重新介入集群时，它们当数据和集群中其它节点的数据也就不会有冲突。
法定人数一般设置为N/2+1。N为集群的节点数。
集群是怎么选举master的？
理论上，集群有很多种选举办法。这里介绍两种。
1. Bully 算法 －－长幼有序
Bully算法很像古代中国的皇位继承制。皇位的继承一直沿用嫡长继承、顺序嗣位的原则。皇位由长子继承，如长子早死，则立其子，然后是第三子。Bully算法与此类似。它为集群中每个节点设一个唯一编号，用编号的大小表示优先次序。在任何时刻，总是编号最大的节点当master。当master节点挂掉时，下一个节点马上当选新的master。
这种方法的好处是实现起来很简单，不过缺点也很明显。最典型的问题是：当编号最大的节点不稳定时，集群就不稳定。因为master节点需要承担额外当管理任务，所以，该节点的负载会比较大。当负载超过节点的承载能力时，节点就卡住了。这时，编号第二大的节点便当选为新的master。于是，负载便转移到第二个节点。那么，第一个节点的负载就会随之变小。过了一会，它可能又恢复正常运行了。按照规则，第一个节点又会重新当选为master。然后，它又因为负载过大再次被卡住，如此反复循环，导致集群无法正常运行。
2. Paxos －－ 少数服从多数
Paxos是希腊的一个小岛，考古学家发现这个岛上在古代就有关于议会制度的记录。岛上的居民通过民主提议和投票的方式选出一个最终决议。不过，城邦居民都不愿意把全部时间和精力放在这件事情上，只愿意不定期来参与提议和投票。但他们制度能够按照少数服从多数的原则，使得提议者最终达成一致意见。计算机科学家Leslie Lamport借鉴了这个议会制度，设计了分布式系统选举的算法，并直接称之为Paxos算法。
Paxos算法中有两个角色，一个是提议者(Proposer), 另一个是接受者(Acceptor)。当然，一个节点可以同时拥有这两个角色，真实情况通常也都是如此。
Paxos选举过程总共有两个阶段。
阶段一：
a) 提议者给一半以上的接受者发送一个预提案(prepare proposal)，预提案中带一个唯一编号n。
b) 接受者接收到一个编号为n的预提案后，就拿它跟之前接收到的预提案比较。
b-1) 如果n大于其它提案编号，它就发送“接受”反馈，并承诺以后不再接受编号<n的提案(含预提案和正式提案)。同时，把它曾经接受过的编号最大的提案信息也反馈回去。
b-2)如果n小于等于其它提案，它就发送“拒绝”反馈。同时，把它曾经接受过的编号最大的提案信息也反馈回去。
阶段二：
a) 如果提议者从大多数(集群一半以上)接受者那里得到了“接受”反馈，那么它就发送一个正式提案(proposal)给所有节点。正式提案中包含两项内容：编号n和值v。其中，n是它之前预提案的编号，而v是它得到的所有反馈中，编号最大的提案的v值。（v表示建议谁当master，可以是参选节点的机器名等）
b) 如果接受者收到正式提案(编号n), 他就接受这个提议，除非它已经给编号>n的预提案发送了“接受”反馈。
下面是一个例子以帮助理解，例子中里有两个提议者和3个接受者。
第一步，提议者1向3个接受者发送预提案#1.
第二步，接受者之前从没有接受过其它预提案，所以提案编号1就是最大编号，因此三个都接受预提案#1.
第三步，提议者1向接受者1发送正式提案，编号=1,v＝A (它建议A节点做master节点)
第四步，接受者1之前没有给任何编号>1的提案反馈过，所以接受提案1，并把v值设置为提案1的值，即v＝A。注意：此后，接受者1永远不可能改变它的v值，也就是说它的v值永远都是A。
第五步，提议者2给两个接受者发送预提案。
第六步，接受者1发现这个预提案编号(2)大于之前的最大编号(1) , 于是接受该预提案。同时，把它接受过的编号最大的正式提案(#1)的v值也反馈回去。见规则 b-1。 提议者2改变自己提案中的v值，从B变为A。接受者2因为之前没有收到过正式提案，所以只返回“接受”。
第七步，提议者1给接受者2和接受者3发送正式提案，编号=1,v＝A (它建议A节点做master节点)
第八步，接受者2发现提案#1的编号小于它接受过的最大编号(#2),就拒绝该提案。
接受者3发现它接受过的最大编号是1，于是就接受该提案，并将提案值v=A记下来。
第九步，提议者2给接受者1和接受者2发送正式提案。编号＝2，v值＝A。注意，现在提议者2已经不是发送它最初的提案，而是发送新提案。它的新提案来自第六步，从接受者1那里得到的新提案（v=A）。
第十步，接受者接受1和接受者2都发现之前最大的编号是2，于是接受提案。至此，选举结束。所有的接受者得到的提案都是v＝A，于是A当选为master。
如果任何一个接受者的v值不是A而是其它值，那么集群就会出现问题。相当于集群出现了多个master。而Paxos是不会让这样的情况发生的。
不过，Paxos算法理论上会出现“活锁”的问题。具体什么是“活锁”，有兴趣的读者可以自己去研究一下。