一致性与共识

接下来是一些分布式系统的相关算法和协议。为了构建容错系统，最好先建立一套通用的抽象机制和与之对应的技术保证，这样只需一次，上面的应用层都可以安全的信赖底层的保证。分布式系统最重要的抽象之一是共识：所有的节点就某一项提议达成一致。

一致性保证

大多数多副本数据库都至少提供了最终的一致性，但这是一个非常弱的保证，不知道系统什么时候达到一致。这让我们开发起应用来非常麻烦。因此需要更强的一致性模型，也意味着更多的代价，如性能降低或容错性差等。但这样可以使上层逻辑简单，更不容易出错。

可线性化（强一致性）

如果数据库能对上提供之一单个副本的假象，那查询起来就会很方便。这就是可线性化（也叫原子一致性，强一致性）的思想。基本的想法是让一个系统看起来好像只有一个副本，所有操作都是原子的。

在一个可线性化的系统中，一个客户端成功提交写请求，所有客户端的读请求一定能看到刚刚写入的值。

这是一个非线性化系统的例子：

如何达到线性化？

下图是三个客户端在线性一致数据库中同时读写相同的键 x。分布式语义下，x 称为寄存器，可能是键值存储的一个键，关系数据库的一行。

每条线代表一个客户端请求，网络延迟不确定，客户端不知道数据库具体什么时候处理。

A 和 B 可能会读到的值：

客户端A的第一个读操作，完成于写操作开始之前，因此必须返回旧值 0。
客户端A的最后一个读操作，开始于写操作完成之后。如果数据库是线性一致性的，它必然返回新值 1。
与写操作在时间上重叠的任何读操作，可能会返回 0 或 1 ，因为我们不知道读取时，写操作是否已经生效。这些操作是并发（concurrent）的。

如果与写并发的读操作可能返回旧值或新值，那么不同客户端会看到旧值和新值之间来回变的情况。这不符合 ”单一数据副本“ 。

为了让系统可线性化，需要添加一个重要的约束：

在一个可线性化的系统中，写操作的开始和结束间必定存在一个时间点，x 值从 0 到 1 改变。如果某个客户端读到了新值 1，即使写操作没提交，后续的读取也要返回新值。

可线性化与可串行化

两个词似乎都在表达类似 ”可以按顺序排列“ 的意思，但它们完全不同。

可串行化

是事务的隔离属性，确保事务的执行结果与串行执行的结果完全相同。

可线性化

可线性化是读写寄存器（单个对象）的最新值保证。不要求将操作组合到事务中，因此无法避免写倾斜等问题，除非采取额外措施（如实现实体化冲突）。

数据库可同时支持可串行化和线性化，这种组合又被称为严格的可串行化或者强的单副本可串行化。基于两阶段加锁或实际以串行执行都是典型的可线性化。但可串行化的快照隔离不是线性化的：按照涉及，从一致性快照读取，避免读写竞争。一致性快照的要点在于里面不包括创建快照时刻后的写入数据，所以不满足线性化。

线性化的依赖条件

什么情况下使用线性化呢？有时存在几秒的延迟不会有很大的伤害，但有时线性化很重要。

加锁与主节点选举

主从复制要确保只有一个主节点，否则会产生脑裂。选举新的主节点经常使用锁。在这种方式中，不管锁具体如何实现，它必须满足可线性化：所有节点都必须同意哪个节点持有锁，否则就会出现问题。

如 ZooKeeper 和 etcd 经常使用分布式锁和主节点选举。它们都使用了支持容错的共识算法确保可线性化。

在一些分布式数据库如 Oracle Real Application Clusters（RAC），分布式锁有更细粒度的实现：RAC 为每个磁盘页面均设置了一把锁，多个节点可以并发地共享访问存储系统。这些可线性化的锁处于事务执行的关键路径上，出于性能考虑，RAC 部署时通常都要求专用的集群互联网络来连接数据库节点。

约束与唯一性保证

唯一性约束在数据库中很常见。在写入时强制执行这些约束，也需要线性化。

硬性的唯一性约束，如主键，需要线性化保证，其他如外键和属性约束，不要求一定线性化。

跨通道的时间依赖

可能存在如下情况：

如果文件存储是可线性化的，那么系统应该可以正常工作。否则就可能出现消息队列比存储服务内部的复制执行更快。那么可能在操作图片时，可能读到旧版本或根本读不到内容。

实现线性化系统

