一致性协议

2PC的提交在执行过程中，所有参与事务操作的逻辑都处于阻塞状态，也就是说，各个参与者都在等待其他参与者响应，无法进行其他操作；
协调者是个单点，一旦出现问题，其他参与者将无法释放事务资源，也无法完成事务操作；
数据不一致。当执行事务提交过程中，如果协调者向所有参与者发送Commit请求后，发生局部网络异常或者协调者在尚未发送完Commit请求，即出现崩溃，最终导致只有部分参与者收到、执行请求。于是整个系统将会出现数据不一致的情形；
保守。2PC没有完善的容错机制，当参与者出现故障时，协调者无法快速得知这一失败，只能严格依赖超时设置来决定是否进一步的执行提交还是中断事务。

3PC

针对2PC的缺点，研究者提出了3PC，即Three-Phase Commit。作为2PC的改进版，3PC将原有的两阶段过程，重新划分为CanCommit、PreCommit和do Commit三个阶段。

阶段一：CanCommit

事务询问。协调者向所有参与者发送包含事务内容的canCommit的请求，询问是否可以执行事务提交，并等待应答；
各参与者反馈事务询问。正常情况下，如果参与者认为可以顺利执行事务，则返回Yes，否则返回No。

阶段二：PreCommit

在本阶段，协调者会根据上一阶段的反馈情况来决定是否可以执行事务的PreCommit操作。有以下两种可能：

执行事务预提交

发送预提交请求。协调者向所有节点发出PreCommit请求，并进入prepared阶段；
事务预提交。参与者收到PreCommit请求后，会执行事务操作，并将Undo和Redo日志写入本机事务日志；
各参与者成功执行事务操作，同时将反馈以Ack响应形式发送给协调者，同事等待最终的Commit或Abort指令。

中断事务

加入任意一个参与者向协调者发送No响应，或者等待超时，协调者在没有得到所有参与者响应时，即可以中断事务：

发送中断请求。协调者向所有参与者发送Abort请求；
中断事务。无论是收到协调者的Abort请求，还是等待协调者请求过程中出现超时，参与者都会中断事务；

阶段三：doCommit

在这个阶段，会真正的进行事务提交，同样存在两种可能。

执行提交

发送提交请求。假如协调者收到了所有参与者的Ack响应，那么将从预提交转换到提交状态，并向所有参与者，发送doCommit请求；
事务提交。参与者收到doCommit请求后，会正式执行事务提交操作，并在完成提交操作后释放占用资源；
反馈事务提交结果。参与者将在完成事务提交后，向协调者发送Ack消息；
完成事务。协调者接收到所有参与者的Ack消息后，完成事务。

中断事务

在该阶段，假设正常状态的协调者接收到任一个参与者发送的No响应，或在超时时间内，仍旧没收到反馈消息，就会中断事务：

发送中断请求。协调者向所有的参与者发送abort请求；
事务回滚。参与者收到abort请求后，会利用阶段二中的Undo消息执行事务回滚，并在完成回滚后释放占用资源；
反馈事务回滚结果。参与者在完成回滚后向协调者发送Ack消息；
中端事务。协调者接收到所有参与者反馈的Ack消息后，完成事务中断。

3PC的优缺点

3PC有效降低了2PC带来的参与者阻塞范围，并且能够在出现单点故障后继续达成一致；

但3PC带来了新的问题，在参与者收到preCommit消息后，如果网络出现分区，协调者和参与者无法进行后续的通信，这种情况下，参与者在等待超时后，依旧会执行事务提交，这样会导致数据的不一致。

Paxos协议

Paxos协议解决了什么问题

像 2PC 和 3PC 都需要引入一个协调者的角色，当协调者 down 掉之后，整个事务都无法提交，参与者的资源都出于锁定的状态，对于系统的影响是灾难性的，而且出现网络分区的情况，很有可能会出现数据不一致的情况。有没有不需要协调者角色，每个参与者来协调事务呢，在网络分区的情况下，又能最大程度保证一致性的解决方案呢。此时 Paxos 出现了。

