分布式理论之分布式选举-创新互联
一个国家需要领导人制定各种国家决策，一个军队也需要最高统领来制定各种军事决策，同理，一个分布式集群也需要一个领导，来协调整个集群的事务，比如保证数据一致性(这也是最重要的！)，分布式集群的领导，我们一般称之为主节点，这个主节点选择的过程我们就叫做分布式选举，而分布式选举可以有各种不同的方案，这些不同的方案叫做分布式选举算法，本文就是来一起来学习常见的分布式选角算法都有哪些，接下来我们就一起看下吧！
常见的算法有bully，raft，zab，分别来看下。
2：分布式选举算法 2.1：bully英文[ˈbʊli] 恐吓，伤害，盛气凌人 school bully校园暴力，该算法比较简单粗暴，直接选择id大的一个节点作为主节点。
- 角色
普通节点，主节点。 - 消息类型
Election消息：发起选举
Alive消息：告知自己拥有更大id的消息
Victory消息：自己成为主。告知其它节点的消息- 选举过程
该算法要求知道所有其它节点的id，用来比较大小，当收到其它节点的消息后就能获取其id（为什么不是在消息中携带自己的id？），则过程如下：
1：如果是节点判断自己当前拥有大的id，则直接向其它节点发送Victory消息，宣布自己成为主节点
2：如果是当前节点判断自己并非拥有大id，则向其它节点发送Election消息，发起选举过程，如果是指定的时间内都没有收到Alive消息回复，则宣布自己成为主节点，并再次向其它节点发送Victory消息，如果是在指定的时间内收到了大于等于1个的Alive消息，则等待接收其它节点发送的Victory消息如下是一个可能的选举过程节点2发起选举最终节点3成为主节点：
选主完成后，正常就不会重新选主了，除非主节点故障，或者是主节点与其它节点失去联系。
- 优缺点
优点：
算法本身简单，容易实现，选举速度快缺点：
1：每个节点都要存储其它节点的id等信息，占用额外存储空间
2：如果是有id更大的节点加入集群，或者是id更大的节点故障后重新加入集群，都会导致重新选主，如果是频繁发生，则会频繁出现重新选主，影响集群的稳定性因此该算法适合节点较少的集群，较大集群首先每个节点都要存储大量的信息，其次，当节点增多时，部分节点出现故障的概率也会增大，导致频繁重新选主。
2.2：raft英文[ræft] 木排；橡皮艇,这是一种少数服从多数的算法。
- 角色
leader：主节点，负责管理和协调其它节点
candidate：候选节点，只有处于该角色的节点才有资格成为leader
follower：leader的跟随者，当选出leader后，其它节点都是该角色- 选主过程
注意：
1：每个节点只能投一票。
2：投票原则是时间优先，即如果是某节点收到投票申请，如果是还没有进行过投票，则直接投票，后续在收到投票申请，因为已经投过票，就不能再次投票了。
集群初始化完成后，每个节点的状态都是follower,如下：
在经过时间范围在150ms到300ms的Election timeout后，会转换状态follower->candidate，如下图其中一个节点首先到达Election timeout，变为candidate状态，如下图：
如图节点A，率先变为candidate状态，其term即任期从0变为1，然后先给自己投一票，所以Vote Count变为1。然后其会向NodeB，Node C，发送投票申请，如下图：
Node B，Node C，收到Node A的投票请求后，发现自己的term小于当前收到请求term，会从0更新为1，另外因为都还未投过票，所以会返回同意票，如下图：
此时，Node A的得票数是3，超过了集群总节点数3的多半，成为新的主节点，其它节点都成为follower节点，主节点会以heartbeat timeout时间间隔发送心跳包到所有follower节点，以供follower检测主节点状态，此时如下图：
接下来当其中一个follower变为candidate状态时，就代表主节点任期结束，此时转换为candidate状态节点，会发起重新选举，如下是发起投票，和接受投票，如下图:
Node C成为term 2的新主节点。
接下来我们看下raft是如何保证数据一致性的，如下当前主节点是Node A：
假设此时客户端向主节点发送了set 5，如下图：
然后主节点会将set 5同步给所有的follower，只有当主节点收到大多数follower数据写入确认后，才会提交数据，返回给客户端数据写入成功，这样就保证了数据的安全性，如下图：
后续有数据更新也是这个流程。
以上我们可以看到，节点状态在不断的转换，如下状态转换图：
- 优缺点
优点：
1：选举速度快，复杂度低。
2：节点退出后重新加入，虽然会触发重新选主，但是因为超过半数投票才能成为主节点，一般一会导致更换主，所以稳定性好缺点：
1：要求所有节点可通信，因为超过半数才能选主成功，所以通信量大
2：重新选主产生的主节点数据比较旧，从而导致大量数据丢失，即数据安全性低英文全程zookeeper atomic broadcast,是zookeeper提出的一种带有优先级的少数服从多数选主算法，该算法和raft相比增加了优先级，而非简单的先到先得选票，这里的优先级主要是数据的最新程度。
- 角色
leader：主节点
follower：跟随节点
observer：观察者，无权投票节点可能的状态如下：
looking状态：选举状态，无主节点时处于该状态
leader状态：主节点状态，代表是主节点，即处于leader角色
follower状态：跟随者状态，选主成功后从looking状态，变更为该状态，即处于follower角色
observer状态：观察者状态，即处于observer角色- 选主过程
因为要根据优先级来决定是否投票，因此发起投票时增加了三元组(server_id, server_zxID, epoch)，含义如下：
server_id：服务器id
server_zxID：服务节点数据id，越大说明数据越新
epoch：选举轮数（为了便于理解，该值可先忽略）对比过程是取server_zxID大的投票，相同的则取server_id投票。
初始状态时，epoch=1，即第一轮投票，server_zxID=0,因为此时还没有任何数据，因此先投自己一票，将投自己的三元组投票发给其它节点，如下图：
接着server1，server2，都发现server3按照优先级，应该投一票，因此将vote_id都改为server3的serverID，即3，然后将其放到投票箱中，并广播出去，如下：
server3成为主节点后开始和follower节点发送heartbeat，follower回复ACK，即开始心跳，如下图：
- 优缺点
优点：
1：算法稳定性好，新节点加入，故障节点恢复，不会造成频繁选主缺点：
1：需要额外比较server_zxID，server_id，选举时间长
2：广播方式发送消息，容易产生广播风暴参考下图：
写在后面少数服从多数算法为什么要奇数个节点？
偶数时，容易出现，相同个数的选票，从而无法选择主节点，即便重新选主，出现相同选票的概率也比较大，但奇数个节点，更容易出现某个节点获取大多数选票，从而成为主节点。
参考文章列表：
raft动画演示 。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：分布式理论之分布式选举-创新互联
文章网址：http://pwwzsj.com/article/deposh.html
