2019-11-12
之前在实习的时候用到了Elasticsearch，看了看它内部的实现原理，发现ES自己实现了一套分布式一致性解决方法，觉得还挺有意思的。学习过程中很多资料都提到了Zookeeper，想起来大三的时候就在hadoop里看到的Zookeeper组件但是一直不知道它是干嘛的，最近不是特别忙就研究一下Zookeeper。
ZooKeeper是一个高可用的一致性协调框架，用来为分布式应用提供一致性服务的软件，提供的功能包括：配置维护、域名服务、分布式同步、组服务等。这些功能实现起来非常复杂，但Zookeeper可以提供给开发者性能高效，功能稳定的服务。
ZooKeeper为了高可用的一致性协调，实现了一种通用的一致性算法ZAB（ZooKeeper Atomic Broadcast）
ZAB是在Fast Paxos算法基础上进行了扩展改造而来的，另一种一致性算法Raft也和ZAB非常类似，所以为了弄懂Zookeeper实现原理，我们比较这三种分布式一致性算法（Paxos，raft和ZAB）的异同：
首先，我们来介绍一下Paxos算法，Lamport大神在1990年提出的这个基于消息传递且具有高度容错特性的一致性算法，他提出了三种Paxos算法：Basic Paxos，Multi Paxos和Fast Paxos。Basic Paxos只能对一个值形成决议，决议的形成至少需要两次网络来回，所以一般只用来进行理论研究；Multi Paxos和Fast Paxos则对它进行一系列的改动，使更适合直接应用在实际项目中。
Basic Paxos
Paxos算法运行在允许宕机故障的异步系统中，不要求可靠的消息传递，可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。
Paxos将系统中的角色分为提议者 (Proposer)，决策者 (Acceptor)，和最终决策学习者 (Learner)：
Proposer: 提出提案 (Proposal)。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
Acceptor：参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
Learner：不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）
Paxos算法通过一个决议分为两个阶段：
Prepare阶段：Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺
Accept阶段：Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
| Proposer | Acceptor |
|---|---|
| 1. 选择一个proposal number n | |
| 2. 广播Prepare(n)和Value给所有的Accepter | |
| 3. 回复Prepare(n): 如果n > minProposal，则minProposal = n，同时将acceptedProposal和acceptedValue返回 |
|
| 4. Proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value； 如果没超半数，则重新发起Prepare请求 |
|
| 5. 广播Accept(n, value)给所有Accepter | |
| 6. Acceptor比较n和minProposal 如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal |
|
| 7. Proposer接收到超半数的成功回复后，将结果通知给所有Learner；如果没到半数，则重新发起Prepare请求 |
Multi Paxos
原始的Paxos算法只能对一个值进行决议，而且每次决议至少需要两次网络来回，在实际应用中可能会产生各种各样的问题，所以不适合直接应用在实际工程中。因此，Multi Paxos解决了这一问题，可以连续确定多个值并提高效率，基于Basix Paxos主要做了如下改进：
所以Multi Paxos的实际过程是：首先进行Leader选举，利用Basic Paxos来实现。选出Leader后，只由Leader来提交Proposal，如果Leader出现宕机，则重新选举Leader，在系统中仅有一个Leader可以提交Proposal。
Multi Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。
Fast Paxos
在之前提到的Paxos协议中，消息最后到达Learner一般都要经历 Client–>Proposer–>Acceptor–>Learner 总共3个步骤；为了更快的让消息到达Learner，可以跳过Proposer这一步，直接将请求发送给Accepter，由Leader在中间进行检查。
基于Paxos，Zookeeper实现了ZAB算法，个人感觉ZAB和Multi Paxos更像一点。
ZAB的算法流程为：
Leader election：leader选举过程，electionEpoch自增，在选举的时候lastProcessedZxid越大，越有可能成为leader
Discovery：
Synchronization：
follower中的事务日志和leader保持一致的过程，就是依据follower和leader之间的lastProcessedZxid进行，follower多的话则删除掉多余部分，follower少的话则补充，一旦对应不上则follower删除掉对不上的zxid及其之后的部分然后再从leader同步该部分之后的数据
Broadcast
正常处理客户端请求的过程。leader针对客户端的事务请求，然后提出一个议案，发给所有的follower，一旦过半的follower回复OK的话，leader就可以将该议案进行提交了，向所有follower发送提交该议案的请求，leader同时返回OK响应给客户端
Raft算法是因为该作者觉得Paxos太难以理解了，所以就提出了Raft，一定程度上也可以看作是Paxos的一种改进。它强化了leader的地位，把整个协议可以清楚的分割成两个部分，并利用日志的连续性做了一些简化： （1）Leader在时。由Leader向Follower同步日志 （2）Leader挂掉了，选一个新Leader，Leader选举算法。
算法演示：（这个演示很简单明白，就不用文字讲了）
由于Paxos偏理论，Raft和ZAB又都是基于他实现的，他们在整体思路上有一些地方还是挺像的，但细节上有些不同，所以我们主要比较这两种算法，下面是我总结的几个区别：
Zookeeper在设计了一套分布式一致性算法后，提供了一系列的基本特性，供开发者使用：