@adamhand 2019-02-27T20:11:00.000000Z 字数 7828 阅读 953

分布式事务

分布式事务概述

数据库事务

关于数据库和数据库事务，已经在另一篇笔记中总结过了，但是为了连贯性，在这里还是简单提一下。

事务是指满足一组ACID的操作。在单机数据库中，一组事务要么全部提交成功，要么全部失败回滚。

单机数据库保证这种操作是通过undo日志和redo日志来实现的。undo日志记录了一组事务开始前数据库的状态，用于事务失败之后的回滚；redo日志用来记录事务执行完成之后的状态，用来将数据库的操作刷到硬盘上。

另外，单机数据库会首先写日志而不是写数据，这种操作叫做“预写日志”。如果事务还没执行完就宕机了，redo日志还没被写完，这是就会根据undo日志恢复到之前的状态；如果redo日志已经写完，这时宕机了，当数据库恢复的时候会根据redo日志中的记录进行数据库操作。

分布式事务

分布式事务就是指事务的参与者、支持事务的服务器、资源服务器以及事务管理器分别位于不同的分布式系统的不同节点之上。以上是《从paxos到zookeeper:分布式一致性原理与实现》中的解释，简单的说，就是一次大的操作由不同的小操作组成，这些小的操作分布在不同的服务器上，且属于不同的应用，分布式事务需要保证这些小操作要么全部成功，要么全部失败。本质上来说，分布式事务就是为了保证不同数据库的数据一致性。

举一个例子，消费者A到商家B的商店里去买东西，其中A和B都有一个银行卡，但是这两张银行卡数据被存放在不同的数据中。付款后，A会将一部分金额转移到B的账户上。这个操作涉及到两个数据库，这就体现了分布式事务。

分布式理论：从CAP到BASE

CAP理论

CAP理论告诉我们，一个分布式系统不可能同时满足一致性(C:Consistency)、可用性(A:Availability)和分区容错性(P:Partition tolerance)，最多只能满足其中的两项。

一致性：一致性是指数据在多个副本之间是否能够保持一致的特性。当一个副本的数据变化的时候，其他副本的数据也会做相同的变化。
可用性：可用性是指系统对于用户的每一个操作总是能够在有限的时间内返回可用的结果。
分区容错性：分区容错性是指，分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络都发生了故障。

其中，一致性又包含很多类型，最常见的有：强一致性、弱一致性和最终一致性。

强一致性：新的数据一旦写入，在任意副本任意时刻都能读到新值。
弱一致性：数据更新后，读操作在数据副本上可能读出来，也可能读不出来。
最终一致性：数据更新后，在某个时间窗口之后保证能够读出来。

在实际工程实践中，最终一致性主要存在五种变种，如下图所示。

在分布式系统中，分区容忍性必不可少，因为需要总是假设网络是不可靠的。因此，CAP 理论实际上是要在可用性和一致性之间做权衡。

BASE理论

BASE 是基本可用（Basically Available）、软状态（Soft State）和最终一致性（Eventually Consistent）三个短语的缩写。

BASE 理论是对 CAP 中一致性和可用性权衡的结果，它的核心思想是：即使无法做到强一致性，但每个应用都可以根据自身业务特点，采用适当的方式来使系统达到最终一致性。

基本可用：指分布式系统在出现故障的时候，保证核心可用，允许损失部分可用性。
比如，一个在线搜索引擎可能需要0.5S的时间将查询结果返回给用户，但是如果出现故障，响应时间可能增加到1~2S。
软状态：指允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性，即允许系统不同节点的数据副本之间进行同步的过程存在时延。
最终一致性：最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。

ACID 要求强一致性，通常运用在传统的数据库系统上。而 BASE 要求最终一致性，通过牺牲强一致性来达到可用性，通常运用在大型分布式系统中。

在实际的分布式场景中，不同业务单元和组件对一致性的要求是不同的，因此 ACID 和 BASE 往往会结合在一起使用。

一致性协议和算法

为了解决分布式一致性的问题，涌现出一批经典的一致性协议和算法，比较著名的有：两段提交协议、三段提交协议、本地消息表方法和Paxos算法。

两段提交协议2PC