线性化本质上意味着 ”表现得好像只有一个数据副本，且其上的所有操作都是原子的“。

系统容错最常见的是采用复制机制。复制中介绍了多种复制方案：

主从复制（部分支持可线性化）

单主复制中，如果数据都从主节点或同步的从节点读取，则满足线性化。但并非每个主从复制的具体数据库实例都是可线性化的，因为他们可能采用了快照隔离的设计。如果使用异步复制，故障切换可能丢失部分写入，违反持久性和线性化。

共识算法（可线性化）

与主从复制类似，不过共识协议通常内置一些措施防止脑裂和过期的副本。

多主复制（不可线性化）

多个主节点并发执行写入，异步复制到其他节点，可能产生冲突的写入，没办法线性化。

无主复制（可能不可线性化）

对于无主复制的系统，有人认为只有配置法定读取和写入满足（ w + r > n ）就可以获得 ”强一致性“，但这取决于具体法定人数的配置，它可能并不保证线性化。

线性化与法定人数

对于规范的 Dynamo 风格复制模型，如果读写遵从了严格 quorum，应该是可线性化的。如果遭遇不确定的网络延迟，就会出现竞争条件。

它虽然满足仲裁条件，但很明显不是线性化的。

使用 Dynamo 风格的复制系统以牺牲性能为代价来满足线性化：读操作在返回结果给应用前，必须同步执行读修复，而写操作在发送结果前，必须读取 quorum 节点来获取新值。这样显著降低性能。由于显著降低性能，Riak 不支持同步读修复，Cassandra 虽然等待读修复完成，但使用了 ”最后写入获胜“ 冲突解决方案，出现同一个主键并发写入，就会丧失线性化。

这种方式只能实现线性化读、写，不支持线性化的 cas 操作，cas 需要共识算法的支持。

所以，最安全的假定就是类似 Dynamo 风格的无主复制无法保证可线性化。

线性化的代价

多主复制中，如果两个数据中心发生网络中断，则数据中心内部可以正常运行，但数据中心间的交互复制就会出问题，从一个数据中心到另一个数据中心的复制是异步，期间的操作暂存在本地，等网络恢复后继续同步。

如果是主从复制，主节点肯定在某个数据中心，数据中心间的网络一旦中断，连接到从数据中心的客户端无法联系主节点，就无法完成数据的写入和线性化读取。从节点可以提供读服务，但内容可能是过期的。如果应用程序要求线性化读写，网络中断一定违背这样的要求。但客户端连接到主节点所在的数据中心，则可以避免此问题。

CAP理论

只要有不可靠的网络，都会发生违背线性化的风险。所以做如下考虑：

应用要求线性化，但网络出问题，就必须等待网络恢复，或直接返回错误。无论哪种方式，结果就是服务不可用。
如果应用不要求线性化，那么网络出问题后，每个副本可独立处理请求。此时服务可用，但不满足线性化。

不要求线性化的应用容忍网络故障，这个思路称为CAP定理。

CAP代表一致性、可用性、分区容错性。在网络正常时，一致性（线性化）和可用性都可以保证。而发生网络故障，要不现在一致性，要么可用性。所以 CAP 也是 “网络分区情况下，选择一致还是可用” 。

可线性化与网络延迟

虽然线性化是很有用的保证，但很少有系统真正满足线性化。现代多核 CPU 上的内存甚至是非线性化：某个 CPU 核上运行的线程修改了一个内存地址，另一个 CPU 核上的线程尝试读取，则系统无法保证可以读到刚刚写入的值，除非使用内存屏障或 fence 指令。

CAP 理论不适用多核-内存一致性模型：计算机内部通常假设通信可靠，不会假定 CPU 核和其他核断开后依然正常工作。放弃线性化的原因是性能。许多分布式数据库也类似。放弃线性化是提高性能。

考虑多数计算机网络高度不确定的网络延迟，线性化读写性能势必非常差。没有足够快的线性化算法，弱一致性模型性能则快得多。

顺序保证

之前提到的，线性化寄存器对外呈现的好像只有一份数据拷贝，而且每一个操作似乎都是原子性生效。意味着操作是按某种顺序执行。

顺序与因果关系

顺序之所以如此重要，是因为它能保持因果关系。因果关系对所发生的事件施加了某种排序：发送消息先于收到消息；问题出现在答案之前等。

如果系统服从因果关系所规定的顺序，我们称为因果一致性。比如快照隔离提供了因果一致性：从数据库中读数据时，如果查询到某些数据，也一定能看到触发该数据的前序事件。

