分布式系统

CAP理论

CAP理论是分布式架构中重要理论

• 一致性(Consistency) (所有节点在同一时间具有相同的数据)
• 可用性(Availability) (保证每个请求不管成功或者失败都有响应)
• 分隔容忍(Partition tolerance) (系统在部分节点无法通信的情况下，仍能够保证整体的可用性)

柔性事务

BASE 理论，它是在CAP 理论的基础之上的延伸。包括 基本可用（Basically Available）、柔性状态（Soft State）、最终一致性（Eventual Consistency）。

通常所说的柔性事务分为：两阶段型、补偿型、异步确保型、最大努力通知型几种。

1. 两阶段型

就是分布式事务两阶段提交，对应技术上的XA、JTA/JTS。这是分布式环境下事务处理的典型模式。

或者三阶段型

两阶段和三阶段都属于数据库层面的

2. 补偿型—详解

TCC 型事务（Try/Confirm/Cancel）可以归为补偿型（ByteTCC，TCC-transaction，Himly）。

TCC属于业务层面的分布式事务。

3. 异步确保型（最终一致性分布式事务）

通过将一系列同步的事务操作变为基于消息执行的异步操作, 避免了分布式事务中的同步阻塞操作的影响。

4. 最大努力通知型

这是分布式事务中要求最低的一种,与异步确保型操作不同的一点是, 在消息由MQ Server 投递到消费者之后, 允许在达到最大重试次数之后正常结束事务。

TCC(Try/Confirm/Cancel)

你要玩儿 TCC 分布式事务的话：首先需要选择某种 TCC 分布式事务框架，各个服务里就会有这个 TCC 分布式事务框架在运行。

然后你原本的一个接口，要改造为 3 个逻辑，Try-Confirm-Cancel：

• 先是服务调用链路依次执行 Try 逻辑。—加入一些中间状态
• 如果都正常的话，TCC 分布式事务框架（ByteTCC，TCC-transaction，Himly）推进执行 Confirm 逻辑，完成整个事务。
• 如果某个服务的 Try 逻辑有问题，TCC 分布式事务框架感知到之后就会推进执行各个服务的 Cancel 逻辑，撤销之前执行的各种操作。

这就是所谓的 TCC 分布式事务。

异步确保型（最终一致性分布式事务）

通过消息中间件来实现最终一致性。

事务消息

事务消息是 RocketMQ 提供的一种消息类型，支持在分布式场景下保障消息生产和本地事务的最终一致性。（将消息发送包含在生产者的本地事务中）

1，生产者投递消息，2，RocketMQ持久化消息并通知生产者（消费者暂不能消费，这种状态下的消息称为半事务消息），3.生产者段执行本地的业务逻辑处理，4，根据本地事务执行结果完成第二阶段的提交。5，RocketMQ服务端消息回查。6，生产者接收回查，检查本地事务。7.生产者根据检查到的本地事务的最终状态完成第二阶段的提交。

分布式事务

Java 事务编程接口（JTA：Java Transaction API）和 Java 事务服务 (JTS；Java Transaction Service) 为 J2EE 平台提供了分布式事务服务。分布式事务（Distributed Transaction）包括事务管理器（ Transaction Manager ）和一个或多个支持 XA 协议的资源管理器 ( Resource Manager )。我们可以将资源管理器看做任意类型的持久化数据存储；事务管理器承担着所有事务参与单元的协调与控制。

两阶段提交

两阶段提交主要保证了分布式事务的原子性：即所有结点要么全做要么全不做，所谓的两个阶段

是指：第一阶段：准备阶段；第二阶段：提交阶段。

1 第一阶段

事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的redo 和undo日志，但不提交。

2 第二阶段

如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)

两阶段提交的缺点

1.同步阻塞问题。执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。

2.单点故障。由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）

3.数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。 而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据部一致性的现象。

三阶段提交

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

1、引入超时机制。同时在协调者和参与者中都引入超时机制。

2、在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit 三个阶段。

第一阶段：CanCommit

该阶段协调者会去询问各个参与者是否能够正常执行事务，参与者根据自身情况回复一个预估值，相对于真正的执行事务，这个过程是轻量的，具体步骤如下：