在两段提交（Two-phase Commit，2PC）中，引入了一种协调者（Coordinator）的组件来统一调度所有分布式节点，这些被调度的分布式节点被称为参与者(Participant)。

两端提交算法分为准备(prepare)阶段和提交(commit)阶段。准备阶段类似于一个投票过程，提交阶段类似于根据投票结果决定执行事务还是回滚的过程。

准备阶段

协调者向所有参与者发送事务内容，并询问是否可以执行事务提交操作，之后就开始等待各个参与者的相应。
参与者执行事务操作，并将undo日志和redo日志写入事务日志中。
如果参与者成功执行了事务操作，就反馈给协调者yes响应，反之返回no响应。

提交阶段

根据参与者反馈的结果，提交阶段可能产生两种情况：

执行事务提交。如果所有的参与者都返回的yes响应，那么协调者就会给所有参与者发送提交请求，参与者收到后会进行事务提交并返回给协调者ack信号，协调者收到ack信号代表事务完成。
中断事务。如果有任意参与者返回了no响应或者协调者等待超时后没有收到反馈，就会向所有参与者发送回滚请求，参与者根据undo日志回滚后发送ack响应给协调者，协调者收到响应后表示中断完成。

需要注意的是，在准备阶段，参与者执行了事务，但是还未提交。只有在提交阶段接收到协调者发来的通知后，才进行提交或者回滚。

整个过程如下图所示：

优缺点

两端提交的优点是原理简单，实现方便。

缺点主要有四个：

同步阻塞：所有事务参与者在等待其它参与者响应的时候都处于同步阻塞状态，无法进行其它操作。
单点问题：协调者在 2PC 中起到非常大的作用，发生故障将会造成很大影响。特别是在阶段二发生故障，所有参与者会一直等待，无法完成其它操作。
数据不一致：在阶段二，如果协调者只发送了部分 Commit 消息，此时网络发生异常，那么只有部分参与者接收到 Commit 消息，也就是说只有部分参与者提交了事务，使得系统数据不一致。
太过保守：任意一个节点失败就会导致整个事务失败，没有完善的容错机制。

三段提交协议3PC

三段提交（Three-phase Commit，3PC)，是对两段提交的改进，它将两段提交的第二阶段一分为二，形成了CanCommit、PreCommit和doCommit三个阶段。

CanCommit阶段

协调者想所有参与者发送一个包含事务内容的canCommit请求，询问是否可以执行事务提交操作，并开始等待各个参与者的响应。
参与者收到请求后，如果认为自己可以顺利执行事务，会反馈yes响应，并进入预准备状态，否则返回no响应。

PreCommit

根据参与者的反馈信号，可能有两种情况：

执行事务预提交。如果所有参与者反馈的都是yes响应，会执行预提交。协调者向所有参与者发出preCommit请求，并进入Prepared阶段。参与者的收到请求后，会执行事务操作，并写入undo和redo日志。如果参与者成功执行了事务，会返回ack响应。
中断事务。如果协调者收到了no响应或者超时未收到响应，就会发送给参与者abort请求。

无论参与者收到了abort或者由于协调者宕机等因素超时未收到消息，都会中断事务。

doCommit

该阶段真正进行事务提交，也有两种情况。

执行提交。如果协调者处于正常工作状态并且收到了来自所有参与者的ack响应，那么它将从“预提交”状态转换到“提交”转台，并向所有参与者发送doCommit请求。参与者收到doCommit请求后，会执行事务提交操作，并向协调者发送ack消息。协调者收到所有ack消息后，完成事务。
中断事务。假如协调者没有收到所有参与者发送的对于preCommit请求的ack响应，就会发送中断请求abort。参与者收到abort请求后会根据undo日志进行事务回滚。完成之后会向协调者发送ack响应。协调者接受到所有ack响应之后代表中断事务完成。

需要注意的是，一旦进入阶段三，可能会出现两种故障：

协调者出现问题。
协调者和参与者之间的网络出现故障。

无论哪种情况，最终都会导致参与者无法及时接收到来自协调者的doCommit或abort请求，针对这种异常情况，参与者都会在等待超时之后，继续进行事务提交或回滚。

三段提交的整个过程如下图：

优缺点

优点：相比较于两段提交协议，三段提交协议最大的优点就是引入了超时机制，降低了参与者的阻塞范围，并能够在出现单点故障后继续达成一致。

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

