分布式一致性详解

发表于 |

本文被拆分自分布式一致性和分布式共识协议。拆分的目的是：

  1. 上一篇文章更贴近于 DDIA 的架构
  2. 本篇文章理论性较强，可以单独被拆出

分布式系统上的一致性和Order

在这个章节中，主要介绍和一致性相关的一些概念，包括：

  1. Consistency
  2. Order
  3. Clock
  4. Broadcast

从概念上：

  1. 分布式中的一致性指的是 CAP 中的 C
    从外部看来，要求多副本的系统的行为表现得像单系统一样，并且对这个系统的修改是原子的。
  2. 事务一致性指的是 ACID 的 C
    强调事务前后不变量不能改变。

一致性的等级

强一致性

分布式系统，特别是CAP理论中对一致性(consistency)的定义是all nodes see the same data at the same time，这个要求是比较高的，一些人会将它等价位强一致性(Strong consistency)、线性一致性(Linearizability)、外部一致性(External consistency)、原子一致性(atomic consistency)。

强一致性强调 each operation appears to execute instantaneously, exactly once, at some point between its invocation and its response。

考虑一个简单的主从架构的例子(来自Designing Data-Intensive Applications)，在下图中比赛结果由 Referee 写入 Leader 主库，并向两个 Follower 同步复制，线性一致性需要这个过程是透明的。

在本场景中即当任何一个读取返回新值后，所有后续读取都必须返回新值。但简单的读写分离主从复制，就会出现当 Leader 只同步了 Follower1 而没有同步到 Follower2 时，对两个副本的读取结果分别返回新值和旧值的现象。

需要注意，线性一致性和“未提交事务不可见”不是一个概念。比如如下图所示，client B 读取到的 x 可能为 0 或 1。因为此时 B 读和 C 写是并发的。按照线性一致的定义，只要在 invocation 和 response 之间瞬间完成读和写就行。

但如下如图所示，一旦 B 读到了 x 为 1，也就是 reponse 了。那么后续就不能读到之前的 x 为 1 的状态了。

如果一个写入返回后，读取还能返回旧值么？我想是不行的。这是因为 “… at some point between its invocation and its response”。所以在 response 后，这个操作就应该被认为已经执行完毕了。

可以参考C++内存模型中的可见性一块。

通过线性一致性可以实现分布式锁、选举、和唯一性约束等功能。我们使用共识算法实现的是线性一致性，而主从复制则不是。由此可见，分布式一致性(Consistency)和共识(Consensus)是完全不同的两个概念，后者是实现前者的一个工具。

辨析Linearizability、Serializability

还需要区分Linearizability和Serializability。

线性一致性(Linearizability)来源于分布式系统和并发编程，其语境是single-operation, single-object, real-time order，线性一致性保证了

  1. 写操作一旦完成，对后续的读操作是可见的，也就是经典的写后读问题。
  2. 一旦某个读操作返回了某个特定值，那么后续的读操作要么返回这个值，要么返回后面的写对应的值。

线性一致性往往对应于CAP中的C，线性一致性是composable，即local的。即如果每一个对象上的操作是线性的，那么系统上的所有操作都是线性的。

顺序一致性(Serializability)来源于数据库，其语境是multi-operation, multi-object, arbitrary total order，它是一个有关事务的保证，涉及一组操作。它保证了在多个对象上执行的多个事务等同于某个序列化的执行过程。听起来贼绕，可以对应着可串行化理解下。Serializability相当于ACID中的I，如果用户的每一个事务都能保证correctness即ACID中的C，那么顺序执行的事务也能保证correctness。

不同于Linearizability，Serializability本身不给事务的执行顺序加上任何的real-time约束，也就是不需要操作是按照真实时间严格排序的。Serializability 也不是composable的，它也不表示任何的确定性的顺序，它只是要求存在一些等价的执行序列。

Strict Serializability

Serializability + Linearizability = Strict Serializability。此时，这个事务可以被 serial 地执行，并且这个 serial order 是 real time 的。比如我发起一个事务 T1，它会写 x；然后发起另外一个事务 T2，它会读 x。Strict Serializability 要求 T1 一定在 T2 之前，并且 T2 要读 T1 的写。对照来看，如果只是 Serializability 的话，那么 T2 可以在 T1 前面。

实现External Consistency

外部一致性由Spanner引入。

在实现外部一致性时，需要考虑写后读一致性(read-after-write consistency)和单调读一致性。也就是不能写完还读不到，或者读到旧的。由于分布式系统是多副本的，所以实现起来需要进行设计。

考虑一个例子：事务1在节点1写入数据A，事务1完成后，事务B在另一个节点2写入数据B。在这个场景下，A和B并不是并发的。在上面这个过程中，有一个并发事务读取A和B，那么它读取A和B的相对顺序是什么呢？例如如果他读到了B而没有读到A，可以认为外部一致性被破坏了。

