2021-07-29

DDIA: 一致性与共识

在分布式系统中，比较重要的抽象概念是共识：所有节点就某一项提议达成一致。

共识在分布式系统中有许多应用场景：比如，对于一个主从复制的数据库集群，如果主节点发生失效，那么就需要切换到另一个节点，而新的主节点的选举就可以采用共识算法来实现。共识算法能够保证在某一时刻，只有一个主节点。

如果两个节点都认为自己是主节点，就会发生脑裂，导致数据丢失，而共识算法能够保证这种异常不会发生

一致性保证

在多副本数据库的复制中（主从复制，多主节点复制，无主节点复制），如果在同一时刻同时访问集群中的两个不同节点，可能会看到不一样的数据，造成这种现象的原因是写请求会在不同的时间到达不同的节点，导致同一时刻各个副本的数据存在不一致现象。

不过，大多数系统都提供了最终一致性：在更新之后的一段时间（时间长度未知），最终所有的副本都会保持一致。也就是说这种副本间不一致的现象是短暂的，最终会收敛；但是，这种最终一致性是很弱的保证，无法告诉我们什么时候会收敛完成。

对于这种只能提供弱一致性保证的系统来说，存在一定的局限性。因此，需要更强的一致性保证，不过相应的会导致性能降低等一些问题。

分布式一致性与事务隔离级别中有相似之处，但是还是存在明显的区别：事务隔离性是为了处理并发执行事务时的各种临界条件，而分布式一致性则主要针对延迟和故障等问题来协调副本之间的状态。

可线性化

可线性化使得一个多副本系统看起来好像只有一个数据副本，并且对这个系统的所有操作都是原子的。（可线性化也被称为原子一致性，强一致性等）

在一个可线性化的系统中，一旦某个客户端成功提交写请求，那么之后所有客户端的读请求一定都能看到这个刚刚写入的值。因此，可线性化能够保证读取最近最新的值，而不是过期的值。

如何达到可线性化

为了实现可线性化，需要对系统进行约束：一旦新值被写入或者读取，所有后续的读到看到的是新值

可线性化背后的思想是：使得整个系统看起来好像只有一个数据副本。结合例子，逐步理解可线性化。

下图展示三个客户端在线性化数据库中读写相同的记录 X（图中是客户端的视角，代表着客户端的请求与相应）。

在读请求与写请求并发时，可能会读到旧值，即对于与写操作有时间重叠的读取操作可能返回 0/1。

如果与写操作并发的读操作可能返回旧值，也可能返回新值，那么整个过程中，不同客户端会看到旧值与新值来回跳变的情况，这与我们期望的可线性化（单一数据副本）是不一致的。

为了使系统满足线性化，我们需要添加一个约束：一旦某个读操作返回了新值，那么之后所有的读（包括相同/不同的客户端）都必须返回新值；即使对应的写操作尚未完全提交。

在一个可线性化的系统中，在写操作的开始与结束之间，一定存在某个时间点，使得 X 的值从 0 变成了 1。在上图中，A 首先读到了新值 1，在 A 读取返回之后，B 开始读，由于 B 的读取在 A 之后发生（箭头表示时序），那么即使 C 的写入仍在进行中，也必须返回 1.

下面对读写操作的生效时间进行细化，下图每个操作中的竖线都表示可能的执行时间点。

可线性化要求，如果依次连接这些标记的竖线，它们总是按照时间箭头（从左到右）向前移动，而不能向后移动（客户端 B 的最后操作不满足可线性化）。这个要求保证了：一旦新值被写入或者读取，所有后续的读到看到的是新值。

可线性化与可串行化

可串行化（Serializability）：事务的隔离属性，其中每个事务可以读写多个对象（记录）；用来确保事务执行的结果与串行执行（即每次执行一个事务）的结果完全相同，即使串行执行的顺序与事务世纪执行的顺序不同。

可线性化（Linearizability）：读写单个对象的最新值保证；并不要求将操作组合到事务中，因此无法避免写倾斜问题。

数据库可以同时支持可线性化与可串行化，这种组合被称为严格的可串行化或者强的单副本可串行化。

快照隔离不支持可线性化