因果顺序并非全序

全序允许任意两个元素进行比较，如果有两个元素，你总是可以说出哪个更大，哪个更小。

全序和偏序的差异也会体现在不同的数据库一致性模型中：

可线性化

在可线性化的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生。
因果关系

如果两个操作都没有发生在对方之前，那么这两个操作是并发关系。如果这两个事件是因果关系（一个发生在另一个之前），那么这两个事件可以被排序；而并发的事件则无法排序比较。这表明因果关系至少可以是偏序，而非全序。

因此，可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行。

可线性化强于因果一致性

可线性化一定意味着因果关系：任何可线性化的系统都将正确的保证因果关系。

可线性化可以确保因果性这一结论，使线性化系统更加简单易懂而富有吸引力。但线性化会显著降低性能和可用性。

但线性化也不是唯一保证因果关系的途径，还有其他办法使系统满足因果一致性，而免于线性化带来的性能问题。因果一致性可以认为是不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。

许多情况下，看似需要线性化的系统实际上需要的只是因果一致性，后者的实现可以高效许多。

捕获因果依赖关系

为了确定因果依赖，我们需要一些方法来描述系统中节点的 “知识” 。如果节点在写入Y 的请求时已经看到了 X 的值，则 X 和 Y 可能属于因果关系。确定请求的先后顺序与第五章 “检测并发写” 类似，因果一致性需要更进一步，跟踪整个数据库请求的因果关系，不仅仅是针对某个主键。版本向量技术可以推广为一种通用的解决方案。

序列号排序

虽然因果关系很重要，但实际上跟踪所有因果关系不切实际。许多应用中，客户端写入前会先读取大量数据，系统无法了解之后的写入依赖那一部分。显示跟踪所有已读数据意味着巨大的运行开销。

有个更好的办法：使用序列号或时间戳来排序事件。时间戳不一定是墙上时钟，可以是一个逻辑时钟，比如算法产生一个数字递增序列。

也就是说，每个操作都有一个唯一的序列号，可以比较哪个大。

可以按照与因果关系一致的顺序来创建序列号：操作 A 如果发生在 B 前，A 一定在全序中出现在 B 之前（A 的序列号更小）。

在主从复制数据库中，复制日志定义了与因果关系一致的写操作全序关系。主节点可以简单地为每个操作递增某个计数器，从而为复制日志中的每个操作赋值一个单调递增的序列号。结果一定满足因果一致性，虽然可能落后于主节点。

非因果序列发生器

如果系统不存在这样唯一的主节点，如何产生序列号就不那么简单了，实践中一般采用如下方法：

每个节点都可以生成自己独立的一组序列号。例如有两个节点，一个节点只能生成奇数，而另一个节点只能生成偶数。通常，可以在序列号的二进制表示中预留一些位，用于唯一的节点标识符，这样可以确保两个不同的节点永远不会生成相同的序列号。
可以将时钟（物理时钟）时间戳附加到每个操作上。这种时间戳并不连续，但是如果它具有足够高的分辨率，那也许足以区分操作。
可以预先分配序列号区块。例如，节点 A 可能要求从序列号 1 ~ 1,000 序列号的所有权，而节点 B 可能要求序列号 1,001 ~ 2,000 权。然后每个节点可以独立分配所属区间中的序列号，并在序列号告急时请求分配一个新的区间。

这三个选项都比单主节点的自增计数器表现要好，并且更具可伸缩性。它们为每个操作生成一个唯一的，近似自增的序列号。然而它们都有同一个问题：生成的序列号与因果不一致：

每个节点每秒可以处理不同数量的操作。因此，如果一个节点产生偶数序列号而另一个产生奇数序列号，则偶数计数器可能落后于奇数计数器，

来自物理时钟的时间戳会受到时钟偏移的影响，这可能会使其与因果不一致。
在分配区块的情况下，某个操作可能会被赋予一个范围在 1001 ~ 2000 内的某个序列号，然而一个后发生的操作可能路由到另一个节点，被赋予一个范围在 1 ~ 1000 之间的数字。这里序列号与因果关系也是不一致的。

lamport 时间戳

为了解决以上问题， Leslie Lamport 在 1978 年提出了可以产生因果关系一致的序列号的方法，称为兰伯特时间戳。

如图，每个节点都有唯一标识符，且有一个计数器来记录各自处理的请求总数。 Lamport 时间戳是一个值对（计数器，节点 ID）。时间戳是唯一的。

