🌏【架构师指南】分布式事务（XA）与一致性算法（Paxos、Raft、Zab、NWR）

每日一句

生活，一半是回忆，一半是继续。

CAP 原理

• 要想数据高可用，就得写多份数据

• 写多分数据就会导致数据一致性问题

• 数据一致性问题会引起性能问题

一致性模型

• 强一致（同步冗余）

• 弱一致性（异步冗余技术体系）

• 最终一致性（一段时间达到一致性）

扩展服务的方案

• 数据分区： uid % 16（更多类比分布式）

• 数据镜像：让多有的服务器都有相同的数据，提供相当的服务（冗余存储，一般 3 份为好）（更多类比集群）

两种方案的事务问题

A 向 B 汇钱，两个用户不在一个服务器上

镜像：在不同的服务器上对同一数据的写操作如何保证一致性。

解决一致性事务问题的技术

Master-Slave

• 读写请求由 Master 负责

• 写请求写到 Master 后，由 Master 同步到 Slave 上（由 Master push or Slave pull，通常是由 Slave 周期性来 pull，所以是最终一致性）

问题

• 若在 pull 周期内（不是期间？），master 挂掉，那么会导致这个时间片内的数据丢失。

• 若不想让数据丢掉，Slave 只能成为 ReadOnly 方式等 Master 恢复。

• 若容忍数据丢失，可以让 Slave 代替 Master 工作。

如何保证强一致性？

Master 写操作，写完成功后，再写 Slave，两者成功后返回成功。若 Slave 失败，两种方法标记 Slave 不可用报错。

• Master 并继续服务，Slave 等恢复后，再同步 Master 的数据，多个 Slave 少了一个而已，或者重新尝试同步 slave 数据。

• Master 回滚自己并返回失败，带用户重新请求，此种方法，数据一致性高可用性高，性能下降很多。

Master-Master

数据同步一般是通过 Master 间的异步完成，所以是最终一致。

好处： 一台 Master 挂掉，另外一台照样可以提供读写服务。当数据没有被赋值到别的 Master 上时，数据会丢失。

对同一数据的处理问题：Dynamo 的 Vector Clock 的设计（记录数据的版本号和修改者），当数据发生冲突时，要开发者自己来处理。

两阶段提交 Two Phase Commit _2PC

第一阶段：针对准备工作

• 协调者问所有节点是否可以执行提交

• 参与者开始事务，执行准备工作：锁定资源（获取锁操作）

• 参与者响应协调者，如果事务的准备工作成功，则回应"可以提交"，否则，拒绝提交

若消息的传递未接收到，则需要协调者作超时处理，要么当做失败，要么重载。

第二阶段：

• 若都响应可以提交，则协调者项多有参与者发送正式提交的命令（更新值），参与者完成正式提交，释放资源，回应完成。

• 协调者收到所有节点的完成响应后结束这个全局事务.。若参与者回应拒绝提交，则协调者向所有的参与者发送回滚操作，并释放资源，当收到全部节点的回滚回应后，取消全局事务存在的问题：若一个没提交，就会进行回滚

若参与者的回应超时，要么重试，要么把那个参与者即为问题节点，题出整个集群，在第二阶段中，参与者未收到协调者的指示（也许协调者挂掉），则所有参与者会进入“不知所措” 的状态（但是已经锁定了资源），所以引入了三段提交。

三段提交：把二段提交的第一阶段 break 成了两段

1. 询问

2. 锁定资源（获取锁）

3. 提交

核心理念：在询问的时候并不锁定资源，除非所有人都同意了，才开始锁定。

好处：当发生了失败或超时时，三段提交可以继续把状态变为 Commit 状态，而二段提交则不知所措？

Paxos 算法（少数服从多数）

解决的问题：一个可能发生异常的分布式系统中如何就某个值达成一致，让整个集群的节点对某个值的变更达成一致

任何一个节点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数（多数）的节点同意（所以节点数总是单数）—— 版本标记。

当一个 Server 接收到比当前版本号小的提案时，则拒绝。当收到比当前大的版本号的提案时，则锁定资源，进行修改，返回 OK。也就是说收到超过一半的最大版本的提案才算成功。

核心思想

在抢占式访问权的基础上引入多个 acceptor，也就是说当一个版本号更大的提案可以剥夺版本号已经获取的锁。

后者认同前者的原则：

肯定旧 epoch 无法生成确定性取值时，新的 epoch 会提交自己的 value，一旦旧 epoch 形成确定性取值，新的 epoch 肯定可以获取到此取值，并且会认同此取值，不会被破坏。

步骤

