背景

分布式系统特性

随着计算机技术的不断进步和相关应用规模的迅速扩大，传统的集中式系统已逐渐被分布式系统所取代（集中式的系统架构存在诸多单点问题），以适应大型互联网应用的需求。分布式系统具有以下特点：多节点分布、对等性、并发性、全局时钟难以定义以及故障的不可避免性。

• 分布性：多台计算机在空间上自由分布，且随时可能发生变动。
• 对等性：分布式计算机不一定区分主从关系，有些情况下组成分布式系统的计算机节点是对等的。
• 并发性：同一个分布式系统的多个节点可能同时对共享资源进行操作。
• 全局时钟：在分布式系统中很难准确定义时间先后关系，因此需要全局时钟序列。
• 故障总是会发生：节点故障、通信异常、网络分区（俗称脑裂）、三态（成功/失败/未知）都是常见的问题。

CAP/BASE理论

CAP定理

在软件开发中，我们经常需要处理事务，事务具有原子性(Atomicity)、一致性(Consistency)、隔离性(Isolation)和持久性(Durability)的特点。在单机数据库中，实现这些特性相对容易，但是在分布式系统中，数据分散在不同的机器上，实现分布式事务会面临着许多挑战。 CAP理论于2000年7月被正式提出，指出一个分布式系统不可能同时满足一致性、可用性和分区容错性这三个基本需求，最多只能同时满足其中的两项。通常情况下需要牺牲一致性或者可用性，可以类比为购房时不可能同时具备三个条件。 具体来说，CAP理论中的三个要素包括：

• 一致性：数据在多个副本之间保持一致
• 可用性：系统服务必须保持可用状态，对于每个操作请求能够在有限时间内返回结果
• 分区容错性：即使遇到网络分区故障，系统仍能保证对外提供一致性和可用性服务，除非整个网络环境都发生了故障。

CAP定理

BASE理论

BASE理论是Basically Available(基本可用)、Soft state(软状态)和Eventually Consistent(最终一致性)三个的集合。BASE是对一致性和可用性权衡的结果，其核心思想是即使无法做到强一致性，但每个应用可以根据自身业务的特点，采用适当的方式使系统达到最终一致性。

分布式事务

在分布式系统中，各个节点在物理上相互独立，通过网络进行通信和协调。尽管每个独立节点都有事务机制，可以保证ACID属性，但因为分布式事务涉及在多个数据库间执行操作，将单一数据库事务概念扩展到多个数据库，节点之间无法准确了解其他节点的事务执行情况。因此，理论上在没有第三方参与的情况下，两台机器无法达到一致状态。 若要保证分布式部署的多台机器中数据的一致性，需确保所有节点的数据写操作要么全部执行，要么全部不执行。然而，在执行本地事务时，一台机器无法知道其他机器中本地事务的执行结果，因此无法确定事务应提交还是回滚。分布式事务处理的关键在于需要一种方法追踪事务在各处的所有动作，确保提交或回滚决策产生统一结果（全部提交或全部回滚）。因此，常规解决方案是引入一个“协调者”组件，以统一调度所有分布式节点的执行。

一致性协议介绍

在长期的研究中，为了解决分布式系统一致性问题，出现了一些经典的一致性协议和算法。接下来将分别介绍它们各自的优缺点。

2PC与3PC

二阶段提交协议（Two-phase Commit，即2PC）是一个经典的强一致性、中心化的原子提交协议。它将事务的提交过程分成了两个阶段来进行处理，分别是表决阶段（Propose）和提交阶段（commit）。

• 第一阶段(提交请求阶段)

在第一阶段（提交请求阶段），协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者节点的响应。参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。然后，各参与者节点会响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个"同意"消息；如果参与者节点的事务操作实际执行失败，则它返回一个"中止"消息。

• 第二阶段(提交执行阶段)

如果协调者节点从所有参与者节点获得的响应消息都为"同意"，则会向所有参与者节点发出"正式提交"的请求。接着，参与者节点会正式完成操作，并释放在整个事务期间内占用的资源，然后向协调者节点发送"完成"消息。一旦协调者节点收到所有参与者节点反馈的"完成"消息，就会完成事务。 相反，如果任一参与者节点在第一阶段返回的响应消息为"终止"，或者协调者节点在第一阶段的询问超时之前无法获取所有参与者节点的响应消息，协调者节点会向所有参与者节点发出"回滚操作"的请求，参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源，参与者节点向协调者节点发送"回滚完成"消息。协调者节点收到所有参与者节点反馈的"回滚完成"消息后，取消事务。 事务提交 事务回滚

二阶段提交原理简单、实现方便，但缺点也很明显，如下图。

• 性能问题：同步阻塞问题存在于执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。也就是说在从投票阶段到提交阶段完成这段时间内，资源是被锁住的。
• 可靠性问题：单点故障是由于协调者的重要性，一旦协调者发生故障，参与者会一直阻塞下去。特别是在第二阶段，如果协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（如果是协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）
• 数据一致性问题：在阶段二，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。
• 二阶段无法解决的问题：协调者发出commit消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。

