大家好，我是指北君。今天，我想学习下zookeeper，毕竟微服务这么火，立志不当最菜程序员的我也不能掉队。

但是，这个zookeepr我也没用过，只能从这个理论基础学起了，最终目的就是对它这个源码也得有个大概的了解。啥，你问我为啥要学习源码？平时也不用！！ 那你要看下为啥现在刚毕业00后的都张口闭口了解各种源码了，不卷能行么，不到35就得退休了。

今天就给大家聊下，对于这个zk理论的学习。

Paxos算法 {#paxos算法}

我从网上了解到呀，这个 zookeeper 最难理解的就是 Paxos 算法，啥破玩意，听过各种算法就是没听过这个 Paxos 呀。

没办法，先百度一把。。

Paxos 算法是莱斯利·兰伯特(Leslie Lamport)1990 年提出的一种基于消息传递的、具有 高容错性 的一致性算法。Google Chubby 的作者 Mike Burrows 说过，世上只有一种一致性算法， 那就是 Paxos，所有其他一致性算法都是 Paxos 算法的不完整版。Paxos 算法是一种公认的 晦涩难懂 的算法，并且工程实现上也具有很大难度。较有名的 Paxos 工程实现有 Google Chubby、 ZAB、微信的 PhxPaxos 等

不知道大家看懂没，好着挺牛逼的，注意关键词， 消息传递 、高容错、一致性 ， 还什么世上只有一种一致性算法 ，就是 Paxos 。 好像挺牛逼呀，嗯！必须得学。 等等， 继续看， 公认的 晦涩难懂 的算法 ？ 指北君着不认怂的性格，今天必须整会，盘它。

那先来看下这个算法是用来干啥，到底能解决啥问题？

Paxos 算法是用于解决什么问题的呢? Paxos 算法要解决的问题是，在分布式系统中如何 就某个决议达成一致。

Paxos与拜占庭将军问题 {#paxos与拜占庭将军问题}

拜占庭将军问题，算法书中好像是有提到过吧，我们还是先从维基百科上看下对它的描述：

相信大家小时候语文课应该不是体育老师教的，说白了就是9个将军一起攻城，为了防止有人进攻有人观望（行动要一致），9个大老爷们就决定少数服从多数，每人一票 过半 就搞。

那拜占庭将军问题就在于，这9个人要是有叛徒咋办? 假如4个人投进攻，4个人投撤离，可恶的叛徒给进攻的那四个人送信说进攻，给撤离的四个人写信说进攻，那大家的行动就发生了不一致了，对于主进攻的人来看确实是5票，过半了，直接开干。 然而主张撤离的四个人收到的撤离消息也过半了，结果就是大家的行动不一致，团队散了，结果可想而知。

计算机系统 {#计算机系统}

那对于分布式网络系统来说，上面的9个人就可以对应9台计算机，每台计算机有可能出错而导致消息发错，也有可能消息在网络传输过程中被拦截伪造，结果都是一样的，传递的消息不可靠。

拜占庭将军问题就是分布式系统中一致性问题的最难解决问题之一。

我们想想也可以窥探一二，毕竟传输的人和传输的信道都不安全，这个就是信息安全的问题，就得加密，验签等方法了。

不过拜占庭将军问题和我们今天学的 Paxos 算法关系并不是要解决这个问题，而是假设这个问题不存在提出来的算法。。。

这个，其实也毛病，解决不了，我们跳过嘛，灵活变通，😂🙅

拜占庭将军问题是由 Paxos 算法作者莱斯利·兰伯特提出的点对点通信中的基本问题。该问题要说明的含义是，在不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所 以，Paxos 算法的前提是不存在拜占庭将军问题，即信道是安全的、可靠的，集群节点间传 递的消息是不会被篡改的。

作者解释说，在不可靠的信道上试图通过消息传递的方式达到一致性是不可能的，大家记住这个就好。

一般情况下，分布式系统中各个节点间采用两种通讯模型:共享内存(Shared Memory) 、消息传递(Messages Passing)。而 Paxos 是基于消息传递通讯模型的。

Paxos算法描述 {#paxos算法描述}

先来看下算法中都涉及些什么角色。

三种角色 {#三种角色}

在 Paxos 算法中有三种角色，分别具有三种不同的行为。注意哦，很多时候，一个进程可能同 时充当着多种角色。

• Proposer: 提案者，提出提案（Proposal）；
• Acceptor: 表决者；
• Learner: 学习者(同步者，即 Proposer 决议形成，将所有形成的决议发送给Learners)

这个没啥好说的，看不懂别急，后面还有图来看看这三位到底能干啥。

Paxos算法流程 {#paxos算法流程}

Paxos 算法的执行过程划分为两个阶段: 准备阶段 prepare 与 接受阶段 accept。Ps: Learn阶段之前决议已经形成。

由于Paxos算法是晦涩难懂的，这里我将以自己的理解来做整个描述，虽然可能在严谨性上会差强人意，但是可读性会提高，希望可以给大家更轻松的阅读体验。

A、Prepare阶段 {#aprepare阶段}

1. 提案者 (Proposer) 准备提交一个编号为 N 的提议，于是其首先向所有 表决者(Acceptor)发 送 prepare(N)请求，用于试探集群是否支持该编号的提议。 如果这里不好理解我们可以试图理解为提议者拿着钞票去贿赂 "表决者（Accept）"
2. 每个表决者（Acceptor）都保存者当前贿赂自己的最大金额数，即（maxN），当每个表决者接收到贿赂自己的提议时，会比较贿赂金额与maxN的值。有以下几种情况：
   1. 若 N 小于 maxN，则说明该提议已过时（钱少不接受），当前表决者采取不回应或回应 Error 的方 式来拒绝该 prepare 请求；
   2. 若 N 大于 maxN，则说明该提议是可以接受的（毕竟谁给的钱多听谁的），当前表决者会首先将该 N（当前贿赂金额） 记录下来， 并将其曾经已经 accept 的编号最大（之前贿赂金额最大）的提案 Proposal(myid,maxN,value) 反馈给提案者， 以向提案者展示自己支持的提案意愿。其中第一个参数 myid 表示表决者 Acceptor 的标识 id，第二个参数表示其曾接受的提案的最大编号 maxN（前老板贿赂的金额），第三个参数表示该 提案的真正内容 value（前任老板提议的内容）。当然，若当前表决者还未曾 accept 过任何提议，则会将 Proposal(myid,null,null)反馈给提案者。
   3. 在 prepare 阶段 N 不可能等于 maxN。这是由 N 的生成机制决定的。要获得 N 的值， 其必定会在原来数值的基础上采用同步锁方式增一。

这里需要说明下，为什么在表决者（Acceptor）判断贿赂金额大于当前保存的最大金额时会将前任已经保存的金额和提案内容返回给提案者，这是因为提案者（Proposer），在收到表决者的答复后，需要判断谁是最有钱的提案者，便推举它为领袖 (修改自己的提案)。

那么问题来了，既然只有提案贿赂金额大于表决者当前接受的受贿最大金额时才会返回前一个接受的受贿提案内容，会啥提案者要用这个结果还比谁时最有钱的提案呢？ 这个你想呀，提案者是将提案发送到了多个表决者，每个表决者受贿的金额也不一样呀，所以在收到所有回复后，还是需要在比一下的。

B、Accept阶段 {#baccept阶段}

经过上面的 Prepare 阶段后，大家应该了解了Paxos算法是如何准备提案的，就是发送自己的max N（贿赂金额），等所有表决者回复，那回复后该怎么干呢？

1. 当提案者 (Proposer) 发出 prepare(N) 后，若收到了超过半数 的 表决者(Accepter)的反馈， 那么该提案者就会将其真正的提案 Proposal(myid,N,value) 发送给所有的表决者。
2. 当表决者 (Acceptor)接收到 提案者 发送的 Proposal(myid,N,value) 提案后，会再次拿出自己 曾经 accept 过的提议中的最大编号 maxN，或曾经记录下的 prepare 的最大编号，让 N 与它们进行比较，若 N 大于等于 这两个编号，则当前表决者 accept 该提案，并反馈给 提案者。若 N 小于这两个编号，则表决者采取不回应或回应 Error 的方式来拒绝该提议。
3. 若 提案者 **没有接收到超过半数的 **表决者 的 accept 反馈（中间有别人以更多的金额贿赂了它），则有两种可能的结果产生。一 是放弃该提案，不再提出；二是重新进入 prepare 阶段，递增提案号，重新提出 prepare 请求。
4. 若提案者接收到的反馈数量超过了半数，则其会向外广播两类信息：
   1. 向曾 accept 其提案的表决者发送 "可执行数据同步信号"，即让它们执行其曾接收到的提案；
   2. 向未曾向其发送 accept 反馈的表决者发送"提案 + 可执行数据同步信号"，即让 它们接受到该提案后马上执行。

上述的过程中，如果某一个提议收到了大多数的表决者（Acceptor）的响应后（提案者（Proposal）中的N必须大于当前maxN才会响应），则提案通过，向所有表决者以及leaner发送同步数据，达成数据一致性。

当然上面只是简单的描述，真是的算法场景更复杂，所有提议者，决策者身份信息都是交叉的，但是流程就是这样来的。如果提议者、决策者的数量是4个,5个。。。但是你按照上面的思路进行推演，最终会发现最终是唯一一个提议获取多数票而胜出，从而其他提议者和决策者同步此提议。

Paxos算法一致性 {#paxos算法一致性}

那了解Paxos算法，我们来看下Paxos 算法的一致性主要体现在以下几点:

• 每个提案者在提出提案时都会首先获取到一个具有全局唯一性的、递增的提案编号N，即在整个集群中是唯一的编号 N，然后将该编号赋予其要提出的提案。
• 每个表决者在accept某提案后，会将该提案的编号N记录在本地，这样每个表决者中保存的就是已经被 accept 的提案中会编号最大的提案，其编号假设为 maxN。每个表决者仅会 accept 编号大于自己本地 maxN 的提案。
• 在众多提案中最终只能有一个提案被选定。
• 一旦一个提案被选定，则其它服务器会主动同步(Learn)该提案到本地。
• 没有提案被提出则不会有提案被选定。

有了这几点理论的支撑，Paxos算法就有了解决在分布式系统中复杂的一致性问题啦。

活锁问题 {#活锁问题}

啥？上面的流程可能会引发活锁问题，那么什么是活锁呢？

活锁指的是任务或者执行者没有被阻塞，但是由于某些条件没有满足，导致一直重复尝试---失败---尝试---失败的过程。处于活锁的实体是在不断的改变状态，活锁有可能自行解开。

那么上面的行为是怎么会引发活锁呢？接下来我们一起来分析下：

在整个选举过程中，每个人谁先来谁后到，"表决者" 什么时间能够接到 "提议者" 的信息，是完全不可控的；

假设，第一个提案者A（Proposal）已经成功过了prepare阶段，准备向 Acceptors 广播发送 Accept 时，有一个更有钱土豪提案者B也向决议者（Acceptors）广播了prepare请求并在 A 的 accept 请求到之前发送给了决议者，这时毫无疑问，决议者会接收该请求，并记录在册。这时候，A 的 accept 请求姗姗来迟，决议者对比此 proposal 的贿赂金额已经小于当前记录的 prepare 最大编号，因此不响应给提议者A，则提议者A收到的响应未过半，此提案废弃。这时它又用大于 Proposer A 的贿赂金额重新发起 preapre 广播请求，这时提议者B的 accept 请求还没有到达决策者（Acceptors），因此 Acceptor 也接受了该 prepare 请求，将其记录在案，在之后提议者B 发出的accept 请求到达，决议者发现贿赂金额已经小于当前prepare的最大贿赂金额，因此拒绝响应，这样就会形成活锁问题。

其实也就是我们也没有阻塞，阻塞了就是死锁了。但是没有阻塞就一直陷入无尽的循环之中，表现的结果和死锁差不多就是无法进行下一步，因此称为活锁。 不过我们懂了活锁的原理，就明白其实它是可以自行解开的，这也是它和死锁不一样的地方，死锁是人为不干预无法解开的。

总结 {#总结}

那今天指北君的学习讲到这里就基本上结束了，来给大家总结一下，其实Paxos算法主要包括两个阶段：

1. prepare阶段，这个阶段主要是准备一个编号为N的提案，首先向所有决议者（Acceptor）发送prepare请求，用于试探是否支持该编号的提议。
2. accept阶段，当一阶段提议收到了超过半数的响应，则开始正式下发提案内容proposal，如果过半则提案提交成功，广播给所有learner。

注意：编号（贿赂金额）很重要，无论在哪个阶段，编号（贿赂金额）小的，都会被鄙视（被拒绝）；

今天的分享就到这里了，学习Paxos算法过程中的一些心得，希望对小伙伴们有些启发。