Paxos 算法是 Lamport 于 1990 年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，Lamport在八年后重新发表，即便如此Paxos算法还是没有得到重视。2006 年 Google 的三篇论文石破天惊，其中的 chubby 锁服务使用Paxos 作为 chubbycell 中的一致性，后来才得到关注。

Paxos 协议是一个解决分布式系统中，多个节点之间就某个值（提案）达成一致（决议）的通信协议。它能够处理在少数节点离线的情况下，剩余的多数节点仍然能够达成一致。

即每个节点，既是参与者，也是决策者

Paxos 协议的角色（可以是同一台机器）

由于 Paxos 和后面的提到的 zookeeper 使用的 ZAB 协议过于相似，详细讲解看ZAB 协议

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。

基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos场景中，先不考虑可能出现消息篡改。(网络环境一般为自建内网，消息安全相对高)

Paxos算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

Paxos 协议的角色主要有三类节点：

提议者（Proposer）：提议一个值；
接受者（Acceptor）：对每个提议进行投票；
告知者（Learner）：被告知投票的结果，不参与投票过程。

过程：

规定一个提议包含两个字段：[n, v]，其中 n 为序号（具有唯一性），v 为提议值。

下图演示了两个 Proposer 和三个 Acceptor 的系统中运行该算法的初始过程，每个 Proposer 都会向所有 Acceptor 发送提议请求。

当 Acceptor 接收到一个提议请求，包含的提议为 [n1, v1]，并且之前还未接收过提议请求，那么发送一个提议响应，设置当前接收到的提议为 [n1, v1]，并且保证以后不会再接受序号小于 n1 的提议。

如下图，Acceptor X 在收到 [n=2, v=8] 的提议请求时，由于之前没有接收过提议，因此就发送一个 [no previous] 的提议响应，并且设置当前接收到的提议为 [n=2, v=8]，并且保证以后不会再接受序号小于 2 的提议。其它的 Acceptor 类似。

如果 Acceptor 接受到一个提议请求，包含的提议为 [n2, v2]，并且之前已经接收过提议 [n1, v1]。如果 n1 > n2，那么就丢弃该提议请求；否则，发送提议响应，该提议响应包含之前已经接收过的提议 [n1, v1]，设置当前接收到的提议为 [n2, v2]，并且保证以后不会再接受序号小于 n2 的提议。

如下图，Acceptor Z 收到 Proposer A 发来的 [n=2, v=8] 的提议请求，由于之前已经接收过 [n=4, v=5] 的提议，并且 n > 2，因此就抛弃该提议请求；Acceptor X 收到 Proposer B 发来的 [n=4, v=5] 的提议请求，因为之前接收到的提议为 [n=2, v=8]，并且 2 <= 4，因此就发送 [n=2, v=8] 的提议响应，设置当前接收到的提议为 [n=4, v=5]，并且保证以后不会再接受序号小于 4 的提议。Acceptor Y 类似。

当一个 Proposer 接收到超过一半 Acceptor 的提议响应时，就可以发送接受请求。

Proposer A 接受到两个提议响应之后，就发送 [n=2, v=8] 接受请求。该接受请求会被所有 Acceptor 丢弃，因为此时所有 Acceptor 都保证不接受序号小于 4 的提议。

Proposer B 过后也收到了两个提议响应，因此也开始发送接受请求。需要注意的是，接受请求的 v 需要取它收到的最大 v 值，也就是 8。因此它发送 [n=4, v=8] 的接受请求。

Acceptor 接收到接受请求时，如果序号大于等于该 Acceptor 承诺的最小序号，那么就发送通知给所有的 Learner。当 Learner 发现有大多数的 Acceptor 接收了某个提议，那么该提议的提议值就被 Paxos 选择出来。

Raft协议

Paxos 是论证了一致性协议的可行性，但是论证的过程据说晦涩难懂，缺少必要的实现细节，而且工程实现难度比较高广为人知实现只有 zk 的实现 zab 协议。

Paxos协议的出现为分布式强一致性提供了很好的理论基础，但是Paxos协议理解起来较为困难，实现比较复杂。

