关于zookeeper:从2PC和容错共识算法讨论zookeeper中的Create请求-京东云技术团队

最近在读《数据密集型利用零碎设计》，其中谈到了 zookeeper 对容错共识算法的利用。这让我想到之前参考的 zookeeper 学习材料中，误将容错共识算法写成了 2PC（两阶段提交协定），所以筹备以此文对共识算法和 2PC 做梳理和辨别，也心愿它能帮忙像我一样对这两者有误会的同学。

1. 2PC（两阶段提交协定）

两阶段提交 (two-phase commit) 协定是一种用于实现 跨多个节点的原子事务（分布式事务）提交 的算法。它能确保所有节点提交或所有节点停止，并在某些数据库外部应用，也以 XA 事务 的模式在分布式服务中应用。

在 Java EE 中，XA 事务应用 JTA(Java Transaction API) 实现。

2PC 的实现

2PC 蕴含 筹备阶段  和  提交阶段  两个阶段，须要借助  协调者（事务管理器，如阿里巴巴的 Seata）  来实现，参加分布式事务的数据库节点为 参与者 。当分布式服务中的节点筹备提交时，协调者开始  筹备阶段 ：发送一个  筹备申请 到每个节点，询问它们是否可能提交，而后协调者会跟踪参与者的响应

• 如果所有参与者都答复 ” 是 ”，示意它们曾经筹备好提交，那么协调者在 提交阶段  收回  提交申请，分布式事务提交
• 如果任意一个参与者答复 ” 否 ”，则协调者在 提交阶段  中向所有节点发送  停止申请，分布式事务回滚

上图是 2PC 提交胜利的状况，咱们来详述下过程：

1. 当服务启动一个分布式事务时，它会向协调者申请一个事务 ID，此事务 ID 是全局惟一的
2. 在每个参与者上启动单节点事务，每个单节点事务会持有这个全局事务 ID。所有的读写都是在这些单节点事务中各自实现的。如果在这个阶段呈现任何问题（节点解体或申请超时），则协调者或任何参与者都能够停止
3. 当利用筹备提交时，对应 筹备阶段 ：协调者向所有参与者发送一个  筹备申请 ，同样也持有全局事务 ID。如果任意一个申请失败或超时，则协调者向所有参与者发送针对该事务 ID 的  停止申请，即 2PC 提交停止的状况
4. 参与者收到 筹备申请  时，须要确保在任意状况下都能够提交事务。这包含将所有事务数据写入磁盘（呈现故障，电源故障，或硬盘空间有余都不能是稍后回绝提交的理由）以及查看是否存在任何抵触或违反束缚。通过向协调者答复“是”，节点承诺这个事务肯定能够不出差错地提交。也就是说： 参与者没有理论提交，同时放弃了停止事务的权力
5. 当协调者收到所有 筹备申请  的回答时，会就  提交或停止事务  作出明确的决定（只有在  所有参与者  投赞成票的状况下才会提交），这里对应 提交阶段 。协调者必须把这个提交或停止事务的决定  写到磁盘上的事务日志中 ，记录为  提交点（commit point）。如果它随后解体，能通过提交点进行复原
6. 一旦协调者的决定曾经保留在事务日志中，提交或停止申请会发送给所有参与者。如果这个申请失败或超时，协调者 必须永远放弃重试，直到胜利为止，对于曾经做出的决定，协调者不论须要多少次重试它都必须被执行

2PC 协定中有两个要害的 不归路 须要留神：

• 一旦协调者做出决定，这一决定是不可撤销的
• 参与者投票“是”时，它承诺它稍后必定可能提交（只管协调者可能依然抉择放弃），即便参与者在此期间解体，事务也须要在其复原后提交，而且因为参与者投了赞成，它不能在复原后回绝提交

这些承诺保障了 2PC 的 原子性。

协调者生效的状况

