zookeeper分布式一致性：分布式学习之zookeeper-4

分布式学习之zookeeper-4一致性协议CAP理论：

• Consistency一致性，数据在多个副本之间能够保持一致性。
• Availability可用性，指系统服务必须一直处于可用状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。
• Partition tolerance 分区容错性，在任何分区故障时候，仍然能够保证对外满足一 致性和可用性的服务。

一个分布式系统无法不可能同时做到三个指标。这个结论就叫做 CAP 定理

BASE理论

BASE是Basically Available（基本可用）、Soft state（软状态）和Eventually consistent（最终一致性）三个短语的缩写。BASE理论的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。

1、基本可用：

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。

2、软状态：

软状态指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

3、最终一致性

最终一致性强调的是所有的数据副本，在经过一段时间的同步之后，最终都能够达到一个一致的状态。因此，最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

2PC

阶段一：提交事务请求：

1、事务询问。协调者向所有参与者发送事务内容，询问是否可以进行事务提交操作，然后就开始等待参与者的响应。

2、执行事务。各参与者节点执行事务奥做，并将Undo和Redo信息记入事务日志中。

3、各参与者向协调者反馈事务询问的响应。

阶段二：执行事务提交： 假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务提交。

1、发送提交请求。

2、事务提交。

3、反馈事务提交结果。参与者在完成事务提交之后，会向协调者发送Ack消息。

4、完成事务。

中断事务：

1、发送回滚请求。协调者向参与者发出rollback请求。

2、事务回滚。参与者接收到Roolback请求利用阶段一种记录的Undo信息来执行事务回滚动作。

3、反馈事务回滚结果。

4、中断事务。

• 优点：原理简单，实现方便；
• 缺点：同步阻塞、单点问题、脑裂（比如协调者的消息在网络异常情况下只给一部分参与者发送了）、太过保守。

3PC

阶段一：CanCommit

1、事务询问。

2、各参与者向协调这反馈事务询问的响应。

阶段二：PreCommit

假设协调者从所有的参与者获得的都是Yes响应，那么将执行事务预提交。

1、发送预提交请求。协调者向所有参与者节点发出preCommit请求，进入prepared阶段。

2、事务预提交。参与者接收到preCommt请求，执行事务擦偶走，将Undo和Redo信息记录到事务日志中。

3、各参与者向协调者反馈事务提交的响应。

假设任何一个参与者向协调者反馈了No反应，活着在等待超时之后，协调者无法获得所有参与者的响应，那么将执行事务的中断。

1、发送终端请求。协调者向所有参与者发出abort请求。

2、中断事务。无论接到abort请求还是等待协调者请求过程出现超时情况，参与者都会中断事务。

阶段三：doCommit

该阶段将进行真正的事务提交： 执行提交

1、发送提交请求。进入这一阶段，假设协调者从正常的工作状态，并且接收到所有的参与者的ack响应，它将从预提交状态转换到提交状态，向所有参与者发送doCommit请求。

2、事务提交。参与者接收到doCommit请求后，正式执行事务提交操作。并在提交后释放在整个事务执行期间占用的事务资源。

3、反馈事务提交结果。参与者完成事务提交之后，向协调者发送Ack消息。

4、完成事务。协调者接收到所有参与者的Ack消息，完成事务。

中断事务 中断事务的4步操作与提交事务完全一致，只不过从提交事务变成了事务回滚。

Paxos算法

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，其解决的问题就是在分布式系统中如何就某个值（决议）达成一致。

Paxos算法类似于两阶段提提交，其算法执行过程分为两个阶段。具体如下：

• 阶段一（prepare阶段）：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。Pareper（N）

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，如果小于它已经响应过的请求，则拒绝，不回应或回复error。若N大于该Acceptor已经响应过的所有Prepare请求的编号（maxN），那么它就会将它已经接受过（已经经过第二阶段accept的提案）的编号最大的提案（如果有的话，如果还没有的accept提案的话返回{pok，null，null}）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

• 阶段二（accept阶段）：