为了解决外部一致性要求的顺序问题，一个简单粗暴的办法是所有事务的序列号都通过一个统一的中心节点分配。例如Spanner就使用了原子钟进行授时。为了解决原子钟的误差问题，我们可以在事务提交时，等待误差这么久的余量。

CockroachDB通过逻辑时钟解决物理时钟太过接近，导致难以排序的问题。逻辑时钟的概念，可以参考Lamport时钟。

弱一致性

有的时候系统保证在更新操作后的一段时间后，系统能够达到一致性状态，这称为弱一致性。弱一致性和强一致性的区别是弱一致性存在“不一致窗口”，在不一致窗口中系统不一定保证用户总能看到最新的值。弱一致性可以分为最终一致性、因果一致性、单调读一致性、单调写一致性、有界旧一致性、前缀一致性等。
在Azure Cosmos中将一致性的强弱程度建立以下的关系。Strong–Bounded staleness–Session–Consistent prefix–Eventual。从前向后的延迟。可用性和扩展性越好，但一致性会差一点。

最终一致性

最终一致性也被称为乐观复制(optimistic replication)，是一种获得HA的常见方式，要求当没有新的对X的提交发生时，最终所有对X的访问都返回最后一次更新的值。最终一致性通常用来提供BASE语义。
我们常见的异步复制的主从架构实现的是最终一致性。它的一个典型常见是用户读取异步从库时，可能读取到较旧的信息，因为该从库尚未完全与主库同步。注意，同步复制的主从架构会出现任一节点宕机导致的单点问题。

读己所写一致性

读己所写一致性(read-your-writes consistency)又称为read-after-write consistency，
这里的己，指的是客户端。如下图所示，读己所写一致性要求客户端总能读到自己最新提交的写入。特别地，读己之写一致性不对其他用户的更新做出承诺。

读己所写一致性可以通过以下的一些方式实现：

  1. 当读取可能被修改过的内容时，强制从主库读。
  2. 对于大部分内容都可能被修改的系统来说，以上的方法并不适用，此时可以跟踪上次被更新的时间，并强制在上次更新后的某段时间内强制从主库读取。
  3. 客户端维护最近一次写入的时间戳，系统只从至少拥有该时间戳的修改的从库中进行查询。
  4. 当数据副本分布在多个数据中心时，可能带来额外的复杂性，这里略过，详见DDIA。

会话一致性

会话一致性能够保证在该会话内一致前缀读、单调读、单调写、读己所写、write-follows-reads一致性。

单调读一致性

单调读一致性要求客户端在已经读到某个数据的某个版本之后，不可能在稍后的读中读到该数据先前的某个版本。如下图所示，User2345首先从Follower1读到了55555这个评论，但是在稍后的对Follower2的读中却没有读到，这是因为Follower2此时还没有收到Leader异步复制过来的日志。令User2345读Follower1的时刻为X，则User2345在晚于X的一个时刻读取到了数据早于X时刻的版本，这违背了单调读一致性，即发生了时光倒流的“现象”。
这种时光倒流的原因通常是用户先查询了一个延迟很小的从库，然后又去查询一个延迟很大的从库。

实现单调读一致性的一种方案是确保每个用户从同一个副本进行读取，例如可以Hash用户的ID到不同的节点上。

DDIA指出单调读一致性介于强一致性和最终一致性之间，保证了先前读取到较新的数据的情况下后续不会读到更旧的数据。

一致前缀读

在一致前缀选项中，返回的更新包含所有更新的一些前缀，不带间隔。一致前缀一致性级别保证读取操作永远不会看到无序写入。

相比于单调读，一直前缀读要求如果一系列写入按照某个顺序发生，那么任何人在读取时，也会读到同样的顺序。
【Q】是不是能对应到Causal广播？应该是的
一致前缀读的要求，往往会用在partitioned/shared数据库中。在这样的数据库中，不同分区是独立运行的，所以不存在全局写入顺序。为了解决这个问题，可以强制所有带有因果的写入都在相同的分区上。当然，也可以采用一些显式跟踪因果关系的算法。

有界旧一致性

有界旧一致性(Bounded staleness)保证了读到的数据和最新版本最多差K个版本。

可调一致性

诸如Cassandra的系统在最终一致性的基础上提供了可调一致性。对于任何读写操作，系统允许用户配置成功写操作的最小节点数W、成功读操作的最小节点数R和副本节点的数量N。我们可以根据读写请求的数量来动态调整可用性C和一致性A之间的trade-off。

因果(Causal)一致性