如果 协调者生效  并且所有参与者都收到了筹备申请并投了是，那么参与者什么都做不了只能期待，而且这种状况  解决方案 是期待协调者复原或数据库管理员染指操作来提交或回滚事务，当然如果在生产期间这须要承当运维压力。

所以，协调者在向参与者发送提交或停止申请 之前 ，将其提交或停止决定写入磁盘上的事务日志（提交点）。这样就能在协调者产生解体复原后，通过读取其事务日志来确定所有  存疑事务  的状态，任何在协调者事务日志中没有提交记录的事务都会被终止。因而两阶段提交在第二阶段（提交阶段）存在阻塞期待协调者复原的状况，所以两阶段提交又被称为  阻塞原子提交协定。

番外：3PC

三阶段提交协定也是利用在分布式事务提交中的算法，它的提出是为了解决两阶段提交协定中存在的阻塞问题。它分为 CanCommit 阶段 、PreCommit 阶段 和 DoCommit 阶段，通过引入  参与者超时判断机制 来解决 2PC 中存在的参与者依赖协调者的提交申请而阻塞导致的资源占用等问题。

上图为在 DoCommit 阶段，参与者判断 DoCommit 申请 超时状况的流程图，咱们详述下它的防止阻塞的流程

1. 服务在每个参与者上启动单节点事务，当参与者筹备提交时，对应 CanCommit 阶段，协调者会向所有参与者发送 CanCommit 申请 ，如果任意一个申请失败或超时，则协调者会向所有参与者发送针对该事务的  停止申请，执行事务回滚
2. 当协调者收到所有 CanCommit 申请的回答时，如果全是“是”那么则进入 PreCommit 阶段，否则发送停止申请，执行事务回滚
3. 进入 PreCommit 阶段后，协调者会向所有参与者发送 PreCommit 申请，同样还是如果存在申请失败或超时，会发送停止申请执行事务回滚
4. 协调者收到所有 PreCommit 申请的回答时，如果全是“是”那么则进入 DoCommit 阶段，否则发送停止申请，执行事务回滚
5. 进入 DoCommit 阶段后，协调者会向所有参与者发送 DoCommit 申请 ，留神这里，如果某个参与者没有收到该申请，它 默认认为协调者会发送提交申请 ，那么便本地执行提交事务，从而 防止阻塞

3PC 尽管解决了 2PC 中存在的阻塞问题，然而也引入了新的问题：

• 如果协调者在 DoCommit 阶段回复的是 停止申请 ，那么超时节点自顾自地提交事务就会产生 数据不统一 的状况
• 通信次数减少和实现绝对简单

3PC 使原子提交协定变成非阻塞的，然而 3PC 假设网络提早和节点响应工夫无限 ，在大多数具备有限网络提早和过程暂停的理论零碎中，它  并不能保障原子性 。非阻塞原子提交须要一个  完满的故障检测器  来以牢靠的机制判断一个节点是否曾经解体，而在有限提早的网络中， 超时并不是一种牢靠的故障检测机制，因为即便节点没有解体也会因为网络提早而超时，出于这个起因，2PC 依然被应用，只管存在协调者故障的问题。

2. 容错共识算法

容错共识算法用于 节点间数据同步，保障各个正本间数据的一致性和集群的高可用 。它的通常模式是一个或多个节点能够  提议（propose）  某些值，而共识算法 决定（decides）  采纳其中的某个值，并让这些节点就提议达成统一。共识算法必须具备如下性质：

• 一致同意：没有两个节点的决定不同
• 完整性：没有节点决定两次
• 有效性 ：如果节点决定了v 值，那么 v 由该节点所提议
• 终止性：由所有未解体的节点来最终决定值

终止性 本质上是说：容错共识算法不能简略地永远闲坐着期待，而是须要依据大多数节点来达成一项决定，因而终止属性也暗含着 不超过一半的节点解体或不可达 的信息。

一致同意和完整性是共识的 核心思想，即所有节点决定了雷同的后果并且决定后不能扭转主见。

