区块链开发：一致性算法（一） #C04

2019-03-16 本文已影响1385人纳兰少

本篇为资料整理

1. 一致性标准

强一致性：假如A先写入一个值到存储系统，存储系统能够保证后续ABC读取操作都将返回最新值。
弱一致性：假如A先写入一个值到存储系统，系统不能保证ABC的读取操作能否读取到最新值。
最终一致性：假如A先写入一个值到存储系统，后续没有写操作更新同样的值，ABC的读取操作最终都会读取到A写入的最新值。从A写入，到ABC读取到最新值的这段时间，称为“不一致性窗口”。

2. 一致性理论

2.1 CAP

CAP 是指在一个分布式系统下，包含三个要素：Consistency（一致性）、Availability（可用性）、Partition tolerance（分区容错性），并且三者不可得兼。

C：Consistency，一致性，所有数据变动都是同步的。
A：Availability，可用性，即在可以接受的时间范围内正确地响应用户请求。
P：Partition tolerance，分区容错性，即某节点或网络分区故障时，系统仍能够提供满足一致性和可用性的服务。

关系型数据库单节点保证了数据强一致性（C）和可用性（A），但是却无法保证分区容错性（P）。

然而在分布式系统下，为了保证模块的分区容错性（P），只能在数据强一致性（C）和可用性（A）之间做平衡。具体表现为在一定时间内，可能模块之间数据是不一致的，但是通过自动或手动补偿后能够达到最终的一致。

2.2 BASE

BASE 理论主要是解决 CAP 理论中分布式系统的可用性和一致性不可兼得的问题。BASE 理论包含以下三个要素：

BA：Basically Available，基本可用。
S：Soft State，软状态，状态可以有一段时间不同步。
E：Eventually Consistent，最终一致，最终数据是一致的就可以了，而不是时时保持强一致。

BASE 模型与 ACID 不同，满足 CAP 理论，通过牺牲强一致性来保证系统可用性。由于牺牲了强一致性，系统在处理请求的过程中，数据可以存在短时的不一致。

系统在处理业务时，记录每一步的临时状态。当出现异常时，根据状态判断是否继续处理请求或者退回原始状态，从而达到数据的最终一致。

3. 复制

复制协议分为两种，强同步和异步复制。两者的区别在于，是否需要同步到备副本才可以返回成功。当系统出现故障时，分布式系统需要将服务自动切换到备副本，实现自动容错。
强同步复制能保证一致性，但是当备副本出现故障时，会阻塞存储系统的正常写服务，系统的整体可用性受到影响。
异步复制可用性好，但是当主副本出现故障时会出现数据丢失的可能性。

3.1 强同步复制

客户端将写请求发送给主副本，主副本将写请求通过同步commit log来复制到其他副本，备副本根据日志进行操作，完成后通知主副本。然后主副本修改本机，等所有操作都完成后通知客户端些完成。

备副本的个数可能大于1个，实现强同步协议时，主复本可以将操作日志并发地发给所有副本并等待回复，只要有一个备副本返回成功就可以继续操作并恢复客户端操作成功。

主复本出现故障时，至少有一个备副本可用。

3.2 异步复制

异步模式下，主副本不需要等待备副本的回应，本地修改成功后就可以通知客户端操作成功。

4. 分布式协议

分布式事务 : 一台机器在执行本地事务的时候无法知道其他机器中的本地事务的执行结果，他也就不知道本次事务到底应该 commit 还是 roolback。所以，常规的解决办法就是引入一个“协调者”的组件来统一调度所有分布式节点的执行。

4.1 两阶段提交协议

二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。

所谓的两个阶段是指：第一阶段：准备阶段(投票阶段) 和第二阶段：提交阶段（执行阶段）。

4.1.1 提交请求阶段(或者叫做投票阶段)

事务协调者(事务管理器)给每个参与者(参与者, 资源管理器)发送Prepare消息，等待直到收到所有参与者的回复。
参与者在本地节点执行事务(之后协调者会要求提交这个事务)，写本地的redo和undo日志。(会对涉及到的资源加锁，直到第二步完成才释放锁资源)
每一个参与者，如果执行成功，回复一个agreement消息(假如参与者同意执行commit)；如果执行失败，回复一个abort消息。(两阶段提交协议)。

4.1.2 提交阶段(或者叫完成阶段)

成功: 如果协调者接收到所有参与者发送回来的agreement消息：
1. 协调者发送一个commit消息给所有的参与者
2. 每一个参与者完成commit操作，(两阶段提交协议)释放所有事务处理过程中使用的锁资源
3. 每一个参与者回复一个acknowledgment给协调者
4. 协调者在收到所有acknowledgment消息之后完成整个操作
失败: 如果任何一个参与者在提交请求阶段回复abort消息给协调者:
1. 协调者回复一个rollback消息给所有的参与者
2. 每一个参与者执行本地事务的undo操作(根据undo日志记录)，并且释放事务执行过程中使用的资源和锁
3. 每一个参与者给协调者回复acknowledgement消息(两阶段提交协议)。
4. 协调者在接收到所有的参与者的acknowledgement消息之后执行事务undo操作

两阶段提交协议最大的缺点是：它是一个阻塞协议。 当一个节点在等待回复消息时进入阻塞状态。其他需要这些资源的处理事务需要等待。如果协调者挂掉，参与者将永远不能结束它们的事务

4.2 三阶段提交协议

与两阶段提交不同的是，三阶段提交有两个改动点。

引入超时机制。同时在协调者和参与者中都引入超时机制。
在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。

分为 CanCommit、PreCommit、DoCommit 三个阶段

4.2.1 CanCommit 阶段

事务询问，协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。
响应反馈，参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态，否则反馈No。

4.2.2 PreCommit 阶段

假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。
1. 发送预提交请求，协调者向参与者发送PreCommit请求，并进入Prepared阶段。
2. 事务预提交，参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。
3. 响应反馈，如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。
假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
1. 发送中断请求，协调者向所有参与者发送abort请求。
2. 中断事务，参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

4.2.3 DoCommit 阶段

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交
1. 发送提交请求协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。
2. 事务提交参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。
3. 响应反馈事务提交完之后，向协调者发送Ack响应。
4. 完成事务协调者接收到所有参与者的ack响应之后，完成事务。
中断事务，协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。
1. 发送中断请求协调者向所有参与者发送abort请求。
2. 事务回滚参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。
3. 反馈结果参与者完成事务回滚之后，向协调者发送ACK消息。
4. 中断事务协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

在doCommit阶段，如果参与者无法及时接收到来自协调者的doCommit或者rebort请求时，会在等待超时之后，会继续进行事务的提交。（其实这个应该是基于概率来决定的，当进入第三阶段时，说明参与者在第二阶段已经收到了PreCommit请求，那么协调者产生PreCommit请求的前提条件是他在第二阶段开始之前，收到所有参与者的CanCommit响应都是Yes。（一旦参与者收到了PreCommit，意味他知道大家其实都同意修改了）所以，一句话概括就是，当进入第三阶段时，由于网络超时等原因，虽然参与者没有收到commit或者abort响应，但是他有理由相信：成功提交的几率很大。）

4.2.4 2PC与3PC的区别

相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。 但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。