因果一致性(causal consistency)是在ZAB协议中常常见到的一种一致性。因果一致性要求如果A在因果上先于B（在实际场景中可以表现为B依赖A的结果、A先于B发生等），那么A一定先于B被提交。因此，因果一致性实际上是偏序的，如果A和B之间没有先后关系，那么A和B就是可以以任意顺序被提交的。因此，可以看出，因果一致性是比线性一致性要弱的一个一致性，因为线性一致要求全序关系。

在单核单线程上的因果一致就是线性一致，这是因为整个程序是顺序执行的。

因果(Causal)一致性和逻辑时钟

由于在集群中维护以现实为标准的物理时钟的性价比是较低的，而从对因果一致性的讨论中可以看出，节点之间只需要在需要共同访问的时间的先后顺序上达成一致，所以逻辑时钟是描述因果一致性的好工具。逻辑时钟主要是Lamport clocks，以及后来加强了的Vector clock。
Lamport Clock或者Lamport timestamp，定义如下

  1. 在同一进程中，如果a先于b发生，那么C(a) < C(b)
    注意**反过来是不成立的**。一个平凡情况，就是进程p1上面有一个事件a，LC是1。另一个进程p2上面发生了非常多的事件b1..b100，b100的LC是100。两个进程没有任何交互。那么肯定是没有happen before的关系。
    下图中列出了另一个case

    注意，虽然反过来不成立，但是也不会有C(a) < C(b)且b -> a的现象了。
  2. 如果消息M从进程P1发送到进程P2，令P1的发送事件为a，P2的接收事件为b，有C(a) < C(b)
  3. 如果C(a) < C(b)，C(b) < C(c)，则C(a) < C(c)

Lamport Clock实际上描述了happen before关系。

Lamport时钟的算法可以被描述如下。注意Wikipedia与诸如文章1和文章2在表述上有一些冲突，但看下面的图发现说的是一个意思。说法的不同是：

  1. Wikipedia是把事件产生和事件发送拆开来说的，产生一个事件+1，发送不加，收到+1。例如原始状态是0，产生一个事件是1，发出去还是1，收到之后要+1，变成了2。

  2. 另外两篇文章说的是我一个事件产生完就立马发送了，这整个过程中，+了1。

  3. 事件在当前节点发生

    1
    time = time + 1;

  4. 发送事件

    1
    send(message, time);

  5. 接收事件

    1
    2
    (message, time_stamp) = receive();
    time = max(time_stamp, time) + 1;


Lamport Clock得到了偏序关系，但是我们可以从这个偏序关系整理出若干种全序关系（一个常用的方式是按照进程号进行排序），虽然真实发生的是其中的一种情况。在下图中展示了B4这个事件的“光锥”。蓝色部分的是因，红色部分的是果。

总而言之，可以按照下面的办法生成全序关系：定义a -> b为，其中->表示Happen before而不是蕴含关系(implication)：

1
2
Ci (a) < Cj (b)
Ci (a) = Cj (b) and Pi < Pj

其中C表示逻辑时钟，P表示进程号，i/j表示进程，a/b表示进程上的事件。

下面看看为什么a -> b，则C(a) < C(b)：

  1. 如果a和b位于同一个进程内，显然是成立的
  2. 如果a和b位于不同进程i和j中，那么必然在事件a到事件b之间有一次从i到j的通信
    我们不妨把这次通信c->d画出来，其中c可能为a，d可能为b。

    容易发现a/c，c/d，d/b之间都会伴随着Lamport Clock的自增。

通过逻辑时钟，可以解决对共享状态访问的竞态问题了，因为我们可以对所有a -> b这样存在happen before关系的时间赋一个逻辑时间戳了。但诸如节点故障单点问题等问题还需要容错机制来解决。

Lamport时钟的缺点

首先，如果A -> B(happen before)则C(A) < C(B)，但是对Lamport时钟来讲，反之并不成立。
其次，它并不能识别a和b不存在happen before关系的情况。如下图所示，A和B上面的事件是平行发生的。所以他们都发送消息给C后，因为B的逻辑时钟更大，所以A的消息被丢掉了。但这个合理吗？站在上帝视角，我们看到其实A事件的发生在物理时间上是比B要更晚的，如果我们走物理时钟，应该把B的消息丢掉！当然，这种平行时空的问题，本来就是婆说婆有理，公说公有理的，所以这是一个时钟冲突。这样的冲突不好解决，但Lamport Clock并不能识别出这种冲突，这是问题所在。我们希望的是Lamport Clock能够在这种情况下告诉我们时钟冲突了，而不是武断认为B更靠后发生。因此，我们有了Vector Clock。

计算机中的时钟

NTP

