面试官：能聊聊Paxos算法和ZAB协议吗
什么是paxos算法
是一种基于消息传递的，具有高容错的一致性算法。
解决了什么问题
主要解决分布式系统中，如何就某个决策达成一致性的问题。主要的工程实现，ZAB，Google Chubby、微信的 PhxPaxos。
paxos算法与拜占庭将军问题
paxos算法的作者认为，在信道不可信的前提下，通过消息传递的方式达成一致性，是不可能的。因此，paxos算法的前提是不存在拜占庭将军问题。也就是，认为信道是可信的，集群间传递的消息，不会被篡改。分布式系统中，各个节点消息的传递方式有两种，共享内存和消息传递。paxos是基于消息传递通信模型。
paxos的三种角色
在paxos算法中有三种角色，每种角色有不同的功能。但很多时候，一个进程可能充当多种角色。Proposal，提案；
Proposer：提案者
Accecptor：决策者
Learner：学习者，同步者
##paxos算法的一致性 paxos算法的一致性，通过以下几点去保证：
每个提案者在提案的时候，首先需要获取一个全局唯一，递增的编号N，将N赋给提案。N的生成方式有两种，全局性生成器、提案者自身维护。
每个表决者在接收到提案之后，会把提案编号保存在本地。这样每个表决者都有一个最大编号，假设是maxN。而每个表决者只会accept编号大于自己本地maxN的提案。
最终只有一个提案被选定
一旦一个提案被选定，那么learner会同步该提案到本地。
当然，没有提案选出就不会有提案被选定
提交提案的两种算法
2PC和3PC算法：
2PC算法：Tow Phase Commit 即，prepare->accept
3PC算法：Three Phase Commit 即，prepare->accept->commit
区别就是accept阶段是否有commit功能。
3PC算法描述
3PC算法一共有三个阶段，准备，接收，提交。
prepare准备阶段：
提案者准备一个编号N的提议，然后向决策者发送prepare(N)，用于试探集群是否支持该提案。
每个决策者本地都有一个maxN，当接收到prepare(N)的时候，会与自己的maxN进行比较，有几种情况。
若N小于maxN，说明该提案已经过时，那么就不回应或者回应error，来拒绝该提案。
若N大于maxN，说明决策者可以接收该提案，会返回一个Proposal(myid,maxN,value)，曾经接收的最大maxN的提案，来表示自己愿意接收该提案。myid就是该提案者的id，maxN就是该提案的编号，value就是提案的值。如果是第一次接收，就都是null。
accept接收阶段
若提案者，接收到超过半数的反馈之后，那么提案者就会把真正的提案Proposal(myid,N,value)，发送给所有的决策者。
当决策者接收到提案之后，会再次与本地的maxN或者prepare记录下的N，进行比较，若N大于等于该编号，那么决策者就会accept该提案，并返回给提案者。否则，就会拒绝该提案
若提案者没有接收到超过半数决策的反馈的accept。那么，要么放弃提案，要么递增编号，重新提交请求，从prepare开始。
commit提交阶段
若提案者接收到超过半数的反馈，就会向外发送广播信息
向accept的决策者发送“可执行数据同步信息”，让决策者执行曾经接收到的提案。
向未反馈的决策者，发送“提案+可执行信息”，让他们接收到后马上执行。
2PC算法过程
2PC就是没有提交过程，就是在prepare成功之后，会把真正的提交直接发送给决策者，决策者接收到提案后会直接执行数据同步。不用等到commit消息。2PC是有较多的弊端的，但是效率较高。
paxos算法的活锁问题
活锁：活锁就是一直重复尝试-失败-尝试-失败的过程，但是活锁有可能自己解开。就是如果有很多提案一直提交，有可能某个提案一直失败，一直递增N，一直重试还是失败，但是有可能某次就成功了。
#ZAB协议 ZAB：zookeeper Atomic Broadcast，zk原子性广播协议。专门为zk设计的支持崩溃恢复的广播协议，用来实现分布式系统中数据一致性。ZAB使用一个单一进程来处理所有的写请求。当服务器数据状态放生变更了之后，集群才用ZAB广播协议，以事务提案Proposal的方式广播给所有的副本。ZAB协议能够保证一个全局唯一递增的xid。zk客户端发送读请求的时候，如果接受者不是leader，那么就会把请求转发给leader，只有master能够处理写请求。
paxos和ZAB
ZAB是paxos的工业实现，目的是构建一个高可用的分布式数据主从系统，follower是leader的从机，leader挂了可以马上从follower选一个leader。ZAB为了解决活锁问题，只允许一个进程提交提案，属于3PC提交。而，leader挂了时候选举算法是2PC，所有的follower都可以提交，就是我选我。
三种角色
leader：zk中写请求的唯一处理者，也能处理读请求。
follower：处理读请求、对leader的提案进行表决、同步leader的结果、具有选举权和被选举权
observer：没有表决权。只能处理写请求、没有选举和被选举权。 learner=follower+observer
三个数据
zxid：64位长度，高位32位是epoch，低32为xid
epoch：每个leader都有一个新的epoch，可以认为是年代????
xid：流水号。
三种模式
zk中有三种模式，没有明显的分界线，都交织在一起
恢复模式：包含两个重要阶段，leader选举和初始化同步
广播模式：包含两类，初始化广播和更新广播
同步模式：包含两类，初始化同步和更新同步
同步模式
初始化同步：恢复模式中有两个阶段，leader选举和初始化同步，当leader选出来之后只是一个准leader，只有经过初始化同步之后，才是一个真正的leader。 同步过程：
Leader为保证向每一个learner发送的有序性，会为每一个learner准备一个对列。
Leader将那些没有被learner同步到的事务封装成proposal放入队列。
Leader将proposal发送给learner并加上commit消息，表示事务已经提交，可以直接执行。
learner接收到消息后，同步到本地
向leader发送ack消息
Leader接收到ack消息之后，会把learner加入到可用的follower列表会在observer列表。如果没有返回ack或者ack没有被leader收到，就不会加入到可用列表中。
消息广播算法： 当leader完成同步之后，就进入正常的工作状态，如果有写请求，过来那么leader会执行以下过程。
leader接收到事务后，会为该事务生成一个全局唯一的id，zxid，并且将事务封装更一个Proposal。
Leader获取到所有的follower列表，并通过每个follower的队列，把proposal发送给follower
follower接收到proposal之后会与自己本地已经保存的最大zxid进行比较，如果当前的zxid较大，则把proposal保存到本地日志事务中，并返回ack
当leader收到超过半数的ack之后，就会向所有的follower发送commit消息，把proposal发送给observer。
当follower接收到commit消息之后，会把事务正式更新到本地。而observer接收到proposal会直接更新到本地。
follower和observer更新完消息之后，就会向leader反馈ack。
四种状态
每台主机，在不同的节点会有不同的状态
LOOKING:选举状态
FOLLOWER:follower正常的工作状态
OBSERVERING:observer正常的工作状态
LEADING:leader正常的工作状态
observer数量问题
observer数量并不需要太多，虽然observer能够在一定程度上提高系统的吞吐量，但是需要从leader同步数据。而Observer的同步时间是小于follower的同步时间的，当follower同步完成observer同步也就结束了，同步完成的observer会被加入到可用列表，而没有同步完成的observer无法提高服务，就会造成资源浪费。
恢复模式的三个原则：
主动让出原则：若leader收到follower心跳的数量没有过半，那么leader会任务自己与集群连接出现问题，会自动把自己的状态改成LOOKING，重新去查找leader。而去他的follower发现超过半数的主机任务失去leader，会重新进行选举
已处理的消息不能丢：如果有的follower还没收到commit消息的时候leader挂了，那么就会导致该事务有的server执行了有的没有。当新的leader被选出，经过恢复模式后，就需要保证集群中所有server执行了之前部分server执行的事务。
被丢的消息不能再现：当一个事务被通过，leader已经更新到本地了，但是还没向follower发送commit之前挂了。这台机器再次成为follower的时候，本地上就会比其他机器多一个事务，是不行的。因此，类似这样的事务是应该被丢弃的。而这种情况，服务端也不会向客户端返回成功的消息。
作者：皮皮熊大白
链接：https://juejin.cn/post/6844904114443436039