1. 协调者向各个参与者发送事务询问通知，询问是否可以执行事务操作，并等待回复；
2. 各个参与者依据自身状况回复一个预估值，如果预估自己能够正常执行事务就返回确定信息，并进入预备状态，否则返回否定信息。

第二阶段：预提交

本阶段协调者会根据第一阶段的询盘结果采取相应操作，询盘结果主要有 3 种：

1. 所有的参与者都返回确定信息。2.一个或多个参与者返回否定信息。3.协调者等待超时。

针对第 1 种情况，协调者会向所有参与者发送事务执行请求，具体步骤如下：

1. 协调者向所有的事务参与者发送事务执行通知；2.参与者收到通知后执行事务但不提交；3.参与者将事务执行情况返回给客户端。

在上述步骤中，如果参与者等待超时，则会中断事务。 针对第2和第3种情况，协调者认为事务无法正常执行，于是向各个参与者发出 abort 通知，请求退出预备状态，具体步骤如下：

1. 协调者向所有事务参与者发送 abort 通知；2.参与者收到通知后中断事务。

第三阶段：事务提交

如果第二阶段事务未中断，那么本阶段协调者将会依据事务执行返回的结果来决定提交或回滚事务，分为 3 种情况：

1. 所有的参与者都能正常执行事务。2.一个或多个参与者执行事务失败。3.协调者等待超时。

针对第 1 种情况，协调者向各个参与者发起事务提交请求，具体步骤如下：

1. 协调者向所有参与者发送事务 commit 通知；2.所有参与者在收到通知之后执行 commit 操作，并释放占有的资源；3.参与者向协调者反馈事务提交结果。

针对第 2 和第 3 种情况，协调者认为事务无法成功执行，于是向各个参与者发送事务回滚请求，具体步骤如下：

1. 协调者向所有参与者发送事务 rollback 通知；2.所有参与者在收到通知之后执行 rollback 操作，并释放占有的资源；3.参与者向协调者反馈事务回滚结果。

在本阶段如果因为协调者或网络问题，导致参与者迟迟不能收到来自协调者的 commit 或 rollback 请求，那么参与者将不会如两阶段提交中那样陷入阻塞，而是等待超时后继续 commit，相对于两阶段提交虽然降低了同步阻塞，但仍然无法完全避免数据的不一致。

分布式系统中接口的幂等性

**在编程中一个幂等操作的特点是其任意多次执行所产生的影响均与一次执行的影响相同。**幂等函数，或幂等方法，是指可以使用相同参数重复执行，并能获得相同结果的函数。这些函数不会影响系统状态，也不用担心重复执行会对系统造成改变。

对于业务中需要考虑幂等性的地方一般都是接口的重复请求，重复请求是指同一个请求因为某些原因被多次提交。导致这个情况会有几种场景：

• 前端重复提交：提交订单，用户快速重复点击多次，造成后端生成多个内容重复的订单。
• 接口超时重试：对于给第三方调用的接口，为了防止网络抖动或其他原因造成请求丢失，这样的接口一般都会设计成超时重试多次。
• 消息重复消费：MQ消息中间件，消息重复消费。

针对前端重复连续多次点击的情况，例如用户购物提交订单，提交订单的接口就可以通过Token的机制实现防止重复提交。

其他方式：数据库去重表，redis实现，状态机

唯一请求标识： 为每个请求生成唯一的请求标识（Request ID）

幂等性检查： 在服务端接收到请求时，进行幂等性检查。可以使用请求标识、请求参数等来判断是否已经处理过相同的请求。

乐观锁： 在数据库层面使用乐观锁机制

记录请求状态： 在服务端记录每个请求的处理状态，确保已处理的请求状态被正确保存，在重试时，首先检查请求状态，如果已处理则直接返回结果。

分布式唯一ID生成方式

1. 数据库自增ID
2. Redis生成ID
3. UUID生成
4. 雪花算法snowflake
5. 其他 Mongdb objectID， 美团Leaf

Raft协议

Raft 把集群中的节点分为三种状态：Leader、 Follower 、Candidate，理所当然每种状态负责的任务也是不一样的，Raft 运行时提供服务的时候只存在Leader 与Follower 两种状态；

Leader

