分布式是指通过网络连接的多个组件，通过交换信息协作而形成的系统。
分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。
而集群，是指同一种组件的多个实例，形成的逻辑上的整体。

1.两阶段提交

1.请求阶段
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意或取消。
2.提交阶段
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。
当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。

两阶段提交的缺点
1.同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。
当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。

2.单点故障。由于协调者的重要性，一旦协调者发生故障。
参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）

3.数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。
而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。

2.三阶段提交协议

与两阶段提交不同的是，三阶段提交有两个改动点。
1、引入超时机制。同时在协调者和参与者中都引入超时机制。
2、在第一阶段和第二阶段中插入一个准备阶段。询问，然后再锁资源，最后真正提交。保证了在最后提交阶段之前各参与节点的状态是一致的。

一致性协议之 ZAB

1. ZAB 协议介绍

1. ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）。
2. Zookeeper 是一个为分布式应用提供高效且可靠的分布式协调服务。在解决分布式一致性方面，Zookeeper 并没有使用 Paxos ，而是采用了 ZAB 协议。
3. ZAB 协议定义：ZAB 协议是为分布式协调服务 Zookeeper 专门设计的一种支持 崩溃恢复 和 原子广播 协议。下面我们会重点讲这两个东西。
4. 基于该协议，Zookeeper 实现了一种 主备模式 的系统架构来保持集群中各个副本之间数据一致性。具体如下图所示：

上图显示了 Zookeeper 如何处理集群中的数据。所有客户端写入数据都是写入到 主进程（称为 Leader）中，然后，由 Leader 复制到备份进程（称为 Follower）中。从而保证数据一致性。从设计上看，和 Raft 类似。

1. 复制过程类似 2PC，ZAB 只需要 Follower 有一半以上返回 Ack 信息就可以执行提交，大大减小了同步阻塞。也提高了可用性。

2.消息广播

ZAB 协议的消息广播过程使用的是一个原子广播协议，类似一个 二阶段提交过程。对于客户端发送的写请求，全部由 Leader 接收，Leader 将请求封装成一个事务 Proposal，将其发送给所有 Follwer ，然后，根据所有 Follwer 的反馈，如果超过半数成功响应，则执行 commit 操作（先提交自己，再发送 commit 给所有 Follwer）。
基本上，整个广播流程分为 3 步骤：

1. 将数据都复制到 Follwer 中

1. 等待 Follwer 回应 Ack，最低超过半数即成功

1. 当超过半数成功回应，则执行 commit ，同时提交自己

还有一些细节：

1. Leader 在收到客户端请求之后，会将这个请求封装成一个事务，并给这个事务分配一个全局递增的唯一 ID，称为事务ID（ZXID），ZAB 协议需要保证事务的顺序，因此必须将每一个事务按照 ZXID 进行先后排序然后处理。
2. 在 Leader 和 Follwer 之间还有一个消息队列，用来解耦他们之间的耦合，解除同步阻塞。
3. zookeeper集群中为保证任何所有进程能够有序的顺序执行，只能是 Leader 服务器接受写请求，即使是 Follower 服务器接受到客户端的请求，也会转发到 Leader 服务器进行处理。
4. 实际上，这是一种简化版本的 2PC，不能解决单点问题。等会我们会讲述 ZAB 如何解决单点问题（即 Leader 崩溃问题）。

3.崩溃恢复

刚刚我们说消息广播过程中，Leader 崩溃怎么办？还能保证数据一致吗？如果 Leader 先本地提交了，然后 commit 请求没有发送出去，怎么办？
实际上，当 Leader 崩溃，即进入我们开头所说的崩溃恢复模式（崩溃即：Leader 失去与过半 Follwer 的联系）。
假设1：Leader 在复制数据给所有 Follwer 之后崩溃，怎么办？
假设2：Leader 在收到 Ack 并提交了自己，同时发送了部分 commit 出去之后崩溃怎么办？
针对这些问题，ZAB 定义了 2 个原则：

1. ZAB 协议确保那些已经在 Leader 提交的事务最终会被所有服务器提交。
2. ZAB 协议确保丢弃那些只在 Leader 提出/复制，但没有提交的事务。

所以，ZAB 设计了下面这样一个选举算法：
能够确保提交已经被 Leader 提交的事务，同时丢弃已经被跳过的事务。
针对这个要求，如果让 Leader 选举算法能够保证新选举出来的 Leader 服务器拥有集群总所有机器编号（即 ZXID 最大）的事务，那么就能够保证这个新选举出来的 Leader 一定具有所有已经提交的提案。而且这么做有一个好处是：可以省去 Leader 服务器检查事务的提交和丢弃工作的这一步操作。

这样，我们刚刚假设的两个问题便能够解决。假设 1 最终会丢弃调用没有提交的数据，假设 2 最终会同步所有服务器的数据。这个时候，就引出了一个问题，如何同步？

4.数据同步

当崩溃恢复之后，需要在正式工作之前（接收客户端请求），Leader 服务器首先确认事务是否都已经被过半的 Follwer 提交了，即是否完成了数据同步。目的是为了保持数据一致。
当所有的 Follwer 服务器都成功同步之后，Leader 会将这些服务器加入到可用服务器列表中。
实际上，Leader 服务器处理或丢弃事务都是依赖着 ZXID 的，那么这个 ZXID 如何生成呢？
答：在 ZAB 协议的事务编号 ZXID 设计中，ZXID 是一个 64 位的数字，其中低 32 位可以看作是一个简单的递增的计数器，针对客户端的每一个事务请求，Leader 都会产生一个新的事务 Proposal 并对该计数器进行 + 1 操作。
而高 32 位则代表了 Leader 服务器上取出本地日志中最大事务 Proposal 的 ZXID，并从该 ZXID 中解析出对应的 epoch 值，然后再对这个值加一。

