zookeeper一致性算法.docx

《zookeeper一致性算法.docx》由会员分享，可在线阅读，更多相关《zookeeper一致性算法.docx（19页珍藏版）》请在第一文库网上搜索。

1、zookeeper 一致性算法上次跟学弟学妹们聊完了 Spring相关的一些知识点，学弟学妹们还是挺开心的，但是上次有学弟在跟我留言，在出去面试的时候被面试官问了个一脸蒙逼急的问题：zookeeper你用过吗？作为注册中心它是怎么如何保证CP的呢？为了对的起学弟学妹们的信赖这次跟大家具体聊聊zookeoper中的一致性选举算法Paxos算法什么是CAP?CAP理论指的是在一个分布式系统中，不可能同时满足Consistency(一致性)、Avai labl i ty (可用性)、Partition tolerance (分区容错性)这三个基本需求，最多只能满足其中的两项。一致性(Consiste

2、ncy)：数据在不同的副本之间数据是保持一致的，并且当执行数据更新之后，各个副本之间能然是处于一致的状态。可用性(Availablity)：系统提供的服务必须是处于一直可用的状态，针对每一次对系统的请求操作在设定的时间内，都能得到正常的result 返回 o分区容错性(Partition tolerance)：分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非整个网络环境全部瘫痪了。什么是三二原则？对于分布式系统，在CAP原则中，P是一定要保证的，如果没有分区容错性那这个系统就太脆落了，但是并不能同时保证一致性或者可用性，在现在我们的分布式系统中，满

3、足一致性，则必然会失去可用性,满足可用性，则必然失去一执性。所以CAP原则对一个分布式系统来说要么满足AP,要么满足CP,这就是三二原则。Zookeeper 与 Eureka 的区别？Zookeeper遵循是的CP原则，即保证了一致性，失去了可用性，体现在当Leader宕机后，zk集群会马上进行新的Leader的选举，但是选举的这个过程是处于瘫痪状态的。所以其不满足可用性。Eureka遵循的是AP原则，即保证了高可用，失去了一执行。每台服务器之间都有心跳检测机制，而且每台服务器都能进行读写，通过心跳机制完成数据共享同步，所以当一台机器宕机之后，其他的机器可以正常工作，但是可能此时宕机的机器还没

4、有进行数据共享同步，所以其不满足一致性。言归正转，基础就跟大家聊到这里了，开始直接开始正文吧！ ！Paxos算法Paxos算法是莱斯利兰伯特(Leslie Lamport) 1990年提出的一种基于消息传递的、具有高容错性的一致性算法。Google Chubby的作者Mike Burrows说过，世上只有一种一致性算法，那就是Paxos,所有其他一致性算法都是Paxos算法的不完整版。Paxos算法是一种公认的晦涩难懂的算法，并且工程实现上也具有很大难度。所以Paxos算法主要用来解决我们的分布式系统中如何根据表决达成一致。算法前置理解首先需要理解的是算法中的三种角色Proposer （提议者

5、）Acceptor （决策者）Learners （群众）一个提案的决策者（Acceptor）会存在多个，但在一个集群中提议者（Proposer）也是可能存在多个的，不同的提议者（Proposer）会提出不同的提案。paxos算法特点： 没有提案被提出则不会有提案被选定。 每个提议者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号N,即在整个集群中是唯一的编号N,然后将该编号赋予其要提出的提案。（在zookeeper中就是zxid,由epoch和xid组成） 每个表决者在accept某提案后，会将该提案的编号N记录在本地，这样每个表决者中保存的已经被accept的提案中会存在一个编

6、号最大的提案，其编号假设为maxNo每个表决者仅会accept编号大于自己本地maxN的提案。 在众多提案中最终只能有一个提案被选定。 一旦一个提案被选定，则其它服务器会主动同步（Learn）该提案到本地。Paxos算法整个选举的过程可以分为两个阶段来理解。阶段一这个阶段主要是准备阶段发送提议提议者（Proposer）准备提交一个编号为N的提议，于是其首先向所有表决者（Acceptor）发送prepare （N）请求，用于试探集群是否支持该编号的提议。每个决策者(Acceptor)中都保存着自己曾经accept过的提议中的最大编号maxNo当一个表决者接收到其它主机发送来的prepare (N

7、)请求时，其会比较N与maxN的值。若N小于maxN,则说明该提议己过时，当前表决者采取不回应来拒绝该prepare请求若N大于maxN,则说明该提议是可以接受的，当前表决者会首先将该N记录下来，并将其曾经己经accept的编号最大的提案Proposal (myid, maxN, value)反馈给提议者，以向提议者展示自己支持的提案意愿。其中第一个参数my id表示表决者Acceptor的标识id,第二个参数表示其曾接受的提案的最大编号maxN,第三个参数表示该提案的真正内容valueo若当前表决者还未曾accept过任何提议(第一次初始化的时候)，则会将Proposal (myid, nu

8、ll, null)反馈给提议者。在当前阶段N不可能等于maxN。这是由N的生成机制决定的。要获得N的值，其必定会在原来数值的基础上采用同步锁方式增一阶段二当前阶段要是真正的发送接收阶段又被称为Accept阶段 当提议者（Proposer）发出prepare（N）后，若收到了超过半数的决策者（Accepter）的反馈， 那么该提议者就会将其真正的提案Proposal （N, value）发送给所有的表决者。 当决策者（Acceptor）接收到提议者发送的Proposal （N, value）提案后，会再次拿出自己曾经accept过的提议中的最大编号maxN,及曾经记录下的prepare的最大编号

