在应用程序中，往往一个业务的完成，需要执行多次操作，我们希望这些操作是可以全部成功，或者全部失败，而不是停止在一半，这就涉及到事务的概念。

事务和ACID

事务是应用程序中一系列严密的操作，所有操作必须成功完成，否则在每个操作中所作的所有更改都会被撤消。也就是事务具有原子性，一个事务中的一系列的操作要么全部成功，要么一个都不做。事务应该具有 4 个属性：

原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

这四个属性通常称为 ACID 特性。

• Atomicity（原子性）：一个事务（transaction）中的所有操作，或者全部完成，或者全部不完成，不会结束在中间某个环节。事务在执行过程中发生错误，会被回滚（Rollback）到事务开始前的状态，就像这个事务从来没有执行过一样。即，事务不可分割、不可约简。
• Consistency（一致性）：在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这表示写入的资料必须完全符合所有的预设约束、触发器、级联回滚等。
• Isolation（隔离性）：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括未提交读（Read uncommitted）、提交读（read committed）、可重复读（repeatable read）和串行化（Serializable）。
• Durability（持久性）：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

在单体应用程序中，可以依赖外部数据库的事务特性来实现。但是分布式系统中，调用远程服务，就无法依赖外部的事务。

不同数据库对事务的实现方式不同，但是大多会使用MVCC机制 事务之「 MVCC」 。具体可以看 PostgreSQL 事务原理：ACID 实现 和 MVCC 多版本并发控制 和 图文并茂讲解 Mysql 事务实现原理

分布式事务

分布式系统最大的特点是：一个业务流程需要组合一组服务实现。

带来的一个明显的问题就是，需要业务上保证一致性。如果⼀个步骤失败了，那么要么回滚到以前的服务调⽤，要么不断重试保证所有的步骤都成功，即保证事务。由于业务操作分布在不同的节点上，所以称作分布式事务。

例如在下单场景下，库存和订单如果不在同一个节点上，就涉及分布式事务。

分布式锁和分布式事务区别：

• 锁问题的关键在于进程操作的互斥关系，例如多个进程同时修改账户的余额，如果没有互斥关系则会导致该账户的余额不正确。
• 而事务问题的关键则在于事务涉及的一系列操作需要满足 ACID 特性，例如要满足原子性操作则需要这些操作要么都执行，要么都不执行。

要解决分布式系统的事务问题，首先要了解分布式系统的CAP原则

CAP原则

CAP 原则又称 CAP 定理，指的是在一个分布式系统中， Consistency（一致性）、 Availability（可用性）、Partition tolerance（分区容错性），最多只能同时满足其中两项。

• 一致性

  一致性指的是多个数据副本是否能保持一致的特性，在一致性的条件下，系统在执行数据更新操作之后能够从一致性状态转移到另一个一致性状态。

  对系统的一个数据更新成功之后，如果所有用户都能够读取到最新的值，该系统就被认为具有强一致性。

• 可用性

  可用性指分布式系统在面对各种异常时可以提供正常服务的能力，可以用系统可用时间占总时间的比值来衡量，4 个 9 的可用性表示系统 99.99% 的时间是可用的。

  在可用性条件下，要求系统提供的服务一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。

  可用性计算公式

  $Availability=\frac{MTTF}{MTTF+MTTR}$

  MTTF 是 Mean Time To Failure，平均故障前的时间，即系统平均能够正常运⾏多⻓时间才发⽣⼀次故障。系统的可靠性越⾼，MTTF越⻓。（注意：从字⾯上来说，看上去有Failure的字样，但其实是正常运⾏的时间。）

  MTTR 是 Mean Time To Recovery，平均修复时间，即从故障出现到故障修复的这段时间，这段时间越短越好。

  

• 分区容忍性

  网络分区指分布式系统中的节点被划分为多个区域，每个区域内部可以通信，但是区域之间无法通信。

  在分区容忍性条件下，分布式系统在遇到任何网络分区故障的时候，仍然需要能对外提供一致性和可用性的服务，除非是整个网络环境都发生了故障。

  例如服务存在ABC三个节点，存储相同的数据，分区容忍性要求在AB不能和C通信的时候，也要满足AC条件。

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

可用性和一致性往往是冲突的，很难使它们同时满足。在多个节点之间进行数据同步时，

• 为了保证一致性（CP），不能访问未同步完成的节点，也就失去了部分可用性；
• 为了保证可用性（AP），允许读取所有节点的数据，但是数据可能不一致。

