一致性杂谈

什么是一致性?

在谈到一致性这个词时,你会想到CAP理论的 consistency,或者 ACID 中的 consistency,或者 cache 一致性协议的 coherence,还是 Raft/Paxos 中的 consensus?

一致性大概是分布式系统中最容易造成困惑的概念之一,因为它已经被用烂了。在很多中文文献中,都将consistency,coherence,consensus 三个单词统一翻译为”一致性”。因此在谈一致性之前,我认为有必要对这几个概念做一个区分:

Consensus

更准确的翻译是共识,关注的是多个提议者达成共识的过程。比如 Paxos,Raft 共识算法本质上解决的是如何在分布式系统下保证所有节点对某个结果达成共识,其中需要考虑节点宕机,网络时延,网络分区等分布式中各种问题。共识算法通常应用在复制状态机中,比如 etcd,zookeeper,用于构建高可用容错系统。在这种应用情景下,Raft/Paxos 共识算法被用来确保各个复制状态机(节点)的日志是一致的。类似的,区块链中非常重要的一部分也是共识算法,但通常使用是 POW(Proof of Work) 或 POS(Proof of Stake),这类共识算法通常适合用在公网,去中心化的情形下。

Coherence

Coherence 通只出现在 Cache Coherence 一词中,作为”缓存一致性”被提出。我们知道现代的多核 CPU Cache 都是多层结构,通常每个 CPU Core 都有一个私有的 LB/SB, L1, L2 级 Cache,多个 CPU Core 共享一个 L3 Cache。比如 CPU1 修改了全局变量 g 并写入了 CPU1 L1 Cache,此时 CPU2 要读取变量 g,然而 CPU2 L1 Cache 中的 g 仍然是旧值,这里就需要 Cache Coherence (以下简称 CC)机制来保证 CPU2 读取到的一定是 g 的最新值。因此,CC 的本质是让多组 Cache 看起来就像一组 Cache 一样。现代 CPU 都已经实现了 CC,通常程序员也不需要关心 CC 的具体实现策略,目前大部分 CPU 采用的是基于 MESI(Modified-Shared-Invalid-Exclusive) 协议的 CC,这里有一篇参考文章

解释完了Consensus 和 Coherence,剩下 ACID 和 CAP,两者的 C 都叫做 Consistency,你可能以为这两者应该就是我们常提到的分布式中的一致性了吧。其实并不是,两者也是完全不同的概念。

ACID Consistency

ACID 中的一致性是指数据库的一致性约束,ACID 一致性完全与数据库规则相关,包括约束,级联,触发器等。在事务开始之前和事务结束以后,都必须遵守这些不变量,保证数据库的完整性不被破坏,因此 ACID 中的 C 表示数据库执行事务前后状态的一致性,防止非法事务导致数据库被破坏。比如银行系统 A 和 B 两个账户的余额总和为 100,那么无论 A, B 之间怎么转换,这个余额和是不变,前后一致的。

CAP Consistency

CAP 理论中的 C 也就是我们常说的分布式系统中的一致性,更确切地说,指的是分布式一致性中的一种: 线性一致性(Linearizability),也叫做原子一致性(Atomic consistency)。

谈到 CAP,和一致性一样,CAP 理论也是个被滥用的词汇,关于 CAP 的正确定义可参考cap faq。很多时候我们会用 CAP 模型去评估一个分布式系统,但这篇文章会告诉你 CAP 理论的局限性,因为按照 CAP 理论,很多系统包括 MongoDB,ZooKeeper 既不满足一致性(线性一致性),也不满足可用性(任意一个工作中的节点都要可以处理请求),但这并不意味着它们不是优秀的系统,而是 CAP 定理本身的局限性(没有考虑处理延迟,容错等)。这里不再展开,有兴趣的同学可以去读读该文。

