关于分布式选举算法你知道多少？

作者:课课家教育更新于： 2019-02-28 22:02:52

　　分布式设计与开发中有些疑难问题必须借助一些算法才能解决，比如分布式环境一致性问题，分布式计算简单来说，是把一个大计算任务拆分成多个小计算任务分布到若干台机器上去计算，然后再进行结果汇总。目的在于分析计算海量的数据，从雷达监测的海量历史信号中分析异常信号(外星文明)，淘宝双十一实时计算各地区的消费习惯等。

　　许多分布式算法需要一个进程充当协调者、发起者或者其他某种特殊的角色。通常由哪个进程充当这个较色并不重要，重要的是它们中要有一个进程来充当。我们假设每个进程有一个唯一的编号，同时还假设每个进程知道所有其他进程的编号。但是进程不知道当前哪个进程正在运行，以及哪些进程崩溃了。

　　bully算法

　　Bully算法是一种协调者（主节点）竞选算法，主要思想是集群的每个成员都可以声明它是主节点并通知其他节点。别的节点可以选择接受这个声称或是拒绝并进入主节点竞争。被其他所有节点接受的节点才能成为主节点。节点按照一些属性来判断谁应该胜出。这个属性可以是一个静态ID，也可以是更新的度量像最近一次事务ID（最新的节点会胜出）。

　　mongodb副本集故障转移功能得益于它的选举机制。选举机制采用了Bully算法，可以很方便从分布式节点中选出主节点。一个分布式集群架构中一般都有一个所谓的主节点，可以有很多用途，比如缓存机器节点元数据，作为集群的访问入口等等。

　　我们先看看这两种架构：

　　1、指定主节点的架构，这种架构一般都会申明一个节点为主节点，其他节点都是从节点，如我们常用的MySQL就是这样。但是这样架构我们在第一节说了整个集群如果主节点挂掉了就得手工操作，上架一个新的主节点或者从从节点恢复数据，不太灵活。

　　2、不指定主节点，集群中的任意节点都可以成为主节点。mongodb也就是采用这种架构，一但主节点挂了其他从节点自动接替变成主节点。如下图：

　　当任何一个进程发现协调者不响应请求时，他发起一次选举，选举过程如下：

　　a\\P进程向所有编号比他大的进程发送一个election消息；

　　b\\如果无人响应，则P获胜，成为协调者

　　c\\如果编号比他大的进程响应，则由响应者接管选举工作，P的工作完成。

　　任何一个时刻，一个进程只能从编号比他小的进程接受election消息，当消息到达时，接受者发送一个OK消息给发送者，表明它在运行，接管工作。

　　最终除了一个进程外，其他进程都放弃，那个进程就是新的协调者。

　　他将获胜消息发送给其他所有进程，通知他们新的协调者。

　　当一个以前崩溃的进程恢复过来了后，它将主持一场选举。如果该进程恰好是当前运行进程中编号最大的进程，它将获胜，故此成为欺负算法。

　　环算法

　　该环算法不适用令牌，假设进程按照物理或者逻辑顺序进行排序，那么进程都知道它的后继者。

　　当任何一个进程注意到协调者不工作时，它构造一个带有自己的进程号的election消息，并将消息发送给后继者。如果后继者崩溃了，发送者沿着此环跳过它的后继者发送给下一个进程，或者再下一个进程。直到找到一个正在运行的进程。

　　在每一步中，发送者将自己的进程编号加入到消息中，以使自己成为协调者候选人之一。

　　最终消息返回到发起这次选举的进程，当发起者收到一条包含自己进程编号的消息时，识别出来。此时消息编程coordinator消息，并再一次绕环运行，向所有进程通知谁是协调者（成员列表中进程号最大的那个）

　　小编结语：

　　更多内容尽在课课家教育！