从互联网的发展可以看出由单机高耦合高资源逐步变成了现在的集群低耦合易扩展的架构，原先的做法都存在一台机器上，保证资源充足，网络稳定的情况下是最好的方案，但随着规模的不断扩大，网络的脆弱性，还有纵向扩展的局限性导致了分布式的出现。当分布式的概念出现后最重要的一点就是如何保证数据的一致性。
我们身边有很多类似的场景，比如火车票的售票系统，比如银行的转账，网上购物等等。
一致性的级别
强一致性
始终一致，体验性最好但对系统的性能影响比较大。
弱一致性
不会承诺在系统写入之后什么时候能正确的读到该值，但会在某个时间级别后能达到数据的一致性。细分还能分成会话一致性与用户一致性。
最终一致性
是弱一致性的一个特例，会保证在一个时间内，达到数据一致性。
事务和分布式事务
我们对于事务这个词听着比较熟悉，他在狭义上讲的是数据库事务，书上的解释是一系列对系统中数据进入访问与更新的操作所组成的一个程序执行逻辑单元。
事务有四个特性ACID，原子性，一致性，隔离性，持久性。
在单机的时代我们可以很容易的实现一套满足ACID的事务处理系统，但分布式数据库中，数据散落在不同的机器上，怎么对这些数据进行分布式的事务就成为了挑战。
CAP理论和BASE理论的提出：
CAP指的是一个分布式系统不可能同时满足一致性，可用性和分区容错性，最多只能满足其中的两项。
可用性：有限的时间内返回结果
分区一致性：在遇到任何网络分区的情况下还能满足一致性和可用性，除非网络通信全断了。
BASE理论是基于CAP演变来的，基本可用，弱状态和最终一致性。
一致性协议
二阶段提交协议
分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的ACID特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。
因此，二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
过程介绍
所谓的两个阶段是指：第一阶段：准备阶段(投票阶段)和第二阶段：提交阶段（执行阶段）。
准备阶段
1.由协调者发起并传递带有事务信息的请求给各个参与者，询问是否可以提交事务，并等待返回结果。
2.各参与者执行事务操作，将Undo和Redo放入事务日志中（但是不提交）
3.如果参与者执行成功就返回YES（可以提交事务），失败NO(不能提交事务)
提交阶段
此阶段分两种情况：所有参与者均返回YES，有任何一个参与者返回NO
1.所有参与者均反馈YES时，即提交事务。
2.任何一个参与者反馈NO时，即中断事务。
提交事务：（所有参与者均反馈YES）
(1) 协调者向所有参与者发出正式提交事务的请求（即Commit请求）。
(2) 参与者执行Commit请求，并释放整个事务期间占用的资源。
(3) 各参与者向协调者反馈Ack完成的消息。
(4) 协调者收到所有参与者反馈的Ack消息后，即完成事务提交。
中断事务：（任何一个参与者反馈NO）
(1) 协调者向所有参与者发出回滚请求（即Rollback请求）。
(2) 参与者使用阶段1中的Undo信息执行回滚操作，并释放整个事务期间占用的资源。
(3) 各参与者向协调者反馈Ack完成的消息。
(4) 协调者收到所有参与者反馈的Ack消息后，即完成事务中断。
优缺点
优点：原理简单，实现方便
缺点：同步阻塞，单点问题，脑裂问题
在阶段2中，如果只有部分参与者接收并执行了Commit请求，会导致节点数据不一致。
三阶段提交协议
过程介绍
三阶段提交是在二基础提交上的改进，即将事务的提交过程分为CanCommit、PreCommit、do Commit三个阶段来进行处理。
CanCommit
1.协调者向所有参与者发出包含事务内容的CanCommit请求，询问是否可以提交事务，并等待所有参与者答复。
2.参与者收到CanCommit请求后，如果认为可以执行事务操作，则反馈YES并进入预备状态，否则反馈NO。
PreCommit
此阶段分为两种情况：
1.所有参与者均受到请求并返回YES。
2.有任何一个参与者返回NO，或者有任何一个参与者超时，协调者无法收到反馈，则事务中断。
事务预提交：（所有参与者均反馈YES时）
(1) 协调者向所有参与者发出PreCommit请求，进入准备阶段。
(2) 参与者收到PreCommit请求后，执行事务操作，将Undo和Redo信息记入事务日志中（但不提交）
(3) 各参与者向协调者反馈Ack响应或No响应，并等待最终指令。
中断事务：（任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈时）
(1) 协调者向所有参与者发出abort请求。
(2) 无论收到协调者发出的abort请求，或者在等待协调者请求过程中出现超时，参与者均会中断事务。
do Commit
此阶段也存在两种情况：
1.所有参与者均反馈Ack响应，即执行真正的事务提交。
2.任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈，即中断事务。
提交事务：（所有参与者均反馈Ack响应时）
(1) 如果协调者处于工作状态，则向所有参与者发出do Commit请求。
(2) 参与者收到do Commit请求后，会正式执行事务提交，并释放整个事务期间占用的资源。
(3) 各参与者向协调者反馈Ack完成的消息。
(4) 协调者收到所有参与者反馈的Ack消息后，即完成事务提交。
中断事务：（任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈时）
(1) 如果协调者处于工作状态，向所有参与者发出abort请求。
(2) 参与者使用阶段1中的Undo信息执行回滚操作，并释放整个事务期间占用的资源。
(3) 各参与者向协调者反馈Ack完成的消息。
(4) 协调者收到所有参与者反馈的Ack消息后，即完成事务中断。
注意：进入阶段三后，无论协调者出现问题，或者协调者与参与者网络出现问题，都会导致参与者无法接收到协调者发出的 do Commit请求或abort请求。此时，参与者都会在等待超时之后，继续执行事务提交。
优缺点
优点：引入超时机制。同时在协调者和参与者中都引入超时机制。降低了阻塞范围，在等待超时后协调者或参与者会中断事务。避免了协调者单点问题，阶段3中协调者出现问题时，参与者会继续提交事务。
缺陷：脑裂问题依然存在，即在参与者收到PreCommit请求后等待最终指令，如果此时协调者无法与参与者正常通信，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。
Paxos协议
上面我们可以看到二阶段和三阶段都可能出现数据不一致的现象，直到提出了paxos后，就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。
简单的说下paxos的提出是作者假想了一个叫paxos的希腊城邦，城邦要采用民主提议和投票的方式选出一个最终的决议，但由于城邦的居民没人愿意把精力都放在这种事情上，所以他们只能不定时的参加提议，不定时的来了解提议和投票进展，不定时的表达自己的意见，paxos算法的目标就是让他们按照少数服从多数的方式来最终达成一致意见。
Paxos的最大特点就是难，不仅难以理解，更难以实现，所以现在大部分的一致性协议都是基于paxos的衍生实现，比如zab，raft。
在2PC或3PC中，主要有协调者和参与者两种角色，在Paxos中，有三种角色，提议者，接收者和学习者。但是Paxos的基本流程主要在提议者和接收者之间发生。
提议者（proposer）：提出提案，提案包含一个提案ID和一个提议的值。
接收者(acceptor)：参与决策，就提议者提出的提案进行承诺接收，如半数以上的接收者同意提案，则提案被通过。
学习者(learner)：参与决策，当提议者和接收者达成最终一致后，学习其最终值。
过程介绍
第一阶段：因为存在多个“提议者”，如果都提意见，那么“接受者“到底应该接受谁？所以要先明确哪个提议者有权提出提议，未来”接受者“们就主要处理这个”提议者“的提议（提出提议时就尽量让意见统一，尽早形成多数派）。
第二阶段：由上阶段选出的提议者提出提议，”接受者“反馈意见。如果多数接受了一个提议，那么提议就通过了。
实现细节
- 怎么明确谁应该是”合适“的提议者？通过编号。每个”提议者“在第一阶段先报个号，谁号大就当提议者。
- 每个”提议者“不会执着于让自己的提议通过，而是每个”提议者“会执着于让提议尽快的达成一致意见。所以如果”提议者“在选举时发现”接受者“之前已经接受过别的”提议者“的提议了，那就算自己赢得了本次选举，也会默默的把自己的提议改成前面”提议者“的提议。（为了尽快的意见统一）
- 号的大小很重要，号小的无论啥时候”接受者“都会直接拒绝。
- 如果你是提议者，在选举时发现”接受者1“说”他见的提议者的提议是方案1“，而”接受者2“说”他见的提议者的提议是方案2“，那么还是要通过对比”号的大小“，”接受者“在接收提案时会记录下”相关提议者号的大小和提议内容（如果有的话）“，所以只需要判断哪个提议者号大就把自己的提议改成哪个提议者的。
zab协议
Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。Zab协议的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播）。Zookeeper 是通过 Zab 协议来保证分布式事务的最终一致性。
基于该协议，zk实现了一种主备模型（即Leader和Follower模型）的系统架构来保证集群中各个副本之间数据的一致性。这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader客户端将数据同步到其他Follower节点。
Zookeeper 客户端会随机的链接到 zookeeper 集群中的一个节点，如果是读请求，就直接从当前节点中读取数据；如果是写请求，那么节点就会向 Leader 提交事务，Leader 接收到事务提交，会广播该事务，只要超过半数节点写入成功，该事务就会被提交。
实现细节
- 使用一个单一的主进程（Leader）来接收并处理客户端的事务请求（也就是写请求），并采用了Zab的原子广播协议，将服务器数据的状态变更以事务proposal（事务提议）的形式广播到所有的副本（Follower）进程上去。
- 保证一个全局的变更序列被顺序引用。
Zab要保证同一个Leader发起的事务要按顺序被apply，同时还要保证只有先前Leader的事务被apply之后，新选举出来的Leader才能再次发起事务。 - 当主进程出现异常的时候，整个zk集群依旧能正常工作。
如何实现数据一致性
可以通过Zab 协议的两种基本的模式：崩溃恢复和消息广播来研究。
当整个集群启动过程中，或者当 Leader 服务器出现网络中弄断、崩溃退出或重启等异常时，Zab协议就会 进入崩溃恢复模式，选举产生新的Leader。
当选举产生了新的 Leader，同时集群中有过半的机器与该 Leader 服务器完成了状态同步（即数据同步）之后，Zab协议就会退出崩溃恢复模式，进入消息广播模式。
消息广播
1）客户端发起一个写操作请求。
2）Leader 服务器将客户端的请求转化为事务 Proposal 提案，同时为每个 Proposal 分配一个全局的ID，即zxid。
3）Leader 服务器为每个 Follower 服务器分配一个单独的队列，然后将需要广播的 Proposal 依次放到队列中取，并且根据 FIFO 策略进行消息发送。
4）Follower 接收到 Proposal 后，会首先将其以事务日志的方式写入本地磁盘中，写入成功后向 Leader 反馈一个 Ack 响应消息。
5）Leader 接收到超过半数以上 Follower 的 Ack 响应消息后，即认为消息发送成功，可以发送 commit 消息。
6）Leader 向所有 Follower 广播 commit 消息，同时自身也会完成事务提交。Follower 接收到 commit 消息后，会将上一条事务提交。
崩溃恢复
Zab 协议崩溃恢复必须满足以下两个要求：
1）Zab 协议需要确保那些已经在 Leader 服务器上提交（Commit）的事务最终被所有的服务器提交。
选择拥有 proposal 最大值（即 zxid 最大） 的节点作为新的 Leader
2）Zab 协议需要确保丢弃那些只在 Leader 上被提出而没有被提交的事务。
Zab 通过zxid 来实现这一目的。一个 zxid 是64位，高 32 是纪元（epoch）编号，每经过一次 Leader选举产生一个新的Leader，其epoch 号 +1。低 32 位是消息计数器，每接收到一条消息这个值 +1，新Leader 选举后这个值重置为 0。
崩溃恢复主要包括两部分：Leader选举和数据恢复。
Leader选举
在 Zab 协议中，为了保证程序的正确运行，整个恢复过程结束后需要选举出一个新的 Leader 服务器。因此 Zab 协议需要一个高效且可靠的 Leader 选举算法，从而确保能够快速选举出新的 Leader 。
所以Zab通过Fast Leader Election（快速选举）来完成leader选择
成为 Leader 的条件：
1）选 epoch 最大的
2）若 epoch 相等，选 zxid 最大的
3）若 epoch 和 zxid 相等，选择 server_id 最大的（zoo.cfg中的myid）
节点在选举开始时，都默认投票给自己，当接收其他节点的选票时，会根据上面的 Leader条件 判断并且更改自己的选票，然后重新发送选票给其他节点。当有一个节点的得票超过半数，该节点会设置自己的状态为 Leading ，其他节点会设置自己的状态为 Following。
数据恢复
1）完成 Leader 选举后（新的 Leader 具有最高的zxid），在正式开始工作之前（接收事务请求，然后提出新的 Proposal），Leader 服务器会首先确认事务日志中的所有的 Proposal 是否已经被集群中过半的服务器 Commit。
2）Leader 服务器需要确保所有的 Follower 服务器能够接收到每一条事务的 Proposal ，并且能将所有已经提交的事务 Proposal 应用到内存数据中。等到 Follower 将所有尚未同步的事务 Proposal 都从 Leader 服务器上同步过啦并且应用到内存数据中以后，Leader 才会把该 Follower 加入到真正可用的 Follower 列表中。
zab协议核心
定义了事务请求的处理方式
zab协议原理
Zab协议要求每个 Leader 都要经历三个阶段：发现，同步，广播。
运行分析：
在zab协议的设计中，每一个进程都有可能处于以下三种状态之一。
- LOOKING： Leader选举阶段
- FOLLOWING： Follower服务器和leader保存同步状态
- LEADING： Leader服务器作为主进程领导状态
代码实现中，多了一种状态：Observing 状态
这是 Zookeeper 引入 Observer 之后加入的，Observer 不参与选举，是只读节点，跟 Zab 协议没有关系。