Lamport 时间戳可以保证全序：给定两个 Lamport 时间戳，计数器较大的那个时间戳大；如计数器值一样，则节点 ID 越大，时间戳越大。

Lamport 的核心亮点在于使它们与因果性保存一致：每个节点以及每个客户端都跟踪迄今为止见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点收到某个请求或回复时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器值修改为该最大值。

只要把最大计数器值嵌入到每个请求中，该方案可以确保 Lamport 时间戳与因果关系一致，而请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。

时间戳排序依然不够

如果，一个账户系统需要确保用户名唯一标识用户，两个用户使用相同用户名创建账户时，一定有一个失败。

如果有这样的操作，一般选取时间戳较低的那个作为获胜者即可，但这样有个前提，节点知道有另一个节点同时创建相同用户名。

为了得到这个信息，系统必须检查每个节点，如果网络出问题，系统则无法运转。

这个问题的关键是，只要收集所有请求的信息后，才知道这些请求间的全序关系。

为了解决这个问题，仅仅对操作进行全序排列是不够的，还需要知道操作是否发生，何时确定等。假如能够在创建用户名时，以及确定有没有其他节点执行相同用户名的创建，就可以直接返回操作成功还是失败。

想知道什么时候全序关系已经确定需要之后的 “全序关系广播”。

全序关系广播

全序关系广播通常指节点之间交互消息的某种协议。它要求满足两个基本安全属性：

可靠发送

没有消息丢失，如果消息发送到了某个节点，则它一定要发送到所有节点。
严格有序

消息总是以相同顺序发送给每个节点。

即节点或网络出故障，全序关系广播算法也要保证上述两条。网络中断是不可能发送成功的，算法要继续重试，直到网络修复，消息发送成功并且以正确的顺序。

使用全序关系广播

ZooKeeper 和 etcd 这种共识服务实际上就实现了全序广播。

全序关系广播正是数据库复制需要的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（可能有些滞后）。这个原理被称为状态机复制（state machine replication）。

全序关系广播的顺序在发送消息时就确定了，也可以将其视为日志，传递消息就像追加方式更新日志。它对于提供 fencing 令牌的锁服务也很有用。

采用全序关系广播实现线性化存储

虽然在一个可线性化的系统中有全序操作集合，但并不是可线性化与全序关系广播相同。

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息何时被送达（所以一个接收者可能落后于其他接收者）。而可线性化则强调就近性：读取时保证能够看到最新的写入值。

如果有全序关系广播，就可以构建一个线性化的存储系统，如确保用户名唯一标识一个用户。

设置用户名时如果使用 cas 的方式，则可以通过全序关系广播以追加日志的方式来实现：

在日志中追加一条消息，试探性地指明你要声明的用户名。
读日志，广播到所有节点，并等待回复。
检查是否有任何消息声称用户名以及被占用。如果这些消息中的第一条就你自己的消息，那么你就成功了：你可以提交并向客户端确认。如果所需用户名的第一条消息来自其他用户，则中止操作。

这样虽然保证线性化写入，但无法确保线性化读取，异步日志更新时，可能读到旧值。它弱于线性化保证，这里只有顺序一致性，也叫时间线一致性。为了同时满足线性化读取，有几个方案：

可以采用追加的方式把读请求排序、广播，然后各个节点获取该日志，本节点收到消息才真正执行读操作。消息在日志中的位置因此定义了读取发生的时间点。
如果日志允许以线性一致的方式获取最新日志消息的位置，则可以查询该位置，等待直到该位置前的所有消息都传达到你，然后执行读取。（这是Zookeeper sync() 操作背后的思想）。
你可以从同步更新的副本中进行读取，因此可以确保结果是最新的。

采用线性化存储实现全序关系广播

假设有一个线性化的寄存器储存一个计数，然后支持原子递增和原子 cas 操作。

每个要通过全序广播发送的消息首先对线性一致寄存器执行自增并返回操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收件人将按序列号发送回复消息。

与 Lamport 时间戳不同，通过递增线性化寄存器获取的数字没有任何间隙，如果完成了消息 4 的发送，之间接受到 6 的消息，那就必须等待 5。

线性化的 cas 或自增寄存器与全序关系广播都等价于共识问题。也就是如果能解决其中一个问题，就可以把方案用于解决其他问题。

分布式事务与共识