BASE

在分布式系统中，ACID很难满足高性能的要求，为了提高性能，提出的一个ACID的变种。

• 基本可用（Basically Available）

  指分布式系统在出现故障的时候，保证核心可用，允许损失部分可用性。

  例如，电商在做促销时，为了保证购物系统的稳定性，部分消费者可能会被引导到一个降级的页面。

• 软状态（Soft State）

  指允许系统中的数据存在中间状态，并认为该中间状态不会影响系统整体可用性，即允许系统不同节点的数据副本之间进行同步的过程存在时延。

• 最终一致性（Eventually Consistent）

  最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能达到一致的状态。

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

举个🌰，在一个下单系统中，ACID要求每个用户的购买请求都需要把库存锁住，同一时间只有一个人能购买下单；而BASE的做法，可以先下单，系统异步的处理订单，判断库存后会通知下单是否成功（亚马逊，京东都是这么玩的）

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

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

本地消息表

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

1. 当系统 A 被其他系统调用发生数据库表更操作，首先会更新数据库的业务表，其次会往相同数据库的消息表中插入一条数据，两个操作发生在同一个事务中
2. 系统 A 的脚本定期轮询本地消息往 mq 中写入一条消息，如果转发成功则将消息从本地消息表中删除，否则继续重新转发。
3. 系统 B 消费 mq 中的消息，并处理业务逻辑。如果本地事务处理失败，会在继续消费 mq 中的消息进行重试，如果业务上的失败，可以通知系统 A 进行回滚操作

此方案的核心是将需要分布式处理的任务通过消息日志的方式来异步执行。消息日志可以存储到本地文本、数据库或消息队列，再通过业务规则自动或人工发起重试。

本地消息表实现的条件：

1. 消费者与生成者的接口都要支持幂等
2. 生产者需要额外的创建消息表
3. 需要提供补偿逻辑，如果消费者业务失败，需要生产者支持回滚操作

容错机制：

1. 步骤 1 失败时，事务直接回滚
2. 步骤 2、3 写 mq 与消费 mq 失败会进行重试
3. 步骤 3 业务失败系统 B 向系统 A 发起事务回滚操作

一致性共识算法

拜占庭将军问题

拜占庭将军问题（Byzantine Generals Problem），是由莱斯利·兰波特在其同名论文[1]中提出的分布式对等网络通信容错问题。

一组拜占庭将军分别各率领一支军队共同围困一座城市。为了简化问题，将各支军队的行动策略限定为进攻或撤离两种。因为部分军队进攻部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或所有军队一起撤离。因为各位将军分处城市不同方向，他们只能通过信使互相联系。在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军，这样一来每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

系统中存在的问题：

1. 将军中存在叛徒，会发起恶意投票
2. 传递的信使中存在叛徒

对应在应用程序中，即存在信息源不可靠，信息的传递过程不可靠。

假使那些忠诚（或是没有出错）的将军仍然能通过多数决定来决定他们的战略，便称达到了拜占庭容错。

拜占庭将军问题比较难解，莱斯利·兰伯特证明，当叛变者不超过 1/3时，存在有效的算法。不论叛变者如何折腾，忠诚的将军们总能达成⼀致的结果。如果叛变者过多，则⽆法保证⼀定能达到⼀致性

即在将军的总数为n，n里面背叛者的数量为t，则只要n > 3t就可以实现容错。目前也有一些解决的算法，例如PBFT算法。

但是这不是我们关注的重点，引入拜占庭问题，只是为了说明分布式系统面临的挑战，在我们实际私有的分布式系统中，可以认为节点不会出现恶意，通信过程除了网络故障外都是可靠的。这样问题变得简化了，成为在系统多个节点拥有不同意见的情况下，如何让所有节点达成共识，

两阶段提交2PC

两阶段提交（Two-phase Commit，2PC），通过引入协调者（Coordinator）来协调参与者的行为，并最终决定这些参与者是否要真正执行事务。

运行过程

1. 准备阶段

   协调者询问参与者事务是否执行成功，参与者发回事务执行结果。询问可以看成一种投票，需要参与者都同意才能执行。

   

2. 提交阶段

   如果事务在每个参与者上都执行成功，事务协调者发送通知让参与者提交事务；否则，协调者发送通知让参与者回滚事务。

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

   

存在的问题

• 同步阻塞

  所有事务参与者在等待其它参与者响应的时候都处于同步阻塞等待状态，无法进行其它操作。