三阶段提交协议主要是为了解决2PC协议的阻塞问题。与两阶段提交不同的是，三阶段提交有两个改动点。

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

3PC协议分为CanCommit、PreCommit、DoCommit三个阶段。

• CanCommit阶段：协调者向参与者发送commit请求，参与者如果可以提交就返回Yes，否则返回No。
• PreCommit阶段：本阶段协调者会根据第一阶段的询盘结果采取相应操作。假如协调者从所有的参与者获得的反馈都是Yes，那么就会执行事务的预执行；假如有任何一个参与者向协调者发送了No或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

执行事务

中断事务

• doCommit阶段：进行真正的事务提交

提交事务

中断事务

3PC的优缺点

与2PC相比，3PC降低了阻塞范围，并且在等待超时后，协调者或参与者会中断中断事务，避免协调者单点问题，阶段三中协调者出现问题时，参与者会继续提交事务。

数据不一致的问题依旧存在，当在参与者收到preCommit请求后等待doCommit指令时，此时如果协调者请求中断事务，而协调者因为网络问题无法与参与者正常通信，会导致参与者继续提交事务，造成数据不一致。

Paxos

2PC 和 3PC 在一定程度上是可以解决数据一致性问题的。 但是并没有完全解决就是协调者宕机的情况。如何解决2PC和3PC的存在的问题呢? 引入多个协调者，又引入主协调者，这个就是最简单的一种Paxos 算法.

Leslie Lamport在1990年提出了Paxos算法，这是工程实践中少数被证实的强一致性、高可用、去中心化的分布式协议之一，它也是基于消息传递且具有高度容错特性的一致性算法，它在有限时间内在多个副本之间达成共识，是目前公认的解决分布式一致性问题最有效的算法之一。它允许消息重复、丢失、延迟或乱序，但没有拜占庭式错误的网络环境中，它利用「大多数 (Majority)机制」保证了2F+1的容错能力，即2F+1个节点的系统最多允许F个节点同时出现故障。

拜占庭式错误释义：一般地把出现故障但不会伪造信息的情况称为“非拜占庭错误”(Non-Byzantine Fault)或“故障错误”(Crash Fault)；而伪造信息恶意响应的情况称为“拜占庭错误”(Byzantine Fault)。

解决了什么问题 在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

Paxos 使用两阶段提交（prepare 和 accept）来对某一个值（在不同的场景中是不同的含义，可以是一条日志或者是命令）达成一致，它把节点分为proposer、acceptor和learner三种角色。包括以下三种

• Proposer(提案者)：处理客户端请求，主动发起提案
• Acceptor(投票者)：被动接受提案消息，参与投票并返回投票给果给Proposer以及发送通知给Learner
• Leaner(学习者)：不参与投票过程，记录投票相关信息，并最终获得投票结果

Paxos的版本有Basic Paxos、Multi Paxos、Fast-Paxos, 具体落地有Raft和zk的ZAB协议。

Basic Paxos

算法分为两个阶段：Prepare阶段和Accept阶段。

Prepare 阶段

• Proposer提出一个提案，编号为N，此N大于这个Proposer之前提出所有提出的编号, 请求Accpetor的多数人接受这个提案
• Acceptor收到提案编号为n的prepare提案请求，则进行以下判断
  • 如果该Acceptor之前接受的prepare请求编号都小于n或者之前没有接受过prepare请求，那么它会响应接受该编号为n的prepare请求并承诺不再接受编号小于n的Accept请求
  • 如果该Acceptor之前接受过至少一个编号大于n的prepare请求，则会拒绝该次prepare请求

Accept 阶段

• 如果Proposer接收到了超过半数节点的Prepare请求的响应数据，该节点就进入 accept 阶段，它会发送accept广播消息给Acceptor。如果Proposer在限定时间内没有接收到超过半数的Prepare请求响应数据，则会等待指定时间后再重新发起Prepare请求。Proposer发送的accept广播请求包含什么内容：
  • accept请求包含相应的提案号
  • accept请求包含对应的提案值。如果Proposer接收到的prepare响应数据中包含Acceptor之前已同意的提案号和提案值，则选择最大提案号对应的提案值作为当前accept请求的提案值，这种设计的目的是为了能够更快的达成共识。而如果prepare返回数据中的提案值均为空，则自己生成一个提案值。
• Acceptor接收到accept消息后的处理流程如下：
  • 判断accept消息中的提案编号是否小于之前已同意的最大提案编号，如果小于则抛弃，否则同意该请求，并更新自己存储的提案编号和提案值。
  • Acceptor同意该提案后发送响应accepted消息给Proposer，并同时发送accepted消息给Learner。Learner判断各个Acceptor的提案结果，如果提案结果已超过半数同意，则将结果同步给集群中的所有Proposer、Acceptor和所有Learner节点，并结束当前提案。