共识问题是分布式计算中最重要也是最基本的问题之一。有很多场景需要集群节点达成某种一致，如：

主节点选举

主从复制的数据库，选举主节点时，由于网络问题出现节点无法通信，就很容易出现争议。此时共识对于避免错误的故障切换很重要，后者会导致脑裂。
原子事务提交

对于跨节点或分区事务的数据库，会面临这样的问题：某个事务可能在一些节点上执行成功，但在其他节点上却不幸失败。但原子性要求在所有节点对事务结果达成一致，要么全部成功提交，要么回滚。

共识的不可能性
FLP结论，作者Fischer，Lynch和Paterson。FLP表明如果节点存在可能崩溃的风险，则不存在总是能够达到共识的稳定算法。在分布式系统中，我们必须假设节点可能会崩溃，所以可靠的共识是不可能的。FLP结论在异步系统模型中得到了证明，这是一种限制性很强的模型，它假定确定性算法不能使用任何时钟或超时。如果允许算法使用超时或其他方法来识别可疑的崩溃节点（即使怀疑有时是错误的），则共识变为一个可解的问题。即使仅仅允许算法使用随机数，也足以绕过这个不可能的结果。

原子提交和两阶段提交

原子性可以防止失败的事务破坏系统。这对多对象事务和维护二级索引格外重要。原子性可以保证二级索引与主数据总是保持一致。

从单节点到分布式的原子提交

单节点执行的事务一般由存储引擎负责。事务提交或中止的关键点在于磁盘完成日志记录的时刻：完成日志记录写之前如果发生崩溃，事务中止；日志写入完成后崩溃也会被安全提交。这是单节点原子提交的核心思路。

但在多节点数据库中的事务就复杂起来，可能在提交的时候部分节点网络超时，违反约束或有冲突，或发生崩溃，都会违反原子性保证。

如果部分节点提交事务，其他节点放弃事务就会变得不一致。某个节点一旦提交了事务，即使事后发现其他节点发生中止，它也无法撤销。所以如果部分节点提交事务，则所有节点都必须提交。

两阶段提交

两阶段提交（ two-phase commit, 2PC ）是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。是分布式数据库中经典算法之一。

2PC 中的提交/中止过程分为两个阶段：

2PC 和 2PL
两阶段提交和两阶段加锁是不同的事情。2PC 在分布式数据库中负责原子提交，而 2PL 则提供串行化的隔离。这是两个概念。

2PC 引入了单节点事务中没有的一个新组件：协调者（事务管理器）。协调者通常实现为共享库，在请求事务的进程中，也可能是单独进程或服务。比如 Naraytana，JOTM。

2PC 的过程：当应用准备提交事务时，协调者开始执行阶段1：发送一个准备请求到所有节点，询问是否提交。然后跟踪参与者的回应：

如果所有参与者回答 “是”，表示他们准备好提交，协调者就会在阶段2发出提交请求，然后开始实际执行。
如果任何参与者回答 “否”，则协调者在阶段2向所有节点发出放弃请求。

系统的承诺

2PC 的工作原理：

应用启动分布式事务时，先向协调者请求事务 ID。该 ID 全局唯一。
应用在每个参与节点上执行单节点事务，并将全局事务 ID 附加到事务上。此时读写都在单节点内完成。这个阶段出问题，协调者和其他参与者都可以安全中止。
应用准备提交时，协调者向所有参与者发送准备请求，并附带全局事务 ID。准备请求有任何失败或超时，协调者会通知参与者放弃事务。
参与者收到准备请求后，确保任何情况下都可以提交事务，并检查是否有冲突或违背约束。一旦向协调者回答 “是” ，节点就会承诺提交事务。
协调者收到所有准备请求的答复时，就会做出决定。协调者把最后的决定写入到磁盘的事务日志中，防止稍后日志崩溃，可以恢复之前的决定。这个时刻叫提交点。
协调者把决定写入磁盘后，向所有参与者发送提交或放弃请求。如果请求出现失败或超时，协调者必须一直重试直到成功。即使参与者此时发生崩溃或任何问题，在恢复后，也必须继续执行。

该协议有两个关键点：首先参与者投票 “是” 时，它做出了肯定提交的承诺。其次，协调者做出了提交或放弃的决定，这个决定不可撤销。正是这两个承诺保证了 2PC 的原子性。

协调者发生故障

如果参与者或网络在 2PC 期间发生失败，如果在第一阶段，协调者就会中止交易；第二阶段请求失败，协调者将无限期重试。但如果协调者发生故障，接下来发生什么现在还不太清楚。

