分布式系统因为涉及到多服务器、多应用服务，系统为了维护各节点之间的联系以及数据同步，势必需要在多个节点之间选举出一个主节点（通常我们称之为leader或者master）来维护节点之间的状态和联系，以及在数据同步时保证数据一致性。由此，随着计算机的发展，衍生出了下面四种选主并且保证数据一致性的算法；
1、Paxos
Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。
角色：
client: 请求发起者;
Proposer： 接受client请求，提出提议(propose);
Accpetor: 投票者，满足多数(Quorum)的决议才被接受；
Learner：backup；
三种模式：
Basic Paxos
Prepare阶段
这个阶段Proposer提出一个提案编号为N；此时N大于这个Proposer之前提出的议案，请求这个集群的Acceptor Quorum接受。
Promise阶段
如果N大于此Acceptor之前接受的任何提案编号则接受，否则拒绝。
Accept阶段
如果Acceptor内部投票通过的人数达到了多数派，则Proposer会发出accept的请求，该请求包括提案编号为N，以及提案的内容V（用户请求的内容）
Accepted阶段
如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。接受之后会向Proposer返回成功，且将议案的内容交给Learner进行backup。
最后learner写入提案向client发送完请求的响应。
整个过程流程图：
Proposer有多个时，Proposer1发送版本1时发生异常，集群切换到Proposer2，提案相同，当Proposer2等待acceptor的propose返回时，Proposer1又复活了，发现自己的prepare1提案被打断了，又准备了更高的版本提案，如此整个集群在不断提交提案，出现了活锁的现象。
解决方式：porposer1上线后再随机生成的时间段内不能提交提案，等Proposer2处理结束，再进行Proposer1的提案。
缺点：
角色多
活锁
每个request需要两轮rpc
由此出现了Multi Paxos，衍生出leader角色，所有请求都得从leader发出。
Multi Paxos
Multi Paxos 从多个Proposer中 通过 basic paxos的prepare到accepted 过程选举出唯一的一个Leader。在basic paxos中，acceptor干了两件事：
1、接受proposer的prepare过程；
2、accepted proposer value的过程；
Proposer选举出leader后就可以直接决定acceptor第一步是否接受proposer的prepare，而不用所有的acceptor各自决定。
第一次请求的2轮rpc后，之后的所有请求都只有一轮rpc，相当于将二阶段提交简化成了一阶段提交，避免了活锁的出现。
为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。
Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。
ZooKeeper使用的Zab也是Multi-Paxos的变形。
2、Raft
角色：
candidate：当未选举出leader和follower时，节点所处的状态;
leader：主节点;
follower：从节点;
raft算法通过给每个节点随机生成一个选举超时时间来决定最先走完选举超时时间的follower节点发起leader选举，等此节点称为leader节点后，通过发送心跳时间维持本节点的leader地位。client发送写请求时，有leader节点接收，并向从节点完成log replication过程。具体过程见下：
election timeout:
follower等待请求的超时时间，如果这个时间结束前还没有收到来自leader或者选举leader的请求，那么当前follower便会变为 candidate。raft给的设定值一般在150ms-300ms之间的随机值。
变成candidate之后，当前节点会立即发送leader的投票请求，其他的follower节点会重置选举的超时时间。
heartbeat timeout：
新选举出来的leader每隔一段时间会发送一个请求给follower，这个时间就是心跳时间。
同样follower在相同的时间间隔内回复leader一个请求，表示自己已经收到。leader会维持这个状态直到follower停止接受心跳或者leader down掉，让follower 变成candidate。
重新选举的过程就是candidate发送选举请求，follower接受到之后返回对应的心跳回应，candidate根据心跳回应的个数判断是否满足多数派，从而变成leader。变成leader之后，会持续发送心跳包来保证follower的存活。
log replication：
客户端发送请求到leader，leader接受之后将请求封装成log entry，并将log副本发送给其他的follower节点。
等待其他的follower节点回复，发现达到了多数派之后leader便将该entry写入。
写入之后再发送请求，表示follower节点也可以写入了。
整个过程可以分为三个步骤：
1、客户端会发送一条请求到leader，这个请求会追加到leader的log上，但此时还没有写入leader所在节点的文件系统之上
2、这个leader的log 会在leader发送下一条心跳包的时候携带该请求的信息 一起发送给follower
3、当entry提交到follower，收到多数派的回复会给client一个回复，表示集群已经写入完成。同时leader将log写入自己的文件系统，并且发送命令让从节点也进行写入。这个过程就是multi paxos中的accepted阶段。
整个过程视频如下：
具体原理可见raft paper ， raft 的动画模型具体描述整个过程。
raft paper
https://raft.github.io/raft.pdf
raft动画模型
http://thesecretlivesofdata.com/raft/
3、ZAB
ZAB协议也是基于 Paxos 算法实现的，不过 ZAB 对 Paxos 进行了很多改进与优化，两者的设计目标也存在差异——ZAB 协议主要用于构建一个高可用的分布式数据主备系统，而 Paxos 算法则是用于构建一个分布式的一致性状态机系统。
ZAB 3个阶段：
fast leader election：快速选举阶段
recovery：恢复阶段
Discovery；
Synchrozation
broadcasting：广播阶段
三个参数：
服务器 ID(myid)：编号越大在选举算法中权重越大；
事务 ID(zxid)：值越大说明数据越新，权重越大；
逻辑时钟(epoch-logicalclock)：同一轮投票过程中的逻辑时钟值是相同的，每投完一次值会增加；
先说明选举时的角色和状态
每个节点拥有角色：
leader 主节点
follower 从节点
observer 观察节点，无投票权限
选举时，节点存在的4种状态：
looking 当集群中无leader时，节点所处的选举状态
leading 当集群中leader已经被选举出，主节点所处的状态
observing 当前节点为 Observer，持观望态度，没有投票权和选举权
following 当集群中leader被选举出，其他节点处在following状态
fast leader election的过程：
每个节点启动的时候都 LOOKING 观望状态，接下来就开始进行选举主流程。这里选取三台机器组成的集群为例。第一台服务器 server1启动时，无法进行 leader 选举，当第二台服务器 server2 启动时，两台机器可以相互通信，进入 leader 选举过程。
（1）每台 server 发出一个投票，由于是初始情况，server1 和 server2 都将自己作为 leader 服务器进行投票，每次投票包含所推举的服务器myid、zxid、epoch，使用（myid，zxid）表示，此时 server1 投票为（1,0），server2 投票为（2,0），然后将各自投票发送给集群中其他机器。
（2）接收来自各个服务器的投票。集群中的每个服务器收到投票后，首先判断该投票的有效性，如检查是否是本轮投票（epoch）、是否来自 LOOKING 状态的服务器。
（3）分别处理投票。针对每一次投票，服务器都需要将其他服务器的投票和自己的投票进行对比，对比规则如下：
a. 优先比较 epoch
b. 检查 zxid，zxid 比较大的服务器优先作为 leader
c. 如果 zxid 相同，那么就比较 myid，myid 较大的服务器作为 leader 服务
（4) 统计投票。每次投票后，服务器统计投票信息，判断是否都有过半机器接收到相同的投票信息。server1、server2 都统计出集群中有两台机器接受了（2,0）的投票信息，此时已经选出了 server2 为 leader 节点。
（5）改变服务器状态。一旦确定了 leader，每个服务器响应更新自己的状态，如果是 follower，那么就变更为 FOLLOWING，如果是 Leader，变更为 LEADING。此时 server3继续启动，直接加入变更自己为 FOLLOWING。
（图片描述来自：https://www.runoob.com/w3cnote/zookeeper-leader.html）
recovery：恢复阶段
leader选举成功后，follower就会开始同步leader上的数据信息。
ZAB通过广播发送信息，每个节点都参与广播，会广播n*(n-1)个消息，并且每个节点都维护其他节点的zxId和serverId，所以会产生广播时间长的问题。但是该算法选举稳定性比较好，当有新节点加入或者节点故障后恢复，会触发选主。但真正切主，则需要serverId和zxId最大，且获得投票数过半，才会发生。
4、Bully
CS 551: Distributed Operating Systems Bully Election Algorithm Example
https://www.cs.colostate.edu/~cs551/CourseNotes/Synchronization/BullyExample.html
以下举例选自上文
6个节点，彼此联系，其中P6是leader，因为它number最大
节点6挂掉
P3节点最先发现master节点宕机，p3节点通知了比自己编号大的p4，p5，p6
P4,P5回应，会接管
P4发送选举信息给P5，P6
只有P5回应并接管
P5仅发送选举信息给P6
P6没有回应，P5宣布当选leader
算法中存在的问题：
1、P6假死，如果再P5当选leader后，P6又因为负载减轻或者网络稳定，对其他节点有回应，此时P6又当选leader，如果循环会对整个集群造成不稳定的问题。解决方法，就是最先发现leader宕机的节点（P3）在发起选举之前，询问其他节点leader是否存活，如果超过半数回应，则重新发起选举有效；
2、脑裂问题。如果网络出现问题发生分区，产生两个leader。解决办法，Quorum算法，只有当要当选为leader的节点超过n/2+1个时，才会被选举为leader。
Bully算法选主很直接，节点编号大的就可以当选为leader，选举速度快、算法复杂度低、简单易实现。缺点也很明显，节点恢复或者新加入的节点只要满足比当前leader节点的编号大就会当选为新的leader，如果此节点频繁加入退出，会让整个集群不稳定。而且因为每个节点之间都得比较，所以每个节点都维护了全局的节点信息，此部分额外信息很大。
总结