在计算机系统中，NTP 协议被普遍用来进行授时。
授时的核心在于计算两个终端之间的 clock drift。计算方式在libutp源码简析这文章中已经介绍过了。这个方案有个很强的假设，就是认为网络是对称的，即 A->B 和 B->A 的时间是对等的。

Lamport Clock

刨去这个假设，我们如何在分布式系统中实现更靠谱的授时呢？其实在分布式系统中，只是需要知道事件发生的全序关系而不是具体的时刻，所以我们自然想到了Lamport时钟。在Lamport时钟中，我们根据发送和接收消息可以确定某些事件之间的偏序关系。剩余的互相处于“平行时空”的事件咋办呢？这个我们根据所处进程号进行排序。这个在之前讲过了，就不再赘述。

Vector Clock(VC)

向量时钟针对 Lamport Clock 做了两点改进：

  1. 提出了 vector clocks ordering，能够识别平行关系
  2. 允许VC(A) < VC(B)则A -> B的反向推理

vector clocks ordering

首先介绍一下vector clocks ordering：

  1. T=T'
    等于关系表示两个向量的每个对应元素都相等。
  2. T<=T'
    ……都小于等于
  3. T<T'
    T<=T'且非T=T'，也就是说只要有一个不等于，那就是小于。
  4. T||T'
    平行关系，既不T<=T'，也不T'<=T

向量时钟的一个作用是发现数据冲突，也就是所谓的 version clock。

规则

假设分布式系统中有 N 个进程，每个进程都有一个本地的向量时间戳 T[i]。它是一个向量，其中 Ti[j] 表示进程 i 知道的进程 j 的本地的向量时钟值。特别地，对于进程 i 来说，Ti[i] 是进程 i 本地的向量时钟值。
向量时钟算法实现如下：

  1. 当进程 i 当有新的事件发生时，自增向量时间戳 Ti[i]。
  2. i 发送消息前需要自增 Ti[i]。也就是认为发送是一个事件。
    可以从下图看到，B 在接收完 C: 1 后产生的是 B: 1 C: 1。
  3. 当进程 i 发送消息时附带自己的向量时间戳 MT=Ti，这是一个向量。
  4. j 接收消息后需要立即自增 Tj[j]。也就是认为接收是一个事件。
  5. 在上一步后，接受消息的进程 j 更新本地的向量时间戳 Tj
    更新方法很简单，zip 一下自己的 Tj，以及来自 i 的 MT 这两个向量，哪个大取哪个。 
    1
    2
    for k = 1 to N:
        Tj[k] = max(Tj[k], MT[k])

应用：判断因果关系

如何使用向量时钟判断两个事件的因果关系呢？不妨先看两个进程比较的情况。在这里把事件的下标放到进程前面，这是为了方便后面推广。
进程 i 和 j 上发生了事件 a 和 b，它们的向量时钟分别为 Ta 和 Tb。Ta[i] 表示进程 i 知道事件 a 时的时间戳。

  1. 如果 Ta[j] < Tb[j]
    1. 如果 Ta[i] > Tb[i] 则 a 和 b 同时发生，记作 a <-> b
      也就是进程 j 上面 a 的时间戳小于 b，但是进程 i 上面 a 大于 b。看上去是个矛盾，这也表明两个事件时同时发生的。
    2. 如果 Ta[i] <= Tb[i] 则 a happens before b，记作 a -> b

推广和证明

上面只是涉及了两个进程，可以推广下，证明对于事件 A 和 B，如果 VC(A) < VC(B) 则 A -> B。

令 VC(A) = [m, n]，VC(B) = [s, t]，由 VC(A) < VC(B) 可以得出：

  1. m <= s。
  2. n <= t。
  3. 两个等号不会同时成立，这是因为收发消息也算事件。

不妨画一张图，Pa 表示事件 A 所在的进程，Pb 表示事件 B 所在的进程。如果说 m < s，那么肯定在不早于 A 和不晚于 B 时，A 往 B 发了消息，也就对应了下图的 [m1, n1] 和 [s1, t1]。不然的话，这个更大的 s 是哪里来的？

大于等于 m 的 s 可能来自如下图所示的4种不同的情况，实际上图只是一个。

能不能只用 Vector Clock 呢？

我觉得是可以的，但这样就是完全依靠通信来同步。通信是不可靠的，如果通信链路上拥塞，或者干脆隔离了，那么系统就不可用了。
此外，对一个 N 节点的集群，每个节点需要维护长度为 N 的向量，并且每次发送消息也得是这个长度。

TrueTime

TrueTime 结合了原子钟和 GPS 时钟，使得误差相比 NTP 的 100ms 级别的误差减少到个位数毫秒的误差。
因此 TrueTime 返回的当前时间 now 会包含 earliest 和 latest 两个值，表示考虑误差下，当前时间最早和最晚可能是什么。

混合时钟