线性化的依赖条件

线性化能够保证总是能够读取到最新已经提交的数据，但是并不是所有的场景都需要实现可线性化，它们能够接收一些延迟同步，并且不会有实质性的损失。不过，存在一些场景，线性化对于保证系统正确工作至关重要。

加锁 & 主节点选举

对于主从复制系统需要确保最多只有一个主节点，否则会产生脑裂。主节点的选举一般使用加锁机制：每个节点都尝试获取锁，其中只有一个节点可以成功获取锁并成为主节点。

因此，对于锁的实现，必须满足可线性化：所有节点必须都同意哪个节点持有锁，否则会出现问题。

约束 & 唯一性保证

唯一性约束在数据库中比较常见，例如用户名必须唯一。同时，在文件系统中，两个文件不能具有相同的路径和文件名。

这些情况本质上与加锁行为非常相似：所有节点对某个最新值达成一致。

实现线性化系统

由于线性化本质上意味着“好像只有一个数据副本，并且对其所有操作都是原子性的”，所以实现一个线性化系统最简单的方式是只用一个数据副本。不过，单副本的实现在可用性与容错性方面较差：如果仅有的单副本节点发生故障，那么可能会导致数据丢失，或者无法对外提供服务。

为了提高容错性，最常见的方式是采用复制机制；对于复制机制，有以下几种方案：

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

在主从复制中，只有主节点承担数据写入功能，从节点则各自维护数据备份。在数据读取中，如果从主节点或者同步更新的从节点上读取，那么可以满足线性化。

然而对于一些场景可能不支持线性化：a. 主从复制中各节点数据库在实现时不支持线性化，那么整个系统就不支持线性化（如使用了快照隔离的设计）；b. 从主节点上读取数据的前提是明确知道哪个节点是主节点，但是可能会存在多个节点同时认为自己是主节点，从而违反线性化；c. 在主从复制中如果使用了异步复制，那么在故障切换中可能会丢失一些已经提交的写入，从而违反线性化与可持久性。
共识算法（可线性化）

与主从机制类似，不过在实现时通过一些措施来防止脑裂和过期的副本，从而可以安全地实现线性化存储；使用共识算法实现的系统包括 Zookeeper & Etcd 等。
多主复制（不可线性化）

多主复制的系统通常无法实现线性化，主要是由于该系统同时在多个节点上执行并发写入，并将数据异步复制到其他节点。因此可能会产生冲突的写入，需要额外的解决方案。
无主复制（可能不可线性化）

直觉上对于 Dynamo 风格的复制模型（w + r > n），如果遵守了严格的 quorum ，应该是可以满足线性化的；但是，仍然可能会出现不满足线性化的情况。

线性化的代价

如果系统要求线性化，但是由于网络方面的问题，某些副本与其他副本断开连接之后无法继续处理请求，就必须等待网络恢复，或者直接返回错误。无论何种方式，结果都是服务不可用。
如果系统不要求线性化，那么断开连接后，每个副本可以独立处理请求，例如写操作（多主复制）。此时，服务可用，但是结果行为不符合线性化。

因此，不要求线性化的系统更能容忍网络故障，这种思路被称为 CAP 理论。

CAP 理论：一致性，可用性，分区容忍性。在网络正常的时候，系统可以同时保证一致性（线性化）和可用性；而一旦发生了网络故障，必须要么选择一致性（CP），要么选择可用性（AP）。

可线性化与网络延迟

虽然线性化是一个很有用的保证，但是实际上很少有系统真正满足线性化。虽然在 CAP 理论中强调在网络分区时，为了提高可用性而放弃一致性。但是更多系统放弃线性化的原因是性能，而不是为了容错。

现代多核 CPU 上的内存就是非线性化的：如果某个 CPU 上运行的线程修改了内存，紧接着另一个 CPU 上的线程尝试读取，则系统无法保证能够读到刚刚写入的值，除非使用内存屏障或者 fence 指令。每个 CPU 都有自己独立的 cache 和寄存器，内存访问首先修改 cache，之后异步刷新到主存。由于 cache 访问比主存访问要快的多，因此这样的异步刷新特性能够提升整个系统的性能。多核 CPU 的架构与分布式中多数据副本架构类似。