正因为 CAP 中的一致性和可用性是强一致性和高可用,后来又有人基于 CAP 理论 提出了BASE 理论,即基本可用(Basically Available)、软状态(Soft State)、最终一致性(Eventual Consistency)。BASE的核心思想是即使无法做到强一致性,但每个应用都可以根据自身的业务特点,采用适当的方法来使系统达到最终一致性。显然,最终一致性弱于 CAP 中的 线性一致性。很多分布式系统都是基于 BASE 中的”基本可用”和”最终一致性”来实现的,比如 MySQL/PostgreSQL Replication 异步复制。

分布式一致性模型

在分布式共享内存系统或者分布式数据存储中,数据一致性模型指定程序员和系统之间的契约,系统保证如果程序员遵守规则,则存储器将是一致的,并且读取,写入或更新存储器的结果将是可预测的。我们最常用于讨论的便是复制状态机(Replicated state machines)的一致性问题,比如 etcd, zookeeper,当进程 A 执行 set x 3 时,进程 B 是否能在 A 执行完成后立即读到 x 的新值。这个问题在单节点上是显而易见的,但在分布式中,对进程 来说,则需要通过一致性模型来确保server 给出的结果可预测。分布式系统中的一致性有强弱之分,如线性一致性,最终一致性等。理想情况下,最强的一致是,当进程 写入 replicate 中的某个节点,其改变会被立即同步到集群其它节点,其它进程 能立即读取到该值。比较弱的一种一致性是最终一致性,也就是操作完成之后的某段时间内可能各个节点的数据副本不一致(导致不同进程 访问到的数据会不一致),但最终会是一致的。比如 DNS 服务。

因此,当别人在谈到”一致性”时,可能需要花些时间来确认他究竟在说什么,有可能你们所谈论的不是一个东西。本文主要讨论的是分布式中的一致性。

分布式一致性基本概念

要理解分布式一致性,先来谈谈分布式中几个必要的概念: 时间,事件,和顺序。

分布式系统的时间主要分为物理时间和逻辑时间两种,物理时间是指程序能够直接获取到的 OS 时间,在分布式系统中,由于光速有限,你永远无法同步两台计算机的时间。想要在分布式中仅依靠物理时间来决定事件的客观先后顺序是不可能的。因此分布式系统中,通常使用逻辑时间来处理事件的先后关系。

分布式中的事件不是瞬间的概念,它有一个起始和结束时间,因此不同进程 发起的事件可能发生重叠,对于发生重叠的事件,我们说它们是并发执行的,在物理时间上是不分先后的。

理想情况下,我们希望整个分布式系统中的所有事件都有先后顺序,这种顺序就是全序,即整个事件集合中任意两个事件都有先后顺序。但 1.物理时间是很难同步的,2. 网络是异步的,因此在分布式系统中,想要维持全序是非常困难的。不同的节点对两个事件谁先发生可能具有不同的看法,并且大部分时候我只需要知道偏序关系,用于确保因果关系。所谓偏序关系是指:

  1. 如果a和b是同一个进程中的事件,并且a在b前面发生,那么 a->b
  2. 如果a代表了某个进程的消息发送事件,b代表另一进程中针对这同一个消息的接收事件,那么a->b
  3. 如果 a->b且b->c,那么a->c (传递性)

逻辑时间中的 Lamport Clock和Vector Clock等都可以用于建立偏序关系。

顺序一致性(Sequential Consistency)

Leslie Lamport 在1979年提出了Sequential Consistency, Leslie Lamport的定义如下:

A multiprocessor is said to be sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program.[How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs by Leslie Lamport ,1979]

这个定义比较晦涩,通常来讲,他可以分为两个部分:

  1. 单个节点的事件历史在全局历史上看符合程序顺序
  2. 事件历史在各个节点上看全局一致