例如，可以在每一秒重置逻辑时钟(是一个integer)为0，然后每一次分配 TSO 都递增逻辑时钟。我们的TSO就是物理时间(秒)+逻辑时钟的值，而对准这1s是容易的。

广播和全序广播

全序广播(total order boardcast)有关一致性的另一个概念。首先，total order即全序关系，是相对于偏序关系(partial order)的一个概念。全序要求在序列中的任何元素都能有确定的先后关系，而偏序则只要求序列中某些元素具有先后关系。整除关系是一个典型的偏序关系。

广播主要分为几个过程，首先是从发送方发出消息的broadcast过程，消息在网络中传播的过程（可能会丢包乱序重复等），以及最后送达接受方的deliver过程。
广播根据broadcast和deliver的顺序可以分为下面几种类型，这些类型是依次增强的，从FIFO开始，对各种乱序的情况进行了规范。

  1. best effort广播
  2. reliable广播
    引入重传
  3. FIFO广播
    如果m1和m2来自同一个node，并且broadcast(m1)->broadcast(m2)（这里箭头表示happen before关系），那么m1也要在m2前面被deliver。
    通俗一点讲，就是从同一个节点broadcast出来的消息的书序和他们被deliver的顺序是一致的，但是对于不同节点出来的，是无所谓顺序的。
    对于下面的图，到C节点的deliver顺序可以是213，123，132。
  4. Causal广播（Causal表示因果的，不要和casual搞混）
    如果broadcast(m1)->broadcast(m2)，那么m1也要在m2前面被deliver。
    看起来，只是比FIFO广播少了“在同一个node上的条件”而已，实际差别是什么呢？其实在后面的文章中定义了happen before，照着happen before的三种情况，就容易理解了。这里多了的就是A发消息，B收消息这种跨node的happen before关系。
    对于下面的图，如果broadcast(m1)->broadcast(m2)且broadcast(m1)->broadcast(m3)，那么合法的deliver顺序是123和132。
  5. Total Order广播
    如果在一个node上，m1在m2前面被deliver，那么在所有node上，m1都在m2前面被deliver。
    既可以像下面的图一样，所有节点都按照123的顺序deliver。这里需要看到来自node A的请求m3，必须要delay到来自node B的请求m2被deliver之后才能deliver，即使这个请求是自己发给自己的。

    当然了，所有节点也可以按照132的顺序来deliver。
  6. FIFO Total Order广播
    就是FIFO和 Total Order的结合。

各类广播的实现

reliable

一个naive的想法是重传，同时处理重复包（例如可以通过编号的方式）。但如果在重传前传播的节点就宕掉了，那么reliable就无法保证。
一个简单的修复，就是每个节点在第一次收到消息之后，往其他节点转发一下消息。但这个行为会导致为了广播每一条消息，整个集群中总共发送$O(n^2)$个消息。
Gossip协议是对上述的一个优化。每个节点在第一次收到消息之后，会随机发送给fanout个节点（例如随机发给3个节点），有点像流行病毒传播一样。Gossip协议能以很高的概率实现reliable。

FIFO

对于每一个node，维护下面几个变量：

  1. i
    表示发送方node的编号
  2. seq
    每个节点维护自己broadcast的信息的序号
  3. delivered[j]
    是一个数组，表示对于node j，我们总共deliver了几个序号
  4. buffer
    用来存放尚未准备好deliver的信息

发送方发送信息m，格式是(i,seq,m)。在发送后，需要自增seq。
接收方在接收来自i的信息后，先放到buffer中。接着在buffer中寻找seq等于delivered[i]的信息，如果存在，就deliver，并且自增delivered[i]。
这个方案实际上就是说接收方给每个发送方维护一个队列，通过这个队列保证自己收到来自i连续递增seq的信息。

Causal

对于发送方，需要复制自己的delivered数组为dep数组，设置dep[i]为seq。发送方发送(i,deps,m)。在发送后，需要自增seq。
接收方在收到某个消息(i,deps,m)之后，需要满足deps<=delivered条件之后，才能deliver这条信息。不过这个涉及到了比较两个数组，其规则就是之前提到的vector clocks ordering。

Total Order

通常有两种方式：

  1. 借助Leader
    如果需要广播信息，则发送给Leader。Leader按照FIFO的方式广播信息。
    这种方式需要解决Leader可能存在的单点问题。
  2. 借助于Lamport timestamp
    对每个消息加上Lamport时间戳，并且按照Lamport时间戳deliver消息。
    这种方式的问题是如何判断自己已经收到了所有timestamp小于T的所有消息。这需要使用FIFO连接，并且等到所有node上大于等于T的信息。

实现全序广播等价于实现线性一致的存储。

可用性

