选举在人类政治生活中的重要地位不言而喻。

由计算机们组成的集群，要能完成大数据集群的任务，也需要一个“leader”来统筹节点的在线情况，数据的状态和任务的进度。

但是机器毕竟是机器，没有聚光灯和狗仔围着，它可能悄无声息地下线，留下群龙无首的机器，不知大数据服务何去何从。

因此，“选举”也是机器们在集群生活中，不可缺少的一环。接下来，就让我们从认识这个国开始，逐步理解Hadoop和Zookeeper两大明星项目为代表的，属于计算机国度的选举生活。

计算机国度的“民众”和“选举”

严格来说，能组成集群的是【服务器】。

它更强调存储运算的能力，不像个人使用的计算机那样，拥有友好的屏幕，方便的鼠标和键盘。

服务器一般看起来都像黑盒子，密密麻麻摞在架子上，摆在机房里。

多个服务器能够通过网络互相访问，它们就具备了共同合作的基础

。如果它们有了共同的目标，比如要一起提供存储服务，或者一起提供某一种数据处理服务，那么它们就自发组成了一个国度，叫做【集群】。

虽然原则上网络能联通，服务器就能进行协作，但为了避免糟糕的网速花掉大部分执行任务的时间，集群内的机器通常会选在同一个机房内。

集群中的机器，会有新增，也会有减少，这部分信息需要统计；用户发来一个任务请求，通常也需要拆解、分配和追踪进度，甚至报告给用户。管理、沟通与分配，就是选举出来的节点所需承担的任务。根据服务的不同，它有时候叫master，有时候叫leader。

好处是没有的，服务器不能图财也不能图色，选出来的leader只是承担了不同的任务而已。原则上每个成员，都有成为leader的潜质。集群是计算机的大同世界，众机平等，忘我奉公。

但是无论是谦让还是争抢，这个位置在同一时刻，也只能容纳一台机器 ——

“皇帝轮流做，明年到我家”

轮流就是最一团和气的节点选举机制。按照加入集群的时间，或者凭管理员高兴，机器可以分到一个唯一的序号。序号最靠前的机器，就是主节点。

比如说一开始有十台机器，编号就是1~10。主节点是1号机器。

现在1号机器因为故障或者其他什么原因，需要退出集群的工作，它就把当主节点的所有资料都传递给2号。传递好后，管理员把1号机器关了，就轮到了2号机器当主节点。

这种办法看似平等简单，其实提出了现实生活中无法满足的苛刻条件：需要所有节点时刻团结一致，互相之间的网络也不能出现问题，否则就会出现混乱。

还是上面的例子，如果1号机器还在，2号机器的网络突然出现了问题，和1号连不上了，那么它就会把自己当成主节点；

与此同时，剩下的9个机器仍然认为1号是主节点。过了一会，2号的网络又正常了，这时集群里就同时出现了两个主节点，它们会互相争抢资源，发出服务命令，其余的机器将会无所适从，集群服务有可能因此瘫痪。这种故障被称为【脑裂】。

现实生活中，黑客不可能放过这样的风险。他们一定会想尽办法，让上述例子的情况出现，好破坏系统的功能。所以没有实际的系统会采用【轮流】这样的策略。

朴素粗糙的策略虽不可行，但能为后续的算法指明一点方向：

1、可以当主节点的机器太多的话，难免会出现一些故障，所以我们限制一下有资格当主节点的机器数量，买更好的机器，降低他们出错的可能性。

2、每个机器依然都有资格当master，但是选举需要集群中半数以上的点通过。

暂且把第一种思路称为【天选团】，后一种称为【普选团】。接下来，我们分析一下这两派的做法。

天选：一人做主，他人陪跑，团内轮流

它与【轮流】的不同之处就是大大缩小了有资格当主节点的机器范围。

集群建立之初，管理员就需要指定一些机器作为master的候选。实际应用中常见的就是【主-备结构】：它包含一个主节点和一个备用节点，其余的都是工作节点。

大名鼎鼎的集群服务Hadoop中的namenode选举，Mysql的master选举使用的就是这种设计。

主-备结构每个时候只有一个主节点在提供服务，接受用户的请求，管理、追踪和分配集群和人物的情况；

备用节点则随时做好准备，主节点所接收到的日志和信息，备选的节点也需要复制过来。