P1 请求 Acceptor 的 #1，Acceptor 这时并没有其他线程获取到锁，所以把锁交给 P1，并返回这时 #1 的值为 null

然后 P1 向 第一个 Acceptor 提交 #1 的值，Acceptor 接受并返回 OK

这个时候，P2 向 Acceptor 请求 #1 上的锁，因为版本号更大，所以直接抢占了 P1 的锁。这时 Acceptor 返回了 OK 并且返回了 #1 的值

这时 P1 向 后面两个 Acceptor 提交 #1 的值，但是由于中间的那个 Acceptor 版本号已经更改为 2 了，所以拒绝 P1。第三个 Acceptor 接受了，并且返回了 OK

由于后者认同前者的原则，这时 P1 已经形成确定性取值了 V1 了，这时新的 P2 会认同此取值，而不是提交自己的取值。所以，P2 会选择最新的那个取值也就是 V1 进行提交。这时 Acceptor 返回 OK

ZAB 算法

ZAB 协议 ( Zookeeper Atomic Broadcast) 原子广播协议：保证了发给各副本的消息顺序相同

定义：原子广播协议 ZAB 是一致性协议，Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的。Zookeeper 使用单一主进程 Leader 用于处理客户端所有事务请求，采用 ZAB 协议将服务器状态以事务形式广播到所有 Follower 上，由于事务间可能存在着依赖关系，ZAB 协议保证 Leader 广播的变更序列被顺序的处理，一个状态被处理那么它所依赖的状态也已经提前被处理。

核心思想：保证任意时刻只有一个节点是 Leader，所有更新事务由 Leader 发起去更新所有副本 Follower，更新时用的是两段提交协议，只要多数节点 prepare 成功，就通知他们 commit。各个 follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务。

协议状态

• Looking：系统刚启动时或者 Leader 崩溃后正处于选举状态

• Following：Follower 节点所处的状态，Follower 与 Leader 处于数据同步状态

• Leading：Leader 所处状态，当前集群中有一个 Leader 为主进程

ZooKeeper 启动时所有节点初始状态为 Looking，这时集群会尝试选举出一个 Leader 节点，选举出的 Leader 节点切换为 Leading 状态；

• 当节点发现集群中已经选举出 Leader 则该节点会切换到 Following 状态，然后和 Leader 节点保持同步；

• 当 Follower 节点与 Leader 失去联系时 Follower 节点则会切换到 Looking 状态，开始新一轮选举；

• 在 ZooKeeper 的整个生命周期中每个节点都会在 Looking、Following、Leading 状态间不断转换。

选举出 Leader 节点后 ZAB 进入原子广播阶段，这时 Leader 为和自己同步每个节点 Follower 创建一个操作序列，一个时期一个 Follower 只能和一个 Leader 保持同步

阶段

• Election：在 Looking 状态中选举出 Leader 节点，Leader 的 LastZXID 总是最新的（只有 LastZXID 的节点才有资格成为 Leader,这种情况下选举出来的 Leader 总有最新的事务日志）。在选举的过程中会对每个 Follower 节点的 ZXID 进行对比只有 highestZXID 的 Follower 才可能当选 Leader

• 每个 Follower 都向其他节点发送选自身为 Leader 的 Vote 投票请求，等待回复；

• Follower 接受到的 Vote 如果比自身的大（ZXID 更新）时则投票，并更新自身的 Vote，否则拒绝投票；

• 每个 Follower 中维护着一个投票记录表，当某个节点收到过半的投票时，结束投票并把该 Follower 选为 Leader，投票结束；

• Discovery：Follower 节点向准 Leader 推送 FollwerInfo,该信息包含了上一周期的 epoch，接受准 Leader 的 NEWLEADER 指令

• Sync：将 Follower 与 Leader 的数据进行同步，由 Leader 发起同步指令，最终保持数据的一致性

• Broadcast：Leader 广播 Proposal 与 Commit，Follower 接受 Proposal 与 commit。因为一个时刻只有一个 Leader 节点，若是更新请求，只能由 Leader 节点执行（若连到的是 Follower 节点，则需转发到 Leader 节点执行；读请求可以从 Follower 上读取，若是要最新的数据，则还是需要在 Leader 上读取）

• 消息广播使用了 TCP 协议进行通讯所有保证了接受和发送事务的顺序性。广播消息时 Leader 节点为每个事务 Proposal 分配一个全局递增的 ZXID（事务 ID），每个事务 Proposal 都按照 ZXID 顺序来处理（Paxos 保证不了）

• Leader 节点为每一个 Follower 节点分配一个队列按事务 ZXID 顺序放入到队列中，且根据队列的规则 FIFO 来进行事务的发送。