可用性即reads and writes always succeed。这个要求系统能够始终在正常时间内对用户的请求进行响应。当然由于可能出现的一致性问题，这个响应不一定是正确的。

分区容错性

分区容错性即the system continues to operate despite arbitrary message loss or failure of part of the system。由于分布式集群中常出现网络分区情况，即集群中的一部分机器与另一部分机器中断连接，这可能是由于网络故障，产生网络分区；也可能是由于某些节点宕机。网络分区可能产生的一个后果是脑裂(split brain)，也就是存在多个节点认为自己是领导者。

我们除非设计出一个永远不会出故障的网络，否则必须要容忍 P。于是 C 和 A 便成为了 trade-off。由于网络分区的概率比较小，并且是易于探测的，所以 C 和 A 大多数情况是能够比较好地满足的.所以要做的不是根除网络分区及其导致的部分失效(partial failure)问题，而是去正确地处理它，这就引入了诸如2PC、RWN、Paxos等协议。

分布式共识

本章将原先分布式一致性和分布式共识协议中一些理论性较强的部分单独讲解。

分布式共识的特性

我们需要区分分布式共识和分布式事务。分布式共识被用来解决分布式系统上出现的一致性问题。共识协议能够让一个集群的行为如同一个单机节点一样，即使其中有一小部分的节点宕机或分区。
具体地讲，一个正确的分布式共识算法应当满足以下三个特性：

  1. agreement
    决议需要得到所有节点的认同，通常是首先批准一个多数票的决议，然后进行同步。
  2. validity
    决议的值需要满足合法性要求。
  3. termination(liveness)
    决议过程能够在有限步内结束，并产生结果。

以上的三个特性可以总结成两点，safety 和 liveness：

  1. safety 要求系统不会产生一个错误的值
    以分布式事务为例，safety 要求一个进程提交则全体进程提交，一个进程回滚则全部进程回滚
  2. liveness 要求系统不至于陷入阻塞。
    以分布式事务为例，liveness 要求如果没有故障，并且可提交则立即提交；如果有故障则立即回滚。

其实在写 TLA+ 验证一些系统的实现时，很多 Invariant 就是围绕 safety 和 liveness 来写的。

FLP定理

论文Impossibility of Distributed Consensus with One Faulty Process证明了在异步系统中，哪怕只允许非拜占庭错误，只要有一个进程出错，那么系统就不一定能达成共识，也就是不满足 termination 要求。而在同步系统中，即使是拜占庭条件下却能够达成。

定义一个异步系统

首先，FLP 定义了一个异步系统，它应该满足如下的特点：

  1. 非拜占庭的 Fail-stop 模型
  2. 最多一个进程失败
  3. 可靠通信、原子广播
    即通信最终会被送达，且仅被送达一次。但是消息可任意延迟、可乱序。例如基于 TCP 的通信并不满足这个条件，因为 TCP 承载的消息是不可以乱序的。
  4. 异步通信
    没有时钟、不能时间同步、不能使用超时。
    此外，进程之间还不能探测失败，因为无法判定一个异步进程到底是宕机了还是只是算得太慢。

系统中包含一系列进程，进程之间通过全局消息队列，称为 message buffer 进行通信。例如进程 p1 可以用 send(p2, m) 向进程 p2 发送消息 m，进程 p2 通过持续不断 receive(p2) 来获取自己的消息，并 event(p2, m) 来执行这个消息。以上的过程称为一个 step，一系列连续的 step 组成一个 run。

如果一个进程 p 在一个 run 中能运行无数个 step，那么它是非故障的。

定义一个 configuration 为当前所有进程和 message buffer 的状态，也就是整个系统的状态。那么一个 step 就会使得系统从一个 configuration 到达另一个 configuration。当然，在上面的例子中，如果 p2 由于分区等原因接受不到消息，这时候就表示为 m 为 NULL，即 evnet(p2, NULL)。

一个 initial configuration 指的是所有进程从某个初始状态启动，并且 message buffer 为空。

这里的 p 可以看做 deterministic 的 transition function。这意味着每个进程后续进入什么状态，完全取决于它从 message buffer 中取到什么消息。

假定所有进程试图达成一个 {0, 1} 的某个值上达成一个决议，并输出到寄存器 yp。yp 的值为 {b, 0, 1}，其中 b 表示未产生表决结果的初始状态。一旦 yp 从 b 变为 0 或 1，这个值就不再可以被修改。这些进程可以从各自的寄存器 xp 中读取初始值，这些初始值是 {0, 1}。

C 上的一个 schedule 是有限或无限的序列 σ。如果它是有限的，由它产生的一系列 run 得到的新的 configuration 称为从 C reachable。定义能从初始 configuration 到达的 configuration 是 accessible 的。