9、，让N与它们进行比较，若N大等于于这两个编号，则当前表决者accept该提案，并反馈给提议者。若N小于这两个编号，则决策者采取不回应来拒绝该提议。 若提议者没有接收到超过半数的表决者的accept反馈，则重新进入prepare阶段，递增提案号，重新提出prepare请求。若提议者接收到的反馈数量超过了半数，则其会向外广播两类信息： 向曾accept其提案的表决者发送“可执行数据同步信号”，即让它们执行其曾接收到的提案 向未曾向其发送accept反馈的表决者发送“提案+可执行数据同步信号”，即让它们接受到该提案后马上执行。看到这里可能很多学弟都是一脸懵逼，什么鬼？为了加深理解，让整个过程更加的透

10、明，还是举例说明一下吧！ ！假设现在我们有三台主机服务器从中选取leader （也可以选择其他的更多的服务器，为了比较方便容易理解这里选少一点）。所以这三台主机它们就分别充当着提议者（Proposer）、决策者（Acceptor）、Learners （群众）三种角色。所以假设现在开始模拟选举，三台服务分别开始获取N （具有全局唯一性的、递增的提案编号N）的值，此时serverOne（主机1）就对应这个ProposerOne （提议者 1）、serverTwo （主机 2）对应 ProposerTwo （提议者 2）、serverThree （主机 3）对应 ProposerThree （提议者

11、 3）。为了整个流程比较简单清晰，过程中更好理解。他们的初始N值就特定的设置为ServerOne （ 2）、ServerTwo （ 1）、ServerThree （ 3）,所以他们都要发送给提议（Proposal）给决策者（Acceptor）,让它们进行表决确定名词解析提议（Proposal）：提议者向决策者发送的中间数据的包装简称提议。同时每个 提议者（Proposer）向其中的两个决策者（Acceptor）发送提案消息。所以假设：ProposerOne （提议者 1）向 AcceptorOne （决策者 1）和 AcceptorTwo （决策者 2）、ProposerTwo （提议者 2）

12、向 AcceptorTwo （决策者 2）和 Ac cep tor Three （决策者 3）、ProposerThree （提议者 3）向 AcceptorTwo （决策者 2）和 AcceptorThree （决策者3）、发送提案消息。为了流程结构简单就向其中的2台发送提案，但是也是已经超过半票了，当然也可以多选几个主机,多发送提案，只是流程就复杂了一点不好理解了。注意点就是一定要超过半票。那么整个图可以如下所示：ProposerOne（提议者 1）2 （提案编号N）AcceptorOne（决策者 1）所以根据上面的图开始走第一阶段按照上面我们假设的流程开始执行流程当ProposerTwo

13、 （提议者2）的N值为1的时候，小于本地存的最大NAcceptorOne （决策者1）和AcceptorTwo （决策者2）第一次收到ProposerOne （提议者1）的提议（Proposal）,由于是第一次收到提议（Proposal）,本地没有存储最大的N值，所以都会接受ProposerOne （提议者1）的提议。所以AcceptorOne （决策者1）和AcceptorTwo （决策者2）都会提议返回给ProposerOne（提议者1）告知我赞同你的提议。同时AcceptorOne （决策者1）和AcceptorTwo （决策者2）因为收到的当前的最大提议编号N为2,并且保存在本地，所以

14、想接受到其他的N值小于2时则不会回复提议。而ProposerOne （提议者1）己经收到超过半数返回，所以提议通过此时：AcceptorOne （决策者1）本地N值为2AcceptorTwo（决策者2）本地N值为2AcceptorThree （决策者3）本地N值为nullProposerTwo （提议者 2）向 AcceptorTwo （决策者 2）和 AcceptorThree （决策者 3）AcceptorTwo （决策者 2）和 AcceptorThree （决策者 3）收到ProposerTwo （提议者 2）的提议（Proposal）时。因为 AcceptorTwo （决策者2）之前

15、己经接受过ProposerOne（提议者1）的提议，所以本地的N值已经存储了 2值，所以不给予通过，也就不回复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）收到Prop