Zookeeper基础篇---面试Leader选举
消息广播算法
当集群已经有过半的Follower完成同步Leader的状态，整个集群zk就进入了消息广播模式。
当集群中其他节点收到客户端的事务请求，那么这些非Leader服务器会先把事物转发到Leader服务器中，然后Leader服务器会议提案的形式广播到其他服务器，然后收集其他服务器的投票结果，在选票过半的统一之后，Leader会进行事物提交，具体过程如下。
- Leader在接受到一个事务之后，会给事务分配一个zxid,通过比较zxid大小进行有序的事务管理
- 为了保证Leader向Follower发送提案的有序，Leader会为每个Follower创建一个FIFO的队列，并将提案副本写入队列，按照队列的发送提案给Follower.
- 当Follower接受到提案的时候 ，会先把zxid和本地最大的zxid进行比较，若大于本地zxid,则将当前的提案记录到本地事务日志中,并向Leader返回一个ACK.
- 当Leader接受过半的ACKS的时候，回向反馈给Leader的Follower，发送commit命令，没有反馈的Follower则把队列的天发送给Follower,并携带commit，Follower接受到commit后执行命令.
恢复模式的两个原则
当集群正在启动过程中，或 Leader 与超过半数的主机断连后，集群就进入了恢复模式。对于要恢复的数据状态需要遵循两 个原则
处理过的消息不能丢失
当Leader收到大多数Follower的ACK反馈时候，Leader就会向其他Follower广播commit消息，让各个server执行该事务，当Follower收到commit的消息，就会在本地执行写请求事务，但是部分server没有收到commit消息，Leader就直接挂了，而这些server并没有执行commit消息，且没有执行写的操作，因此当新的Leader选举出来之后，就要保证所有的server上都要执行那些已经被执行过的事务。为了保证这个原则，ZAB实现下面策略
- 选举出最大zxid的节点作为Leader,由于每个提案被commit之前都必须有合法数量的节点反馈，所以肯定有部分的server记录了被commit事物的日志，因此，只要合法数量的server正常服务，就必然保存了所有被执行commit的proposal的状态。
- 新的Leader先将自身拥有并非其他Follower都有提案发送给Follower，在将这些提案的Commit命令发送给Follower,保证所有的Follower保存了提案，并执行了提案，通过这个策略保证处理过的消息不能丢失。
被丢弃的消息不再被恢复
当Leader接受到事务生成提案了，但是还有广播出去，就直接挂了，因此当新选出的Leader选举出来的，这个事务就会被跳过了，但是旧的Leader重启启动的时候会成为Follower，但由于保留了跳过的提案，所以就会产生状态不一致，需要清除这个提案。
zxid是一个64为long类型，高32位是epoch，低32位是zxid,当新的Leader生成之后，epoch和zxid都会增加1，这样设计是为了重启之后，不会把旧的Leader不会重新选举成为Leader,且新的Leader会把所有旧的epoch编号，和未commit的提案清除。
Leader选举算法
服务启动Leader选举和断开后重新选举Leader是稍微不同的。
集群启动Leader选举
我们这里以三台机器为例说明一下Leader选举
在集群初始化启动的时候，server1启动首先会选自己，使用server1(myid,zxid)表示，此时他的投票就是（1，0），由于其他机器还没有启动，收不到反馈，server1一直处于Looking，即非服务状态。
当第二台server2启动，两条机器就可以进行通讯，选出集群的Leader,选举过程如下。
每个server进行投票，此时server1(1,0),server2(2,0),然后将各自的投票发给集群。
接收到各个服务器的投票，每个服务器接受到投票之后，就会验证是否有效，如是否是本轮投票，是否来自Looking状态的服务器。
处理投票，针对每一个投票，会拿自己的投票和别人的投票进行比较。比较的原则如下
- 先比较zxid
- 如果zxid一样，再比较myid进行比较，myid大的就是Leader服务器
对于server1而言，他的投票是(1,0),接受到server2是(2,0),首先比较zxid,他们两都一样，再比较myid比较，有server2的myid比较大，因此server1更新自己的投票为（2，0),然后重新投票，对于server2只需要重新把投票向集群发起投票信息就可以了。
统计投票，每次投票之后，zkserver都会统计投票结果，此时server2，server1的投票的是（2，0），因此server2就会被选举成Leader.
改变服务状态，一旦Leader选举成功，就会更新自己的状态，如果是Follower就会更新自己的状态为Following,Leader更新自己的状态是Leading.
添加主机，当server3添加进来的时候，集群的Leader已经确定，server3只能以Follower身份加入。
断开后选举Leader
在zookeeper集群中，Leader和非Leader服务各司其职，但是当leader挂了，此时集群就暂停对外服务，进入新的一轮选举Leader.
假设正在运行有server1，server2，server3,正常服务，但是server2挂掉了，此时新的Leader选举开始
- 变更其他非Observer的服务为Looking,然后开始选举投票，
- 每个服务开始会自己投自己，假设server1是(1,11),server3(3,33)的投票，然后发给集群
- 接受到各个服务器的投票，检验投票的有效性，是否是本轮投票，或是否是来自LOOKING服务的投票
- 比较投票，有server3的zxid比server1的zxid大，所以更新server1的投票为（3，33），server3不需要更新自己的投票，只需要把信息再次发送给集群
- 统计投票，和启动一样，此时投票的结果都是（3，33），因此server3就是Leader.
- 改变服务状态，和启动选举一样，一旦leader确定，其他Follower更新自己的状态为Following,Leader更新自己的状态为Leading.
恢复下的数据同步
当完成Leader选举完成之后，就进入到恢复模式，Leader会为每一个Follower准备一个队列，并将那些没有被Folloer同步的事务逐个发送个Follower,紧跟着发送commit命令，Follower接受到在进行本地执行后，反馈给Leader 服务器ack,Leader服务器会把follower加入到真正的follower服务列表。
CAP原则
CAP原则又称CAP定理，指的是在一个分布式系统中，Consistency（一致性）、 Availability （可用性）、 Partition tolerance（分区容错性），三者不可兼得。
一致性:在分布式系统中所有的主机在每一个时刻是否保证具有完全相同的数据备份，若具有，则分布式系统具有一致性。
可用性:在集群部分节点发生故障是否会影响客户端的响应，哪怕是短暂的的影响，也不具备可用性。
分区容错性:分布式系统中一台主机是一个分区，错误是就是分布式中无法保证数据一致性或可用性，对于分布式系统，必须具有对这些错误的包容性，及容错性。
对于分布式系统， 在 CAP 原则中分区容错性 P 是必须要保证的。但其并不能同时保证 一致性与可用性。因为现在的分布式系统在满足了一致性的前提下，会牺牲可用性；在满足 了可用性的前提下，会牺牲一致性。所以，CAP 原则对于一个分布式系统来说，只可能满足 两项，即要么 CP，要么 AP。这就是 CAP 的三二原则。
zk遵循的是CP原则，即保证一致性，牺牲可用性，
当Leader宕机之后，zk集群会马上选举Leader,期间会有30-120的不可用状态，即不接受客户端的读写状态，所以不满足可用性
为什么会这么长时间进行Leader选举，是因为同步问题，同步分为初始化同步和更新同步，当Leader选举出来之后，各个Follower需要同步Leader的数据到自己的缓存中，这是初始化同步，而当Leader的数据被客户端修改后，会向Follower发起广播，然后各个Follower主动同步Leader的数据，这就是更新同步，当同步超时，则会再次发起同步，这个过程zk集群是处于不可用状态.
由于zk采用cp,所以导致其可用性降低，这是致命的的问题，Spring cloud的Eureka在分布式系统中起到的作用类似于zk，但是采用的AP原则，其牺牲一致性，但保证可用性。