某个 configuration C 能 reachable 的所有 configuration 中的 decision value 的集合是 V。可以说这个 configuration 是 v-valent 的。如果 V 中只有一个元素，那么就是 univalent。根据这个元素是什么，可以分为 0-valent 和 1-valent。如果 V 中有两个元素，就是 bivalent。

这里补充一下，如果一个 C 的初始值中包含 1，那么它有可能是 0-valent，也可能是 1-valent。如果初始值只包含1，那么就不可能是 0-valent。

我们期望所有的正常进程最终都能达成正确的决议，但实际上 FLP 定理的证明中构造了一种情况，即使某些进程能够最终进入 univalent 的这一点都无法保证。

一个共识算法是部分正确的，当

  1. 所有 accessible 的 configuration 都有相同的决定值。
  2. 所有 accessible 的 configuration 里面不能只有 0 或者 1，不然这样我搞一个系统永远输出 0，那不是永远部分正确了么？不考虑这样的平凡解。

定义一个共识算法是完全正确的，当它是部分正确的，此外还能满足终止条件。

整个的 FLP 定理的证明分为三个引理。

第一个引理

第一个引理很直观，把进程分为两个不相交集合 P1 和 P2，往 P1 和 P2 分别发送 R1 和 R2，那么 R1 和 R2 的提交顺序不影响最终结果。这个对 Lamport 时钟有了解的都能够想明白。

第二三引理类似于归纳法。先证明任意共识算法 P 都不能保证 initial configuration 都是 univalent。然后证明从 bivalent 能得到 bivalent。

第二个引理

定义一个 run 是 admissible 的，如果最多一个进程故障了，并且所有其他非故障的进程都收到了所有的消息。
第二引理证明了在有一个进程失败的系统中，对于任意的共识算法 P，一定存在一个 bivalent initial configuration。这就是在说这样的系统中，同样的 initial configuration 可能运行出不同的结果。

证明用到了构建相邻环的思路，用大白话讲一下就是反证法假设系统从某个 univalent 开始，根据部分正确的条件2，要求有两个 configuration 为 C0 和 C1 分别是 0/1-valent 的。论文中指出，必然存在 decision value 为 0 的系统 C0 和为 1 的系统 C1 只差一个进程 p 。

例如三个进程的初始状态 xp = {1, 1, 0} 和 xp = {1, 0, 0} 就只差一个 p2。然后假设通过某个 Quorum 的共识算法，前者是 1-valent，后者是 0-valent。当然这里也可以用其他的算法让前者 0-valent，后者 1-valent，虽然这样很反直觉，但其目的主要是说明这样的 p2 是存在的。

现在假设 p2 故障了，也就是它不能运行哪怕一个 step，或者说不能 send 或者 receive 任何消息了。这样 C0 和 C1 在排除掉这个 p2 之后其实是一样的。

然后尝试以 C0 或 C1 为 initial configuration 来进行 admissible deciding run。那么 C0 和 C1 必然会进入同一个值，假如令它为 1，那么 C0 这个原本 0-valent 的 configuration 中的 decision value 就是 {0, 1} 了。这样 C0 就不是 univalent 的了，从而推出矛盾。

总而言之，第二个引理描述了对于任意的共识算法 P，一定存在 0-valent 的 configuration 和 1-valent 的 configuration 只差一个进程，令这个进程故障，那么就会得到一个 bivalent。所以对于 P，只要考虑一个故障节点，它就不能保证 initial configuration 都是 0-valent 和 1-valent 的。

第三个引理

第三个引理承接了第二个引理。它证明了从一个不确定的状态开始，也会得到不确定的状态。也就是说，在某种情况下，如果 C 是 bivalent 的，那么从它可达的 D 也是 bivalent 的。

首先定义事件 e=(p,m)，可以分出：

  1. 集合1：不应用 e 可达的 configuration 的集合 E。
  2. 集合2：对 E 中的 configuration 应用 e 可达的 configuration 的集合 D。

因为 e 能应用到 C，并且可以被任意延迟，所以它肯定也能应用到 E。

现在同样使用反证法，假设 D 中不含有 bivalent 的 configuration，Ei 是从 Ci 可以 reachable 的某个 i-valent 的 configuration。由于 Ci 是 bivalent 的，所以 i 能够取 0 或 1。现在讨论 Ei：

  1. 如果 Ei 属于 E，那么对它应用 e 得到 Fi，则根据集合2 的特性，Fi 肯定就属于 D 了。
  2. 如果 Ei 不属于 E，说明 Ei 已经在之前收到过消息 e 了，那么它会先到达一个同样属于 D 的配置 Fi，然后再到达 Ei。

总而言之，无论走那条路，得到的 Fi 的 configuration 都是落在集合 D 中的。