上图是一个主备切换的例子，刚开始a是主机，b是备用节点；这时如果a下线，b成为主节点；a重新上线，成为备用节点，b仍然是主节点；这时如果b下线，a成为主节点；b再重新上线，则成为备用节点。

一旦备选节点连不上主节点了，这时有两种可能：

主节点真的故障了：这个时候备选节点具备了主节点的全部信息，就能顺理成章，继承主节点的位置，原先的主节点将转换为备用节点。万一它回来了，就会执行备用节点的任务。

备选节点下线了，它把自己转换成主节点，把正在正常工作的主节点当成了备用节点：这个时候就需要用一些【fencing】机制，验一验谁更有权威。

比如说，主节点定时和其他工作节点联络，都记一下联络次数。理论上这个次数是递增的。如果备选节点下线了，它的联络次数将会比真正的主节点少，其他工作节点可以依照这个特征排除掉伪主节点的命令。

当然这只是思路探讨，实际的实现比这个复杂得多。Hadoop采用了一个消息队列(QJM)来进行fending，本文就不多作展开了，有兴趣可参阅hadoop的官方说明。

只有两个节点轮流当主节点可以避免天选团内部产生分裂，避免单点故障，为主节点挂掉后，管理员检查和抢救服务赢得许多时间，在工程实践上颇受欢迎。

但它显然也不完美：毕竟候选master只有两台，都离线了也不是不可能；而且没法简单地通过加机器的方法，分摊天选团宕机的风险。

hadoop这类的服务，工作的节点希望能发挥它100%的算力，全部布上冗余的备选主节点服务有些浪费，所以主-备也差不多够用了。但如果是消耗不高的任务，比如配置管理，那么，我们可以试着让它有一个“普选”的机制，让集群不再为master节点的机选匮乏而崩溃。

普选：众望所归，业务领跑者胜

既然涉及选择，那么有一个原则放诸四海皆准：

得票超过总票数半数者获胜。

在机器的世界里，这就是铁律，不存在耍赖的可能。

同样，既然是投票了，那么得解决以下几个问题：

• 何时开始投票？
• 哪些机器有资格投票？
• 什么样的票是有效票？

这几个问题比较简单，我们可以提出下面的答案：

当一个机器找不到主节点了，它就可以申请开始一轮投票；

所有能收到这条信息，并且也找不到主节点的机器，将参与投票；

有效的票除了必须选取集群内的机器外，还需要是当前这一轮选举中投的票。

但机器们还有一个难题：如果所有的机器始终都是投给自己，那么集群里的节点永远选不出来——没有人票数过半。机器们的使命是提供服务，所以它们需要协商一个投票的机制，达到以下目的：

• 如何快速选举出leader？

这方面的研究，最为知名的就是Paxos算法。在这个算法的基础上，许多分布式系统都实现了自己的改进策略。关于一定能选出以及平均多久能选出的问题此处就不展开了。仅介绍一个业界的明星项目zookeeper所采取的策略：FastLeaderElection。

FastLeaderElection中，在保证前三个问题都检查好了的基础上，机器需要按以下方式投票：

投票形式：广播。就是每个机器的投票都会发给其他所有机器。

选票内容：my_id(投票机器的id)，my_zxid(表明投票机器最近工作时间的一个标志)；vote_id(推选的机器的id)，(vote_zxid)表明候选者最近工作时间的一个标志；机器的状态，用于宣告是否产生了leader，一旦产生则投票结束。

投票过程：

每个机器投给自己，这样相当于网络中的自我介绍，向其他机器都广播了my_id,zx_id，否则其他机器没法了解自己的情况，就投不了自己；

根据收到的票判断是否要改投，如果需要更改，就再广播出去；改投的规则是，收到选票的vote_zxid大于自己的vote_zxid；或是二者相等时，vote_id大于自己vote_id，那么自己的选票就跟着这张选票投(vote_id)

检查投票箱，看是否有过半的票数支持同一个机器；有的话，这个投票过程就结束了。获得半数以上支持的机器将成为leader，其他成为follower；否则重复第二步。

算法最初的想法并不神秘。它们大多来源于我们的生活，然后通过抽象、限定条件和逻辑推理，在各个专门的领域大显神通。大数据时代下，审视其中关键算法的思路起源，能帮助我们更好地理解其系统设计思路，反过来，对生活中的制度设计，亦能多一份思考的角度。希望各位在此文中有所收获。