你好，我是聂鹏程。今天，我来继续带你打卡分布式核心技术。
相信你对集群的概念并不陌生。简单说，集群一般是由两个或两个以上的服务器组建而成，每个服务器都是一个节点。我们经常会听到数据库集群、管理集群等概念，也知道数据库集群提供了读写功能，管理集群提供了管理、故障恢复等功能。
接下来，你开始好奇了，对于一个集群来说，多个节点到底是怎么协同，怎么管理的呢。比如，数据库集群，如何保证写入的数据在每个节点上都一致呢？
也许你会说，这还不简单，选一个“领导”来负责调度和管理其他节点就可以了啊。
这个想法一点儿也没错。这个“领导”，在分布式中叫做主节点，而选“领导”的过程在分布式领域中叫作分布式选举。
然后，你可能还会问，怎么选主呢。那接下来，我们就一起去揭开这个谜底吧。
为什么要有分布式选举？
主节点，在一个分布式集群中负责对其他节点的协调和管理，也就是说，其他节点都必须听从主节点的安排。
主节点的存在，就可以保证其他节点的有序运行，以及数据库集群中的写入数据在每个节点上的一致性。这里的一致性是指，数据在每个集群节点中都是一样的，不存在不同的情况。
当然，如果主故障了，集群就会天下大乱，就好比一个国家的皇帝驾崩了，国家大乱一样。比如，数据库集群中主节点故障后，可能导致每个节点上的数据会不一致。
这，就应了那句话“国不可一日无君”，对应到分布式系统中就是“集群不可一刻无主”。总结来说，选举的作用就是选出一个主节点，由它来协调和管理其他节点，以保证集群有序运行和节点间数据的一致性。
分布式选举的算法
那么，如何在集群中选出一个合适的主呢？这是一个技术活儿，目前常见的选主方法有基于序号选举的算法（ 比如，Bully算法）、多数派算法（比如，Raft算法、ZAB算法）等。接下来，就和我一起来看看这几种算法吧。
长者为大：Bully算法
Bully算法是一种霸道的集群选主算法，为什么说是霸道呢？因为它的选举原则是“长者”为大，即在所有活着的节点中，选取ID最大的节点作为主节点。
在Bully算法中，节点的角色有两种：普通节点和主节点。初始化时，所有节点都是平等的，都是普通节点，并且都有成为主的权利。但是，当选主成功后，有且仅有一个节点成为主节点，其他所有节点都是普通节点。当且仅当主节点故障或与其他节点失去联系后，才会重新选主。
Bully算法在选举过程中，需要用到以下3种消息：
- Election消息，用于发起选举；
- Alive消息，对Election消息的应答；
- Victory消息，竞选成功的主节点向其他节点发送的宣誓主权的消息。
Bully算法选举的原则是“长者为大”，意味着它的假设条件是，集群中每个节点均知道其他节点的ID。在此前提下，其具体的选举过程是：
- 集群中每个节点判断自己的ID是否为当前活着的节点中ID最大的，如果是，则直接向其他节点发送Victory消息，宣誓自己的主权；
- 如果自己不是当前活着的节点中ID最大的，则向比自己ID大的所有节点发送Election消息，并等待其他节点的回复；
- 若在给定的时间范围内，本节点没有收到其他节点回复的Alive消息，则认为自己成为主节点，并向其他节点发送Victory消息，宣誓自己成为主节点；若接收到来自比自己ID大的节点的Alive消息，则等待其他节点发送Victory消息；
- 若本节点收到比自己ID小的节点发送的Election消息，则回复一个Alive消息，告知其他节点，我比你大，重新选举。
目前已经有很多开源软件采用了Bully算法进行选主，比如MongoDB的副本集故障转移功能。MongoDB的分布式选举中，采用节点的最后操作时间戳来表示ID，时间戳最新的节点其ID最大，也就是说时间戳最新的、活着的节点是主节点。
小结一下。Bully算法的选择特别霸道和简单，谁活着且谁的ID最大谁就是主节点，其他节点必须无条件服从。这种算法的优点是，选举速度快、算法复杂度低、简单易实现。
但这种算法的缺点在于，需要每个节点有全局的节点信息，因此额外信息存储较多；其次，任意一个比当前主节点ID大的新节点或节点故障后恢复加入集群的时候，都可能会触发重新选举，成为新的主节点，如果该节点频繁退出、加入集群，就会导致频繁切主。
民主投票：Raft算法
Raft算法是典型的多数派投票选举算法，其选举机制与我们日常生活中的民主投票机制类似，核心思想是“少数服从多数”。也就是说，Raft算法中，获得投票最多的节点成为主。
采用Raft算法选举，集群节点的角色有3种：
- Leader，即主节点，同一时刻只有一个Leader，负责协调和管理其他节点；
- Candidate，即候选者，每一个节点都可以成为Candidate，节点在该角色下才可以被选为新的Leader；
- Follower，Leader的跟随者，不可以发起选举。
Raft选举的流程，可以分为以下几步：
- 初始化时，所有节点均为Follower状态。
- 开始选主时，所有节点的状态由Follower转化为Candidate，并向其他节点发送选举请求。
- 其他节点根据接收到的选举请求的先后顺序，回复是否同意成为主。这里需要注意的是，在每一轮选举中，一个节点只能投出一张票。
- 若发起选举请求的节点获得超过一半的投票，则成为主节点，其状态转化为Leader，其他节点的状态则由Candidate降为Follower。Leader节点与Follower节点之间会定期发送心跳包，以检测主节点是否活着。
- 当Leader节点的任期到了，即发现其他服务器开始下一轮选主周期时，Leader节点的状态由Leader降级为Follower，进入新一轮选主。
节点的状态迁移如下所示（图中的term指的是选举周期）：
请注意，每一轮选举，每个节点只能投一次票。这种选举就类似人大代表选举，正常情况下每个人大代表都有一定的任期，任期到后会触发重新选举，且投票者只能将自己手里唯一的票投给其中一个候选者。对应到Raft算法中，选主是周期进行的，包括选主和任值两个时间段，选主阶段对应投票阶段，任值阶段对应节点成为主之后的任期。但也有例外的时候，如果主节点故障，会立马发起选举，重新选出一个主节点。
Google开源的Kubernetes，擅长容器管理与调度，为了保证可靠性，通常会部署3个节点用于数据备份。这3个节点中，有一个会被选为主，其他节点作为备。Kubernetes的选主采用的是开源的etcd组件。而，etcd的集群管理器etcds，是一个高可用、强一致性的服务发现存储仓库，就是采用了Raft算法来实现选主和一致性的。
小结一下。Raft算法具有选举速度快、算法复杂度低、易于实现的优点；缺点是，它要求系统内每个节点都可以相互通信，且需要获得过半的投票数才能选主成功，因此通信量大。该算法选举稳定性比Bully算法好，这是因为当有新节点加入或节点故障恢复后，会触发选主，但不一定会真正切主，除非新节点或故障后恢复的节点获得投票数过半，才会导致切主。
具有优先级的民主投票：ZAB算法
ZAB（ZooKeeper Atomic Broadcast）选举算法是为ZooKeeper实现分布式协调功能而设计的。相较于Raft算法的投票机制，ZAB算法增加了通过节点ID和数据ID作为参考进行选主，节点ID和数据ID越大，表示数据越新，优先成为主。相比较于Raft算法，ZAB算法尽可能保证数据的最新性。所以，ZAB算法可以说是对Raft算法的改进。
使用ZAB算法选举时，集群中每个节点拥有3种角色：
- Leader，主节点；
- Follower，跟随者节点；
- Observer，观察者，无投票权。
选举过程中，集群中的节点拥有4个状态：
- Looking状态，即选举状态。当节点处于该状态时，它会认为当前集群中没有Leader，因此自己进入选举状态。
- Leading状态，即领导者状态，表示已经选出主，且当前节点为Leader。
- Following状态，即跟随者状态，集群中已经选出主后，其他非主节点状态更新为Following，表示对Leader的追随。
- Observing状态，即观察者状态，表示当前节点为Observer，持观望态度，没有投票权和选举权。
投票过程中，每个节点都有一个唯一的三元组(server_id, server_zxID, epoch)，其中server_id表示本节点的唯一ID；server_zxID表示本节点存放的数据ID，数据ID越大表示数据越新，选举权重越大；epoch表示当前选取轮数，一般用逻辑时钟表示。
ZAB选举算法的核心是“少数服从多数，ID大的节点优先成为主”，因此选举过程中通过(vote_id, vote_zxID)来表明投票给哪个节点，其中vote_id表示被投票节点的ID，vote_zxID表示被投票节点的服务器zxID。ZAB算法选主的原则是：server_zxID最大者成为Leader；若server_zxID相同，则server_id最大者成为Leader。
接下来，我以3个Server的集群为例，此处每个Server代表一个节点，与你介绍ZAB选主的过程。
第一步：当系统刚启动时，3个服务器当前投票均为第一轮投票，即epoch=1，且zxID均为0。此时每个服务器都推选自己，并将选票信息<epoch, vote_id, vote_zxID>广播出去。
第二步：根据判断规则，由于3个Server的epoch、zxID都相同，因此比较server_id，较大者即为推选对象，因此Server 1和Server 2将vote_id改为3，更新自己的投票箱并重新广播自己的投票。
第三步：此时系统内所有服务器都推选了Server 3，因此Server 3当选Leader，处于Leading状态，向其他服务器发送心跳包并维护连接；Server1和Server2处于Following状态。
小结一下。ZAB算法性能高，对系统无特殊要求，采用广播方式发送信息，若节点中有n个节点，每个节点同时广播，则集群中信息量为n*(n-1)个消息，容易出现广播风暴；且除了投票，还增加了对比节点ID和数据ID，这就意味着还需要知道所有节点的ID和数据ID，所以选举时间相对较长。但该算法选举稳定性比较好，当有新节点加入或节点故障恢复后，会触发选主，但不一定会真正切主，除非新节点或故障后恢复的节点数据ID和节点ID最大，且获得投票数过半，才会导致切主。
三种选举算法的对比分析
好了，我已经带你理解了分布式选举的3种经典算法，即Bully算法、Raft算法和ZAB算法。那么接下来，我就从消息传递内容、选举机制和选举过程的维度，对这3种算法进行一个对比分析，以帮助你理解记忆。
知识扩展：为什么“多数派”选主算法通常采用奇数节点，而不是偶数节点呢？
多数派选主算法的核心是少数服从多数，获得投票多的节点胜出。想象一下，如果现在采用偶数节点集群，当两个节点均获得一半投票时，到底应该选谁为主呢？
答案是，在这种情况下，无法选出主，必须重新投票选举。但即使重新投票选举，两个节点拥有相同投票数的概率也会很大。因此，多数派选主算法通常采用奇数节点。
这，也是大家通常看到ZooKeeper、 etcd、Kubernetes等开源软件选主均采用奇数节点的一个关键原因。
总结
今天，我首先与你讲述了什么是分布式选举，以及为什么需要分布式选举。然后，我和你介绍了实现分布式选举的3种方法，即：Bully算法、Raft算法，以及ZooKeeper中的ZAB算法，并通过实例与你展示了各类方法的选举流程。
我将今天的主要内容总结为了如下所示的思维导图，来帮助你加深理解与记忆。
思考题
- 分布式选举和一致性的关系是什么？
- 你是否见到过一个集群中存在双主的场景呢？
我是聂鹏程，感谢你的收听，欢迎你在评论区给我留言分享你的观点，也欢迎你把这篇文章分享给更多的朋友一起阅读。我们下期再会！
精选留言
2019-09-30 10:21:42
https://www.infoq.cn/article/coreos-analyse-etcd/
还有一个Raft算法动画链接
http://thesecretlivesofdata.com/raft/#election
2019-09-30 07:19:39
1.分布式选举算法是为了保证数据一致性的
在集群中存在多个节点提供服务，如果每个节点都可以写数据，这样容易造成数据的不一致，所以需要选举一个leader，往leader节点中写数据，然后同步到follower节点中。这样就能更好的保证一致性
但因为同步数据存在延迟，所以follower节点的数据不是每时每刻都和leader节点数据保持一致的
有的框架是由leader提供读写操作，这样能保证写和读都是最新的数据，我没记错的话kafka就属于这种，读写都发生在主副本上。
而像mysql集群是在主节点写入数据，从节点提供读功能，即主从架构
总之，我觉得，一个好的分布式选举算法能更好的保证数据的一致性
2.老师说的集群中存在双主是说选举算法出了问题，出现了两个主，还是说双主是正常情况，两个主互提供写服务，然后再互相同步数据的情况呢？
2019-09-30 09:35:48
2019-09-30 16:53:41
个人理解选举本身其实就是一致性的一次协商，要求全局认可同一个节点做主节点。选举的目的是为了简化一致性协商的流程，让选出的master来协调各成员针对某项决议达成一致；
2、你是否见到过一个集群中存在双主的场景？
双主是可能发生的，例如原主网络与外部中断，集群发生脑裂，则老的集群主还存在，分裂的剩余节点由于与老主失联，大家重新选了新主出来。此时就会产生双主。规避双主的影响，需要通过租约机制，让老主发现在租约到期后与大多数节点失联主动降备；新主的选举也要等待超过这个租约时间后去选举新主，避免业务同一时刻看到双主。但是由于各个服务器资源、负载、调度等问题，时间并不是一个精确的可靠保障，例如定时器失真，还是可能导致同一时刻出现双主，所以每个地方的租约时间配置是个技术点。另外新主产生，生成新的epoch（+1），这样可以避免大家去处理老消息，从而进一步规避双主的问题。
2019-10-23 07:25:17
2019-11-21 21:43:50
2. https://github.com/sluk3r/sofa-jraft
3. http://thesecretlivesofdata.com/raft/#election 动画效果。
4. 自己搞一个新的算法的微创新？
2019-10-04 14:19:39
2020-02-13 16:32:36
赞，老师的专栏有两个创新点，一是有一个扩展点，另一个是专栏的总结，特别是以脑图的形式展现。
之前也学习过分布式选举算法，不知道是老师有裁剪还是怎么回事，感觉比这复杂难懂，老师讲解的基本能听懂。
OK，记一下自己的理解。
1：分布式选主算法，为选主而生，那为啥非要有一个主哪？人人平等不好嘛？分布式系统和人类社会非常的像，如果没有主，有些事情特别是有冲突的需要协作完成的，有谁来负责呢？针对数据库，好多机器都存数据，为了提高性能和可用性，如果都能接受写请求，各个库中的数据不一致了，又该怎么办呢？这就是要有主的原因了！
2：选主的算法，老师介绍了三种经典的，已经总结的很好了，我就不总结啦！我来个比喻，方便记忆。
bully算法——类似选武林盟主，谁武功最高，谁来当
raft算法——类似选总统，谁票数最高，谁来当
zab算法——类似选优秀班干部，是班干部且票多才行
感觉只有能确定一台电脑为主就行，不管什么方式，比如：一组两台跑定时任务的集群，刚开始无主，谁先启动谁就是主，当启动一台机器后先看有没有主，有主自己就是从，否则就告诉其他机器自己是主。
2019-10-19 07:47:02
2020-04-28 12:32:58
2019-12-25 21:27:04
前几天我们看到了分布式集群中都会有一个协调者存在，比如那个厕所叫号员就是这么个角色。那究竟是谁能来做这个协调者或者管理者呢？选出这个负责协调和管理的主节点的过程就是分布式选举。同样我们前面也提到过多次的单点问题，很多时候就是领导者“驾崩”导致的，如何在领导者驾崩后立即再次选出下一任领导者，也是分布式选举中需要十分关注的一个点。
选主的常见原则是基于序号以及基于投票。类似资历优先（岁数大）还是能力优先（票数高）。
基于资历（序号）的常见算法就是Bully（恶霸）算法：就是选取所有节点中，ID最大的节点作为主节点。
既然需要判断自己是不是最大，就需要自己来存储其他所有节点的ID。选举开始后：
1. 宣誓主权：判断自己是不是最大的，如果是就通知各位自己是主了（向所有人发送Victory消息）
2. 认怂：如果自己不是最大的，需要向比自己大的认怂，承认各位大佬江湖地位，并等待回复（向大佬们发送Election）
3. 大佬收到小弟发来的Election消息，就会给小弟发送Alive，表示自己活着。（向小弟发送Alive信息）/
4. 小弟如果没有收到大佬发来的Alive信息，说明比自己大的都死绝了，我可以登基了（向所有人发送Victory消息）
可见其选举速度快、复杂度低、简单易实现。
但所有节点的信息存了所有其他节点的ID，存储的冗余度较高。而且有一个风险，就是ID最大的频繁进出集群，就会频繁切换主节点。还有一个缺点没提到就是ID最大的并不一定是能力最强的。
基于能力，民主一点的可以是Raft算法：核心思想是”少数服从多数“。
Raft算法规定了包括Leader主节点、Candidate 候选节点以及Follower跟随节点：
1. 开始选举时，大家都会变成候选节点，向其他节点发送选举请求
2. 每个节点根据先后顺序回复是否同意
3. 若同意数超过一半，则成为主节点，其他节点降为跟随节点，并与主节点互发心跳包
4. 主节点失效活着任期结束再来一轮选举
可见这种方式选举速度快、复杂度低、易于实现。
但选举时的通信量是n * (n -1 )。Raft如果ID最大的频繁进出集群，虽然会触发选主，但不一定真正切主。除非得票数过半。
基于能力，还有一种算法是ZAB算法：核心思想是“少数服从多数+ID大的优先”
ZAB是ZK实现协调所设计的。偏向于数据更新的节点。ZAB添加了server_zxID 来表示本节点存放的数据ID，越大越新（能力越强）。选举过程与Raft算法类似，只不过Raft根据先后顺序来判断，而ZAB先比较数据ID，数据ID相同的再比较ServerID，也就是说ZAB喜欢“能力强的年轻人”。
但同样也有广播风暴的问题，且增加了一点选举的复杂度，但会使得主节点更加稳定，因为新节点增加或故障节点（数据不会太新）恢复，触发选举后切主的可能性要更小一些。
因此你看后两种投票少数服从多数的情况下，最好还必须候选者是单数，否则可能因为票数相同而需要多次重新投票。所以经常看到ZK、etcd、K8S都会建议奇数节点。
2019-10-31 00:18:24
2019-10-01 22:56:23
2019-09-30 14:34:58
希望老是解答一下
2019-09-30 08:17:08
https://www.cnblogs.com/xybaby/p/10124083.html
2.有个brain split（脑裂），比如说两个机房原来网络想通，可以正确选主，后来网络不通，每个机房都只知道自己的小山头，他们就容易各自占山为王。
http://www.ruanyifeng.com/blog/2018/07/cap.html
也可以搜下维基百科brain split。
在地铁上写的，有不对之处，请老师指出
2021-02-27 14:22:11
1. 投票（选举）类：raft
2. 竞争（证明）类：PoX
3. 随机（指定）类：PBFT，PoET，Bully
4. 联盟（代议）类：DPOS
5. 混合类：如 PoW+PoS等等
2022-07-30 23:54:54
1. 提到zab选主保证最新数据的时候，提到算是对raft的优化，这个说法并不恰当，zab协议比raft早出来几年，而且raft的选举也会保证有最多数据的优先选到主，并不是谁先发起选举就能选到leader。
2. 文中在提到raft协议的时候提到了kubernetes（k8s），k8s是用etcd作为自己的"数据库"，etcd是基于raft协议的kv存储，k8s中的组件的选主实现和raft协议中领导者选举完全没有关系, 也就是说etcd组件本身节点之间的leader选举算法，和使用etcd实现的leader选举是两个不同的东西，实现思路也不同, 不能混为一谈。
3. 文中提到多数派协议一般不使用偶然个节点，只提到了偶数节点可能出现会平分投票的问题(zab和raft对这种情况都有各自的解法），但没有说出我觉得更重要的点，就是偶数个节点相比奇数个节点的集群，在没有增加集群可用性的同时还可能会导致集群写性能的下降。如3节点组成的zk集群和4节点的相比，都只能容忍最多1个节点故障集群可用，但3节点的集群写请求需要2个节点回复成功才算写成功，4节点的就需要3节点
2020-04-09 10:57:37
1:与一致性的关系就是分布式选举可以在一些场景下决定一致性,比如raft中就是在客户端向leader写入信息.leader在收到大多数follower的回复后视为写入成功,这就是保证了最终一致性,如果改为收到全部节点的回复的话就是强一致性了.之所以说是一些场景是因为选举其实并不一定发生在选一个主节点去处理客户端请求,也可以是选举进行故障转移等.例子是redis哨兵或者redis集群的故障转移需要选一个leader进行操作.
2.双主的情况发生在网络分区中,这其实就是算法可用性的一个体现,可以容忍N/2个节点失效(奇数),因为在那个较少节点网络分区中的节点写的数据不会被视为成功,节点数不可能大于一半,自然也不会收到一半的回复了从而视为写入成功了.这也是raft的过程.当然这里的双主说的是选举出来的主.复制模型中我们还可以使用多主节点模型,这样主节点不就有很多啦(偷换概念小能手)
还有一点很有意思也想提一下,这里的ZAB算法让我想起了redis集群中在选举选出来一个leader执行故障转移的时还需要选择一个从节点,使用的就是简化版ZAB(不需要通信),因为心跳包的原因所有主节点中有宕机主节点从节点的信息,直接选一个数据最新ID最大的即可!
2020-03-29 12:35:35
2020-03-09 16:50:06