那既然开始的集合 C 是 bivalent 的，最后又都会落到同一个集合中，那么 D 中肯定既有 0-valent 又有 1-valent 的 configuration，到这里为止和假设还是不矛盾的。

定义两个 configuration 相邻，如果第一个 configuration 可以通过一个 step 得到另一个。

可以认为，E 中一定存在相邻的两个 C0 和 C1，对于这两个 Ci，D0=e(C0) 是 0-valent，D1=e(C1)是 1-valent 的。不失一般性地，设 C1=e'(C0)，其中 e'=(p', m')，当然反过来假设也可以。

我们可以得到一个如下图中实线所表示的有向图，但是否有虚线所示的关系是不确定的，所以要展开讨论

  1. 如果 p 不等 p'，可以将它们划分到两个不相交集合中。所以根据引理1，可以得到 D1=e'(D0) （上图中的虚线）。那么这也就意味着从一个 0-valent 的节点到达一个 1-valent 的节点，而这是不可能的，因为 0-valent 的后继只能是 0-valent 的。
  2. 那么 p 等于 p' 了，也就是说从 C0 到 D0 和从 C0 到 C1 都源于同一个节点进行的 step。那将这个进程独立出来，假定它宕掉了。那么从 C0 就能通过 σ 到达一个 A 状态。看图的左半部分，假设对于这个 A 状态应用 e，可以到达 E0，那么根据引理1，对 D0 应用 σ 得到 E0。同理，可以构造右边的一个 E1，从而发现 A 既可以变到 E0 又可以变到 E1 ，它是 bivalent 的，与假设矛盾。

FLP 定理

拜占庭将军问题

拜占庭将军问题指在一个有 N 个节点的集群内部，有 F 个节点可能发生任意错误的情况下，如果 N <= 3F ，一个正确的共识不可能达成。这里的任意错误包括节点前后的行为不一致，例如在投票时投给两个不同的节点。

诸如 Paxos 之类的算法只能对节点宕机进行容错，而不能对节点的拜占庭故障进行容错。这类基于复制状态机实现的协议，需要N >= 2F + 1才能确保共识的达成。

实用拜占庭容错算法(Pratical Byzantine Fault Tolerance, PBFT)是一种多项式复杂度的状态机复制算法。

CAP 定理

CAP 理论认为一致性(consistency)、可用性(availability)和分区容错性(partition tolerance)是不可能同时被满足的。

CAP 论文中讨论了四种一致性：

  1. Trivial services
    这种服务不需要在节点间协调，因此不是论文的讨论对象
  2. Weakly consistent services
  3. Simple services
    这是论文关注的主要对象。这个一致性主要包含两点：
    1. sequential
    2. atomic
  4. Complicated services

这里的证明大概可以理解为，一致性要求当某个节点返回给客户端某个值之后，所有节点不能返回给客户端更旧的值。但如果发生了分区故障，写入节点就无法将新的数据发送给所有节点了。而可用性又要求任何一个节点不能拒绝客户端的请求，这就逼迫被分区的节点必须要返回一个更旧的值。

如果将这里的Consistency 替换为 Consensus（实际上两者说的不是一个东西），那么根据 FLP 定理，异步系统上无法保证 CA，所以只能选择 CP 和 AP。比如 Paxos、Raft 等系统实际上都是有 Liveness 问题的。这很能理解，例如 Raft 可能无限在选主过程中徘徊。

但在工程上，CAP 是可以被优化的，例如：

  1. 可以引入一些同步机制，当一个节点与其他节点分区达到超时时间后，就会去声明自己宕掉了。
  2. 使用像 Redis Sentinel 一样的机制，使用另外一套班子来检测集群的状态。

Reference

  1. http://yang.observer/2020/07/11/time-ntp/
    介绍计算机中的时钟
  2. Time, Clocks, and the Ordering of Events in a Distributed System
    Lamport的有关分布式时钟的论文
  3. https://zhuanlan.zhihu.com/p/56886156
    对向量时钟的一个讲解
  4. https://writings.sh/post/logical-clocks
    同样是对逻辑时钟的讲解，我这边摘录了他的几幅图
  5. https://www.raychase.net/5768
    用了其中的图和某个case
  6. http://gaocegege.com/Blog/%E9%9A%8F%E7%AC%94/consistency
    论述了Linearizability和Serializability的区别。即“Linearizability 要求操作生效的顺序等于实际的实时操作排序。Serializability 允许操作被重新排序，只要在每个节点上观察到的顺序保持一致。作为用户, 能区分两者的唯一方法是，观察系统的所有输入和时间. 从客户端与节点交互的角度来看，两者是等价的”
  7. Perspectives on the CAP Theorem
    CAP 定理的论文
  8. Impossibility of distributed consensus with one faulty process
    FLP 定理的论文