在计算机内部，我们不会假设某个 CPU 与其他核断开之后仍能正常工作；其放弃线性化的原因就是为了提升性能。许多分布式数据库也是类似，不支持线性化的原因是为了提高性能，而不是保住容错性。无论是否发生了网络故障，线性化对于性能的影响都是巨大的。

一个线性化系统的读写性能都比较差

顺序保证

顺序也是一个非常重要的概念；事实证明，排序，可线性化，共识之间存在这深刻的联系。

顺序与因果关系

我们研究顺序的一个原因是其有助于保持因果关系。而因果关系对所发生的事件施加了某种排序：发送消息先于收到消息；问题出现在答案之前等。因果关系的依赖链条定义了系统中的因果顺序，即某件事情应该发生在另一个事情之前。

如果系统服从因果关系所规定的顺序，称之为因果一致性。例如，快照隔离提供了因果一致性：读取某些数据时，能够看到该数据的前序事件。

因果顺序并非全序

全序关系支持任何两个元素之间进行比较，即对于集合中的任意两个元素总是可以判断出哪个更大，哪个更小。因果关系并不是全序，而是一种偏序。

可线性化：在一个可线性化系统中，存在全序操作关系。系统的行为好像只有一个数据副本，并且每个操作都是原子性的；这意味着对于任意两个操作，总是可以判断出哪个操作在先；这种全序排列类似于之前的数据库操作时间线。

因果关系：如果两个操作都没有发生在对方之前，那么这两个操作是并发关系。如果两个操作是因果关系，那么这两个事件可以进行排序；而并发的事件无法进行排序。

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

可能存在多个请求处于等待处理的状态，但是数据存储保证了在特定的时间点执行特定的操作，所以是单个时间轴，单个数据副本，没有并发。

而因果关系的时间线会出现分支与合并，而不同分支上的操作无法进行直接比较，类似于 git 中的版本记录。

可线性化强于因果关系

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

不过线性化并不是实现因果关系的唯一方式，还有其他方式既能够满足因果关系，又能避免线性化带来的性能问题，比如版本向量

因果一致性可以看作是，不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。

序列号排序

我们可以使用时间戳或者序列号来对事件进行排序，其中时间戳不一定是物理时钟，可以是逻辑时钟。

通过这种方式，每个操作都有一个唯一的顺序号，并且可以通过时间戳或者序列号来对操作进行比较，从而使得所有操作具有全序关系。除了全序，我们也可以使用支持因果关系的序列号：如果 A 操作发生在 B 操作之前，那么 A 操作的序列号更小；如果 A，B 同时发生，那么它们的序列号可以是任意的。这样的全局排序可以捕获所有的因果信息，但也强加了比因果关系更为严格的顺序性。

序列号的产生有几种方式：

通过唯一的主节点（主从复制）为每个操作产生递增的序列号，则产生的序列号一定满足因果一致性
每个节点独立产生一组自己的序列号（多主或者无主复制），同时需要保证每个节点产生的序列号不会冲突：一个节点生成偶数，一个节点生成奇数；每个节点只产生指定区间的序列；将序列号与物理时间戳绑定

第二种方式相对于第一种有更好的扩展性，并且能够为每个操作生成唯一的，近似单调递增的序列号；但是多个节点产生的序列号并不一定符合因果一致性。

每个节点可能有不同的处理速度，可能奇数产生的速度比偶数的速度更快，那么就不能准确判断哪个操作在前，哪个操作在后
对于区间分配，如果 A 节点分配了 1 ～ 100 的范围，B 节点分配了 101 ～ 200 的范围；假设某个操作路由到了 B 节点，之后的一个操作被路由到了 A 节点，那么这两个操作的序列号不符合因果顺序
物理时钟可能会受时钟偏移的影响导致各个节点的时间戳不一致

Lamport 时间戳

Lamport 时间戳是一个值对 ⇒（计数器，节点 ID）：

节点 ID 是各个节点的唯一标识符
计数器用来记录各个节点处理的请求总数

通过计数器 + 节点 ID 可以确保时间戳的唯一性

