分布式事务
提出问题
数据的一致性：
- 数据的并发访问、修改。
- 多个服务共同完成一个业务请求，保证都完成或失败。发生异常时的数据回滚。
- 在分布式系统中，为了保证数据的高可用，通常，我们会将数据保留多个副本(replica)，这些副本会放置在不同的物理机器上。为了对用户提供正确的CRUD等语义，我们需要保证这些放置在不同物理机器上的副本是一致的。
是什么
- 分布式事务就是将多个节点的事务看成一个整体处理。
- 分布式事务由事务参与者、资源服务器、事务管理器等组成。
- 事务参与者：例如下订单、扣除库存、支付的机器。
- 资源服务器：控制我们在用的订单状态、库存数量等。
- 事务管理器：帮助协调等功能。如果一个事务参与者挂掉了，由它进行通知其他两个。
应用
适用性
应用场景
理论
CAP
CAP定理，又被叫作布鲁尔定理。对于设计分布式系统来说(不仅仅是分布式事务)的架构师来说，CAP就是你的入门理论。
- C (一致性)：对某个指定的客户端来说，读操作能返回最新的写操作。对于数据分布在不同节点上的数据上来说，如果在某个节点更新了数据，那么在其他节点如果都能读取到这个最新的数据，那么就称为强一致，如果有某个节点没有读取到，那就是分布式不一致。
- A (可用性)：非故障的节点在合理的时间内返回合理的响应(不是错误和超时的响应)。可用性的两个关键一个是合理的时间，一个是合理的响应。合理的时间指的是请求不能无限被阻塞，应该在合理的时间给出返回。合理的响应指的是系统应该明确返回结果并且结果是正确的，这里的正确指的是比如应该返回50，而不是返回40。
- P (分区容错性)：当出现网络分区后，系统能够继续工作。打个比方，这里个集群有多台机器，有台机器网络出现了问题，但是这个集群仍然可以正常工作。
- 网络分区：即分区间的机器无法进行网络通信的情况是必然会发生的。
- 一个分布式系统里面，节点组成的网络本来应该是连通的。然而可能因为一些故障，使得有些节点之间不连通了，整个网络就分成了几块区域。数据就散布在了这些不连通的区域中。这就叫分区。
- 当你一个数据项只在一个节点中保存，那么分区出现后，和这个节点不连通的部分就访问不到这个数据了。这时分区就是无法容忍的。
- 提高分区容忍性的办法就是一个数据项复制到多个节点上，那么出现分区之后，这一数据项就可能分布到各个区里，容忍性就提高了。
- 然而，要把数据复制到多个节点，就会带来一致性的问题，就是多个节点上面的数据可能是不一致的。
- 要保证一致，每次写操作就都要等待全部节点写成功，而这等待又会带来可用性的问题。
- 总的来说就是，数据存在的节点越多，分区容忍性越高，但要复制更新的数据就越多，一致性就越难保证。为了保证一致性，更新所有节点数据所需要的时间就越长，可用性就会降低。
熟悉CAP的人都知道，三者不能共有，如果感兴趣可以搜索CAP的证明，在分布式系统中，网络无法100%可靠，分区其实是一个必然现象，如果我们选择了CA而放弃了P，那么当发生分区现象时，为了保证一致性，这个时候必须拒绝请求，但是A又不允许，所以分布式系统理论上不可能选择CA架构，只能选择CP或者AP架构。
对于CP来说，放弃可用性，追求一致性和分区容错性，我们的zookeeper其实就是追求的强一致。
对于AP来说，放弃一致性(这里说的一致性是强一致性)，追求分区容错性和可用性，这是很多分布式系统设计时的选择，后面的BASE也是根据AP来扩展。
顺便一提，CAP理论中是忽略网络延迟，也就是当事务提交时，从节点A复制到节点B，但是在现实中这个是明显不可能的，所以总会有一定的时间是不一致。同时CAP中选择两个，比如你选择了CP，并不是叫你放弃A。因为P出现的概率实在是太小了，大部分的时间你仍然需要保证CA。就算分区出现了你也要为后来的A做准备，比如通过一些日志的手段，是其他机器回复至可用。
BASE
BASE 是 Basically Available(基本可用)、Soft state(软状态)和 Eventually consistent (最终一致性)三个短语的缩写。是对CAP中AP的一个扩展：
- 基本可用：分布式系统在出现故障时，允许损失部分可用功能，保证核心功能可用。
- 软状态：允许系统中存在中间状态，这个状态不影响系统可用性，这里指的是CAP中的不一致。
- 最终一致：最终一致是指经过一段时间后，所有节点数据都将会达到一致。
BASE解决了CAP中理论没有网络延迟，在BASE中用软状态和最终一致，保证了延迟后的一致性。BASE和 ACID 是相反的，它完全不同于ACID的强一致性模型，而是通过牺牲强一致性来获得可用性，并允许数据在一段时间内是不一致的，但最终达到一致状态。
一致性模型
强一致性
当更新操作完成之后，任何多个后续进程或者线程的访问都会返回最新的更新过的值，直到这个数据被其他数据更新为止。
但是这种实现对性能影响较大，因为这意味着，只要上次的操作没有处理完，就不能让用户读取数据。
弱一致性
系统并不保证进程或者线程的访问都会返回最新更新过的值。系统在数据写入成功之后，不承诺立即可以读到最新写入的值，也不会具体的承诺多久之后可以读到。但会尽可能保证在某个时间级别（比如秒级别）之后，可以让数据达到一致性状态。
最终一致性
最终一致性也是弱一致性的一种，它无法保证数据更新后，所有后续的访问都能看到最新数值，而是需要一个时间，在这个时间之后可以保证这一点，而在这个时间内，数据也许是不一致的，这个系统无法保证强一致性的时间片段被称为「不一致窗口」。不一致窗口的时间长短取决于很多因素，比如备份数据的个数、网络传输延迟速度、系统负载等。
| 类型 | 说明 |
|---|---|
| 因果一致性 | 如果 A 进程在更新之后向 B 进程通知更新的完成，那么 B 的访问操作将会返回更新的值。而没有因果关系的 C 进程将会遵循最终一致性的规则（C 在不一致窗口内还是看到是旧值）。 |
| 读你所写一致性 | 因果一致性的特定形式。一个进程进行数据更新后，会给自己发送一条通知，该进程后续的操作都会以最新值作为基础，而其他的进程还是只能在不一致窗口之后才能看到最新值。 |
| 会话一致性 | 读你所写一致性的特定形式。进程在访问存储系统同一个会话内，系统保证该进程可以读取到最新之，但如果会话终止，重新连接后，如果此时还在不一致窗口内，还是可嫩读取到旧值。 |
| 单调读一致性 | 如果一个进程已经读取到一个特定值，那么该进程不会读取到该值以前的任何值。 |
| 单调写一致性 | 系统保证对同一个进程的写操作串行化。 |
概述
分类
- 第一行表头代表了分布式系统中通用的一致性方案，包括冷备、Master/Slave、Master/Master、两阶段提交以及基于Paxos算法的解决方案。
- 第一列表头代表了分布式系统大家所关心的各项指标，包括一致性、事务支持程度、数据延迟、系统吞吐量、数据丢失可能性、故障自动恢复方式。
实现
分布式事务主要的关注是资源与网络问题。
2PC、3PC实际上很少有在用，都是在用变形。
两段式事务(2PC)
- 保证在分布式事务中，要么所有参与进程都提交事务，要么都取消事务。
- 在数据一致性中，它的含义是：要么所有副本（备份数据）同时修改某个数值，要么都不更改，以此来保证数据的强一致性。
2PC的思路是：参与者将操作结果通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。从而使得节点知道其他节点的操作状态。
过程
- 表决阶段：此时Coordinator（协调者）向所有的参与者发送一个vote request，参与者在收到这请求后，如果准备好了就会向Coordinator发送一个
VOTE_COMMIT消息作为回应，告知Coordinator自己已经做好了准备，否则会返回一个VOTE_ABORT消息。 - 提交阶段：Coordinator收到所有参与者的表决信息，如果所有参与者一致认为可以提交事务，那么Coordinator就会发送
GLOBAL_COMMIT消息，否则发送GLOBAL_ABORT消息；对于参与者而言，如果收到GLOBAL_COMMIT消息，就会提交本地事务，否则就会取消本地事务。
如果都就绪了，但是其中一个事务提交了之后立即宕机了，即对事务处理器而言是不知道事务是否处理成功了。
存在的问题
网络角度考虑：
可能发生 Coordinator 或者参与者突然宕机的情况，在不同时期宕机可能有不同的现象：
| 情况 | 分析及解决方案 |
|---|---|
| Coordinator 挂了，参与者没挂 | 这种情况其实比较好解决，只要找一个Coordinator的替代者。当他成为新的Coordinator的时候，询问所有参与者的最后那条事务的执行情况，他就可以知道是应该做什么样的操作了。所以，这种情况不会导致数据不一致。 |
| 参与者挂了（无法恢复），Coordinator 没挂 | 如果挂了之后没有恢复，那么是不会导致数据一致性问题。 |
| 参与者挂了（后来恢复），Coordinator 没挂 | 恢复后参与者如果发现有未执行完的事务操作，直接取消，然后再询问Coordinator目前我应该怎么做，协调者就会比对自己的事务执行记录和该参与者的事务执行记录，告诉他应该怎么做来保持数据的一致性。 |
参与者挂了，Coordinator 也挂了，需要再细分为几种类型来讨论：
| 情况 | 分析及解决方案 |
|---|---|
| Coordinator 和参与者在第一阶段挂了 | 由于这时还没有执行commit操作，新选出来的Coordinator可以询问各个参与者的情况，再决定是进行commit还是roolback。因为还没有commit，所以不会导致数据一致性问题。 |
| Coordinator 和参与者在第二阶段挂了，但是挂的这个参与者在挂之前还没有做相关操作 | 这种情况下，当新的Coordinator被选出来之后，他同样是询问所有参与者的情况。只要有机器执行了abort（roolback）操作或者第一阶段返回的信息是No的话，那就直接执行roolback操作。如果没有人执行abort操作，但是有机器执行了commit操作，那么就直接执行commit操作。这样，当挂掉的参与者恢复之后，只要按照Coordinator的指示进行事务的commit还是roolback操作就可以了。因为挂掉的机器并没有做commit 或者roolback操作，而没有挂掉的机器们和新的Coordinator又执行了同样的操作，那么这种情况不会导致数据不一致现象。 |
| Coordinator 和参与者在第二阶段挂了，挂的这个参与者在挂之前已经执行了操作。但是由于他挂了，没有人知道他执行了什么操作 | 这种情况下，新的Coordinator被选出来之后，如果他想负起Coordinator的责任的话他就只能按照之前那种情况来执行commit或者roolback操作。这样新的Coordinator和所有没挂掉的参与者就保持了数据的一致性，我们假定他们执行了commit。但是，这个时候，那个挂掉的参与者恢复了怎么办，因为他已经执行完了之前的事务，如果他执行的是commit那还好，和其他的机器保持一致了，万一他执行的是roolback操作呢？这不就导致数据的不一致性了么？虽然这个时候可以再通过手段让他和Coordinator通信，再想办法把数据搞成一致的，但是，这段时间内他的数据状态已经是不一致的了！ |
- 单点问题:事务管理器在整个流程中扮演的角色很关键，如果其宕机，比如在第一阶段已经完成，在第二阶段正准备提交的时候事务管理器宕机，资源管理器就会一直阻塞，导致数据库无法使用。
- 实际生产应用中，Coordinator 都会有相应的备选节点。
- 同步阻塞:在准备就绪之后，资源管理器中的资源一直处于阻塞，直到提交完成，释放资源。
- 超时判断机制来解决的，但并不能完全解决同步阻塞问题。
- 数据不一致:两阶段提交协议虽然为分布式数据强一致性所设计，但仍然存在数据不一致性的可能，比如在第二阶段中，假设协调者发出了事务commit的通知，但是因为网络问题该通知仅被一部分参与者所收到并执行了commit操作，其余的参与者则因为没有收到通知一直处于阻塞状态，这时候就产生了数据的不一致性。
适用性
XA协议比较简单，成本较低，但是其单点问题，以及不能支持高并发(由于同步阻塞)依然是其最大的弱点。
三段式事务(3PC)
如果出现协调者和参与者都挂了的情况，有可能导致数据不一致。为了解决这个问题，衍生出了3PC。
在准备提交与已经提交中间加入了一个预备提交的阶段。
过程
阶段一 CanCommit
- 事务询问：Coordinator向各参与者发送CanCommit的请求，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
- 参与者向Coordinator反馈询问的响应：参与者收到CanCommit请求后，正常情况下，如果自身认为可以顺利执行事务，那么会反馈Yes响应，并进入预备状态，否则反馈No。
阶段二 PreCommit
执行事务预提交：如果Coordinator接收到各参与者反馈都是Yes，那么执行事务预提交。
- 发送预提交请求：Coordinator向各参与者发送preCommit请求，并进入prepared阶段。
- 事务预提交：参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo信息记录到事务日记中。
- 各参与者向Coordinator反馈事务执行的响应：如果各参与者都成功执行了事务操作，那么反馈给协调者ACK响应，同时等待最终指令，提交commit或者终止abort，结束流程。
中断事务：如果任何一个参与者向Coordinator反馈了No响应，或者在等待超时后，Coordinator无法接收到所有参与者的反馈，那么就会中断事务。
- 发送中断请求：Coordinator向所有参与者发送abort请求。
- 中断事务：无论是收到来自Coordinator的abort请求，还是等待超时，参与者都中断事务。
阶段三 doCommit
执行提交
- 发送提交请求：假设Coordinator正常工作，接收到了所有参与者的ack响应，那么它将从预提交阶段进入提交状态，并向所有参与者发送doCommit请求。
- 事务提交：参与者收到doCommit请求后，正式提交事务，并在完成事务提交后释放占用的资源。
- 反馈事务提交结果：参与者完成事务提交后，向Coordinator发送ACK信息。
- 完成事务：Coordinator接收到所有参与者ack信息，完成事务。
中断事务：假设 Coordinator 正常工作，并且有任一参与者反馈 No，或者在等待超时后无法接收所有参与者的反馈，都会中断事务：
- 发送中断请求：Coordinator向所有参与者节点发送abort请求。
- 事务回滚：参与者接收到abort请求后，利用undo日志执行事务回滚，并在完成事务回滚后释放占用的资源。
- 反馈事务回滚结果：参与者在完成事务回滚之后，向Coordinator发送ack信息。
- 中断事务：Coordinator接收到所有参与者反馈的ack信息后，中断事务。
存在的问题
3PC依然带来其他问题：在阶段三时，协调者出现问题、协调者与参与者之间网络出现故障。不论出现哪种情况，最终都会导致参与者无法及时接收到来自协调者的doCommit或是abort请求，针对这种情况，参与者都会在等待超时后，继续进行事务提交（timeout后中断事务）。
而且由于3PC 的设计过于复杂，在解决2PC 问题的同时也引入了新的问题，所以在实际上应用不是很广泛。
基于XA的分布式事务
本质上也是一种两段式提交，MySQL、Oracle等基本都支持该XA事务。
Paxos（解决单点问题）
提出问题
如果对多个副本执行的操作序列[op1, op2, …, opn]不进行任何控制，那网络延迟、超时等各种故障都会导致各个副本之间的更新操作是不同的，这样很难保证副本间的一致性。所以为了保证分布式存储系统数据的一致性，我们希望在各个副本之间的更新操作序列是相同的、不变的，即每个副本执行[op1, op2, …, opn]顺序是相同的。我们通过Paxos算法依次来确定不可变变量opi的取值，即第i个操作是什么。每次确定完opi之后，可以让各个副本来执行opi，依次类推。
是什么
基于消息传递且具有高度容错性的一致性算法。Paxos算法要解决的问题就是如何在可能发生几起宕机或网络异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。
其解决的问题是：Paxos如何确定一个不可变变量的取值。取值可以是任意二进制数据，并且一旦确定将不再更改，并且可以被获取到（不可变性、可读取性）。
分类
- Basic Paxos。
- 一个或多个提议者，一次只能通过一个提案。
- 例如提议中午吃什么。
- Multi Paxos。
- 多个提议者，可以同时通过多个提案。
- 例如同时提出多个提议，比如中午吃什么、吃完去哪里嗨皮、谁请客等提议。
三个角色
- Proposer负责提出议案。Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。
- Acceptor参与决策，回应Proposers的提案。收到Proposal后可以接受提案，若Proposal获得多数Acceptors的接受，则称该Proposal被批准。
- Learner不参与决策，从Proposers/Acceptors学习最新达成一致的提案（Value）。
适用性
- 与2PC、3PC是互补关系。
- Paxos协议用于保证同一个数据分片在多个副本的一致性。2PC用于保证多个数据分片上事务的原子性。
详解
两个阶段
- Prepare阶段。
- Proposer向Acceptors发出Prepare请求，Acceptors针对收到的Prepare请求进行Promise承诺。
- 作用是阻止旧的提案，以及检查是否有已接受的提案值。
- Accept阶段。
- Proposer收到多数Acceptors承诺的Promise后，向Acceptors发出Propose请求，Acceptors针对收到的Propose请求进行Accept处理。
- Learn阶段。
- Proposer在收到多数Acceptors的Accept之后，标志着本次Accept成功，决议形成，将形成的决议发送给所有Learners。
两个消息
- Prepare：Proposer生成全局唯一且递增的Proposal ID (可使用时间戳加Server ID)，向所有Acceptors发送Prepare请求，这里无需携带提案内容，只携带Proposal ID即可。
- Promise：Acceptors收到Prepare请求后，做出“两个承诺，一个应答”。
两个承诺
- 不再接受Proposal ID小于等于（注意：这里是<= ）当前请求的Prepare请求。
- 不再接受Proposal ID小于（注意：这里是< ）当前请求的Propose请求。
一个应答
不违背以前作出的承诺下，回复已经Accept过的提案中Proposal ID最大的那个提案的Value和Proposal ID，没有则返回空值。
过程
Prepare阶段
- Proposer选择一个提案编号n，发送Prepare(n)请求给超过半数（或更多）的Acceptor。
- Acceptor收到消息后，如果n比它之前见过的编号大，就回复这个消息，而且以后不会接受小于n的提案。另外，如果之前已经接受了小于n的提案，回复那个提案编号和内容给Proposer。
Accept阶段
- 当Proposer收到超过半数的回复时，就可以发送Accept(n, value)请求了。 n就是自己的提案编号，value是Acceptor回复的最大提案编号对应的value，如果Acceptor没有回复任何提案，value就是Proposer自己的提案内容。
- Acceptor收到消息后，如果n大于等于之前见过的最大编号，就记录这个提案编号和内容，回复请求表示接受。
- 当Proposer收到超过半数的回复时，说明自己的提案已经被接受。否则回到第一步重新发起提案。
Basic Paxos
Multi Paxos
Multi Paxos会从Proposer中选出一个Leader，只由Leader提交Proposal，还可以省去Prepare阶段，减少了性能损失。
由于可以并行提案，则要能存储不同的提案，也要保证提案的顺序。Acceptor的结构如图所示，每个方块代表一个Entry，用于存储提案值。用递增的Index来区分Entry。
省略Prepare阶段
当只有一个Leader发送提案的时候，Prepare是不会产生冲突的，可以省略Prepare阶段，这样就可以减少一半RPC请求。
Prepare请求的逻辑修改为：
- Acceptor记录一个全局的最大提案编号。
- 回复最大提案编号，如果当前entry以及之后的所有entry都没有接受任何提案，回复noMoreAccepted。
当Leader收到超过半数的noMoreAccepted回复，之后就不需要Prepare阶段了，只需要发送Accept请求。直到Accept被拒绝，就重新需要Prepare阶段。
问题
- Basic Paxos只需超过半数的节点达成一致。但是在Multi-Paxos中，这种方式可能会使一些节点无法得到完整的entry信息。我们希望每个节点都拥有全部的信息。
- Proposer给全部节点发送Accept请求。
- 只有Proposer知道一个提案是否被接受了（根据收到的回复），而Acceptor无法得知此信息。
- 我们可以增加一个Success RPC，让Proposer显式地告诉Acceptor，哪个提案已经被接受了。
- 或在Accept请求中，增加一个firstUnchosenIndex参数，表示Proposer的第一个未接受的Index，这个参数隐含的意思是，对该Proposer来说，小于Index的提案都已经被接受了。因此Acceptor可以利用这个信息，把小于Index的提案标记为已接受。另外要注意的是，只能标记该Proposer的提案，因为如果发生Leader切换，不同的Proposer拥有的信息可能不同，不区分Proposer直接标记的话可能会不一致。
Raft
Raft算法是对Paxos的简化和改进，变得更加容易理解和实现。
Raft协议实战之Redis Sentinel的选举Leader源码解析
基于消息的最终一致性方案
常见场景：
- 扫码下单后，支付成功了，钱已经到了支付宝。此时要下单，然而下单失败了。
- 先下单，然后sleep，已经准备提交了。然后告诉订单去修改状态。如果订单状态修改成功了，则支付成功；否则支付失败。
- 好处：强一致性方案，不会出现资源浪费，要么成功要么失败。
- 缺陷：会对时间有一定影响。
消息中间件：rabbitMQ、rocketMQ(支持一些增强功能)等。
单机系统下的事务：
分布式系统下：
- 发送预备消息：
TCC编程式补偿式事务
Try-Confirm-Cancel。最优？
- 启动事务：业务系统执行任务。
- Try：尝试进行事务操作，根据返回结果，确定是否Confirm。
- 提交或回滚事务：如果Try的结果是有一个服务执行失败，则执行Cancel接口。
对于APP与业务系统，不需要关心接口的实现。并且通过Cancel进行补偿事务的错误。
适用性
功能：
- 解决了协调者单点，由主业务方发起并完成这个业务活动。业务活动管理器也变成多点，引入集群。
- 同步阻塞:引入超时，超时后进行补偿，并且不会锁定整个资源，将资源转换为业务逻辑形式，粒度变小。
- 数据一致性，有了补偿机制之后，由业务活动管理器控制一致性。
场景：
- 强隔离性，严格一致性要求的活动业务。
- 执行时间较短的业务。
对比
- 基于消息的事务是强一致性事务，存在资源浪费。
- 解决支付宝等支付问题，是非常有效的解决方案。即解决无法补偿的任务。
- 线程需要等待，如果很多基于消息的事务，则会很慢。
- TCC事务是柔性事务。在try阶段要对资源做预留，在Confirm与Cancel阶段释放资源。
- TCC事务时效性比基于消息的事务更好。
分布式事务的前世今生
分布式事务框架
全局事务服务(Global Transaction Service)：GTS。
蚂蚁金服分布式事务（Distributed Transaction-eXtended）：DTX，解决金融相关的强事务。
开源TCC框架（TCC-transaction）
开源TCC框架（ByteTCC）