文章目录
分布式系统存在太多可能出错的场景，如果一出故障就停机，未免不太现实。我们需要更加容错的解决方案，即使某些内部组件发生故障，整个系统仍然可以对外提供服务。
本章将讨论构建容错式分布系统的相关算法和协议。为了构建容错系统，最好建立一套通用的抽象机制和与之对应的技术保证，这样只需实现一次，其上的各种应用程序都可以安全地信赖底层的保证。总之，抽象的事务机制可以屏蔽系统内部很多复杂的问题。
分布式系统最重要的抽象之一就是共识：所有的节点就某一项提议达成一致。本章主要研究的就是解决共识问题的相关算法。
1. 一致性保证
最终一致性是一个非常弱的一致性保证。分布式一致性模型和我们之前在事务隔离中讨论的相似，但是总体上有显著区别：事务隔离主要是为了处理并发执行事务时的各种临界条件，而分布式一致性则主要是针对延迟和故障等问题来协调多副本之间的状态。
本章将探索更强的一致性模型。这也意味着更多的代价，例如性能降低或容错性差。但是，更强的保证的好处是使上层应用逻辑更简单，更不易出错。
2. 可线性化
2.1 就近保证
可线性化的思想：让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。有了这个保证，应用程序就不需要关心系统内部的多个副本。
可线性化的一种就近的保证：在一个可线性化的系统中，一旦某个客户端成功提交写请求，所有客户端的读请求一定都能看到最新的值，直到被再次覆盖。这种看似单一副本的假象意味着它可以保证读取最近最新值，而不是过期的缓存。
2.2 可线性化 VS 可串行化
可线性化与可串行化概念完全不同，需要仔细区分：
可串行化：事务的隔离属性，其中每个事务可以读写多个对象，它确保事务执行的结果与串行执行的结果完全相同。
可线性化：读写寄存器（单个对象）的最新值保证。她它并不要求将操作组合到事务中，因此无法避免写倾斜与幻读等问题，除非采取其他额外措施。
实际以串行执行和两阶段加锁都是典型的可线性化。
可串行的快照隔离则不是线性化的：按照设计，它可以从一致性快照中读取，以避免读、写之间的竞争。一致性快照的要点在于它里面不包括快照点创建时刻之后的写入数据，因此从快照读取肯定不满足线性化。
2.3 线性化的场景
- 加锁与主节点选举
主从复制的系统需要确保有且仅有一个主节点，否则会产生脑裂。选举新的主节点常见的方法就是使用锁：即每个启动的节点都试图获得锁，但其中只有一个可以成功，继而成为主节点。不管锁具体如何实现，它必须满足可线性化：所有的节点都必须同意哪个节点持有锁，否则就会出现问题。
- 约束与唯一性保证
这种情况和加锁非常类似，其实本质都是要确保唯一性。
硬性的唯一性约束，常见如关系型数据库中的主键约束，则需要线性化保证。
- 跨通道的时间依赖
当系统中存在多个不同的通信通道时，如果没有线性化的就近保证，这些通道之间存在竞争条件。
线性化并非避免这种竞争的唯一方法，但却是最容易理解的。
2.4 实现线性化系统
线性化本质上意味着“表现得好像只有一个数据副本”，所以最简单的方案自然是只用一个数据副本。但显然，该方法无法容错：如果仅有的副本所在的节点发生故障，就会导致数据丢失。
系统容错最常见的方法：复制机制。但是非常遗憾，三种主流复制方案，都无法实现完全的可线性化。
（1）主从复制（部分支持可线性化）
同步方式：理论上可以满足线性化。但是，如果某节点自认为是主节点，但事实并非如此，主要是因为他们可能会采用快照隔离的设计，或者实现时存在并发方面的bug。（这显然不满足线性化的就近一致保证）这个“自以为是”的主节点如果对外提供服务，就会违反线性化。
异步方式：故障切换过程中甚至可能会丢失一些已提交的写入，结果是同时违反持久性和线性化。
（2）多主复制（不可线性化）
多主节点复制的系统通常是无法线性化的，这其实正是多副本，从定义上就违背了可线性化。
（3）无主复制（可能不可线性化）
对于无主节点复制的系统，完全取决于具体的quorum的配置，以及如何定义强一致性，它非常有可能并不保证线性化。比如：“最后写入者获胜”冲突解决方法几乎肯定是非线性化的；宽松的quorum也会破坏线性化。
综上所述，单纯依靠三种常见的复制机制都无法安全地实现线性化。我们需要专门设计的共识算法来实现可线性化，这些系统包括：ZooKeeper和etcd。
2.5 可线性化的代价
根据CAP理论：
（1）一致性，可用性，分区容错性，系统只能同时支持其中两个特性。
（2）但是，这种理解存在误导性。网络分区是一种故障，不管愿不愿意，它都可能发生，所以无法选择或逃避分区问题。
（3）在网络正常的时候，系统可以同时保证一致性（线性化）和可用性。而一旦发生了网络故障，就必须选择一致性或可用性。
理想与现实：为了性能放弃可线性化
（1）多核CPU上的内存就是非线性化的。原因是每个CPU核都有自己独立的cache和寄存器。内存访问首先进入cache系统，所有修改默认会异步地刷新到主存。由于访问cache比访问主存快得多，所以这样的异步刷新特性对于现代CPU的性能至关重要。但是，这样就导致出现了多个数据副本，而副本更新是异步方式，无法保证线性化。
（2）很多分布式数据库也是类似，往往不支持线性化，是为了提高性能，而不是为了保住容错特性。因为无论是否发生网络故障，线性化对性能的影响都是巨大的。
3. 顺序保证
让我们再次回顾“可线性化”的思想：让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。这其实就是意味着操作是按照某种顺序执行。
顺序、可线性化与共识之间存在着某种深刻的联系。
3.1 顺序与因果关系
之所以关注“顺序”，是因为它有助于保持因果关系。
如果系统服从因果关系所规定的顺序，我们称之为因果一致性。
（1）一致性模型：全序与偏序
全序与偏序：
全序关系支持任何两个元素之间进行比较，即对于任意两个元素，总是可以指出哪个更大，哪个更小。
有些集合无法直接进行比较，我们称之为不可比较，因此只能定义偏序。
不同的数据库一致性模型的全序和偏序：
可线性化：全序。对于任何两个操作，我们总是可以指出哪个操作在先。
因果一致性：在因果一致性系统中，存在因果关系和并发关系。如果两个事件是因果关系，那么这两个事件可以被排序；如果两个事件都没有发生在对方之前，则两个事件是并发关系，而并发的事件无法排序比较。这表明因果一致性可以被定义为偏序，而非全序。
根据这个定义，我们可以理解为：
在可线性化数据存储中不存在并发操作，一定有一个时间线将所有操作都全序执行。可能存在多个请求处于等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作，所以是单个时间轴，单个数据副本，没有并发。
（2）可线性化强于因果一致性
可线性化一定意味着因果关系：任何可线性化的系统都将正确地保证因果关系
。特别是，如果系统存在多个通信通道，可线性化确保了因果关系会自动全部保留，而不需要额外的工作。而因果一致性在多个通信通道之间是一种并发，无法确保因果关系。
一方面，可线性化可以确保因果性这一结论，使线性化系统更加简单易懂且具有吸引力。但是，“线性化的代价”已经阐述，线性化将会显著降低性能ヘ可用性，尤其是在严重网络延迟的情况（多数据中心，分布式系统）
另一方面，我们很多时候真正的需求并不是线性化，而是因果一致性，后者的实现可以高效很多。好消息是线性化并非是保证因果关系的唯一途径，还有其他方法使得系统可以满足因果一致性而免于线性化所带来的性能问题。
3.2 序列号排序
显示跟踪所有因果关系不切实际
：虽然因果关系很重要，但实际上跟踪所有的因果关系并不切实际。在许多应用程序中，客户端在写入之前会先读取大量数据，系统无法了解之后的写入究竟是依赖于全部读取内容，还是仅仅只需要其中一部分。但很明显，显示跟踪所有已读数据意味着巨大的运行开销。
使用序列号或时间戳来排序事件是更好的方法
：递增的序列号或时间戳非常紧凑，并且它们可以保证全序关系。根据唯一且可比较的序列号或时间戳，对于任何操作，我们总是可以比较大小，从而确定顺序。
因果序列发生器
在主从复制数据库中，复制日志定义了与因果关系一致的写操作全序关系：主节点可以简单地为每个操作递增某个计数器，从而为复制日志中的每个操作赋值一个单点递增的序列号。从节点按照复制日志出现的顺序来应用写操作，最终结果一定满足因果一致性。
如果系统不存在这样唯一的主节点（比如：多主或无主），如何产生序列号就是个大难题了，直观上可以有三种思路，不过它们各有问题：
思路一：每个节点都独立产生自己的一组序列号
。例如，如果有两个节点，则一个只生成奇数，另一个只生成偶数。
问题是
：每个节点可能有不同的处理速度，一个节点差生偶数而另一个产生奇数，偶数的计数器产生速度可能远远落后于奇数的计数器，反之亦然。这样就无法准确知道哪个操作在先。
思路二：可以把墙上时间戳（物理时钟）附加到每个操作上
。时间戳可能是不连续的，但是只要它们有足够高的分辨率，就可以用来区分操作。“最后写入者获胜”的冲突解决方案就是采用这种方法。
问题是
：物理时钟的时间戳会受到时钟偏移的影响，也可能导致与实际因果关系不一致。
思路三：预先分配序列号的区间范围
。例如，节点A负责区间1~ 1000的序列号，节点B负责区间1001~ 2000。然后每个节点独立地从区间中分配序列号，当序列号出现紧张时就分配更多的区间。
问题是
：对于存在因果关系的两个操作，一个操作可能被分配到1 ~1000之间的某个序列号，而后发生的操作可能被分配到另一个节点，拿到1001 ~2000之间的序列号，导致因果关系不一致。
Lamport时间戳
刚才上面描述的三个序列号发生器可能与因果关系存在不一致，有一个简单的方法可以产生与因果关系一致的序列号：兰伯特时间戳（Lamport Timestamp）。
原理与关键设计：
（1）首先每个节点都有一个唯一的标识符，且每个节点都有一个计数器来记录各自已经处理的请求总数。
（2）Lamport时间戳是一个值对（计数器，节点ID）。两个不同的节点可能会有相同的计数器值，但是时间戳中还包含了节点ID信息，因此可以确保每个时间戳都是唯一的。
（3）只根据上面两点，得到的其实和奇/偶计数器并未区别。**Lamport的核心亮点在于使他们与因果性保持一致：每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。**当节点收到某个请求时，如果发现请求内嵌的最大计数器值大于节点自身的计数器值，则立即把自己的计数器修改为该最大值。
只要把最大计数器值嵌入到每一个请求中，该方案可以确保Lamport时间戳与因果关系一致，请求的因果依赖性一定会保证后发生的请求得到更大的时间戳。
Lamport时间戳 VS 版本矢量
它们的目的有本质不同：版本矢量用以区分两个操作是并发还是因果依赖，而Lamport时间戳主要用于确保全序关系。
换言之，Lamport时间戳无法区分两个操作属于并发关系，还是因果依赖关系。
Lamport时间戳排序依然不够
虽然Lamport时间戳定义了与因果序一致的全序关系，但还不足以解决实际分布式系统中许多常见的问题。比如，如果使用时间戳排序来实现唯一性约束，就会丧失容错性。
问题的关键在于：只有收集了所有的请求信息后，才能清楚这些请求之间的全序关系。如果另一个节点执行了某些操作，但你无法知道那是什么，就无法构造出最终的请求序列。
要想知道何时全序关系已经确定，就需要之后的“全序关系广播”。
3.3 全序关系广播
顺序保证的范围
每个分区只有一个主节点的数据库通常只会维护分区内的顺序，即它们不提供跨分区的一致性保证。跨分区的全序关系并非不可能，但需要很多额外的工作，这就是“全序关系广播（原子广播）”
全序关系广播的概念
通常指节点之间交换消息的某种协议。例如下面的一个非正式定义，它要求满足两个基本安全属性：
（1）可靠发送：没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。
（2）严格有序：消息总是以相同的顺序发送给每个节点。
即使节点或网络出现了故障，全序关系广播算法的正确实现也必须保证上述两条。当然，网络中断时是不可能发送成功的，但算法要继续重试，直到最终网络恢复，消息发送成功。
全序关系广播的应用范围
（1）共识。像ZooKeeper和etcd这样的共识服务实际上就实现了全序关系广播，这暗示了全序关系广播和共识之间有着密切联系。
（2）数据库复制。全序关系广播正是数据库复制需要的：如果每条消息代表数据库写请求，并且每个副本都按照相同的顺序处理这些写请求，那么所有副本可以保持一致。该原则也被称为“
状态机复制
”
（3）串行化事务。如果每条消息表示一个确定性事务并且作为存储过程来执行，且每个节点都遵循相同的执行顺序，那么可以保证数据库各分区以及各副本之间的一致性。
（4）提供fencing令牌的锁服务。每个获取锁的请求都作为消息附加到日志中，所有消息按照日志中的顺序依次编号。序列号可以作为令牌，它符合单调递增的要求。在ZooKeeper中，该序列号被称为zxid。
全序关系广播和线性化存储的相互实现
直观上，全序关系广播和线性化存储的区别和联系：
（1）一方面，两者是完全不同的概念。全序关系广播是基于异步模型，保证消息以固定的顺序可靠地发送，但是不保证消息何时发送成功（因此，某个接收者可能明显落后于其他接收者）。而可线性化强调就近性；读取时保证能够看到最新的写入值。
（2）另一方面，如果有了全序关系广播，就可以在其上构建线性化的存储系统。而利用线性化的寄存器，使其支持原子自增-读取操作或者原子比较-设置操作，可以很容易实现全序关系广播。
本质上，我们可以证明：线性化的原子比较-设置（或自增-读取）寄存器与全序关系广播二者都等价于共识问题。
4. 分布式事务与共识
共识问题是分布式系统中最重要也是最基本的问题之一。
有很多重要的场景都需要集群节点达成某种一致，例如：主节点选举，原子事务提交。
4.1 原子提交与两阶段提交
从单节点到分布式的原子提交
原子性的目的是：当一个包含了多笔写操作的事务在执行过程中出现任何意外，原子性可以为上层应用提供简单的语义——“事务的结果要么是成功提交，要么是失败中止，不存在中间状态”。
在单节点上，就比较简单了，事务提交依赖数据持久写入磁盘的顺序关系：先写入数据，然后再提交记录。事务提交（或中止）的关键点在于磁盘完成日志记录的时刻：在完成日志记录写之前如果发生崩溃，则事务需要中止；在日志写入完成之后，即使发生崩溃，事务也被安全提交。
但是，当一个事务涉及多个节点时，如果不加干涉，很容易出现部分节点提交成功，而其他节点发生失败，从而违反原子性保证。如果一部分节点提交了事务，而其他节点却放弃了事务，节点之间就会变得不一致。
两阶段提交
两阶段提交（2PC）是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。
协调者
2PC的关键设计是：引入了单节点事务所没有的新组件——协调者（事务管理器）。其工作原理是：
当应用程序准备提交事务时，协调者开始阶段1：发送一个准备请求到所有节点，询问他们是否可以提交。协调者跟踪参与者的回应：
所有参与者回答“是”，表明所有参与者都准备好提交，那么参与者在阶段2发出提交请求，提交开始实际执行。
如果有任意一个参与者回复“否”，则协调者在阶段2向所有节点发送放弃请求。
系统的承诺
即使对于2PC，准备和提交也一样可能发生丢失，那么2PC究竟有何不同？
首先，先了解下2PC的详细步骤:
（1）应用程序启动事务。向协调者申请事务ID，全局唯一。
（2）应用程序在每个节点上执行单节点事务，将全局事务ID附加到事务上。这一阶段所有读写都发生在单节点内部，如果出现问题，则协调者可以协调所有节点安全中止事务。
（3）当应用程序准备提交时，协调者向所有节点发送准备请求，并附带事务ID。如果出现问题，协调者通知所有节点放弃事务.
（4）节点回答准备请求，如果回答”是”，则节点需要保证在任何情况下都可以提交事务。
提交点。协调者收到所有节点回复”是”，作出明确的决定。协调者把决定写入到磁盘事务日志(为了崩溃恢复)。
（5）决定写入磁盘后协调者向所有节点发送提交(或放弃)请求。如果请求出现失败/超时，则协调者必须一直重试，直到成功为止。
根据其工作过程，2PC有两个关键的“不归路”：
（1）当参与者投票“是”，他做出了肯定提交的承诺。
（2）协调者做出了提交的决定，这个决定也是不可撤销的。
正是这两个承诺确保了2PC的原子性。
协调者发生故障
由上可知，2PC的实现，十分依赖协调者。但是，如果协调者本身发生了故障，接下来会发生什么？
如果协调者在发送准备请求之前就已故障失败，则参与者可以安全地中止交易。但是，一旦参与者收到了准备请求并做出了投票“是”，则参与者不可以单方面放弃，它必须等待协调者的决定。如果在决定到达之前，出现协调者崩溃或故障，则参与者只能等待，此时参与者处于一种不确定状态。这就是为什么协调者必须在向参与者发送提交（或中止）请求之前要将决定写入磁盘的事务日志，等协调者恢复之后，通过读取事务日志来确定所有未决的事务状态。
4.2 支持容错的共识
通俗理解，共识就是让几个节点就某项提议达成一致。
共识问题通常形式化描述如下：一个或多个节点可以提议某些值，由共识算法来决定最终值。在这个描述中，共识算法必须满足以下性质：
（1）协商一致性：所有的节点都接受相同的决议
（2）诚实性：所有的节点不能反悔，即对一项决议不能有两次决定
（3）合法性：如果决定了值x，则x一定是由某个节点所提议的。
（4）可终止性：节点如果不崩溃，则最终一定可以达成决议。
1.协商一致性和诚实性定义了共识的核心思想：决定一致的结果，一旦决定，就不能改变。
2.合法性主要是为了排除一些无意义的方案：例如，无论什么建议，都可以有一个总是为空（NULL）的决定，这虽然可以满足一致性和诚实性，但没有任何实际效果。
3.可终止性则引入了容错的思想。它强调一个共识算法不能原地空转，它必须取得实质性进展。即使某些节点出现了故障，其它节点也必须最终做出决定。
4.可终止性是一种活性，而另外三种属于安全性。
5.可终止性的前提是：发生崩溃或者不可用的节点数必须小于半数节点。因为我们可以证明任何共识算法都需要至少大部分节点正确运行才能确保终止性。
4.3 分布式系统的共识
真正实践中，
分布式系统往往采用ZooKeeper等工具以一种类似外包的形式来实现共识
。这远比自己开发共识算法要好的多。
ZooKeeper或etcd项目通常被称为”分布式键值存储”或”协调与配置服务”。它们对外提供的API和数据库非常相像：读取、写入对应主键的值、遍历主键。
应用开发者很少直接使用ZooKeeper，绝大多数情况是其他项目间接地依赖于ZooKeeper，如HBase，Hadoop YARN，OpenStack Nova，Kafka等。（ZooKeeper大写的惨！工具人石锤。）
ZooKeeper/etcd可以实现的功能
ZooKeeper/etcd主要针对保存少量、可完全载入内存的数据而设计，所以不要用他们保存大量数据。它们通常采用容错的全序广播算法在所有节点上复制数据从而实现高可靠。
ZooKeeper的实现其实模仿了Google的Chubby分布式锁服务。但它不仅实现了全序广播(因此实现了共识)，还提供了很多非常有用的功能:
（1）线性化的原子操作
（2）操作全序
（3）故障检测
（4）更改通知
上述特征中，其实只有第一个——线性化的原子操作才依赖于共识。但是ZooKeeper一次性全部集成了这些功能，在分布式协调服务中发挥了关键作用。（这是什么奉献精神？都给我哭！）
总的来说，如果面临的问题最终可以归结为共识，并且还有容错性需求，建议别想了，直接采用ZooKeeper等已经经过验证的系统。