负责日志的同步管理，处理来自客户端的请求，与Follower 保持这heartBeat 的联系；

Follower

刚启动时所有节点为Follower 状态，响应Leader 的日志同步请求，响应Candidate 的请求，把请求到Follower 的事务转发给Leader；

Candidate

负责选举投票，Raft 刚启动时由一个节点从Follower 转为Candidate 发起选举，选举出Leader 后从Candidate 转为Leader 状态；

Term

在Raft 中使用了一个可以理解为周期（第几届、任期）的概念，用Term 作为一个周期，每个Term 都是一个连续递增的编号，每一轮选举都是一个Term 周期，在一个Term 中只能产生一个Leader；当某节点收到的请求中Term 比当前Term 小时则拒绝该请求。

选举Election

在一个Term 期间每个节点只能投票一次，所以当有多个Candidate 存在时就会出现每个Candidate 发起的选举都存在接收到的投票数都不过半的问题，这时每个Candidate 都将Term递增、重启定时器并重新发起选举，由于每个节点中定时器的时间都是随机的，所以就不会多次存在有多个Candidate 同时发起投票的问题。

日志追加

在Raft 中当接收到客户端的日志（事务请求）后先把该日志追加到本地的Log 中，然后通过heartbeat 把该Entry 同步给其他Follower，Follower 接收到日志后记录日志然后向Leader 发送ACK，当Leader 收到大多数（n/2+1）Follower 的ACK 信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下个heartbeat 中Leader 将通知所有的Follower 将该日志存储在自己的本地磁盘中。

尽管 Raft 协议通过上述机制设计来减轻脑裂问题，但在极端情况下，仍然可能发生脑裂。例如，在网络异常的情况下，可能导致节点之间无法通信，形成多个分离的子集。在这种情况下，Raft 协议无法防止脑裂，因为它无法区分是网络故障还是真正的分区。

Paxos协议

Paxos 三种角色Proposer Acceptor Learners

Proposer

只要Proposer 发的提案被半数以上Acceptor 接受，Proposer 就认为该提案里的value 被选定了。

Acceptor

只要Acceptor 接受了某个提案，Acceptor 就认为该提案里的value 被选定了。

Learner

Acceptor 告诉Learner 哪个value 被选定，Learner 就认为那个value 被选定。

Proposal Number & Agreed Value

Proposal Number 也叫提案编号，我们用n表示，对于每一个Proposer来说，每一个提案编号都是唯一的。 Agreed Value也叫确认值，我们用v来表示，v是Acceptors确认的值。 两个值组合起来就是（n，v）。

阶段1

• 阶段1A：Prepare

  在Prepare阶段，一个Proposer会创建一个Prepare消息，每个Prepare消息都有唯一的提案编号n。n并不是将要提案的内容，而只是一个唯一的编号，用来标志这个Prepare的消息。 n必须比该Proposer之前用过的所有编号都大，一般来说我们可以以数字递增的方式来实现这个编号。 接下来Proposer会把该编号发送给Acceptors，只有大多数Acceptors接收到Proposer发来的消息，该消息才算是发送成功。

• 阶段1B：Promise

  所有的Acceptors都在等待从Proposers发过来的Prepare消息。当一个Acceptor收到从Proposer发过来的Prepare消息时候，会有两种情况：

  • 该消息中的n是Acceptor所有收到的Prepare消息中最大的一个，那么该Acceptor必须返回一个Promise消息给Proposer，告诉它后面所有小于n的消息我都会忽略掉。如果该Acceptor在过去的某个时间已经确认了某个消息，那么它必须返回那个消息的proposal number m 和 accepted value w （m，w）。如果该Acceptor在过去并没有确认过任何消息，那么会返回NULL。
  • 如果Prepare消息中的n小于该Acceptor之前接收到的消息，那么该消息会被Acceptor忽略（为了优化也可以返回一个拒绝消息给Proposer，告诉它不要再发小于n的消息给我了）。

阶段2