• Recovery ：根据 Leader 的事务日志对 Follower 节点数据进行同步更新。

同步策略：

SNAP ：如果 Follower 数据太老，Leader 将发送快照 SNAP 指令给 Follower 同步数据；

DIFF ：Leader 发送从 Follower.lastZXID 到 Leader.lastZXID 议案的 DIFF 指令给 Follower 同步数据；

TRUNC ：当 Follower.lastZXID 比 Leader.lastZXID 大时，Leader 发送从 Leader.lastZXID 到 Follower.lastZXID 的 TRUNC 指令让 Follower 丢弃该段数据；（当老 Leader 在 Commit 前挂掉，但是已提交到本地）Follower 将所有事务都

同步完成后，Leader 会把该节点添加到可用 Follower 列表中；

Follower 接收 Leader 的 NEWLEADER 指令，如果该指令中 epoch 比当前 Follower 的 epoch 小，那么 Follower 转到 Election 阶段

Raft 算法

Raft 算法也是一种少数服从多数的算法，在任何时候一个服务器可以扮演以下角色之一：

• Leader：负责 Client 交互和 log 复制，同一时刻系统中最多存在一个。

• Follower：被动响应请求 RPC，从不主动发起请求 RPC。

• Candidate : 由 Follower 向 Leader 转换的中间状态。

在选举 Leader 的过程中，是有时间限制的，raft 将时间分为一个个 Term，可以认为是“逻辑时间”：

每个 Term 中至多存在 1 个 Leader

某些 Term 由于不止一个得到的票数一样，就会选举失败，不存在 Leader。则会出现 Split Vote ，再由候选者发出邀票每个 Server 本地维护 currentTerm

选举过程：

自增 CurrentTerm，由 Follower 转换为 Candidate，设置 votedFor 为自身，并行发起 RequestVote RPC,不断重试，直至满足下列条件之一为止：

1. 获得超过半数的 Server 的投票，转换为 Leader，广播 HeatBeat

2. 接收到合法 Leader 的 AppendEnties RPC，转换为 Follower

3. 选举超时，没有 Server 选举成功，自增 currentTerm，重新选举

当 Candidate 在等待投票结果的过程中，可能会接收到来自其他 Leader 的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term，则认可该 Leader 身份的合法性，主动降级为 Follower，反之，则维持 candida 身份继续等待投票结果

Candidate 既没有选举成功，也没有收到其他 Leader 的 RPC (多个节点同时发起选举，最终每个 Candidate 都将超时)，为了减少冲突，采取随机退让策略，每个 Candidate 重启选举定时器。

日志更新问题：

如果在日志复制过程中，发生了网络分区或者网络通信故障，使得 Leader 不能访问大多数 Followers 了，那么 Leader 只能正常更新它能访问的那些 Follower 服务器，而大多数的服务器 Follower 因为没有了 Leader，他们重新选举一个候选者作为 Leader，然后这个 Leader 作为代表于外界打交道，如果外界要求其添加新的日志，这个新的 Leader 就按上述步骤通知大多数 Followers，如果这时网络故障修复了，那么原先的 Leader 就变成 Follower，在失联阶段这个老 Leader 的任何更新都不能算 commit，都回滚，接受新的 Leader 的新的更新。

流程

1. Client 发送 command 命令给 Leader

2. Leader 追加日志项，等待 commit 更新本地状态机，最终响应 Client

3. 若 Client 超时，则不断重试，直到收到响应为止（重发 command，可能被执行多次，在被执行但是由于网络通信问题未收到响应）- 幂等性

4. 解决办法：Client 赋予每个 Command 唯一标识，Leader 在接收 command 之前首先检查本地 log

paxos 算法与 raft 算法的差异

Raft 强调是唯一 Leader 的协议，此 Leader 至高无上。

Raft：新选举出来的 Leader 拥有全部提交的日志，而 Paxos 需要额外的流程从其他节点获取已经被提交的日志，它允许日志有空洞

相同点：得到大多数的赞成，这个 entries 就会定下来，最终所有节点都会赞成。

NWR 模型

N：N 个备份

W：要写入至少 w 份才认为成功

R : 至少读取 R 个备份

W+ R > N ——> R > N - W (未更新成功的) ，代表每次读取，都至少读取到一个最新的版本（更新成功的），从而不会读到一份旧数据

问题：并非强一致性，会出现一些节点上的数据并不是最新版本，但却进行了最新的操作。

版本冲突问题：矢量钟 Vector Clock ： 谁更新的我，我的版本号是什么（对于同一个操作者的同一操作，版本号递增）