如下图，协调者在发送给数据库 2 后崩溃，数据库 1 就不知道该提交还是中止，没有协调者的消息，参与者无法直到下一步的行动。

2PC 能够顺利完成的唯一方法就是等待协调者的恢复。这就是协调者向参与者发送请求前将决定写入磁盘的事务日志的原因：协调者恢复后，通过读取其事务日志来确定所有未决事务的状态。任何在协调者日志中没有提交记录的事务都会中止。此时，2PC 的提交点现在归结为协调者在常规单节点上的原子提交。

三阶段提交

两阶段提交也叫阻塞式原子提交协议，因为 2PC 可能在等待协调者恢复时卡住。

作为 2PC 的替代方案，目前也有三阶段提交算法。然而，3PC 假定一个有界的网络延迟和阶段在规定时间内响应。考虑到大多数无线网络延迟和进程暂停，它无法保证原子性。所以大家普遍使用 2PC。

实践中的分布式事务

两阶段提交虽然有较高的安全性保证，但也有操作的缺陷、性能的问题、承诺不可靠而遭受诟病。很多云服务厂商由于运维方面的问题不支持分布式事务。有报告称MySQL的分布式事务比单节点慢10倍以上。性能下降主要是网络开销和磁盘IO。

但我们不应该直接忽视分布式事务，而应当更加仔细地审视这些事务，因为从中可以汲取重要的经验教训。首先，我们应该精确地说明“分布式事务”的含义。两种截然不同的分布式事务类型经常被混淆：

数据库内部的分布式事务

一些分布式数据库支持数据库节点间的内部事务。如 MySQL Cluster 的 NDB 存储引擎。这种情况下，所有参与事务的节点都运行相同的数据库软件。
异构分布式事务

在异构分布式事务中，存在两种或两种以上不同参与者实现技术。例如来自不同供应商的数据库，甚至非数据库系统（中间件）。跨系统的分布式事务也必须确保原子提交。

数据库内部的分布式事务往往可行且工作不错，但异构环境的事务则充满挑战。

Exactly-once 消息处理

异构的分布式事务旨在无缝集成多种不同的系统。例如：当且仅当数据库中处理消息的事务成功提交，消息队列才会标记该消息已处理完毕。这个过程是通过自动提交消息确认和数据库写入来实现的。数据库和消息队列在两个节点，采用分布式事务也能达成。

如果消息发送或数据库事务任何一个发生失败，两者必须中止，消息队列可以稍后再次重传消息。因此，通过自动提交消息和消息处理的结果，可以确保消息可以有效处理有且仅有一次。

XA 交易

X/Open XA（扩展架构，eXtended Architecture）是异构环境下实施两阶段提交的异构工业标准，1991年推出。目前，许多数据库（PostgreSQL、MySQL、Oracle、SQL Server）和消息队列都支持 XA。

XA 不是异构网络协议，而是一个与事务协调者进行通信的C API。但也支持其他语言的 API 绑定。Java 中，XA 事务是使用Java事务API（JTA, Java Transaction API）实现的，而许多使用JDBC（Java Database Connectivity）的数据库驱动，以及许多使用Java消息服务（JMS）API的消息代理都支持Java事务API（JTA）。

XA 假定应用通过网络或客户端的库函数与参与者节点进行通信。如果驱动支持 XA，就可以调用 API 来确定操作是否是异构分布式事务的一部分。

事务协调者需要实现 XA API，这些 API 会跟踪事务中的所有参与者，协调节点进行准备（通过回调）工作，然后负责收集参与者的投票，并在本地磁盘的日志文件里记录事务最终的决定。

停顿时仍持有锁

为什么我们非常关注陷入停顿的参与者节点？（即不确定该提交还是中止）因为数据库事务通常持有待修改行的行级独占锁，防止脏写。事务结束前，数据库不会释放这些锁。所以就会阻塞很多其他事务，导致上层应用基本处于不可用的状态。所以必须解决这些停顿状态的节点。

从协调者故障中恢复

协调者崩溃后重新启动，应该可以从日志恢复那些停顿的事务。但在实践中，孤立的不确定事务确实会发生。比如软件 bug 导致交易日志丢失或损坏，最终协调者还是恢复失败。悬而未决的事务就会留在那里，还阻塞其他事务。