高 32 位代表了每代 Leader 的唯一性，低 32 代表了每代 Leader 中事务的唯一性。同时，也能让 Follwer 通过高 32 位识别不同的 Leader。简化了数据恢复流程。
基于这样的策略：当 Follower 链接上 Leader 之后，Leader 服务器会根据自己服务器上最后被提交的 ZXID 和 Follower 上的 ZXID 进行比对，比对结果要么回滚，要么和 Leader 同步。

5.总结

ZAB 协议和我们之前看的 Raft 协议实际上是有相似之处的，比如都有一个 Leader，用来保证一致性（Paxos 并没有使用 Leader 机制保证一致性）。再有采取过半即成功的机制保证服务可用（实际上 Paxos 和 Raft 都是这么做的）。
ZAB 让整个 Zookeeper 集群在两个模式之间转换，消息广播和崩溃恢复，消息广播可以说是一个简化版本的 2PC，通过崩溃恢复解决了 2PC 的单点问题，通过队列解决了 2PC 的同步阻塞问题。
而支持崩溃恢复后数据准确性的就是数据同步了，数据同步基于事务的 ZXID 的唯一性来保证。通过 + 1 操作可以辨别事务的先后顺序。

Raft 算法

1.什么是 Raft 算法

首先说什么是 Raft 算法：Raft 是一种为了管理复制日志的一致性算法。
什么是一致性？
Raft 的论文这么说的：一致性算法允许一组机器像一个整体一样工作，即使其中一些机器出现故障也能够继续工作下去。这里的一致性针对分布式系统。

一致性算法是从复制状态机的背景下提出的，复制状态机通常都是基于复制日志实现的，这个日志可以理解为一个比喻，相当于一个指令。
关于状态机的描述：

多个节点上，从相同的初始状态开始，执行相同的一串命令，产生相同的最终状态。实际上，与其说是一致，其实可以泛化为分布式的两个节点状态存在某种约束。
复制状态机通常都是基于复制日志实现的，保证复制日志相同就是一致性算法的工作了。

2.领导人选举

Raft 通过选举一个高贵的领导人，然后给予他全部的管理复制日志的责任来实现一致性。
而每个 server 都可能会在 3 个身份之间切换：

• 领导者——Leader
• 候选者——Candidate
• 跟随者——Follower

而影响他们身份变化的则是 选举。
当所有服务器初始化的时候，都是 跟随者（Follower），这个时候需要一个 领导者（Leader），所有人都变成 候选者（Candidate），直到有人成功当选 领导者（Leader）。
角色轮换如下图

而领导者也有宕机的时候，宕机后引发新的 选举，所以，整个集群在选举和正常运行之间切换，具体如下图：

从上图可以看出，选举和正常运行之间切换，但请注意， 上图中的 term 3 有一个地方，后面没有跟着 正常运行 阶段，为什么呢?
答：当一次选举失败（比如正巧每个人都投了自己），就执行一次 加时赛，每个 Server 会在一个随机的时间里重新投票，这样就能保证不冲突了。所以，当 term 3 选举失败，等了几十毫秒，执行 term 4 选举，并成功选举出领导人。
接着，领导者周期性的向所有跟随者发送心跳包来维持自己的权威。如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时（time_out），那么他就会认为系统中没有可用的领导者,并且发起选举以选出新的领导者。
要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后请求其他服务器为自己投票。那么会产生 3 种结果：
a. 自己成功当选
b. 其他的服务器成为领导者
c. 僵住，没有任何一个人成为领导者
注意：

1. 每一个 server 最多在一个任期内投出一张选票（有任期号约束），先到先得。
2. 要求最多只能有一个人赢得选票。
3. 一旦成功，立即成为领导人，然后广播所有服务器停止投票阻止新领导产生。

僵住怎么办？ Raft 通过使用随机选举超时时间（例如 150 - 300 毫秒）的方法将服务器打散投票。每个候选人在僵住的时候会随机从一个时间开始重新选举。
以上，就是 Raft 所有关于领导选举的策略。

3.日志复制

一旦一个领导人被选举出来，他就开始为客户端提供服务。
客户端发送日志给领导者，随后领导者将日志复制到其他的服务器。如果跟随者故障，领导者将会尝试重试。直到所有的跟随者都成功存储了所有日志。
下图表示了当一个客户端发送一个日志给领导者，随后领导者复制给跟随者的整个过程。

4 个步骤：

1. 客户端提交
2. 复制数据到所有跟随者
3. 跟随者回复 确认收到
4. 领导者回复客户端和所有跟随者 确认提交。

可以看到，直到第四步骤，整个事务才会达成。中间任何一个步骤发生故障，都不会影响日志一致性。

4.总结

Raft 算法如同他的论文名字一样：寻找一种易于理解的一致性算法，这里的 易于理解 是相对于 Paxos 的，的确，Paxos 实在过于复杂了。
而如何实现易于理解？
答：Raft 将一致性算法分成了2部分：领导选举，日志复制。
领导选举基于一个随机的时间来保证不会冲突（如果冲突的话）。
而日志复制则类似于 2PC。
通常 5 个节点，只要不超过 2 个节点死亡都不会影响系统的运行。保证了系统的可用性，通过领导者的日志复制，实现了系统的一致性。