• 单点问题

  协调者在 2PC 中起到非常大的作用，发生故障将会造成很大影响。特别是在提交阶段发生故障，所有参与者会一直同步阻塞等待，无法完成其它操作。

• 数据不一致

  在提交阶段，如果协调者只发送了部分 Commit 消息，此时网络发生异常，那么只有部分参与者接收到 Commit 消息，也就是说只有部分参与者提交了事务，使得系统数据不一致。

• 太过保守

  任意一个节点失败就会导致整个事务失败，没有完善的容错机制。

现在，很多公司的分布式系统事务基本上都是两阶段提交的变种。⽐如：阿⾥推出的TCC(Try–Confirm–Cancel)，或是亚⻢逊的Plan–Reserve–Confirm的⽅式，等等。凡是通过业务补偿，或是在业务应⽤层上做的分布式事务的玩法，基本上都是两阶段提交，或是两阶段提交的变种。

三阶段提交3PC

三段提交（3PC）是对两段提交（2PC）的一种升级优化，3PC在2PC的第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前，各参与者节点的状态都一致。


3PC 的三个阶段分别是CanCommit、PreCommit、DoCommit

CanCommit：协调者向所有参与者发送CanCommit命令，询问是否可以执行事务提交操作。如果全部响应YES则进入下一个阶段。

PreCommit：协调者向所有参与者发送PreCommit命令，询问是否可以进行事务的预提交操作，参与者接收到PreCommit请求后，如参与者成功的执行了事务操作，则返回Yes响应，进入最终commit阶段。一旦参与者中有向协调者发送了No响应，或因网络造成超时，协调者没有接到参与者的响应，协调者向所有参与者发送abort请求，参与者接受abort命令执行事务的中断。

DoCommit： 在前两个阶段中所有参与者的响应反馈均是YES后，协调者向参与者发送DoCommit命令正式提交事务，如协调者没有接收到参与者发送的ACK响应，会向所有参与者发送abort请求命令，执行事务的中断。

对比2阶段提交：

1. 引入了超时机制，解决了同步阻塞的问题。

   在2PC中，准备阶段执行了事务，但是协调者需要等待所有参与者返回yes后，才会进入提交阶段，如果因为网络原因准备阶段协调者没有收到某个响应，剩下的参与者会一直等待

2. 在提交阶段发生失败，依旧可以回滚

当然，缺点是最终也会在因为网络问题导致状态不一致。

TCC的实现

关于 TCC（Try-Confirm-Cancel）的概念，最早是由 Pat Helland 于 2007 年发表的一篇名为《Life beyond Distributed Transactions:an Apostate’s Opinion》的论文提出，又被称补偿事务。 TCC 事务机制相比于上面介绍的 2PC，解决了其几个缺点：

1. 解决了协调者单点，由主业务方发起并完成这个业务活动。业务活动管理器也变成多点，引入集群。
2. 同步阻塞：引入超时，超时后进行补偿，并且不会锁定整个资源，将资源转换为业务逻辑形式，粒度变小。
3. 数据一致性，有了补偿机制之后，由业务活动管理器控制一致性

执行过程

1. Try 阶段：尝试执行，完成所有业务检查（一致性）, 预留必须业务资源（准隔离性）
2. Confirm 阶段：确认执行真正执行业务，不作任何业务检查，只使用 Try 阶段预留的业务资源，Confirm 操作满足幂等性。要求具备幂等设计，Confirm 失败后需要进行重试。
3. Cancel 阶段：取消执行，释放 Try 阶段预留的业务资源 Cancel 操作满足幂等性 Cancel 阶段的异常和 Confirm 阶段异常处理方案基本上一致。

在 Try 阶段，是对业务系统进行检查及资源预览，比如订单和存储操作，需要检查库存剩余数量是否够用，并进行预留，预留操作的话就是新建一个可用库存数量字段，Try 阶段操作是对这个可用库存数量进行操作。

基于 TCC 实现分布式事务，会将原来只需要一个接口就可以实现的逻辑拆分为 Try、Confirm、Cancel 三个接口，所以代码实现复杂度相对较高。

以A账户向B账户汇款100元为例，图9-11展示了TCC的流程。汇款服务和收款服务需要分别实现Try、Confirm、Cancel这三个接口，并在业务初始化阶段将这三个接口的实现注入TCC事务管理器。


Paxos

