1. 一致性概念
分布式系统通常由异步网络连接的多个节点构成，每个节点有独立的计算和存储，节点之间通过网络通信进行协作。分布式一致性指多个节点对某一变量的取值达成一致，一旦达成一致，则变量的本次取值即被确定[12]。
在分布式存储系统中，通常以多副本冗余的方式实现数据的可靠存储。同一份数据的多个副本必须保证一致，而数据的多个副本又存储在不同的节点中，这里的分布式一致性问题就是存储在不同节点中的数据副本（或称为变量）的取值必须一致。不仅如此，因为变量是可变的，变量会有多次取值，变量的多次取值构成一个序列，分布式一致性还要求多个节点对该变量的取值序列必须一致。
在大量客户端并发请求读/写的情况下，维护数据多副本的一致性无疑非常重要，且富有挑战。作为分布式一致性系列文章的第一篇，本文主要介绍相关基础理论，后续篇章将重点介绍Paxos、Raft、ZAB等有着广泛应用的一致性协议。
2. 时间、事件和顺序
一致性问题隐含了一个非常重要的要素：时间。比如多副本一致性在考虑时间要素后可描述为：在某一个时间点，多个节点上看到的数据副本其取值必须达成一致。数据取值（或称为变量取值）通常由某个事件（如客户端的写请求）先行触发，之后因节点之间消息延时之长短差异，先后将数据取值依次更新到分布式系统中的多个节点。
分布式系统中时间、事件、顺序等概念在Leslie Lamport于1978年发表的论文“Time Clocks and the Ordering of Events in a Distributed System”中有系统性论述。Lamport自述其灵感源于以狭义相对论的角度从事物本质上去理解分布式系统中使用消息时间戳来表述事件的全序关系。狭义相对论告诉我们时空中的事件不存在一个始终如一的全序关系，事件之间的先后关系完全取决于事件间的因果关系（即事件2是由事件1引起的），希望通过时间戳来描述事件的全序关系本质上与事件间因果关系是一致的。文中，Lamport提出了逻辑时钟（logical clock）的概念，并给出定义事件全序关系的算法，Lamport声称基于这样的算法可以实现任意的分布式系统。
分布式系统中，事件之间的顺序至关重要。举例说，假设分布式存储系统由三个节点s1、s2和s3构成，现有两个客户端c1和c2，客户端c1首先发起写请求x=v1希望将变量x的值从v0更新为v1，紧接着c2发起请求读取变量x的值。变量x在节点s1、s2、s3上都有副本，c2可能从任意节点读取x的值。考虑到网络延时的影响，c2的读请求消息可能先于c1的写请求到达节点s3，如果没有全局的顺序控制，c2就有可能读到变量x的旧值，这显然是不希望看到的。
3. 基础理论
ACID、CAP和BASE等理论是探讨分布式环境下一致性相关问题的基础。
3.1 ACID
ACID是数据库（DBMS）事务正确执行所必须满足的四个特性的首字母缩写。
Atomicity（原子性）：一个事务的所有操作，要么全部完成，要么全部不完成。所谓事务，是指由一系列数据操作所组成的完整逻辑过程。比如银行转账事务由两个操作组成：从源账户扣除金额，以及向目标账户增加金额。
Consistency（一致性）：指事务开始之前和事务结束之后，数据的完整性约束没有被破坏。包含两层含义：a)数据库机制层面，事务执行前后，数据能符合设置的约束，如唯一约束、外键约束；b)业务层面，由应用开发人员保证业务一致性。还是以银行转账为例，A、B两个账号，转账之前和之后，A、B两个账号余额总额必须一致。
Isolation（隔离性）：数据库能够防止由于多个并发事务交叉执行而导致数据的不一致。
Durability（持久性）：指事务结束后，对数据的修改是永久的，不会回滚到之前的状态。
3.2 BASE
Eric Brewer和他在Inktomi公司的同事于1988年提出BASE设计理念，其初衷是为了抓住当时逐渐出现的一些针对高可用性的设计思路。BASE缩写定义如下：
● BasicallyAvailable：基本可用
● Soft State：软状态
● Eventual consistent：最终一致性
其中Soft State和Eventual
consistent两种策略主要用于解决网络分区引起的问题，从而提高系统可用性。Soft State是服务端状态设计的一种策略，介于stateful和stateless之间，服务端无状态（stateless）设计可简化网络通信正常之后的分区恢复过程，更多描述可参考REST[8]。对Eventually consistent的理解可参考3.5小节。
Brewer在2000年PODC（Principles Of Distributed Computing）大会所做“Towards Robust Distributed Systems”主题演讲，其中就有BASE和ACID做了比较，如下：
BASE和ACID代表两种截然相反的设计理念，ACID注重一致性，是传统关系型数据库的设计思路，BASE关注高可用性。当今大规模、跨数据中心的分布式系统（如云计算）大多同时采用这两种设计理念，并在两者之间寻求平衡。
3.3 CAP
3.3.1 CAP基本概念
BASE理念在提出之初还不怎么被人们接受，主要是大家看到ACID的优点而不愿意放弃。为了证明有必要开阔设计思路，Brewer于1998年秋季提出更为系统的CAP理论，次年正式发表[6]，并于2000年在PODC大会上做主题演讲[7]。
CAP理论主张基于网络的数据共享系统，都最多只能拥有以下三条中的两条：
● Consistency：指数据一致性，也就是开篇第1节所讨论的分布式一致性概念。Brewer对Consistency的描述为“等同于所有节点访问同一份最新的数据副本”
● Available：对数据更新具备高可用性
● Partitions tolerance：指容忍网络分区
CAP“三选二”模式指AP、CP和AC。假设在分区模式下，有两个节点分别位于分区两侧，如果为了可用性就必须允许其中一个节点更新数据，然而因为网络分区两个节点无法通信，所以会导致两个节点数据不一致，即无法做到C(Consistency)；而为了保证数据一致性，只能将分区一侧的节点设置为不可用，则又无法做到A(Available)。只有两个节点能够通信，才能同时保证Available和Consistency，这又违背了分区容忍P(Partitions tolerance)的特性。
3.3.2 CAP设计参考
在分布式环境中，容忍网络分区被认为是分布式系统必须满足的特性，然而如果认为要保证P以致于A、C只能二选一，那其实是对CAP理论的误解。Brewer本人更是于十二年后发文[9]阐述，认为应该正确看待网络分区并进行策略性处理。
首先，因为网络分区发生概率很小，那么在系统不存在分区的情况下，应同时保证A和C；其次，因为存在分区的可能，所以应主动探测分区发生并进入分区模式；最后，在通信恢复后启动分区恢复过程。图3是从分区探测到分区模式再到分区恢复全过程的简单示意。
显然分区是问题根源，CAP理论对分布式系统设计的主要价值也在于指导如何分析并解决分区以及分区引起的相关问题，具体包括以下三方面内容：
● 如何探测到分区
● 在分区模式下，允许或限制哪些操作，跟踪或记录哪些信息用于分区恢复
● 分区恢复过程如何使分区两侧最终实现一致性
分区探测
网络分区导致两侧节点无法正常通信，表现为一侧节点发出的请求迟迟没有收到另一侧节点的回复，或者超出预定的时间仍未收到对方的消息(如心跳检测)，此类现象本质上是由延时(网络超时)引起，类似的原因还有程序异常、节点宕机等等。
所以分区探测核心是处理响应时间的策略，设定合理时限，一旦响应时间超过时限，即进入分区模式。时限越短，进入分区模式越频繁，相应地分区恢复也会频繁执行，而时限越长则可能会影响用户体验。
分区模式
分区模式设计要点主要有以下两点：
● 基于“不变性约束”决定限制、推迟或允许哪些操作
● 跟踪操作历史用以数据一致性恢复
比如“表中键的唯一性”就是一种不变性约束，由于重复键易于发现与合并，因此可以考虑在分区模式下放宽要求，允许有重复的键。又比如网中购场景的“信用卡扣费”，因为流程中明确含有“订单处理中”的状态，所以可以将扣费操作推迟到分区结束，即以用户不易察觉的方式牺牲了可用性。
分区模式设计重点是列举所有操作以及不变性约束，分析每一项操作和约束相冲突的地方，对于存在冲突的情况，决定是否限制、推迟或修改相应的操作。
跟踪操作历史的目的是合并分区两侧的操作并用于恢复一致性，一种优选方案是使用版本向量，向量的元素是[节点，逻辑时间]数值对，分别表示执行数据更新操作的节点和最后更新的时间。
分区恢复
一旦网络通信恢复，分区模式结束，系统进入分区恢复过程，有两个关键问题需要解决：
● 分区两侧的状态最终必须实现一致，即最终一致性(Eventually Consistency)
● 补偿分区期间产生的错误
恢复状态一致最简单的办法是回退到分区开始的状态，以特定的方式推进两侧的一系列操作，逐步合并更新，并在过程中一直保持一致的状态。因为可能存在一些不能自动合并的冲突，因此系统设计可选择在分区模式下限制部分操作，以便分区恢复的时候能够自动合并状态。
3.3.3 CAP vs ACID
虽然CAP和ACID缩写中都有C、和A，但是它们分别所代表的概念是不同的，CAP与ACID之间的对比主要有以下几点：
1、 ACID中的A指原子性，CAP中的A指可用性，但二者并不冲突，没有理由为了可用性而改变分区两侧的原子性，而原子操作实际上会简化分区恢复过程。
2、 ACID中的C指的是事务不能破坏任何数据库规则，比如键的唯一性。相比之下CAP中的C仅仅指数据的多个副本必须一致。显然ACID的C包含的含义更广，而CAP中的C只是其中一个子集。
3、 ACID中的I（隔离性）在分区期间只能在分区一侧维持操作，理由是事务的可串行性（serializability）要求全局通信，而网络分区时无法做到这点。
4、 ACID的D（持久性操作）在分区期间可在分区两侧各自 进行，待分区结束，在分区恢复过程中，根据每个分区提供的持久化记录进行一致性恢复。
总之，分区期间，分区两侧尽可能满足ACID特性将有助于分区恢复过程中的一致性恢复以及错误补偿。
4. 一致性模型
严格意义上的一致性，是指某个数据被更新的“瞬间”，其它节点读取到的就是更新过的值，或者说，任何在某个数据上的读操作，都能返回对该数据的最近一次写操作的结果，然而这样严格一致性（Strict Consistency）并不存在。从数据被更新后，到更新后的数值能够被正确读取到，这中间存在一个时间片段，在这个时间段内，数据的一致性不能保证。换句话说，所谓的一致性都是有附加条件的，而一致性模型主要讨论在满足什么样的条件下即可认为达到一致性。不同的应用场景对一致性要求不一样，因此也就有了不同的一致性模型。下面介绍常见的一致性模型，虽然这些一致性模型大多在上世纪基于multi-processor或shared memory等应用场景进行讨论，但本质上都属于一种广义上的分布式系统，仍然能够指导和约束今天的分布式系统设计。
4.1Sequential Consistency顺序一致性
Lamport于1979年在论文How to Make a Multiprocessor Computer That Correctly Executes
Multiprocess Programs [1]中提出Sequential
Consistency。Lamport给出的定义是：
”…theresult of any execution is the same as ifthe
operations of all the processorswere executedin some sequential order, and the operations of each individualprocessor appear in this sequence in the order specified by its program.”
定义较为抽象，先举个例子。假设两个processor（p1和p2），有两个初始值都为0的全局共享变量x、y。p1、p2程序指令分别为：
P1：{x=1；r1=y}
P2：{y=1；r2=x}
因为两个processor并行交错执行，所以程序可能会有如下执行顺序：
Execution1：{x=1; r1=y; y=1; r2=x;} 执行结果：{r1==0; r2==1}
Execution2：{ y=1; r2=x; x=1; r1=y;} 执行结果：{r1==1; r2==0}
Execution3：{x=1; y=1; r1=y; r2=x;} 执行结果：{r1==1; r2==1}
程序还可能会有其他执行顺序，但是不可能会有第四种执行结果，这里我们以这三种执行顺序为例。
Sequential Consistency规定了两点：
1) 每个processor按照程序指定的顺序（program order）执行操作。（单个processor视角）
2) Processor并行交错的情况下，程序执行顺序可以任意，但所有processor看到的执行顺序必须一致，即所谓的顺序一致性。（多processor构成的程序全局视角）
第1)点说明process1中，x=1必须先于r1=y执行。第2)点说明p1和p2看到的程序执行顺序必须是一样的，如果p1看到的程序执行顺序是Execution1，那么p2看到的程序执行顺序也必须是Execution1，而不能是Execution2或Execution3。
再看图4所示例子。P1、P2先后更新变量x的值，P3、P4读取x的值。图中(a)符合Sequential Consistency，而(b)则不符合Sequential Consistency，因为P3、P4看到的程序顺序不一致。
4.2 Linearizable Consistency线性一致性
Herlihy和Wing于1990年在论文“Linearizability: A correctness
condition for concurrent objects.”[3]中提出Linearizability。
Sequential Consistency仅定义了每个processor看到的程序执行顺序必须是一致的，并没有限制在多processor并行交叉执行的情况下，某个processor上某一操作必须在另外一processor的某个操作之前或之后，意即Sequential Consistency并不关心时间顺序。Linearizability则关心时间顺序，它在Sequential Consistency模型基础上，为每个操作增加了时间戳，并定义：如果操作1的时间戳小于（意即早于）操作2的时间戳，那么操作1应该在操作2之前完成。因此Linearizable
Consistency一致性要求强于Sequential Consistency。
图1中(a)满足Sequential Consistency但不满足linearizability，因为write(x=a)操作先于write(x=b)，而read操作却先读到x=b的值。
队列的FIFO特性适用于解释linearizability。即使多个进程在同一队列上进行操作，也必须满足队列FIFO特性。E(x) A表示进程A执行元素x的入队列操作，D(x) B表示进程B执行出队列操作，得到元素x。图5中(a)、(c)符合linearizability，(b)、(d)不符合linearizability，因为(b)、(d)中元素x早于y入队列，而y却先出队列。
实现Linearizable Consistency模型需借助于全局时钟，如Google Spanner利用原子钟和GPS接收器，实现了较为精准的全局时钟，即TrueTime。
4.3 Causal Consistency因果一致性
Causal Consistency[4]要求对于有因果关系（causally related）的若干操作，在所有节点上看到的执行顺序都必须一致，而没有因果关系的并行操作，在不同节点上可以看到不同的执行顺序。
以分布式数据读写操作为例解释因果关系。假设一个事务由先读后写的两个操作构成，写操作创建的值依赖于读操作读取到值，我们说该读和写操作具有因果关系。
图6是因果一致性的例子，因为进程P3上的读操作R3(x)依赖于P2的写操作W2(x)，进程P4上的读操作R4(x)依赖进程P1的写操作W1(x)，而P1和P2上的并行（没有因果关系）写操作W1(x)、W2(x)在进程P3、P4上看到的顺序是不一样的。
图7所示的场景则违反了因果一致性。图中进程P2读操作R2(x)依赖进程P1的写操作W1(x)，即R2(x)、W1(x)具有因果关系，所有进程上都应该看到W1(x)先于R2(x)，同时根据进程P2的Program order，R2(x)应先于W2(x)，所以可以推导出W1(x)应先于W2(x)，而实际上进程P3却不是这样的顺序。
4.4 PRAM Consistency
PRAM（Pipelined Random Access Memory）管道式存储器，是Lipton和Sandberg于1988年在学术报告”
PRAM: A scalable shared memory”[5]中提出。如前所述，Sequential
Consistency要求所有进程看到的程序执行顺序必须一致，而Causal Consistency降低了一致性要求，它要求有因果关系的操作在所有进程上看到必须一致，而PRAM Consistency进一步降低一致性要求。先看PRAM定义：
“…Writesdone by a single process are received by all other processes in the order inwhich they were issued, but writes from different processes may be seen in adifferent order by different processes.”
意即在PRAM中，不同进程可以看到不同的程序执行顺序，但在某一进程上的多个写操作，在所有进程上看到的顺序必须一致，而不同进程上的写操作在不同进程上看起来其执行顺序则可以不一致。
图8所示场景中，进程P1、P2分别可以看到如下执行顺序S1、S2：
S1 = w1(x)0; w2(x)1; r1(x)1
S2 = w2(x)1; w1(x)0; r2(x)0
因为写操作w1(x)、w2(x)分别在进程P1、P2中，它们在S1、S2中可以有不同的顺序，因此图5所示场景符合PRAM一致性。
5. 失效模型
探讨分布式一致性算法通常需要先明确分布式环境的失效模型，这里我们先介绍常见的失效模型。
5.1 fault、error和failure
讨论失效模型之前，先区分fault、error、failure三者含义的不同：
● fault：导致系统或功能失效的异常条件，可译为“缺陷”
● error：由fault造成系统处于错误状态，是一种中间状态，当系统能够修复，回到正确的状态，则可以避免发生failure。Error通常译为“错误”
● failure：指系统的行为偏离其原先定义好的规格，意即跟预期输出不符的异常行为，可译为“失效”
三者之间的关系，通俗来讲就是：缺陷（fault）发生了，会导致错误（error），错误有可能造成系统功能失效（failure）。
5.2 失效模型
在分布式系统中，进程和网络通信都有可能失效（failure），即它们可能偏离被认为是正确或所期望的行为。失效模型（failure
modes）定义失效可能发生的方式，以便理解失效所产生的影响。
按照不同的标准，有不同的划分失效类型的方法，这里按照Cristian、Hadzilacos和Toueg提供的分类方法[10,11]介绍几种主要的失效模型。
● Fail-stop failure（异常失效并停止服务）：即节点失效后立即停止接收和发送所有消息，故障不会恢复。节点失效状态能够被其它节点检测到。
● Crash failure（崩溃性失效）：属于突然失效以至于无法提前发出一些通告性消息，导致其它节点无法检测到自己已经失效。电源掉电或操作系统死机都会导致崩溃性失效。
● Omission failure（遗漏性失效）：是指节点不能执行预期的动作。表现为对某些输入请求没有响应，可能是因为收不到请求，也可能是处理请求之后在发送响应时出错。
● Arbitrary failure（随意性失效）：可形象的比喻为“不按常理失效”，一种随机性失效，时而正常，时而异常，节点也可能不按程序逻辑执行，错误难以定位，拜占庭失效（byzantine failure）就属于这一类。
参考
[1] LAMPORT, L. Time, clocks,and the ordering of events in a distributed system. Communications of the ACM21, 7 (July 1978), 558–565.15
[2] Lamport, Leslie (Sep1979). "How to make a multiprocessor computer that correctly executes multi-process programs.". Computers, IEEE Transactions C–28 (9): 690–691.
[3] Herlihy, Maurice P.;Jeannette M. Wing (July 1990). ""Linearizability: A correctnesscondition for concurrent objects." ACM Transactions on ProgrammingLanguages and Systems". ACM Transactions on Programming Languages andSystems 12 (3): 463–492.
[4] Mustaque Ahamad , GilNeiger , James E. Burns , Prince Kohli , P.W. Hutto: "Causal emory: Definitions, Implementation and Programming". 1994.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3356
[5] Lipton, R.J.; J.S.Sandberg. (1988). PRAM: A scalable shared memory (Technical report). PrincetonUniversity. CS-TR-180-88.
[6] Armando Fox and EricBrewer, “Harvest, Yield and Scalable Tolerant Systems”, Proc. 7th Workshop HotTopics in Operating Systems (HotOS 99), IEEE CS, 1999, pg. 174-178.
[7] Eric Brewer (2000),"Towards Robust Distributed Systems"
[8] Fielding, Roy Thomas (2000). Architectural Styles and the Design of Network-based Software
Architectures (Ph.D.). University of California, Irvine.
[9] Eric Brewer, “CAP TwelveYears Later How the Rules Have Changed”,
https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
[10] Cristian F.: “UnderstandingFault-Tolerant Distributed Systems”, Communications of the ACM, Vol.34, No.2,pp.56-78, Feb. 1991.
[11] Hadzilacos V. and Toueg S.:“Fault-Tolerant Broadcasts and Related Problems”, In Mullender S.(ed.),Distributed Systems, pp.97-145, Wokingham: Addison-Wesley, 2nd ed., 1993.
[12] https://raft.github.io/
