《从 PAXOS 到 ZOOKEEPER：分布式一致性原理与实践》读书笔记

1 分布式

1.1 定义

分布式系统是一个硬件或软件组件分布在不同的网络计算机上，彼此之间仅仅通过消息传递进行通信和协调的系统

1.2 特点

分布性、对等性、并发性、缺乏全局时钟、故障总是会发生

2 CAP 和 BASE

2.1 CAP

CAP 理论：一个分布式系统不可能同时满足一致性、可用性和分区容错性

一致性：一致性是指数据在多个副本之间是否能够保持一致的特性

可用性：可用性是指系统提供的服务必须一直处于可用的状态

分区容错性：分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务

2.2 BASE

Base 理论：基本可用、软状态、最终一致性

基本可用：分布式系统在出现不可预知故障的时候，允许损失部分可用性

弱状态：允许系统中的数据存在中间状态，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时

最终一致性：系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一直的状态

3 一致性协议

3.1 2PC

二阶段提交协议就是将事务的提交过程分成两个阶段来进行处理

3.1.1 执行流程

提交事务请求

• 1、事务询问：协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应
• 2、执行事务：各参与者节点执行事务操作，并将 Undo 和 Redo 信息记入事务日志中
• 3、各参与者向协调者反馈事务询问的响应：如果参与者成执行了事务操作，那么就反馈给协调者 YES，表示事务可以执行；反正为 NO，事务不可以执行

执行事务提交

协调者从所有的参与者获得的反馈都是 YES

• 1、发送提交请求：协调者向所有参与者节点发出 Commit 请求
• 2、事务提交：参与者在接收到 Commit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源
• 3、反馈事务提交结果：参与者在完成事务提交后，向协调者发送 Ack 消息
• 4、完成事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务

中断事务

假设任何一个参与者向协调者反馈了 NO 请求，或者等待超时后吗，协调者尚无法接收所有参与者的反馈响应，就会中断事务

• 1、发送回滚请求：协调者向所有参与者节点发送 Rollback 请求
• 2、事务回滚：参与者收到 Rollback 请求后，会利用其在阶段一中记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放在这个事务执行期间占用的资源
• 3、反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送 Ack 消息
• 4、中断事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务中断

3.1.2 优缺点

优点：原理简单，实现方便

缺点：

• 同步阻塞：在事务提交过程中，所以参与该事务操作的逻辑都处于阻塞状态，无法进行其他任何操作
• 单点问题：如果协调者在事务提交阶段挂掉，那么其他参与者将一直处于锁定事务资源的状态，而无法继续完成事务操作
• 数据不一致：如果协调者在发送 Commit 请求时，出现局部网络异常，那么就会导致只有部分参与者收到了 Commit 请求并进行事务的提交，而其他没有收到 Commit 请求的参与者则无法进行事务提交，于是会出现数据不一致现象
• 太过保守：没有设计较为完善的容错机制，任意一个节点的失败都会导致整个事务的失败

3.2 3PC

3.2.1 执行流程

CanCommit

• 1、事务询问：协调者向所有参与者发送一个包含事务内容的 canCommit 请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应
• 2、各参与者向协调者反馈事务询问的响应：参与者在接收到来自协调者 canCommit 请求后，正常情况下，如果其自身认为可以顺利执行事务，就会反馈 Yes 响应，并进入预备状态，否则反馈 NO 响应

PreCommit

执行事务预提交

• 1、发送预提交请求：协调者向所有参与者节点发出 preCommit 的请求，并进入 Prepared 阶段
• 2、事务预提交请求：参与者接收到 preCommit 请求后，会执行事务操作，并将 Undo 和 Redo 信息记录到事务日志中
• 3、各参与者向协调者反馈事务执行的响应：如果参与者成功执行了事务操作，那么就会反馈给协调者 Ack 响应，同时等待最终的指令

中断事务

假设任何一个参与者向协调者反馈了 No 响应，或者在等待超时之后，协调者尚无法接收到所有参与者的反馈响应，就会中断事务

• 1、发送中断请求：协调者向所有参与者节点发送 abort 请求
• 2、中断事务：参与者中断事务

doCommit

执行提交

• 1、发送提交请求：协调者收到所有参与者的 Ack 的响应后，会向所有参与者发送 doCommit 请求
• 2、事务提交：参与者接收到 doCommit 请求后，会正式执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源
• 3、反馈事务提交结果：参与者在完成事务提交后，向协调者发送 Ack 消息
• 4、完成事务：协调者接收到所有参与者反馈的 Ack 消息后，完成事务

中断事务

任何一个参与者向协调者发送 NO 反馈，或者协调者无法接收到所有参与者的反馈响应

• 1、发送中断请求：协调者向所有参与者节点发送 abort 请求
• 2、事务回滚：参与者接收到 abort 请求后，会利用其记录的 Undo 信息来执行事务回滚操作，并在完成回滚之后释放占用的资源
• 3、反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送 Ack 消息
• 4、中断事务

3.2.2 优缺点

优点：降低了参与者的阻塞范围，并且能够在出现单点故障后继续达成一致

缺点：参与者接收到 preCommit 消息后，如果网络出现分区，此时协调者所在的节点和参与者无法进行正常的网络通信，这种情况下，该参与者依然会进行事务的提交，这必然出现数据的不一致性

3.3 PAXOS

Paxos 一致性算法中，有三种参与角色，Proposer（生成提案），Acceptor（批准提案），Learner

提案选定

阶段一

• 1、Proposer 选择一个提案编号 Mn，然后向 Acceptor 的某个超过半数的子集成员发送编号为 Mn 的 Prepare 请求
• 如果一个 Acceptor 收到一个编号为 Mn 的 Prepare 请求，且编号 Mn 大于该 Acceptor 已经响应的所有 Prepare 请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给 Proposer，同时该 Acceptor 会承诺不再批准任何编号小于 Mn 的提案。举个例子来说，假定一个 Acceptor 已经响应过的所有 Prepare 请求对应的提案编号分别为 1、2、3…、5 和 7，那么该 Acceptor 在接收到一个编号为 8 的perpare 请求后，就会将编号 7 的提案作为响应反馈给 Proposer

阶段二

• 1、如果 Proposer 收到来自半数以上的 Acceptor 对于其发出的编号为 Mn 的 Prepare 请求的响应，那么它就会发送一个针对 [Mn,Vn] 提案的 Accept 请求给 Acceptor。注意，Vn 的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值
• 2、如果 Acceptor 收到针对 [Mn,Vn] 提案的 Accept 请求，只要该 Acceptor 尚未对编号大于 Mn 的 Prepare 请求做出响应，它就可以通过这个提案

提案获取

Acceptor 可以将批准的提案发送给一个特定的 Learner 集合，该集合中的每个 Learner 都可以在一个提案被选定后通知所有其他的 Learner