Lamport 时间戳与物理时钟没有任何关系，但是也可以保证全序关系：对于给定的两个时间戳，计数器大的时间戳更大；如果两者的计数器相同，则节点 ID 大的时间戳更大。

Lamport 时间戳看起来与上面描述的多节点序列号产生的方式类似，不过其为了保证因果关系做了一些约束：

每个节点 & 客户端都跟踪迄今为止见到的最大的计数器值，并在请求中携带该计数器值
当节点收到某个请求（或者回复）时，如果发现请求（或者回复）携带的计数器值大于节点自身的计数器值，则立即把自己的计数器值修改为该最大值

在 Client A 的最后两个操作中，首先从 Node 2 中获得最大的计数器值 5，然后将 5 发送给 Node 1，该节点收到请求后将自身计数器值更新为 5，接着为下一个操作的计数器值设置为 6.

只要把最大计数器值附加在每个请求中，那么就能确保 Lamport 时间戳满足因果一致性，因为后发生的请求一定能获得更大的时间戳。

Lamport 时间戳能够确保全序关系，相应地也能确保因果关系，但是对于两个操作是否是并发关系无法确定

Lamport 时间戳虽然能够保持全序关系，但是对于实现线性化还是不够的。例如，一个系统中的用户名需要保证唯一性，即对于两个想要同时创建同一个用户名的操作来说，只能有一个操作成功，另一个操作必须失败。

看起来全序关系能够解决这类操作：对这两个操作进行排序，较小的请求成功，较大的失败。但是这个排序关系需要先收集系统中所有节点的操作后才能进行比较；即当某个节点收到创建用户的请求时，不能立马做出判断该操作是成功还是失败，必须先检查其他所有节点是否存在创建该用户的请求，然后才能进行排序判断。

所以为了实现类似的唯一性约束，仅仅能够对操作进行全序排列是不够的，还需要知道这些操作是否发生，何时确定等；那么想要知道全序关系什么时候确定了，就需要全序广播。

全序关系广播

将所有操作的全序关系广播到所有副本中

在分布式系统中，想要让所有的节点就全序关系达成一致是不容易的。Lamport 时间戳虽然能够保证全序关系，但是实现起来没有主从复制那么直接有效。

对于主从复制来说，首先需要确定一个节点作为主节点，然后主节点顺序执行操作。该系统最大的挑战是如何扩展系统的吞吐量，以及如何处理主节点失效时的故障切换。这些问题被成为全序关系广播。

全序关系广播是指节点之间交换消息的某种协议，需要满足两个基本安全属性：

可靠发送：没有消息丢失，如果消息发送到了某个节点，则一定要发送到所有节点
严格有序：消息总是以相同的顺序发送给每个节点

即使出现故障，上述两条也必须要保证

全序关系广播是数据库复制所需要的：如果每条消息代表数据库写请求，并且每个副本都按照相同的顺序处理这些请求，那么所有副本可以保持一致（可能会有些滞后），该原则被称为状态机复制。

全序关系广播的顺序在发送消息时已经确定，如果消息发送成功，节点不允许追溯地将某条消息插入到先前的某个位置上。

Zookeeper & Etcd 等共识服务均实现了全序广播

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

在一个可线性化的系统中存在全序关系操作集合，不过两者并不完全相同：

全序关系广播基于异步模型：保证消息以固定的顺序可靠地发送，但是不保证消息什么时候发送成功（会出现某些节点明显滞后）
可线性化强调就近性：读取时保证能够看到最新的写入值

可以基于全序关系广播构建线性化存储系统，例如确保用户名唯一性。

使用全序关系广播以追加日志的方式来实现线性化的原子比较-设置操作（确保用户名唯一）：

在日志中追加一条消息，并指明想要的用户名
读取日志，将其广播给所有节点，并等待回复
检查是否有任何消息声称该用户名已经被占用。如果第一条这样的回复来自当前节点，那么就成功获取该用户名，可以提交该声明并返回给客户端；反之，如果声称占用的第一条消息来自其他节点，则终止操作