约束1保证了单个节点的所有事件是按照程序中指定的顺序执行的,约束2保证了所有的事件是原子的,不会相互干扰。更通俗的理解是,将整个分布式系统想象成一个调度器,将多个进程 的请求看做是多个FIFO请求队列, 调度器依次处理队列中的请求,并在多个队列中不断切换。是的,这和Go调度器原理类似,只不过我们探讨一致性模型时,会将系统规约为一个黑盒,从进程 的角度来看这个黑盒对外表现出的一致性强弱。

下面举个例子来加深理解,假设我们有个分布式 KV 系统,以下是四个进程 对其的操作顺序和结果:

1
2
3
4
A: --W(x,1)--
B: --W(x,2)--
C: -R(x,1)- --R(x,2)-
D: -R(x,1)- --R(x,2)--

其中W(x,1)表示更新 x 的值为1,R(x,1)表示读出 x 的值为2,横向为物理时间,事件两边的’-‘代表事件持续时间,那么按照我们前面对顺序一致性的描述,显然这个 KV 系统是满足顺序一致性的。

如果我们将进程 C 和 D 的 R(x,1)R(x,2) 对换一下,也就是如果 C 和 D 都是先读出 x 为 2,再读出 x 为 1,那么还满足顺序一致性么,答案是肯定的,因为仍然能够找出一个全局的执行顺序: B W(x,2) -> A W(x,1) -> C R(x,2) -> D R(x,2) -> C R(x,1) -> D R(x,1),这个顺序满足前面提到的两点约束,即使直观上看来,这是”错误的一致性”。

如果我们只是把进程 D 的两个 R 操作对换,那么我们说这个系统是不满足顺序一致性的,因为你无法找出一个全局顺序满足以上两点约束。同样,如果 W(x,1)W(x,2) 都发生在进程 A 中,那么系统也不满足顺序一致性。

线性一致性(Linearizability)

也叫做strong consistency或者atomic consistency,于 1987年提出,线性一致性强于顺序一致性,是程序能实现的最高的一致性模型,也是分布式系统用户最期望的一致性。 与顺序一致性相比,线性一致性只多了一条约束:如果事件A开始时间晚于事件B结束时间,则在最终事件历史中,要求B在A前。或者换句话说:事件生效时间是在事件开始时间到结束事件之间的某个时刻。 举个例子:

1
2
3
4
A: --W(x,1)--
B: ---W(x,2)---
C: --R(x,2)-- -R(x,1)-
D: --R(x,1)-

这个案例是满足线性一致性的,因为W(x,1)W(x,2)两个事件是同时发生的,因此事件生效点可能出现在开始和结束之间的任意点,就这个例子来讲,全局事件历史为: B-W(x, 2), C-R(x,2), A-W(x,1), D-R(x,1), C-R(x,1),其中D-R(x,1), C-R(x,1)可以对换。

如果将 D 的 R(x,1)改为 R(x,2),则不满足线性一致性,因为 C 的 R(x,1) 和 D 的 R(x,2)都发生在 A, B 的 W 事件之后,因此它们应该对 x 的值结果具有相同的视角,不会读出不一致的结果。

如果说顺序一致性只保证单节点事件先后顺序的话,线性一致性还保证节点间的事件先后顺序,因此线性一致性的实现是非常困难的,一方面它需要一个全局同步的时钟(顺序一致性不需要全局同步的时钟),另一方面,越严格的一致性,会让分布式系统的复杂度更高,并且与之对应的,性能也会更差。

除了线性一致性和顺序一致性外,还一些其它更弱的一致性模型,比如因果一致性,最终一致性等,这里不再赘述。理解一致性本身和一些基础概念之后,理解其它一致性都不难。

内存一致性模型

在前面我将顺序一致性简单描述为调度器模型,这可能会让你想到操作系统的进程/线程调度,在进程/线程的视角下,多路 CPU 本身不就是个”微型分布式系统”么。是的,不过多核体系是早于分布式的,因此它的一致性模型叫做内存一致性模型。那问题来了,现代多核体系的内存一致性模型满足顺序一致性么?再来看个例子:

初始状态下,x = 0, y = 0

进程 A 进程 B
x=1 y=1
r1=y r2=x

按照顺序一致性的定义,我们将四条指令交叉任意排列,最终可能得到三种结果: r1==1,r2==0,r1==0,r2=1, r1=1,r2=1 三种结果,但不可能得到 r1=0,r2=0 的结果,因为这意味着全局执行顺序为 r1=y, r2=x, x=1, y=1,并不符合单个进程内部的执行顺序。那么实际上,这段程序会输出r1=0,r2=0的结果么?答案是会的,原因如下:

  1. 编译器指令重排,编译器会在不影响程序语义的情况下,调整代码中的指令顺序。但编译器只能够解析显示语义,即单线程上下文,它无法(或者说非常难)解析程序的隐式语义,即程序的多线程上下文依赖。
  2. CPU指令乱序执行,由于内存读取非常慢,CPU在不影响单线程语义的情况下,会将数据提前加载到缓存,提高执行效率。这就可能造成CPU指令处理顺序和程序指令顺序不一致,由于CPU 乱序只保证单线程语义,因此同样无法解析程序逻辑隐私因果关系,也可能造成结果不符程序预期。
  3. 缓存一致性,由于 LB/SB 的存在,缓存一致性是有极短延迟的,可能某个共享数据被CPU更新并写入到 SB(Store Buffer)中,其它 CPU 并不能即时看到。

基于以上三点,现代 CPU 架构基本都是不支持顺序一致性的,因为其需要非常高昂的代价,严重限制编译器和硬件的优化能力。比如顺序一致性要求处理器按照程序序(program order)来执行程序,但在大部分情况下,这是没必要的。因此,现代硬件体系遵循的其实是: sequential consistency for data race free programs,即对没有 data race 的程序来说,是满足顺序一致性的(编译器能够分析上下文相关性),但如果涉及到 data race,程序员需要使用 compile barrier 和 memory barrier 来限制编译器和 CPU 的乱序能力,以保证多线程下顺序一致性。这方面推荐一些优秀的文章:

  1. 为什么程序员需要关心顺序一致性而不是Cache一致性?
  2. 浅谈Memory Reordering
  3. 聊聊原子变量、锁、内存屏障那点事

最后

一致性模型的局限性

一致性模型是被简化过的模型,它将整个分布式系统简化为single-object(如 k-v store, queue),single-op(如 Read/Write, Enqueue/Dequeue),因此有些东西是它没有讨论到的:

  1. single-object: 分布式系统有多个节点,不同的节点可能提供的一致性并不相同,比如连 master 节点可能满足线性一致性,而 slave 节点则不是。
  2. single-op: 前面的例子中,我们简单将事件当做原子性的操作,而在实践中,往往需要事务(2PC, 3PC)来保证整个分布式系统的内部一致性,这个内部一致性和我们前面讨论的外部一致性是有区别的。同样,事务,串行化这些东西和一致性模型也是不同的东西。

因此一些分布式系统在不同的配置选项或不同的连接状态下,可能体现出不同的一致性。

微观 vs 宏观

在理解顺序一致性的时候,我引入了内存一致性模型,这其实是一个很大的课题,寥寥几句不可能交代清楚。我之所以要放到这里, 是因为两者可以相互启发,分布式设计中很多难题都可以从计算机体系结构中借鉴,比如分布式 Cache 同步 和 CPU Cache 同步,或者内存一致性和分布式一致性。计算机体系结构就是一本历史书,里面包含很多经验教训和千锤百炼的最佳实践,如果能够将其抽象泛化,应用到实际问题中,将是非常宝贵的。比如你要设计一个安全的消息加密,那么 https 会让你少走很多弯路,如果你要实现微服务间的流量控制,tcp 拥塞控制算法会给你很多启发,等等。学底层知识,可能最终学的就是这些”套路”。