本地消息表

本地消息表与业务数据表处于同一个数据库中，这样就能利用本地事务来保证在对这两个表的操作满足事务特性，并且使用了消息队列来保证最终一致性。

在分布式事务操作的一方完成写业务数据的操作之后向本地消息表发送一个消息，本地事务能保证这个消息一定会被写入本地消息表中。
之后将本地消息表中的消息转发到 Kafka 等消息队列中，如果转发成功则将消息从本地消息表中删除，否则继续重新转发。
在分布式事务操作的另一方从消息队列中读取一个消息，并执行消息中的操作。

Paxos算法

Paxos算法用于达成共识性问题，即对多个节点产生的值，该算法能保证只选出唯一一个值。

Paxos算法解决的是非拜占庭问题，即消息在传输的过程中可能会延迟、丢失或者重复，但是不会被篡改。

Paxos中的节点被分成三类，一个节点可能同时具有多个身份：

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

执行过程

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

1. Prepare 阶段

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

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

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

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

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

2. Accept 阶段

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

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

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

3. Learn 阶段

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

约束条件

1. 正确性

指只有一个提议值会生效。

因为 Paxos 协议要求每个生效的提议被多数 Acceptor 接收，并且 Acceptor 不会接受两个不同的提议，因此可以保证正确性。

2. 可终止性

指最后总会有一个提议生效。

Paxos 协议能够让 Proposer 发送的提议朝着能被大多数 Acceptor 接受的那个提议靠拢，因此能够保证可终止性。

活性(liveness)

活性即算法不会产生死锁。考虑一种情况：

Proposer P1提出了一个编号为M1的提案，并完成了Prepare阶段；与此同时，Proposer P2提出了一个编号为M2(M2>M1)的提案，同样也完成了Prepare阶段，于是Accepter已经承诺不再批准编号小于M2的提案了。因此当P1进入Accept阶段的时候，它发出的Accept请求将被Accepter忽略，于是P1再次进入Prepare阶段并提出了一个编号为M3(M3>M2)的提案，而这又导致了P2在第二阶段的Accept请求被忽略，以此类推，提案的选定将会陷入死循环。

为了保证算法的活性，Paxos就必须选择一个主Proposer，并规定只有主Proposer才能提出议案，这样一来，只要主Proposer和过半的Accepter能够通信，那么但凡主Proposer提出一个编号更高的提案，那么这个提案终究会被批准。

约束条件

1. 正确性

指只有一个提议值会生效。

因为 Paxos 协议要求每个生效的提议被多数 Acceptor 接收，并且 Acceptor 不会接受两个不同的提议，因此可以保证正确性。

2. 可终止性

指最后总会有一个提议生效。

Paxos 协议能够让 Proposer 发送的提议朝着能被大多数 Acceptor 接受的那个提议靠拢，因此能够保证可终止性。

可以看到，两段提交协议存在着同步阻塞、无限期等待和“脑裂”(网络分区)等问题；三段提交通过引入超时机制和PreCommit，解决了无期限等待和同步阻塞的问题；Paxos算法通过引入“过半”(少数服从多数的理念)解决了“脑裂”的问题。

Raft算法

Raft 也是分布式一致性协议，主要是用来竞选主节点。

首先介绍几个概念：

三个状态
在一个由Raft协议组织的集群中存在三种角色：

Leader：领导人，负责整个集群与外界客户端的交互；
Candidate：候选人，Follower节点想要变为Leader节点要经过的中间状态；
Follower：群众，所有节点在初始化时都是Follower，具有投票权；

一个任期

Term：任期，其实是一个编号，标志现在有某个Leader进行“统治”。当发生Leader变化的时候，Term会加一。

两个过程

Leader Election：Follower竞选变为Leader的过程；一般有两种情况，单个Candidate竞选和多个Candidate竞选。
Log Replication：Leader节点对客户端发来的消息进行全网共识的过程；

两个timeout

Election timeout：是follower变成candidate需要等待的一段时间，是一个介于150ms~300ms之间的随机数；
Heartbeet timeout：Leader会每隔heartbeat timeout向所有follower发送Append Entries消息来维持其任期；

两个消息