这种情况只能让管理员手动决定是执行提交还是回滚。管理员必须仔细检查每个有问题的参与者，确定是否有节点已经事实完成提交或中止。

许多 XA 实现都支持某种紧急避险措施称之为启发式决策：这样参与者节点可以在紧急情况下单方面做出决定，放弃或继续那些停顿的事务，不需要协调者的指令。这里的启发式是可能破坏原子性的委婉说法。只能应急。

分布式事务的限制

XA 事务解决了多个参与者之间如何达到一致的问题，但也引入了不少操作方面的限制。特别是，核心的事务协调者本身就是一种数据库（存储事务的投票结果），因此需要和其他重要的数据库一样格外消息：

如果协调者不支持数据复制，而是单节点运行，那么它就是整个系统的单点故障。现实情况是许多协调者默认情况下并非高可用，或者只支持最基本的复制。
许多应用都倾向于无状态，所有持久状态都保存在数据库中，这样服务器可以轻松添加或删除实例。但协调者就是服务器的一部分时，部署方式就改变了。协调者日志称为可靠系统的重要组成部分，要求和数据库本身一样重要。应用服务器不再无状态。
由于 XA 需要与各种数据库系统保存兼容，最终可以是多系统可兼容的最低标准。例如它无法深入检测不同系统之间的死锁条件，不适用 SSI，后者要求一个复杂协议来识别不同系统的写冲突。
数据库内部的分布式事务（不是 XA），限制则少很多，SSI 的分布式版本是可行的。但 2PC 要成功提交事务还是存在潜在的限制，要求所有参与者都投票赞成。所以分布式事务有扩大事务失败的风险，与构建容错系统的目标有些背道而驰。

支持容错的共识

共识就是让几个节点就某项协议达成一致。共识问题通常如此描述：一个或多个节点可以提议某些值，由共识算法来决定最终值。

共识算法必须满足以下性质：

协商一致性：所有的节点都接受相同协议。
诚实性：所有节点不能反悔，即对一项提议不能有两次决定。
合法性：如果决定了值 v，则 v 一定是由某个节点所提议的。
可终止性：由所有未崩溃的节点来决定最终值。

协商一致性和诚实性属性定义了共识的核心思想：决定一致的结果，一旦决定，就不能改变。合法性主要是为了排除一些无意义的方案：比如，无论什么建议，都可以有一个总是为空的决定，虽然可以满足一致性和诚实性，但没有实际效果。

可终止性引入了容错的思想。它强调了一个共识算法不能原地空转，必须取得进展。即使某些节点故障，其他节点也能做出决定。可终止性属于一种活性，其他三种属于安全性方面的属性。

共识算法需要保证大部分节点都正确运行才能确保终止性。这个多数就可以安全地构成 quorum。所以，可终止性的前提就是发生故障或不可用的节点数必须小于半数节点。

大多数共识算法都假定系统不存在拜占庭式错误。

共识算法与全序广播

最著名的容错式共识算法包括 VSR， Paxos， Raft 和 Zab。这些算法大部分其实不是直接使用上述的形式化模型（提议并决定某个值，并满足上面 4 个属性）。相反，他们是决定了一系列值，然后采用全序关系广播算法。

全序关系广播的要点是：消息按相同的顺序发送到所有节点，有且只有一次。这其实相当于进行了多轮的共识过程：每一轮，节点提出他们接下来要发送的消息，然后决定下一个消息的全局顺序。

全序关系广播相当于持续的多轮共识（每一轮共识决定对应于一条消息）：

由于协商一致性，所有节点决定以相同的顺序发送相同的消息。
由于诚实性，消息不能重复。
由于合法性，消息不会被破坏，也不是凭空捏造的。
由于可终止性，消息不会丢失。

VSR， Raft 和 Zab 都直接采用了全序关系广播，这比重复性的一轮共识只解决一个提议更加高效。而 Paxos 有对应的优化版本 Multi-Paxos。

主从复制与共识

在主从复制中，如果主节点是由运营人员手动选择和配置的，那就是只允许一个节点接受写入，如果该节点发生故障，系统将无法写入，直到操作人员再手动配置新的节点成为主节点。它需要人为干预才能取得进展，不满足共识的可终止性。

一些数据库支持自动选举主节点和故障切换，通过选举吧某个从节点提升为新的主节点。这样更容易接近容错式全序关系广播，从而达成共识。

所有的节点都需要同意主节点，否则就会脑裂。所以需要共识算法选出一位主节点。但这里的共识算法实际上是全序关系广播，全序关系广播很像主从复制，主从复制现在又需要选举主节点。

