上次跟师弟聊完了一些Spring相关的知识点。小辈们很开心，不过上次有个小辈给我留言，我出去面试的时候，面试官问了我一个很急的问题：你用过zookeeper吗？作为注册中心，如何保证CP？为了建立起同学们的信任感，这次给大家讲讲zookeeper中的共识选举算法Paxos算法。什么是上限？CAP理论是指在分布式系统中，不可能同时满足Consistency（一致性）、Availablity（可用性）、Partitiontolerance（分区容错）。性）这三种基本需求最多只能满足其中的两种。一致性：不同副本之间的数据是一致的，在进行数据更新后，副本仍然可以处于一致的状态。可用性：系统提供的服务必须始终可用，每次对系统的请求都能在设定的时间内得到正常的结果返回。分区容忍：分布式系统在遇到任何网络分区故障时，仍然需要能够对外提供满足一致性和可用性要求的服务，除非整个网络环境完全瘫痪。什么是三二原则？对于分布式系统，在CAP原则中，必须保证P。如果没有分区容错，系统就太脆了，但不能同时保证一致性或可用性。现在我们在分布式系统中，如果满足一致性，必然会损失可用性，而如果满足可用性，则必然会损失一致性。所以对于分布式系统，CAP原则要么满足AP，要么满足CP，也就是三二原则。Zookeeper和Eureka的区别？Zookeeper遵循CP原则，保证了一致性，失去了可用性。体现在当Leader宕机时，zk集群会立即选举出新的Leader，但选举过程处于瘫痪状态。所以它不符合可用性。Eureka遵循AP原则，保证高可用，丢一次执行。每台服务器之间有心跳检测机制，每台服务器都可以读写，通过心跳机制完成数据共享和同步，所以当一台机器宕机时，其他机器可以正常工作，但此时可能宕机本机的机器还没有进行数据共享同步，所以不满足一致性。言归正传，基本就到这里跟大家聊一聊，直接开始写吧！！！Paxos算法Paxos算法是一种基于消息的高度容错的共识算法。GoogleChubby的作者MikeBurrows表示，世界上只有一种共识算法，那就是Paxos，其他所有共识算法都是Paxos算法的不完整版本。Paxos算法是公认的比较晦涩的算法，在工程实现上难度也很大。所以Paxos算法主要用来解决我们分布式系统中如何基于投票达成共识。前置算法首先要了解的是算法中的三个角色：Proposer（提议者）、Acceptor（决策者）、Learners（人群），一个proposal会有多个决策者（Acceptor），但是在一个集群，proposer（可能有多个Proposer，不同的Proposer会提出不同的proposal。Paxos算法特点：如果没有提出proposal，则不会选择proposal。每个proposer在提出proposal时，首先会得到一个全局唯一且递增提案编号N，即整个集群中唯一的编号N，然后将这个编号分配给待提案的提案。（在zookeeper中为zxid，由epoch和xid组成）每个voter接受一个提案后，它会在本地记录提案的编号N，这样每个voter中保存的已接受提案就会存在一个编号最大的提案，其编号假设为maxN，每个voter只会接受编号更大的提案比他们自己的本地maxN。最终只能在众多提案中选择一个提案。一旦一个提案被选中，其他服务器会主动同步（Learn）该提案到本地。Paxos算法的整个选举过程可以分为两个阶段来理解。Stage1这个阶段主要是准备阶段。提议者（Proposer）准备提交编号为N的提案，因此它首先向所有投票者（Acceptors）发送prepare(N)请求，测试集群是否支持编号为N的提案。提议。每个决策者（接受者）在其已接受的提案中保存最大数量maxN。当投票者收到来自另一台主机的prepare(N)请求时，它将N的值与maxN进行比较。如果N小于maxN，则意味着该提案已过时，当前投票者通过不响应来拒绝准备请求。如果N大于maxN，则意味着该提议是可以接受的。当前投票者会先记录N，并将已经接受的数量最多的提案Proposal(myid,maxN,value)反馈给提议者，以表明提议者支持该提议的意愿。第一个参数myid代表voterAcceptor的标识id，第二个参数代表它接受的proposal的最大个数maxN，第三个参数代表proposal的真实内容值。如果当前投票者还没有接受任何提案（第一次初始化时），Proposal(myid,null,null)将被反馈给提议者。N在现阶段不可能等于maxN。这是由N的生成机制决定的，要获得N的值，必须在原值的基础上通过同步锁来增加值。Phase2.当前阶段是真正的发送和接收阶段，也称为Accept阶段。当提议者（Proposer）发送prepare（N）时，如果收到半数以上决策者（Accepters）的反馈，提议者将其真正的提议Proposal（N，value）发送给所有投票者。当决策者（Acceptor）收到提议者发送的Proposal(N,value)提议时，会再次取出自己已经接受的提议中的最大数量maxN，以及自己记录的最大准备数量，所以即N和There进行比较，如果N大于或等于这两个数，则当前投票者接受该提议，并反馈给提议者。如果N小于这两个数，则决策者不采取任何反应来拒绝该提议。如果proposer没有收到半数以上投票者的accept反馈，则重新进入prepare阶段，递增proposalnumber，重新提交prepare请求。如果提议者收到的反馈数量超过一半，它会广播两种信息：还没有发送accept反馈给他们发送一个“proposal+executabledatasynchronizationsignal”，表示他们接受了proposal并立即执行。看到这里，可能很多同学都懵了，这什么鬼？为了加深理解，让整个过程更加通俗易懂，举个例子吧！！！假设现在我们有三台主机服务器可以选择leader（也可以选择其他服务器比较多，这里为了方便和容易理解，选择少一点）。因此，这三台主机分别充当Proposer、Acceptor、Learner（crowd）三个角色。所以假设现在开始模拟选举，三个服务分别开始获取N的值（一个全局唯一且递增的提案数N）。此时serverOne（宿主1）对应这个ProposerOne（提议者1），serverTwo（宿主2）对应ProposerTwo（提议者2），serverThree（宿主3）对应ProposerThree（提议者3）。为了让整个过程更简单明了，更好理解流程。它们的初始N值具体设置为ServerOne(2)、ServerTwo(1)、ServerThree(3)，所以它们都需要发送给提案（Proposal）给决策者（Acceptor），让它们投票决定名词性决议提案（Proposal）：提案人发送给决策者的中间数据的封装称为提案。同时，每个提议者（Proposer）向其中的两个决策者（Acceptor）发送提议消息。所以假设：ProposerOne（提议者1）向AcceptorOne（决策者1）和AcceptorTwo（决策者2）、ProposerTwo（提议者2）向AcceptorTwo（决策者2）和AcceptorThree（决策者3）、ProposerThree（提议者3）发送提案给AcceptorTwo（决策者2）和AcceptorThree（决策者3）的消息。为了简化流程结构，我给其中2个发了proposal，但是已经超过了一半的票数。当然你也可以选择更多的hosts，发送更多的proposals，但是过程稍微复杂一点，也比较难理解。请注意，必须有超过一半的选票。那么整个画面可以如下图所示：那么根据上图，开始进入到第一阶段，按照我们上面假设的流程开始执行流程。Acceptor1）和AcceptorTwo（决策者2）第一次收到ProposerOne（提议者1）提案（Proposal）。由于是第一次收到提案（Proposal），本地没有存储最大N值，所以他们都接受了。ProposerOne（提议者1）提案。所以AcceptorOne（决策者1）和AcceptorTwo（决策者2）都会提议返回ProposerOne（提议者1）告诉我，我同意你的提议。同时，AcceptorOne（决策者1）和AcceptorTwo（决策者2）如果要接受其他N个小于2的值，则不会回复提案，因为当前收到的最大提案数N为2，存储在本地.而ProposerOne（提议者1）已经收到了一半以上的回报，所以此时提案通过：AcceptorOne（决策者1）局部N值为2AcceptorTwo（决策者2）局部N值为2AcceptorThree（决策者3）本地N当ProposerTwo（提议者2）收到ProposerTwo（提议者2）给AcceptorTwo（决策者2）和AcceptorThree（决策者3）的提议（Proposal）时，该值为null。因为AcceptorTwo（决策者2）之前接受过ProposerOne（提议者1）的提议，所以本地的N值已经存储为2。当ProposerTwo（提议者2）的N值为1时，小于存储的最大N本地。Value，所以不会通过，不会回复ProposerTwo（提议者2）和AcceptorThree（决策者3），因为是第一次收到提案，没有最大N值，所以同意提案（Proposal）并返回当前提案。更新本地N值。最终ProposerTwo（提议者2）只收到AcceptorThree（决策者3）的同意反馈，选择不超过一半，所以没有通过。此时：AcceptorOne（决策者1）局部N值为2AcceptorTwo（决策者2）局部N值为2AcceptorThree（决策者3）局部N值为1ProposerThree（提议者3）到AcceptorTwo（决策者2）和AcceptorThree（决策者3）当AcceptorTwo（决策者2）和AcceptorThree（决策者3）收到来自ProposerThree（提议者3）的Proposal时。因为AcceptorTwo（决策者2）和AcceptorThree（决策者3）都去过提案（Proposal），所以当AcceptorTwo（决策者2）收到ProposerThree（提议者3）的提案时，局部N值2小于ProposerThree（Proposer3）的N值为3，所以通过proposalAcceptorThree（decisionmaker3）因为本地接收到的最大值为1，所以这一pass也通过了proposal，此时的N值更新为3.最后，ProposerThree（提议者3）收到了超过一半的同意反馈，因此通过。此时：AcceptorOne（决策者1）局部N值为2AcceptorTwo（决策者2）局部N值为3）和AcceptorThree（决策者3）在没有过半票的情况下发出了提案。因此，将重新获得最大N值（全局唯一且递增的提案编号N）。此时ProposerTwo（提议者2）在本地获得的N值为4，因此会为AcceptorTwo（决策者2）发起另一轮投票，当AcceptorThree（决策者3）收到来自ProposerTwo的提案（Proposal）时（提议者2)再次。AcceptorTwo（决策者2）和AcceptorThree（决策者3）本地存储的最大N值小于最新的ProposerTwo（提议者2）的当前N值4，所以它们都返回proposal，并在ProposerTwo时更新本地N值（proposer2）当N值为1时，小于本地存储的最大N值，因此不会通过，也不会回复ProposerTwo（Proposer2）。最终，ProposerTwo（提议者2）获得了超过半数的认可反馈，因此通过了。此时：AcceptorOne（决策者1）局部N值为2AcceptorTwo（决策者2）局部N值为4AcceptorThree（决策者3）局部N值为4现在第一阶段的工作已经完成，整个过程文字很多，看来要多看几遍。同时我也给大家画了一个流程图如下：既然上面已经完成了第一阶段，那么接下来的阶段一定是第二阶段的过程。同时整体第二阶段可以分为两部分来理解，第一部分是正式提交提案，第二块是第一阶段投票确定阶段的结果：ProposerProposerOne（提议者1）局部N值为2ProposerTwo（提议者2）局部N值为4ProposerThree（提议者3）局部N值为3AcceptorAcceptorOne（决策者1）局部N值为2AcceptorTwo（决策者2）局部N值为4AcceptorThree（decisionmaker3)LocalNvalueis4第一块：ProposerOne（提议者1）正式向AcceptorOne（决策者1）和AcceptorTwo（决策者2）发送提案，通过第一阶段的结果，我们可以知道只有AcceptorOne（决策者1）投票，AcceptorTwo（决策者2）因为小于本地N值而没有通过ProposerTwo（提议者2）正式向AcceptorTwo（决策者2）和AcceptorThree（决策者3）发送提案。同样，通过第一阶段的结果，可以知道两个决策者都通过了，所以超过半数的票数ProposerThree（提议者3）正式发布提案GoingtoAcceptorTwo（决策者2）和AcceptorThree（决策者3）),通过第一阶段的结果，我们可以知道两个决策者都没有通过第二个区块：从上面第一个区块的结果来看，只有**ProposerTwo（提议者2）**获得了一半的同意，因此ProposerTwo（提议者2）可以立即成为领导者。至此，选举状态结束，即ProposerTwo（提议者2）会广播给所有的学习者，通知他们过来同步数据。当数据同步后，整个服务器集群就可以正常工作了。总结整个Paxos算法流程还是比较难理解的。为了理解里面的流程，还是以最简单的例子来说明。也可以有更多的机器发起更多的提议。但是整个过程比较难理解。理解Paxos算法需要根据以上两个阶段来理解。第一阶段是做什么，得到什么结果，第二阶段是在第一阶段的结果基础上实施什么样的选举过程。这是每个人都需要思考的重点。这里主要给大家分享一下Paxos算法的选举过程，还有很多其他的优化版本比如FastPaxos、EPaxos等等。Zookeeper中Zookeeper的选举算法是FastPaxos算法。为什么要使用Fastpaxos？FastPaxos算法是Paxos的优化版本，解决了Paxos算法的活锁问题，保证每个线程获得唯一的N值。ZAB（ZookeeperAtomicBroadcast）原子广播协议ZAB其实就是上述算法的一种实现，所以Zookeeper也依赖于ZAB来实现分布式数据的一致性。所以在zookeeper中，只有一台server机器作为leader机器，所以当client连接到机器的某个节点，当client提交读取数据的请求时，那么当前连接的机器节点会保存自己的数据被退回。当客户端提交写入数据的请求时，会先检查当前连接的节点是否为leader节点。如果不是leader节点，则转发给leader机器的节点，由leader机器写入，然后广播通知其他节点过来同步数据。ZAB中的Leader角色分为三类：ZK集群的领导者，唯一可以写入数据的机器。Follower：在ZK集群中具有一定地位的worker。它只能读取数据。当领导者（leader）机器挂了，就可以参与选举投票。观察：最小的工作男孩只能读取数据。即使leader（领导者）机器宕机，也与他无关，不能参与选举投票。ZAB中的三个关键数据Zxid：zookeeper中的事务ID，Long型数据，总长度为64位。有两部分。前32位为epoch，后32位为xidEpoch：每个leader都会有这个值，表示当前leader获得的最大N值，可以理解为“age”xid：事务ID，表示当前zookeeper集群当前提交的事务ID是多少（watch机制），这样选举过程后不会出现重复执行或遗漏事务等特殊情况。这里分享zookeeper中的一些知识点，因为这里面的东西很多很多，比如Session，Znode，Watcher机制，ACL，三种状态模式，zookeeper是如何实现分布式事务锁的等等，没办法讲一下子给大家。这次主要是想让同学们了解Zookeeper中的一致性算法是如何保证的。最后，对于面试，如果你能把这个共识算法完整的解释给面试官，那你就已经领先了。整个过程还是比较复杂的，需要一直看多画图才能理解。在这个互联网内卷时代，只有比别人知道的更多，才能比别人走得更远。最后，希望我所有的学弟学妹们都能有一个好的校招结果！！！