• 阶段2A：Accept

  如果一个Proposer从Acceptors接收到了足够多的Promises（>n/2），这表示该Proposer可以开始下一个Accept请求的阶段了，在Accept阶段，Proposer需要设置一个值，然后向Acceptors发送Accept请求。 在阶段1B我们讲到了，如果Acceptor之前确认过消息，那么会把该消息编号和消息的值（m，w）返回给Proposer， Proposer收到多个Acceptors返回过来的消息之后，会从中选择编号最大的一个消息所对应的值z，并把他作为Accept请求的值（n，z）发给Acceptor。如果所有的Acceptors都没有确认过消息，那么Proposer可以自主选择要确认的值z。

• 阶段 2b: Accepted 当Acceptor接收到了Proposer的确认消息请求（n，z），如果该Acceptor在阶段1b的时候没有promise只接收>n的消息，那么该（n，z）消息就必须被Acceptor确认。 当（n，z）消息被Acceptor确认时，Acceptor会发送一个Accepted（n，z）消息给Proposer 和所有的Learner。当然在大部分情况下Proposer和Learner这两个角色可以合并。 如果该Acceptor在阶段1b的时候promise只接收>n的消息，那么该确认请求消息会被拒绝或者忽略。 按照以上的逻辑就会出现在一个轮次中，Acceptor 确认多次消息的情况。什么情况下才会出现这样的情况呢？ 我们举个例子： Acceptor 收到Accept（n，z），然后返回了Accepted（n，z），接下来该Acceptor 又收到了Prepare（n+1)请求，按照阶段1B的原则，Acceptor会 Promise （n+1，z），然后Acceptor 收到Accept（n+1，z），最后返回Accepted（n+1，z）。大家可以看到尽管Acceptor 确认了多次请求，但是最终会确保确认的值是保持一致的。

ZAB协议

Zab协议 的全称是 Zookeeper Atomic Broadcast （Zookeeper原子广播）。 Zookeeper 是通过 Zab 协议来保证分布式事务的最终一致性。

Zab协议是为分布式协调服务Zookeeper专门设计的一种 支持崩溃恢复 的 原子广播协议 ，是Zookeeper保证数据一致性的核心算法。Zab借鉴了Paxos算法，但又不像Paxos那样，是一种通用的分布式一致性算法。它是特别为Zookeeper设计的支持崩溃恢复的原子广播协议。

在Zookeeper中主要依赖Zab协议来实现数据一致性，基于该协议，zk实现了一种**主备模型（即Leader和Follower模型）**的系统架构来保证集群中各个副本之间数据的一致性。 这里的主备系统架构模型，就是指只有一台客户端（Leader）负责处理外部的写事务请求，然后Leader客户端将数据同步到其他Follower节点。

在 Zab 的事务编号 zxid 设计中，zxid是一个64位的数字。

其中低32位可以看成一个简单的单增计数器，针对客户端每一个事务请求，Leader 在产生新的 Proposal 事务时，都会对该计数器加1。而高32位则代表了 Leader 周期的 epoch 编号。

Zab协议要求每个 Leader 都要经历三个阶段：发现，同步，广播。

• 发现：要求zookeeper集群必须选举出一个 Leader 进程，同时 Leader 会维护一个 Follower 可用客户端列表。将来客户端可以和这些 Follower节点进行通信。

成为 Leader 的条件： 1）选 epoch [ˈiːpɒk] 最大的 2）若 epoch 相等，选 zxid 最大的 3）若 epoch 和 zxid 相等，选择 server_id 最大的（zoo.cfg中的myid）

节点在选举开始时，都默认投票给自己，当接收其他节点的选票时，会根据上面的 Leader条件 判断并且更改自己的选票，然后重新发送选票给其他节点。当有一个节点的得票超过半数，该节点会设置自己的状态为 Leading ，其他节点会设置自己的状态为 Following。

• 同步：Leader 要负责将本身的数据与 Follower 完成同步，做到多副本存储。这样也是提现了CAP中的高可用和分区容错。Follower将队列中未处理完的请求消费完成后，写入本地事务日志中。
• 广播：Leader 可以接受客户端新的事务Proposal请求，将新的Proposal请求广播给所有的 Follower。

Zab协议的核心：定义了事务请求的处理方式

1）所有的事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被叫做 Leader服务器。其他剩余的服务器则是 Follower服务器。