Paxos 算法是分布式技术大师 Lamport 提出的，主要目的是通过这个算法，让参与分布式处理的每个参与者逐步达成一致意见。用好理解的方式来说，就是在一个选举过程中，让不同的选民最终做出一致的决定。

Lamport 为了讲述这个算法，假想了一个叫做 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和Y先收到了A的请求，Acceptor Z收到了B的请求

   如下图，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 选择出来。

   

Paxos 算法的通俗理解：

在整个提议和投票过程中，主要的角色就是 “提议者”（向“接受者” 提出提议）和 “接受者”（收到“提议者” 的提议后，向 “提议者” 表达自己的意见）。

整个算法的大致过程为：

1. 第一阶段：因为存在多个 “提议者”，如果都提意见，那么“接受者” 接受谁的不接受谁的？太混乱了。所以，要先明确哪个 “提议者” 是意见领袖有权提出提议，未来，“接受者”们就主要处理这个 “提议者” 的提议了**（这样，也可以在提出提议时就尽量让意见统一，谋求尽早形成多数派）。**

   所有的提议者向所有的接受者发送建议（prepare请求），一个接受者会收到多个意见，根据意见的序号，确定会接受谁的意见。

   接受者对收到的prepare请求，如果序号低于当前已经收到的，忽视；大于等于当前序号，返回之前保存的建议（可能是空，也可能是序号比较低的建议）