假设分布式环境中有两个Proposer和三个Acceptor，ProposerB成功发送prepare请求，在发送Accept请求时出现故障宕机，只成功给Acceptor1发送了accept请求并得到响应。

ProposerA发起prepare(3)的请求，最终选择提案编号3作为当前的提案值。

• 在不违背自己向其他Proposer 承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求

最终值的选择

Acceptor 每次同意新的提案值都会将消息同步给 Learner，Learner 根据各个 Acceptor 的反馈判断当前是否已超过半数同意。如果达成共识则发送广播消息给所有 Acceptor 和 Proposer 并结束提案。 活锁 当一个proposer提交的Accept请求被拒绝时，可能是因为acceptor已经承诺了只接受更大编号的Prepare请求，因此proposer提高编号继续提交。如果多个proposer都发现自己的编号过低转而提出更高编号的proposal，会导致死循环，也称为活锁。Paxos的作者本人提出的方案是leader选举，即从Proposer中选举一个leader，只能由leader提交提案,当Leader宕机时马上再选举其他的Leader。

Multi-Paxos

basic paxos是对一个值达成一致，可以将每一次basic paxos 的流程称之为 paxos instance。如果想对一系列的value 达成一致，那么就执行一系列的 paxos instance，但是这样效率是非常低的。

• 每一次达成一致，需要经过多次 prepare和accept流程
• 多个proposer 同时 propose ，容易导致冲突，导致“活锁”

#为了在Multi-Paxos中解决先前存在的问题，引入了leader的角色，仅有leader才能提出提案并直接进入accept阶段。相较之下，在Basic-Paxos中是通过Proposal Number实现的，每个日志对应一个独立的执行过程，不同日志的Proposal Number是隔离的，因此无法确定不同日志之间的顺序。Multi-Paxos中的Proposer-Leader的引入使得可以为所有日志设置全局序号，通过全局序号来确定不同日志的顺序，从而解决了这一问题。这使得Multi-Paxos具备了对全局日志整体的感知能力。 目前市场上实际的开源项目，大部分也并不是采用了 Paxos 或者 Multi-Paxos 算法，而是往往采取了简化和变形，几个使用paxos协议的系统见下表。

系统名称	简单介绍
Chubby	一个粗粒度的锁服务，主要解决 GFS、Bigtable 这些系统的元数据的一致性问题，以及容错场景下的灾难恢复问题。
Megastore	支持SQL的跨数据中心的分布式数据库，只是google迈向spanner的一个过渡产品。号称多数据中心的同步，但是是有前提的，得在同一个分区即实体组，只能保证实体组内的事务
Spanner	采用了原子钟 +GPS 时钟，可以把时钟误差范围缩小到 1 毫秒到 7 毫秒之间，来更好地实现分布式事务下的可线性化。
OceanBase	阿里自研的原生分布式关系数据库

Raft算法

Paxos 算法可以从任何一个节点发起数据写入，达成一致的流程也比较繁琐，难以理解。而 Raft 算法则把问题拆分成了一个个独立的子问题，比如 Leader 选举（Leader Election）、日志复制（Log Replication）、安全（Safety）和成员变化（Membership Changes）等等。现在市面上有很多对Raft的实现，比如Etcd、Consul等等。

Raft的集群角色分成这3中，不同的节点在运行环境中处于不同的角色，任何节点的任何一个时刻都处于以下三种角色之一。

• Leader：主节点。选主之后的节点称之为leader，也就是主节点，只有一个。它会接收外部客户端数据写入，并且向 Follower 请求同步日志的服务器。同一时间，在整个 Raft 集群里，只会有一个 Leader。
• Follower：从节点。集群的初始状态，刚加入集群中都是folloer角色。它会接收 Leader 同步的日志，然后把日志在本地复制一份。
• Candidate：候选人。专门用于在follower在进行选举的时候被投票者的称谓，这是一个中间角色。

raft节点角色流转图 Raft 算法是有一个强 Leader 的，而 Paxos 算法是无 Leader 或者弱 Leader 的。而因为有了强 Leader，Raft 算法就可以进一步地要求日志里面不能有空洞，几个明细的问题解决方案如下：

• Leader 选举问题：系统里始终有一个 Leader，所有的数据写入都是发送到 Leader。系统里始终有 Leader 可用，数据是基于 Leader 向其他节点复制数据。因为 Leader 所在的服务器可能会挂掉，那么挂掉之后，也需要尽快确认一个新 Leader。在 Leader 选举上，Raft 采用的是典型的心跳检测 Leader 存活，以及随机超时时间投票，确保不会死循环，来确保我们可以快速选出 Leader。
• 日志复制问题：Leader 需要把日志复制到其他节点上，并且确保所有节点的日志始终是一致的。
• 安全性问题：在 Leader 挂掉，切换新 Leader 之后，新的 Leader 可能没有同步到最新的日志写入。而这可能会导致新的 Leader 会尝试覆盖之前 Leader 已经写入的数据，需要避免。