Epoch和Quorum

目前所讨论的共识协议都在其内部使用了某种形式的主节点，虽然主节点不是固定的。他们都采用了一种弱化的保证：协议定义了一个世代编号（epoch number，比如 Paxos 的 ballot number，VSP 的 view number，Raft 的 term number），保证在每个世代里，主节点是唯一确定的。

如果主节点失效，则节点开始投票选新的主节点。选举会赋予一个单调递增的 epoch 号。如果出现两个不同的主节点对应不同的 epoch 号，则具有更高 epoch 号的主节点获胜。

主节点做出任何决定前，都需要检查是否存在比他更高的 epoch 号，通过投票的方式来检查。从 quorum 节点中收集投票，等待 quorum 节点的响应。 quorum 节点通常由多数节点构成，只有没发现更高的 epoch 主节点时，节点才会对当前提议投票。

所以，实际上存在两轮投票：首先投票决定主节点，然后是对主节点的提议投票。关键的一点是，两轮的 quorum 必须有重叠。

共识的局限性

共识算法对于分布式系统来说是一个巨大的突破：它为其他充满不确定性的系统带来了基础的安全属性（一致性，完整性和有效性），然而它们还能保持容错（只要多数节点正常工作且可达，就能取得进展）。它们提供了全序广播，因此它们也可以以一种容错的方式实现线性一致的原子操作。

但好处都是有代价的：

达成一致性前，节点投票是一个同步复制的过程。
共识体系需要严格的多数节点才能运行。
多数共识算法假定一组固定参与投票的节点集，不能动态添加或删除节点。
共识系统依靠超时机制检测节点失效，在网络延迟高度不确定的环境中，经常会误判。
有时共识算法对网络问题特别敏感。例如Raft已被证明存在不合理的边界条件处理：如果整个网络工作正常，但只有一条特定的网络连接一直不可靠，Raft可能会在两个节点间反复切换主节点。其他一致性算法也存在类似的问题，而设计能健壮应对不可靠网络的算法仍然是一个开放的研究问题。

成员与协调服务

zookeeper 和 etcd 主要针对少量，可完全载入内存的数据而设计，通常采用容错的全序广播算法在所有节点复制这些数据从而实现高可靠。全序关系广播主要用来实现数据库复制：每条消息代表数据库写请求，然后按相同顺序在多个节点应用写操作，达到多副本一致性。

zookeeper 的一些特性：

线性化的原子操作：使用原子 cas 操作，可以实现加锁服务。
操作全序：zookeeper 在实现此功能时，采用了对所有操作执行全局排序，然后为每个操作都赋予一个单调递增的事务 ID 和版本号。
故障检测：客户端在ZooKeeper服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检查节点是否还活着。即使连接暂时中断，或者ZooKeeper节点失效，会话仍保持在活跃状态。但如果心跳停止的持续时间超出会话超时，ZooKeeper会宣告该会话已死亡。当会话超时，会话持有的任何锁都可以配置为自动释放。
更改通知：客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。因此，客户端可以知道另一个客户端何时加入集群（基于新客户端写入ZooKeeper的值），或发生故障（因其会话超时，而其临时节点消失）。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

上面几个，只有线性化的原子操作需要共识。

节点任务分配

zookeeper 非常适合系统有多个流程或服务的实例。另外对一些分区资源的分配，当有新节点加入集群时，需要将某些现有分区从当前节点迁移到新节点，从而实现负载均衡。

应用可能在数千个节点运行，这样进行投票效率比较低，zookeeper 可以控制在固定数量节点（3-5个）投票，高效支持大量客户端。

服务发现

zookeeper 经常用于服务发现，比如需要某个服务，要连哪个 ip 等。云环境中，虚拟机会起起停停，这种动态的变化让节点无法提前知道服务节点的 IP，所以可以让节点启动时在 zookeeper 注册，其他人想 zookeeper 注册表询问。

成员服务

成员服务用来确定哪些节点当前处于活动状态并且是群集的活动成员。由于无限的网络延迟，无法可靠地检测到另一个节点是否发生故障。但是，如果你通过一致的方式进行故障检测，那么节点可以就哪些节点应该被认为是存在或不存在达成一致。

即使它确实存在，仍然可能发生一个节点被共识错误地宣告死亡。但是对于一个系统来说，就成员资格的问题的决定是全体一致的，这是最重要的。