然后斯坦福大学RamCloud项目中提出了易实现，易理解的分布式一致性复制协议 Raft。Java，C++，Go 等都有其对应的实现，之后出现的Raft相对要简洁很多。

引入主节点，通过竞选。
节点类型：Follower、Candidate 和 Leader

Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段。

基本名词

节点状态
- Leader（主节点）：接受 client 更新请求，写入本地后，然后同步到其他副本中
- Follower（从节点）：从 Leader 中接受更新请求，然后写入本地日志文件。对客户端提供读请求
- Candidate（候选节点）：如果 follower 在一段时间内未收到 leader 心跳。则判断 leader 可能故障，发起选主提议。节点状态从 Follower 变为 Candidate 状态，直到选主结束
termId：任期号，时间被划分成一个个任期，每次选举后都会产生一个新的 termId，一个任期内只有一个 leader。termId 相当于 paxos 的 proposalId。
RequestVote：请求投票，candidate 在选举过程中发起，收到 quorum (多数派）响应后，成为 leader。
AppendEntries：附加日志，leader 发送日志和心跳的机制
election timeout：选举超时，如果 follower 在一段时间内没有收到任何消息(追加日志或者心跳)，就是选举超时。

竞选阶段流程

① 下图表示一个分布式系统的最初阶段，此时只有 Follower，没有 Leader。Follower A 等待一个随机的竞选超时时间之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。

② 此时 A 发送投票请求给其它所有节点。

③ 其它节点会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。

④ 之后 Leader 会周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重新开始计时。

多个 Candidate 竞选

① 如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票，例如下图中 Candidate B 和 Candidate D 都获得两票，因此需要重新开始投票。

② 当重新开始投票时，由于每个节点设置的随机竞选超时时间不同，因此能下一次再次出现多个 Candidate 并获得同样票数的概率很低。

日志复制

① 来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。

② Leader 会把修改复制到所有 Follower。

③ Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交。

④ 此时 Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。

ZAB协议

Google 的粗粒度锁服务 Chubby 的设计开发者 Burrows 曾经说过：“所有一致性协议本质上要么是 Paxos 要么是其变体”。Paxos 虽然解决了分布式系统中，多个节点就某个值达成一致性的通信协议。但是还是引入了其他的问题。由于其每个节点，都可以提议提案，也可以批准提案。当有三个及以上的 proposer 在发送 prepare 请求后，很难有一个 proposer 收到半数以上的回复而不断地执行第一阶段的协议，在这种竞争下，会导致选举速度变慢。

所以 zookeeper 在 paxos 的基础上，提出了 ZAB 协议，本质上是，只有一台机器能提议提案（Proposer），而这台机器的名称称之为 Leader 角色。其他参与者扮演 Acceptor 角色。为了保证 Leader 的健壮性，引入了 Leader 选举机制。

ZAB协议还解决了这些问题

在半数以下节点宕机，依然能对台提供服务
客户端所有的写请求，交由 Leader 来处理。写入成功后，需要同步给所有的 follower 和 observer
leader 宕机，或者集群重启。需要确保已经再 Leader 提交的事务最终都能被服务器提交，并且确保集群能快速回复到故障前的状态

ZAB协议基本概念

基本名词
- 数据节点（dataNode）：zk 数据模型中的最小数据单元，数据模型是一棵树，由斜杠（ / ）分割的路径名唯一标识，数据节点可以存储数据内容及一系列属性信息，同时还可以挂载子节点，构成一个层次化的命名空间。
- 事务及 zxid：事务是指能够改变 Zookeeper 服务器状态的操作，一般包括数据节点的创建与删除、数据节点内容更新和客户端会话创建与失效等操作。对于每个事务请求，zk 都会为其分配一个全局唯一的事务 ID，即 zxid，是一个 64 位的数字，高 32 位表示该事务发生的集群选举周期（集群每发生一次 leader 选举，值加 1），低 32 位表示该事务在当前选择周期内的递增次序（leader 每处理一个事务请求，值加 1，发生一次 leader 选择，低 32 位要清 0）。
- 事务日志：所有事务操作都是需要记录到日志文件中的，可通过 dataLogDir 配置文件目录，文件是以写入的第一条事务 zxid 为后缀，方便后续的定位查找。zk 会采取“磁盘空间预分配”的策略，来避免磁盘 Seek 频率，提升 zk 服务器对事务请求的影响能力。默认设置下，每次事务日志写入操作都会实时刷入磁盘，也可以设置成非实时（写到内存文件流，定时批量写入磁盘），但那样断电时会带来丢失数据的风险。
- 事务快照：数据快照是 zk 数据存储中另一个非常核心的运行机制。数据快照用来记录 zk 服务器上某一时刻的全量内存数据内容，并将其写入到指定的磁盘文件中，可通过 dataDir 配置文件目录。可配置参数 snapCount，设置两次快照之间的事务操作个数，zk 节点记录完事务日志时，会统计判断是否需要做数据快照（距离上次快照，事务操作次数等于snapCount/2~snapCount 中的某个值时，会触发快照生成操作，随机值是为了避免所有节点同时生成快照，导致集群影响缓慢）。

核心角色
- leader：系统刚启动时或者 Leader 崩溃后正处于选举状态；
- follower：Follower 节点所处的状态，Follower 与 Leader 处于数据同步阶段；
- observer：Leader 所处状态，当前集群中有一个 Leader 为主进程。

节点状态
- LOOKING：节点正处于选主状态，不对外提供服务，直至选主结束；
- FOLLOWING：作为系统的从节点，接受主节点的更新并写入本地日志；
- LEADING：作为系统主节点，接受客户端更新，写入本地日志并复制到从节点

ZAB协议常见的误区

写入节点后的数据，立马就能被读到，这是错误的。zk 写入是必须通过 leader 串行的写入，而且只要一半以上的节点写入成功即可。而任何节点都可提供读取服务。例如：zk，有 1~5 个节点，写入了一个最新的数据，最新数据写入到节点 1~3，会返回成功。然后读取请求过来要读取最新的节点数据，请求可能被分配到节点 4~5 。而此时最新数据还没有同步到节点4~5。会读取不到最近的数据。如果想要读取到最新的数据，可以在读取前使用 sync 命令。
zk启动节点不能偶数台，这也是错误的。zk 是需要一半以上节点才能正常工作的。例如创建 4 个节点，半数以上正常节点数是 3。也就是最多只允许一台机器 down 掉。而 3 台节点，半数以上正常节点数是 2，也是最多允许一台机器 down 掉。4 个节点，多了一台机器的成本，但是健壮性和 3 个节点的集群一样。基于成本的考虑是不推荐的。

ZAB协议选举同步过程

发起投票的契机

节点启动
节点运行期间无法与 Leader 保持连接，
Leader 失去一半以上节点的连接

如何保证事务

ZAB 协议类似于两阶段提交，客户端有一个写请求过来，例如设置 /my/test 值为 1，Leader 会生成对应的事务提议（proposal）（当前 zxid为 0x5000010 提议的 zxid 为Ox5000011），现将set /my/test 1（此处为伪代码）写入本地事务日志，然后set /my/test 1日志同步到所有的follower。

follower收到事务 proposal ，将 proposal 写入到事务日志。如果收到半数以上 follower 的回应，那么广播发起 commit 请求。follower 收到 commit 请求后。会将文件中的 zxid ox5000011 应用到内存中。

上面说的是正常的情况。有两种情况。第一种 Leader 写入本地事务日志后，没有发送同步请求，就 down 了。即使选主之后又作为 follower 启动。此时这种还是会日志会丢掉（原因是选出的 leader 无此日志，无法进行同步）。第二种 Leader 发出同步请求，但是还没有 commit 就 down 了。此时这个日志不会丢掉，会同步提交到其他节点中。

服务器启动过程中的投票过程

现在 5 台 zk 机器依次编号 1~5

节点 1 启动，发出去的请求没有响应，此时是 Looking 的状态
节点 2 启动，与节点 1 进行通信，交换选举结果。由于两者没有历史数据，即 zxid 无法比较，此时 id 值较大的节点 2 胜出，但是由于还没有超过半数的节点，所以 1 和 2 都保持 looking 的状态
节点 3 启动，根据上面的分析，id 值最大的节点 3 胜出，而且超过半数的节点都参与了选举。节点 3 胜出成为了 Leader
节点 4 启动，和 1~3 个节点通信，得知最新的 leader 为节点 3，而此时 zxid 也小于节点 3，所以承认了节点 3 的 leader 的角色
节点 5 启动，和节点 4 一样，选取承认节点 3 的 leader 的角色

服务器运行过程中选主过程

节点 1 发起投票，第一轮投票先投自己，然后进入 Looking 等待的状态
其他的节点（如节点 2 ）收到对方的投票信息。节点 2 在 Looking 状态，则将自己的投票结果广播出去（此时走的是上图中左侧的 Looking 分支）；如果不在 Looking 状态，则直接告诉节点 1 当前的 Leader 是谁，就不要瞎折腾选举了（此时走的是上图右侧的 Leading/following 分支）
此时节点 1，收到了节点 2 的选举结果。如果节点 2 的 zxid 更大，那么清空投票箱，建立新的投票箱，广播自己最新的投票结果。在同一次选举中，如果在收到所有节点的投票结果后，如果投票箱中有一半以上的节点选出了某个节点，那么证明 leader 已经选出来了，投票也就终止了。否则一直循环

zookeeper 的选举，优先比较大 zxid，zxid 最大的节点代表拥有最新的数据。如果没有 zxid，如系统刚刚启动的时候，则比较机器的编号，优先选择编号大的。

同步的过程

在选出 Leader 之后，zk 就进入状态同步的过程。其实就是把最新的 zxid 对应的日志数据，应用到其他的节点中。此 zxid 包含 follower 中写入日志但是未提交的 zxid 。称之为服务器提议缓存队列 committedLog 中的 zxid。

同步会完成三个 zxid 值的初始化。

peerLastZxid：该 learner 服务器最后处理的 zxid。
minCommittedLog：leader服务器提议缓存队列 committedLog 中的最小zxid。
maxCommittedLog：leader服务器提议缓存队列 committedLog 中的最大 zxid。系统会根据 learner 的peerLastZxid和 leader 的minCommittedLog，maxCommittedLog做出比较后做出不同的同步策略

直接差异化同步

场景：peerLastZxid介于minCommittedLogZxid和maxCommittedLogZxid间

此种场景出现在，上文提到过的，Leader 发出了同步请求，但是还没有 commit 就 down 了。 leader 会发送 Proposal 数据包，以及 commit 指令数据包。新选出的 leader 继续完成上一任 leader 未完成的工作。

例如此刻Leader提议的缓存队列为 0x20001，0x20002，0x20003，0x20004，此处learn的peerLastZxid为0x20002，Leader会将0x20003和0x20004两个提议同步给learner

先回滚在差异化同步/仅回滚同步

此种场景出现在，上文提到过的，Leader写入本地事务日志后，还没发出同步请求，就down了，然后在同步日志的时候作为learner出现。

例如即将要 down 掉的 leader 节点 1，已经处理了 0x20001，0x20002，在处理 0x20003 时还没发出提议就 down 了。后来节点 2 当选为新 leader，同步数据的时候，节点 1 又神奇复活。如果新 leader 还没有处理新事务，新 leader 的队列为，0x20001, 0x20002，那么仅让节点 1 回滚到 0x20002 节点处，0x20003 日志废弃，称之为仅回滚同步。如果新 leader 已经处理 0x30001 , 0x30002 事务，那么新 leader 此处队列为0x20001，0x20002，0x30001，0x30002，那么让节点 1 先回滚，到 0x20002 处，再差异化同步0x30001，0x30002。

全量同步

peerLastZxid小于minCommittedLogZxid或者leader上面没有缓存队列。leader直接使用SNAP命令进行全量同步

2PC

阶段一：提交事务请求

阶段二：执行事务提交

2PC具有明显的优缺点

3PC