容错共识算法在节点集群外部都以某种模式应用一个领导者，并定义了一个 纪元编号（epoch number）  来确保在每个时代中，领导者都是惟一的。每当现任领导宕机时，节点间会开始一场投票，来选出一个新的领导，每次选举被赋予一个新的纪元编号（全序且枯燥递增 ），如果有两个不同时代的领导者之间呈现抵触（脑裂问题），那么带有更高纪元编号的领导者说了算。领导者每想要做出的每一个决定，都必须将提议值发送给其余节点，并期待  法定人数 的节点响应并赞成提案。法定人数通常（但不总是）由少数节点组成（个别为过半），只有在没有发现任何带有更高纪元编号的领导者的状况下，一个节点才会投票赞成提议。

容错共识算法的局限性

1. 节点在做出决定之前对提议进行投票的过程是一种同步复制
2. 共识零碎总是须要有 法定人数 的节点存活来保障运行
3. 大多数共识算法假设参加投票的节点是固定的汇合，这意味着你不能简略的在集群中增加或删除节点
4. 共识零碎通常依附 超时 来检测生效的节点，在网络提早高度变动的环境中，特地是在天文上分布的零碎，常常产生一个节点因为临时的网络问题，谬误地认为领导者曾经生效。尽管这种谬误不会侵害平安属性，但频繁的领导者选举会导致蹩脚的性能体现，所以共识算法对网络问题比拟敏感，而在面对不牢靠的网络相干的共识算法钻研仍在停顿中

3. 2PC 和容错共识算法的区别

1. 负责解决的问题不同：2PC 解决的是分布式事务的一致性，各个节点存储的数据各有不同，指标侧重于保障事务的 ACID；容错共识算法解决的是节点正本间数据的一致性和保障集群的高可用，节点间存储的数据完全一致，指标侧重于数据的复制和同步
2. 每个提议通过要求的参加节点数不同 ：2PC 要求  所有的参与者表决胜利  才通过；容错共识算法只须要  遵循基于法定人数的表决  即可，这也是容错共识算法  终止属性（由所有未解体的节点来决定最终值）  的体现
3. 集群的高可用保障：2PC 的协调者不是通过选举产生的，而是独自部署并人为指定的组件，所以它没有选主机制，不具备高可用性；利用容错共识算法的集群领导者是通过选举机制来指定的，并且在产生异常情况时（主节点宕机）可能选出新的领导者，并进入统一的状态，以此来保障集群的高可用

4. zookeeper 中的一次 Create 申请

一些材料中会提到 zookeeper 在执行 CRUD 申请时，应用的是 2PC，而 实际上它应用的是容错共识算法。咱们以 Create 申请的流程为例（如下图），来加深和记忆这一常识

1. 客户端发 create 申请到 Leader，即便申请没落到 Leader 上，那么其余节点也会将写申请转发到 Leader
2. Leader 会先发一个 提议（proposal）申请给各个 Follower，且本人将数据写到本地文件
3. Follower 集群收到 proposal 申请后会将数据写到本地文件，写胜利后返回给 Leader 一个 ack 回复
4. Leader 发现收到 ack 回复的数量为 法定人数 （过半，蕴含以后 Leader 节点）时，则提交一个 commit 申请给各个 Follower 节点。发送 commit 申请就代表该数据在集群内同步状况没有问题，并且  能够对外提供拜访 了，此时 Leader 会把数据写到内存中
5. Follower 收到 commit 申请后也会将数据写到各自节点的内存中，同时 Leader 会将数据发给 Observer 集群，告诉 Observer 集群 将数据写到内存

伟人的肩膀

• 《数据密集型利用零碎设计》第九章：分布式事务与共识
• 百度百科：三阶段提交
• 浅谈分布式一致性协定之 3PC
• 分布式事务(2PC) vs 共识协定(Paxos/raft)
• 《深度分析 zookeeper 外围原理》
• 原文收录：GitHub-Enthusiasm

作者：京东物流 王奕龙

内容起源：京东云开发者社区