该流程是主节点接收客户端请求并发送给从节点，如果所有从节点之前都没有应用过该用户名，则主节点将用户名应用到状态机中。在 Raft 中，如果从节点与主节点中的日志不一致，则会直接覆盖从节点；在其他共识算法中可能会将当前主节点与从节点的日志进行整合，使得新的主节点重新获取丢掉的日志

日志条目以相同的顺序发送到所有节点，而如果存在并发写入，则所有节点首先决定哪个请求在先；选择第一个写请求作为获胜者并终止其他请求，以确保所有节点同意一个写请求要么提交成功要么终止。

上述流程只保证了线性化写，无法保证线性化读；如果用户直接从落后的副本中读取数据，仍然可能读取到旧值。为了同时满足线性化读，有几个方案：

把读请求也使用追加日志的方式排序，广播，然后在各个节点中获取该日志，当本节点收到消息后菜执行读操作
获取当前最新日志中消息的位置，直到该位置之前所有的日志条目都发送后，在执行读取
从同步更新的副本上读取

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

如果已经有了线性化存储系统，想要实现全序关系广播是比较容易的。可以利用线性化存储实现一个单调递增的计数器，对于每个消息都附加一个递增的序列号；然后将消息广播到所有节点，而接受者也严格按照序列号来回复消息。

分布式事务与共识

共识问题也是分布式系统中最基本的问题之一，共识的目的是让几个节点就某一事件达成一致。

在许多场景中都需要集群中的节点达成某种一致：

主节点选举

对于主从复制的数据库，需要对谁来充当主节点达成一致。如果由于网络问题使得部分节点之间无法通信，可能会导致两个节点都认为自己是主节点，从而产生数据异常等问题；而共识能够避免这种错误的故障切换。
原子事务提交

对于跨节点或者跨分区的事务，在执行中可能会存在部分节点成功，其他节点失败的情况。为了保证事务的原子性，需要所有节点对事务的执行结果达成一致：要么成功提交，要么失败回滚。

两阶段提交（2PC）

2PC 是一种在多节点之间实现事务原子提交的算法，用来确保所有的节点要么全部提交，要么全部终止。

2PC 引入了一个组件：协调者（事务管理器）；参与分布式事务的数据库节点称为参与者。整体流程如下：

2PC 事务从应用程序在多个数据库节点上执行数据读写开始。当应用程序准备提交事务时，协调者开始阶段 1：发送一个准备请求到所有节点，询问它们是否可以提交，然后等待所有参与者的响应：

如果所有参与者都回答“是”，则表示所有参与者均准备好提交，那么协调者就会在阶段 2 发出提交请求，事务提交开始实际执行。
如果有任何参与者回复“否”，则协调者在阶段 2 中向所有节点发送放弃请求。

系统承若

2PC 为什么能确保跨节点的原子性，需要进一步分析下：

当应用程序开启一个分布式事务时，首先向协调者请求事务 ID（全局唯一）
应用程序在每个参与者上执行单节点事务，并将全局唯一的事务 ID 附加到事务上。此时的读写操作都是在单节点上完成，如果在该阶段出现问题，则协调者与其他参与者都可以安全终止事务
当应用程序准备提交事务时，协调者向所有参与者发送准备请求，并附带之前的全局事务 ID。如果准备请求有任何一个发生失败或者超时，则协调者都会通知所有参与者放弃事务
参与者在收到准备请求之后，需要检查自己是否可以安全地提交事务。一旦向事务协调者响应“是”之后，该节点就会承诺会提交事务
当协调者收到所有准备请求的响应后，就是否提交事务做出明确的决定（只有所有参与者都响应“是”时才会提交）。协调者将决定写入到磁盘的事务日志中，防止系统崩溃，该时刻称为提交点
协调者将事务提交的决定写入磁盘后，向所有参与者发送提交（放弃）事务的请求。如果该请求出现超时或者失败的情况，则协调者必须一直重试直至成功。如果有参与者此时出现了故障，则在其恢复后也必须继续执行。

在整个流程中存在两个承诺，用来确保 2PC 的原子性：

当参与者投票“是”时，做出了肯定提交的承诺
协调者对于事务提交（放弃）的决定也做了承诺

协调者发生故障

如果协调者在发送准备请求之前发生故障，则参与者可以安全地终止事务。