(a) 如果一个Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value（某个acceptor响应的它已经通过的{acceptN，acceptV}），如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。如果N小于Acceptor以及响应的prepare请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求）。 在上面的运行过程中，每一个Proposer都有可能会产生多个提案。但只要每个Proposer都遵循如上述算法运行，就一定能保证算法执行的正确性。

Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个”一致性算法”以保证每个节点看到的指令一致。 分布式系统中一般是通过多副本来保证可靠性，而多个副本之间会存在数据不一致的情况。所以必须有一个一致性算法来保证数据的一致，描述如下：   

假如在分布式系统中初始是各个节点的数据是一致的，每个节点都顺序执行系列操作，然后每个节点最终的数据还是一致的。   

Paxos算法就是解决这种分布式场景中的一致性问题。对于一般的开发人员来说，只需要知道paxos是一个分布式选举算法即可。多个节点之间存在两种通讯模型：共享内存（Shared memory）、消息传递（Messages passing），Paxos是基于消息传递的通讯模型的。

在Paxos算法中，有三种角色:

• Proposer
• Acceptor
• Learners

在具体的实现中，一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner。Proposer负责提出提案，Acceptor负责对提案作出裁决（accept与否），learner负责学习提案结果。

还有一个很重要的概念叫提案（Proposal）。最终要达成一致的value就在提案里。只要Proposer发的提案被Acceptor接受（半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。

为了避免单点故障，会有一个Acceptor集合，Proposer想Acceptor集合发送提案，Acceptor集合中的每个成员都有可能同意该提案且每个Acceptor只能批准一个提案，只有当一半以上的成员同意了一个提案，就认为该提案被选定了。

Paxos算法的解决的问题描述

假设有一组可以提出（propose）value（value在提案Proposal里）的进程集合。一个一致性算法需要保证提出的这么多value中，只有一个value被选定（chosen）。如果没有value被提出，就不应该有value被选定。如果一个value被选定，那么所有进程都应该能学习（learn）到这个被选定的value。对于一致性算法，安全性（safaty）要求如下：

• 只有被提出的value才能被选定。
• 只有一个value被选定，并且如果某个进程认为某个value被选定了，那么这个value必须是真的被选定的那个。 Paxos的目标：保证最终有一个value会被选定，当value被选定后，进程最终也能获取到被选定的value

Zookeeper集群一致性协议ZAB

Zab协议 的全称是 Zookeeper Atomic Broadcast Zookeeper原子广播。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

正常情况下当客户端对zk有写的数据请求时，leader节点会把数据同步到follower节点，这个过程是消息的广播模式在新启动的时候，或者leader节点奔溃的时候会要选举新的leader，选好新的leader之后会进行一次数据同步操作，整个过程就是崩溃恢复。

为了保证分区容错性，zookeeper是要让每个节点副本必须是一致的。

广播步骤

Zab协议中的leader等待follower的ack反馈，只要半数以上的follower成功反馈就好，不需要收到全部的follower反馈。

• 客户端发起一个写操作请求
• Leader服务器将客户端的request请求转化为事务proposql提案，同时为每个proposal分配一个全局唯一的ID，即ZXID。
• leader服务器与每个follower之间都有一个队列，leader将消息发送到该队列
• follower机器从队列中取出消息处理完(写入本地事物日志中)毕后，向leader服务器发送ACK确认。
• leader服务器收到半数以上（包含leader本身）的follower的ACK后，即认为可以发送commit
• leader向所有的follower服务器发送commit消息。

崩溃恢复

zookeeper集群中为保证任何所有进程能够有序的顺序执行，只能是leader服务器接受写请求，即使是follower服务器接受到客户端的请求，也会转发到leader服务器进行处理。当leader服务器崩溃或者重启的时候整个集群就失去了leader节点，这个时候就需要采用崩溃恢复机制。

新选举出来的leader不能包含未提交的proposal，即新选举的leader必须都是已经提交了的proposal的follower服务器节点。同时，新选举的leader节点中含有最高的ZXID。这样做的好处就是可以避免了leader服务器检查proposal的提交和丢弃工作。

• 每个Server会发出一个投票,第一次都是投自己。投票信息：（myid，ZXID）
• 收集来自各个服务器的投票
• 处理投票并重新投票，处理逻辑：优先比较ZXID,然后比较myid
• 统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定leader
• 改变服务器状态

,