分布式计算与处理研究生找不到工作（《分布式技术原理与算法解析》学习笔记Day04）
分布式选举算法
为什么需要分布式选举？
分布式意味着我们的应用部署在一个集群中 ，集群包含多个节点或者服务器 ，对于一个集群来说 ，多个节点是怎么协同工作的呢？我们需要有一个主节点来负责对其他节点的协调和管理 。
分布式选举是为了选出一个主节点 ，由它来协调和管理其他节点 ，以保证集群有序运行和节点间数据的一致性 。
常见的分布式选举算法有哪些？
分布式选举算法一般会分为两类：
基于序号选举的算法（例如Bully算法） 多数派算法（Raft ，ZAB等）Bully算法
Bully算法中 ，节点的角色有两种：普通节点和主节点 。初始化时 ，所有节点都是平等的 ，都是普通节点 ，并且都有成为主节点的权利 ，但是当选主结束后 ，有且仅有一个节点成为主节点 ，其他所有节点变为普通节点 。
Bully算法在选举的过程中 ，需要使用3种消息：
Election消息 ，用于发起选举 。 Alive消息 ，对Election消息的应答 。 Victory消息 ，竞选成功的主节点向其他节点发送的宣誓主权的消息 。Bully算法选举的原则是“长者为大 ” ，它假设集群中的每个节点都知道其他节点的ID 。整个选举过程如下：
集群中每个节点判断自己的ID是否为当前活着的节点中ID最大的 ，如果是 ，则直接向其他节点发送Victory消息 ，宣示自己的主权 。 如果自己不是当前活着的节点中ID最大的 ，则向比自己ID大的所有节点发送Election消息 ，并等待其他节点的回复 。 若在给定的时间范围内 ，本节点没有收到其他节点回复的Alive消息 ，则认为自己成为主节点 ，并向其他节点发送Victory消息 ，宣誓自己成为主节点 ，若接收到来自比自己ID大的节点的Alive消息 ，则等待其他节点发送Victory消息 。 若本节点收到比自己ID小的节点发送的Election消息 ，则回复一个Alive消息 ，告知其他节点 ，我比你大 ，重新选举 。Bully算法的优点是选举速度快 、算法复杂度低 、简单易实现 。它的缺点在于需要每个节点都保存全局的节点信息 ，因此额外信息存储比较多 ，其次 ，任意一个比当前主节点ID大的新节点或者节点故障后回复加入集群的时候 ，都会触发重新选举 ，成为新的主节点 ，如果该节点频繁退出 、加入集群 ，就会导致频繁切主 。
Raft算法
Raft算法是典型的多数派投票选举算法 ，它的核心思想是“少数服从多数 ” 。
在Raft算中 ，集群节点的角色有3种：
Leader ，主节点 ，同一时刻只有一个Leader Candidate ，候选者 ，每一个节点都可以成为Candidate ，节点在该角色下才可能被选为新的Leader Follower ，跟随者 ，不可以发起选举 。Raft选举的流程如下：
初始化时 ，所有节点都是Follower状态 。 开始选主时 ，所有节点的状态由Follower转化为Candidate ，并向其他节点发送选举请求 。 其他节点根据收到的选举请求的先后顺序 ，回复是否同意成为主 ，在每一轮选举中 ，一个节点只能投出一张票 。 如果发起选举请求的节点获得超过一半的投票 ，则成为主节点 ，其状态转化为Leader ，其他节点的状态则由Candidate变为Follower 。 Leader节点和Follower节点之间会定期发送心跳包 ，来检测主节点是否正常 。 当Leader节点的任期到了 ，即发现其他服务器开始下一轮选主周期时 ，Leader节点的状态也会由Leader降级为Follower ，进入新一轮选主 。Raft算法的优点是选举速度快 、算法复杂度低 、易于实现 。它的缺点是要求系统内每个节点都可以相互通信 ，其需要获得过半的投票数才能选主成功 ，因此通信量大 。
Kubernetes的选主采用开源组件etcd ，etcd的集群管理器etcds ，是一个高可用 、强一致性的服务发现存储仓库 ，就是采用了Raft算法实现选主和一致性的 。
http://thesecretlivesofdata.com/raft/#election对Raft算法做了很好的动画演示 ，可以很好的帮助我们理解Raft算法的选举过程 。
ZAB算法
ZAB选举算法是为ZooKeeper实现分布式协调功能而设计的 ，和Raft算法相比 ，ZAB算法增加了通过节点ID和数据ID作为参考进行选主 ，节点ID和数据ID越大 ，标识数据越新 ，优先成为主节点 。
ZAB选举算法的核心是“少数服从多数 ，ID大的节点优先成为主节点 ” 。
ZAB算法中 ，集群里的每个节点拥有三种角色：
Leader ，主节点 Follower ，跟随者节点 Observer ，观察者 ，无投票权选举过程中 ，集群中的节点拥有4个状态：
Looking状态 ，选举状态 ，当节点处于该状态时 ，它会认为当前集群中没有Leader ，会进入选举状态 。 Leading状态 ，领导者状态 ，表示已经选择出主节点 ，且当前节点为Leader 。 Following状态 ，跟随者状态 ，集群中已经选出主节点后 ，其他非主节点的状态变更为Following 。 Observing状态 ，观察者状态 ，表示当前节点为Observer ，持观望态度 ，没有投票权和选举权 。投票过程中 ，每个节点都有一个唯一的三元组(service_id, service_zxID, epoch)：
servier_id：该节点唯一ID service_zxID：该节点存放的数据ID ，数据ID越大 ，表示数据越新 ，选举权重越大 epoch：当前选举论数 ，一般用逻辑时钟表示 。选举的原则：server_zxID最大者成为Leader ，如果server_zxID相同 ，则service_id最大者成为Leader 。
ZAB算法性能高 ，对系统无特殊要求 ，采用广播方式发送信息 ，若集群中有n个节点 ，每个节点同事广播 ，则集群中的信息量为n*(n-1)个消息 ，容易出现广播风暴 ，而且消息中增加了节点ID和数据ID ，意味着需要知道所有节点的ID和数据ID ，所以选举时间相对较长 。但是该算法稳定性比较好 ，当有新节点加入或者节点故障恢复后 ，会触发选主 ，但不一定会真正切主 ，除非新节点或者故障恢复后的节点数据ID和节点ID最大 ，且获得投票数过半 ，才会切主 。
ZAB算法适合大规模分布式场景 ，例如ZooKeeper 。
关于Bully算法 、Raft算法和ZAB算法 ，有一个比较形象的比喻：
Bully算法：类似于选武林盟主 ，谁武功最高 ，谁来当 Raft算法：类似于选总统 ，谁票数最高 ，谁来当 ZAB算法：类似于选优秀班干部 ，是班干部且票多才可以更加详细的比较信息如下表所示 。
创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！