2）Leader服务器 负责将一个客户端事务请求，转换成一个 事务Proposal，并将该 Proposal 分发给集群中所有的 Follower 服务器，也就是向所有 Follower 节点发送数据广播请求（或数据复制）

3）分发之后Leader服务器需要等待所有Follower服务器的反馈（Ack请求），在Zab协议中，只要超过半数的Follower服务器进行了正确的反馈后（也就是收到半数以上的Follower的Ack请求），那么 Leader 就会再次向所有的 Follower服务器发送 Commit 消息，要求其将上一个 事务proposal 进行提交。

崩溃恢复 和 消息广播

当整个集群启动过程中，或者当 Leader 服务器出现网络中弄断、崩溃退出或重启等异常时，Zab协议就会 进入崩溃恢复模式，选举产生新的Leader。

当选举产生了新的 Leader，同时集群中有过半的机器与该 Leader 服务器完成了状态同步（即数据同步）之后，Zab协议就会退出崩溃恢复模式，进入消息广播模式。

这时，如果有一台遵守Zab协议的服务器加入集群，因为此时集群中已经存在一个Leader服务器在广播消息，那么该新加入的服务器自动进入恢复模式：找到Leader服务器，并且完成数据同步。同步完成后，作为新的Follower一起参与到消息广播流程中。

投票机制

每个sever 首先给自己投票，然后用自己的选票和其他sever 选票对比，权重大的胜出，使用权重较大的更新自身选票箱。具体选举过程如下：

1. 每个Server 启动以后都询问其它的Server 它要投票给谁。对于其他server 的询问，server 每次根据自己的状态都回复自己推荐的leader 的id 和上一次处理事务的zxid（系统启动时每个server 都会推荐自己）

2. 收到所有Server 回复以后，就计算出zxid 最大的哪个Server，并将这个Server 相关信息设置成下一次要投票的Server。

3. 计算这过程中获得票数最多的的sever 为获胜者，如果获胜者的票数超过半数，则改server 被选为leader。否则，继续这个过程，直到leader 被选举出来

4. leader 就会开始等待server 连接

5. Follower 连接leader，将最大的zxid 发送给leader

6. Leader 根据follower 的zxid 确定同步点，至此选举阶段完成。

7. 选举阶段完成Leader 同步后通知follower 已经成为uptodate 状态

8. Follower 收到uptodate 消息后，又可以重新接受client 的请求进行服务了

区别

raft协议和ZAB协议是leader和follower，而paxos协议没有leader节点，只有Proposer和Acceptor。

raft协议和ZAB协议都是由leader来发起写操作。

paxos的Proposer可能会被ack很多次，但是ack的值是不变的。

raft选举使用的是term和index（选term最高的那个），而ZAB使用的是epoch和count的组合（选zxid最大那个）。

raft 协议的心跳是从leader 到follower, 而zab 协议则相反

raft 协议数据只有单向地从leader 到follower(成为leader 的条件之一就是拥有最新的log)

Gossip协议

是一个通信协议，用于节点或进程之间进行信息交换。它利用一种随机的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点的数据保持一致性。Gossip协议主要应用于分布式系统中，如数据库复制、信息扩散、集群成员身份确认和故障探测等。它的基本思想是，一个节点会周期性地随机选择一些其他节点，并将信息传递给这些节点。这些收到信息的节点会继续将信息传递给其他节点，直到所有节点都收到信息。由于不能保证某个时刻所有的节点都收到消息，但能保证最终所有节点都会收到消息，因此它是一个最终一致性协议。Gossip协议在Redis Cluster、Consul和Apache Cassandra等系统中得到了广泛应用。

如何解决脑裂问题

1. **投票机制（Quorum）：**使用投票机制来确保在分布式系统中的节点集合中必须达到一定数量的一致性才能进行操作。例如，在一个节点集合中，需要大多数节点达成一致才能认为系统是正常的。这样可以防止部分节点在无法通信时形成独立的子系统。
2. **选主机制（Leader Election）：**在分布式系统中引入选主机制，确保系统中只有一个主节点负责处理请求，其他节点处于备份状态。选主机制可以通过一些算法如 Paxos 或 Raft 来实现，确保在无法通信时只有一个节点被选为主节点。
3. 仲裁机制：设置第三方检测服务器，判断节点的状态。