2. 第二阶段：由上阶段选出的意见领袖提出提议，“接受者”反馈意见。如果多数 “接受者” 接受了一个提议，那么提议就通过了。

   当每个提议者获得超过一半的接受者的回复后，开始发起accept请求，请求的序号还是之前自己提议的序号，但是请求的v是上一阶段收到的接受者的反馈最大序号的v，如果上一阶段反馈是no previous则v还是自己提议的v，如果上一阶段有多个人反馈，则取其中序号最大的对应的v(这个序号最大不包含自己的序号！！）

   接受者还是会丢弃序号小于当前已经保存的提议，大于等于时则更新。

3. 第三阶段：如果一个接受者接收到了大于等于当前序号的accept请求，则向learn发出一个提议，如果learn发现大部分接受者都接受了某个提议，这个提议就被接受了。

必须要了解的其他相关背景：

1. 怎么明确意见领袖呢？通过编号。每个 “提议者” 在第一阶段先报个号，谁的号大，谁就是意见领袖。如果不好理解，可以想象为贿选。每个提议者先拿着钞票贿赂一圈 “接受者”，谁给的钱多，第二阶段“接受者” 就听谁的。（注：这里和下文提到的 “意见领袖”，并不是一个新的角色，而是代表在那一轮贿赂成功的“提议者”。所以，请把意见领袖理解为贿赂中胜出的“提议者” 即可）
2. 有个跟选举常识不一样的地方，就是每个 “提议者” 不会执着于让自己的提议通过，而是每个 “提议者” 会执着于让提议尽快达成一致意见。所以，为了这个目标，如果 “提议者” 在贿选的时候，发现 “接受者” 已经接受过前面意见领袖的提议了，即便 “提议者” 贿选成功，也会默默的把自己的提议改为前面意见领袖的提议。所以一旦贿赂成功，胜出的 “提议者” 再提出提议，提议内容也是前面意见领袖的提议**（这样，在谋求尽早形成多数派的路上，又前进了一步）**。
3. 钱的多少很重要，如果钱少了，无论在第一还是第二阶段 “接受者” 都不会尿你，直接拒绝。
4. 上面 2）中讲到，如果 “提议者” 在贿选时，发现前面已经有意见领袖的提议，那就将自己的提议默默改成前面意见领袖的提议。这里有一种情况，如果你是 “提议者”，在贿赂的时候，“接受者 1” 跟你说 “他见过的意见领袖的提议是方案 1”，而“接受者 2” 跟你说 “他见过的意见领袖提议是方案 2”，你该怎么办？这时的原则也很简单，还是：钱的多少很重要！你判断一下是“接受者 1” 见过的意见领袖有钱，还是 “接受者 2” 见过的意见领袖有钱？如何判断呢？因为 “接受者” 在被 “提议者” 贿赂的时候，自己会记下贿赂的金额。所以当你贿赂 “接受者” 时，一旦你给的贿赂多而胜出，“接受者”会告诉你两件事情：a. 前任意见领袖的提议内容（如果有的话），b. 前任意见领袖当时贿赂了多少钱。这样，再面对刚才的情景时，你只需要判断一下 “接受者 1” 和“接受者 2”告诉你的信息中，哪个意见领袖当时给的钱多，那你就默默的把自己的提议，改成那个意见领袖的提议。
5. 最后这一部分最有意思，但描述起来有点绕，如果不能一下子就理解可以先看后面的例子。在整个选举过程中，每个人谁先来谁后到，“接受者”什么时间能够接到 “提议者” 的信息，是完全不可控的。所以很可能一个意见领袖已经产生了，但是由于这个意见领袖的第二阶段刚刚开始，绝大部分 “接受者” 还没有收到这个意见领袖的提议。结果，这时突然冲进来了一个新的土豪 “提议者”，那么这个土豪“提议者” 也是有机会让自己的提议胜出的！**这时就形成了一种博弈：**a. 上一个意见领袖要赶在土豪 “提议者” 贿赂到 “接受者” 前，赶到 “接受者” 面前让他接受自己的提议，否则会因为自己的之前贿赂的钱比土豪少而被拒绝。b. 土豪 “提议者” 要赶在上一个意见领袖将提议传达给 “接受者” 前，贿赂到 “接受者”，否则土豪“提议者” 即便贿赂成功，也要默默的将自己的提议改为前任意见领袖的提议。这整个博弈的过程，最终就看这两个 “提议者” 谁的进展快了。但最终一定会有一个意见领袖，先得到多数 “接受者” 的认可，那他的提议就胜出了。

总结好啦，故事到这里基本讲述完了，咱们来总结一下，其实 Paxos 算法就下面这么几个原则：

• Paxos 算法包括两个阶段：第一个阶段主要是贿选，还没有提出提议；第二个阶段主要根据第一阶段的结果，明确接受谁的提议，并明确提议的内容是什么（这个提议可能是贿选胜出 “提议者” 自己的提议，也可能是前任意见领袖的提议，具体是哪个提议，见下面第 3 点原则）。
• 编号（贿赂金额）很重要，无论在哪个阶段，编号（贿赂金额）小的，都会被鄙视（被拒绝）。
• 在第一阶段中，一旦 “接受者” 已经接受了之前意见领袖的提议，那后面再来找这个 “接受者” 的“提议者”，即便在贿赂中胜出，也要被洗脑，默默将自己的提议改为前任意见领袖的提议，然后他会在第二阶段提出该提议（也就是之前意见领袖的提议，以力争让大家的意见趋同）。如果 “接受者” 之前没有接受过任何提议，那贿选胜出的 “提议者” 就可以提出自己的提议了。

约束条件

• 正确性

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

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

• 可终止性

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

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

Raft

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

Raft: Understandable Distributed Consensus

单个 Candidate 的竞选

有三种节点：Follower、Candidate 和 Leader。Leader 会周期性的发送心跳包给 Follower。每个 Follower 都设置了一个随机的竞选超时时间，一般为 150ms~300ms，如果在这个时间内没有收到 Leader 的心跳包，就会变成 Candidate，进入竞选阶段。

• 下图展示一个分布式系统的最初阶段，此时只有 Follower 没有 Leader。Node A 等待一个随机的竞选超时时间之后，没收到 Leader 发来的心跳包，因此进入竞选阶段。

• 此时 Node A 发送投票请求给其它所有节点。

• 其它节点会对请求进行回复，如果超过一半的节点回复了，那么该 Candidate 就会变成 Leader。

• 之后 Leader 会周期性地发送心跳包给 Follower，Follower 接收到心跳包，会重新开始计时。

多个 Candidate 竞选

• 如果有多个 Follower 成为 Candidate，并且所获得票数相同，那么就需要重新开始投票。例如下图中 Node B 和 Node D 都获得两票，需要重新开始投票。

• 由于每个节点设置的随机竞选超时时间不同，因此下一次再次出现多个 Candidate 并获得同样票数的概率很低。

数据同步

• 来自客户端的修改都会被传入 Leader。注意该修改还未被提交，只是写入日志中。

• Leader 会把修改复制到所有 Follower。

• Leader 会等待大多数的 Follower 也进行了修改，然后才将修改提交。

• 此时 Leader 会通知的所有 Follower 让它们也提交修改，此时所有节点的值达成一致。

PoW（Proof of Work）工作量证明

以上的算法都是假设不存在拜占庭将军问题的情况下，解决分布式系统一致性的问题。

但是在比特币的系统中，不像系统内部可以确认节点不会发出恶意的投票，比特币中每个节点都是不可靠的，所以比特币使用PoW来解决共识问题。

Pow的核心是：

• 增加投票的成本，限制同一时间内产生的提案数量（需要大量算力挖矿）；
• 放宽对最终一致性确认的需求，大家可以选择任意一个提案（由于提案成本高，大家也只能选择其中一个），最终支持比较少的提案（较短的链路）最终会被废弃

同时，由于产生提案的成本很高，伪造提案几乎变得不可能。关于挖矿和难度参考 区块链技术和比特币

⽐特币的挖矿算法并不是⽐特币开创的，其原型叫 Hashcash，起初发明的原因是为了解决垃圾邮件的问题，要求邮件发送方，将邮件头信息产生一个开头有5个0的sha-1 hash值。这对发送方来说比较容易，但是对需要发送大量垃圾邮件的人来说，成本就有点高。

PoS （Proof of Stake）股权证明协议

Pow的机制，在比特币中，随着算力的提升越来越难，对电力资源浪费严重，为了每个Block更快的生成，产生了Pos协议，中文翻译为股权证明协议。

在PoS机制下，矿⼯不再叫矿⼯，⽽是叫Validator（校验者）。假设现在有⼀个区域需要被⽣成，⽽现在有4个Validator，每⼀个Validator需要以"交押⾦"的⽅式来取得记账权。假如，A交的押⾦占了38%，B占25%，C点21%，D占16%。那么，他们按照股权的⽐权来获得记账权。⽐如，A有38%的概率可以获得记账权（不是由系统随机分配，还是要算hash值，只不过是财富越多的⼈挖矿的难度越⼩）。⽽如果你发起恶意攻击的话，你的钱就会被系统没收充公。⽽Validator记账后没有奖⾦，只有⼿续费。
也就是说，在PoS机制下，记账权不再像PoW那样由谁的算⼒⼤谁就越有机会来记账，⽽是由谁的财富多，谁就越有可能来记账。于是，记账权按⼤家财富的⽐例来分配。

PoW好像是"多劳多得"的社会，⽽PoS更像是"资本主义"社会，钱越多的⼈越有话语权。这其实也没有什么不对的。从博弈论的⻆度上来说，钱越多的⼈越有动⼒维护社会的稳定，因为如果社会不稳定了，他是损失最为惨重的⼈。

（这⾥有⼀个逻辑问题：如果钱越多的⼈越有动⼒维护社会稳定，那么，是不是中⼼化的机构也越有动⼒维护整个系统的健康度？如果是这样的话，我们为什么要去中⼼化呢？）
在以太坊下，是根据拥有以太币的总量，来决定成为Validator的机率。

PoS的优点

• 不需要耗费大量电力挖矿了
• Pow的机制下，现在算力要求越来越高，不是普通人能参与了，几家大公司合作起来，就能满足超过50%的算力，就可以作弊了，这是不是违背了去中心化的思想？而在Pos下，你需要拥有50%以上财富才能作弊，你作弊了，被发现，钱被没收，作弊的意义就没有了。

PoS的缺点

• 记账成本低了，在PoW中，如果出现了一个分叉，矿工由于算力有限，智能赌选择其中一个分叉，解决了一致性问题，但是在PoS中，可以跟踪多个分叉，导致存在一致性问题

为了解决分叉产生的攻击问题，有人又提出来DPoS。

DPoS（Delegated Proof ofStake）委托股权证明机制

在常规PoW和PoS中，⼀⼤影响效率之处在于任何⼀个新加⼊的区块，都需要被整个⽹络所有节点做确认。DPoS优化⽅案在于：通过不同的策略，不定时地选中⼀⼩群节点，这⼀⼩群节点做新区块的创建、验证、签名和相互监督。这样就⼤幅度减少了区块创建和确认所需要消耗的时间和算⼒成本。同时也可以避免分叉了。

DPoS下每个token都是选票，⼤家票选20个选举⼈团+1个随机选举⼈=21个选举⼈代表⽹络。然后每隔⼀段时间，在这21个⼈中挑选⼀个出来维护账本并获得收益。

总结

TODO: Kafka的事务

不同算法对CAP原则的实现如图


通常，在应用层实现分布式事务，只能使用两阶段提交；数据层推荐使用Paxos。

参考

• distrib
• 分布式系统的事务处理
• 深入理解分布式事务
• What is CAP theorem in distributed database system?
• NEAT ALGORITHMS - PAXOS
• Paxos By Example