如果参与者收到了准备的请求并响应了“是”，则该参与者必须等待协调者的决定，不能单方面放弃；即使协调者出现故障，也要一直等待下去。

支持容错的共识

共识问题通常形式化描述为：一个或者多个节点可以提议某些值，由共识算法来决定最终值。

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

协商一致性（Uniform agreement）

所有节点都接收相同的决议
诚实性（Integrity）

所有节点不能反悔，即对一项提议不能有两次决定
合法性（Validity）

如果最终决定了值 v，那么 v 一定是由某个节点所提议的
可终止性（Termination）

节点如果不崩溃，则最终一定可以达成决议

协商一致性 & 诚实性定义了共识的核心思想：决定一致的结果，一旦决定，就不能有所改变。

可终止性引入了容错的思想，它强调一个共识算法必须取得实质性进展，不能原地空转（在 2PC 中，如果协调者出现故障，则参与者就只能继续等待）。即使某些节点出现故障，其他节点也必须做出决定（前提是需要大部分节点仍能正确运行）。

可终止性属于活性，另外三个属性属于安全性

共识算法与全序广播

常见的容错式共识算法有 Paxos, Raft, Zab 和 VSR。这些算法其实并不是直接采用上面的形式化模型（提议并决定某个值，同时满足上面 4 个属性）；相反，它们是决定了一系列的值，然后采用全序关系广播算法。

全序关系广播需要将消息按照相同的顺序发送到所有节点，有且只有一次，相当于进行了多轮共识过程：在每一轮，节点提出它们接下来想要发送的消息，然后决定下一个消息的全局顺序。所以全序关系广播相当于持续的多轮共识（每轮共识对应一条消息）。

主从复制与共识

在主从复制中，所有的写入操作都由主节点负责，并以相同的顺序发送到从节点来保持副本更新，所以主从复制实际上就是全序关系广播。

不过，主从复制可能不能满足共识算法的可终止性：如果主节点故障，如何选举新的主节点？而为了选举新的主节点，又需要共识算法来实现。

重新梳理下，全序关系广播相当于多轮共识，主从复制就是全序关系广播，主从复制的主节点选举又依赖共识 ⇒ 共识算法的实现，需要依赖共识。看起来像一个循环依赖。

Epoch & Quorum

目前的共识算法都是用了某种形式上的主节点，主节点并不固定。这些算法使用了一种弱化的保证：定义一个世代编号（Raft: term number, Paxos: ballot number），并保证在每个世代里，主节点是唯一的。

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

在主节点做决定之前，需要先检查是否存在比它更高的 epoch 号码，确保不会同时存在多个主节点。主节点如果想要做某个决定，需要将提议发送给其他所有的节点，等待 quorum 节点响应；如果其他节点没有发现更高的 epoch 主节点存在时，才会对该提议进行投票。

所以，每次提议都会进行两轮投票：

对主节点投票：如果没有更高的 epoch，则当前主节点的地位保持不变
对主节点的提议投票

两轮投票的 quorum 必须有重叠

共识的局限性

共识可以提供全序关系广播，以容错的方式实现线性化的原子操作。

不过，共识的实现是有局限性的：

在达成一致性决议之前，节点投票过程是一个同步复制过程，性能会有影响
共识体系需要多数节点运行才行
多数共识算法假定参与投票的节点数是固定的，意味着不能动态调整节点
共识系统通常依靠超时机制检测节点失效，不过由于网络延迟可能会导致主节点被频繁选举

小结

共识意味着就某一项提议，所有节点做出一致的决定，而且决定不可撤销。多个广泛的问题都可以归结于共识：

可线性化的 CAS 寄存器
原子事务提交
全序关系广播
锁与租约
唯一性约束
成员服务（系统决定节点的存活状态）

主从复制系统能够提供线性化操作，唯一性约束，完全有序的复制日志等能力，但是如果唯一的主节点发生故障，为了保证服务的可用性，我们需要重新选取一个主节点。共识算法能够帮助我们选出唯一的主节点。

共识算法对于主从数据库系统来说，主要用于主节点角色的维护与主节点变更的处理。对于多主复制和无主复制系统来说，通常不支持全局共识。