行业科普
什么是分布式系统中的一致性？
从本文开始连续三篇文章将会讲述一致性问题。而所探讨的线性一致性是在铺垫了多副本、网络问题、时钟问题后的一个综合探讨。
首先，我们会探讨了线性一致的内涵：让系统表现得好像只有一个数据副本。然后讨论如何实现线性一致性，以及背后所做出的的取舍考量。其间花了一些笔墨探讨 CAP，可以看出作者很不喜欢 CAP 的模糊性。
如前所述，分布式系统中很多事情都有可能出错。解决出错最简单粗暴的方法是让整个系统宕机，并给出出错原因。但在实际生产中，这种方式多不可接受，此时我们就需要找到容错（tolerating faults）的方法。即，即使系统构件出现了一些问题，我们能保证系统仍然正常运行。
从现在开始，我们将会讨论一些用于构建具有容错性分布式系统的算法和协议（alogrithm and protocol）。在设计算法和协议时，我们假设上文提到的分布式系统中的问题都会存在：
数据包可能会丢失、乱序、重复和不确定延迟
多机时钟最好的情况也就是近似一致
机器节点可能会不确定停顿、宕机重启
构建一个容错系统最好的方法是：找到一些基本抽象，可以对上提供某些承诺，应用层可以依赖这些承诺来构建系统，而不必关心底层细节。在之前的文章中，通过使用事务，应用层可以假设不会发生宕机（原子性，意思是不会因为宕机出现让事务停留在半成功的状态），没有其他应用并发访问数据库数据（隔离性），且存储系统非常可靠（持久性）。事务模型会隐藏节点宕机、竞态条件（race conditions）、硬盘故障等底层细节，即使这些问题出现了，应用层也不必关心。
在本文后面，我们将继续讨论一些可以减轻应用层负担的分布式系统中的基本抽象。比如，分布式系统中最重要的一个抽象——共识（consensus），即，让所有节点在某件事情上达成一致。在稍后的讨论可以看出，让系统中的所有节点在有网络故障和节点宕机的情况下达成共识，是一件非常棘手的事情。
为什么共识协议如此重要呢？他和真实系统的连接点在于哪里？答曰，操作日志。而大部分数据系统都可以抽象为一系列数据操作的依次施加，即状态机模型。而共识协议可以让多机对某个确定的操作序列达成共识，进而对系统的任意状态达成共识。
一旦我们实现了共识协议，应用层可以依赖其做很多事情。例如，你有一个使用单主模型的数据库，如果主副本所在节点宕机，我们便可以使用共识协议选出新的主。在之前处理节点下线（Handling Node Outages）一节中我们提到过，只有唯一的主，并且所有副本都认可该主，是一个需要确保的非常重要的特性。如果有超过一个节点都认为自己是主，我们称之为脑裂（split brain）。脑裂很容易导致数据丢失，而正确实现的共识协议能够避免该问题。
在随后文章的“分布式事务和共识协议”一小节里，我们将会详细讨论用以解决共识相关问题的算法。但在此之前，我们需要探索下分布式系统中我们可以提供的保证和抽象有哪些。
我们需要理解容错的边界，哪些事情可以做、哪些事情做不了：在某些情况下，系统可以容忍某些故障；但在另外情况下，系统却容忍不了。我们将通过理论证明和具体实现来深入探讨，可能与不可能的边界限制。我们会对诸多基本限制有个概览式串讲。
分布式系统领域针对这些主题的研究已经持续了数十载，因此积累了很多材料，但我们只能进行简要介绍其皮毛。由于篇幅所限，我们不会详细探究其严谨的模型描述和详细证明，相反，我们只会给一些其背后的直觉（informal intuitions）。如果你感兴趣，后面文章文末的参考文献应该可以提供一些足够深入的细节。
Part.01 一致性保证
在之前的日志滞后问题（Problems with Replication Lag）小节，我们分析了一些多副本数据所遇到的时序问题。在相同时刻，如果对比多副本数据库中一份数据的两个副本，我们可能会看到不一致的数据。这是因为，写请求到达不同的数据节点，总会存在一个时间差。无论我们使用什么数据副本模型（单主、多主和无主），这种数据的不一致性都有可能会发生。
大部分多副本数据库（replicated databases）提供最终一致性（eventually consistency）的保证，这意味着，只要你对数据库停写，并等待足够长的时间，则所有对相同数据的读取请求最终会返回相同的结果。从另一个角度来说，所有的不一致都是暂时的，最终都会被解决（当然，这得是在网络故障能最终修复的假设之下）。描述相同意思的一个更好的名字可能：收敛性（convergence），即最终，所有副本都会收敛到相同的值。
但这是一个相当不靠谱的保证——没有提供任何关于何时收敛的信息。而在收敛之前，对于相同数据的读取，可能会返回任意值甚至不返回。举个例子，你向多副本数据库中写入了一条数据，并立即读取他。你能读到什么，最终一致性对此不会提供任何保证，因为读取请求可能会被路由到任何其他副本。
最终一致性对于应用层开发者很不友好，因为它表现出的行为和单线程程序中的变量完全不一致。在单线程模型里，如果对某个变量赋值后立即读取，我们默认一定会读到刚才的赋值，而不是读到旧值或者读取失败。数据库在对外表现上很像一组可读写的变量集，但具有复杂得多的语义。
在使用只提供弱保证的数据库时，我们需要时刻记得其限制，而不能偶尔自己增加额外假设，否则，会产生非常致命且难以察觉的 BUG。因为大部分时间里，应用层表现得毫无波澜，只有在系统中出现故障（网络拥塞、节点宕机）或在高负载场景下，这些边缘情况才会被触发。
本文我们会一起探究一些更强的一致性模型，但选择这些模型是有代价的。相对弱一致性模型系统来说，这么做要么会牺牲性能，要么会牺牲可用性。但提供强保证会让应用层能更加容易、正确的使用。但当然，我们最终还是得根据具体场景，来选择使用何等强度一致性模型。
在实践中，我们常会使用分层策略，让某些底层解决可用性、性能和容量的问题，让上层解决一致性的问题。比如云上各种基于 aws s3 的关系型数据库。另外，也有些系统会同时提供多种一致性模型供用户选择，在一致性和性能间进行取舍。
分布式系统中的一致性模型的强弱和之前讲的事物的隔离级别层次有一些共通之处，比如在性能和隔离性/一致性间做取舍。但他们是相对独立的抽象：
事务隔离级别是为了解决并发所引起的数据竞态条件
分布式一致性是处理由于多副本间延迟和故障所引入的数据同步问题
本文涉及到很多主题，乍看起来很宽泛，但其内里是互相勾连的：
首先，我们从常用的最强的一致性模型：线性一致性（linearizability）开始，探究其优缺点。
接着，我们会考察分布式系统中时间的顺序问题，尤其是关于因果关系（causality）和全序问题（total ordering）。
最后，在第三部分，我们会探索如何原子性的提交一个分布式事务，最终导出共识问题的解决方法。
Part.02 线性一致性
在提供最终一致性语义的数据库里，如果你问不同副本同一个问题（比如说查询某条数据），则很可能得到不同的回答（响应），这就很让人迷惑了。如果多副本数据库在行为上能够表现的像只有一个副本，应用层编程将会简单很多。这样在任意时刻，每个客户端所看到的数据视图都是一样的，而不用去担心引入多副本带来的副本滞后（replication lag）等问题。
这就是线性一致性（linearizability）的基本思想，他还有很多其他称呼：原子一致性（atomic consistency）、强一致性（strong consistency）、即时一致性（immediate consistency），或者外部一致性（external consistency）。线性一致性的精确定义很精妙，后面会进行详细探讨。但其基本思想是，一个系统对外表现的像所有数据只有一个副本，作用于数据上的操作都可以原子地完成。有了这个保证，不管系统中实际上有多少副本，应用层都不用关心。这种抽象，或者说保证，类似于编程中的接口。
在一个提供线性一致性的系统中，只要某个客户端成功的进行了写入某值，其他所有客户端都可以在数据库中读到该值。提供单副本的抽象，意味着客户端任何时刻读到的都是最近、最新（up-to-date）的值，而不会是过期缓存、副本中的旧值。换句话说，线性一致性是一种数据新鲜度保证（recency guarantee）。为了理解这个说法，让我们看一个非线性一致性系统的例子：
上图显示了一个非线性一致性的体育网站。Alice 和 Bob 在一间屋子里，分别通过手机来查看 2014 年国际足联世界杯的总决赛的结果。在最终比分出来后，Alice 刷新了网页，并且看到了发布的赢家信息，并且将该结果告诉了 Bob。Bob 有点难以置信，重新刷了一下网页，但是他的请求被打到了一个滞后的数据库副本上，该副本显示比赛仍在进行。
如果 Alice 和 Bob 同时（也就是并发）刷新网页，可能还不会对出现不同结果有太多惊讶，毕竟他们也不知道谁的查询请求先到（因为并发）。但，上述例子中，Bob 是在 Alice 告知他结果后刷新的网页，因此他才会期待至少能看到和 Alice 一样新的结果。该例子中 Bob 的请求返回了一个过期的结果，这便是违反了线性一致性。
如何让系统满足线性一致？
线性一致性背后的思想很简单：让系统表现得好像只有一个数据副本。但精确地将其拆解开，还需要花很多心思。下面我们来看更多的例子，以更好得理解线性一致性。
下图显示了三个客户端并发访问提供线性一致性的数据库的同一个键。在分布式系统论文中，x 被称为“寄存器”（register）。在实践中，x 可以是一个键值存储中的键值对、关系型数据中的一行或者文档数据中的一个文档。
为了简单起见，上图只显示了客户端角度数据读写视图，而略去了数据库的内部数据视角。每个时间条代表一个客户端的请求，起点代表客户端发出请求时刻、终点代表客户端收到响应时刻。由于网络延迟的不确定性，客户端不能够确切的知道数据库会在什么时刻处理其请求，而只能知道这个时间点一定在请求发出和收到回复之间，即时间条中的某个时刻。
在本例中，寄存器支持两种类型的操作：
read_(x) ⇒ v: 客户端请求读寄存器 x 的值，数据库会返回值 v
write(x, v) ⇒ r：客户端请求将寄存器 x 的值设置为 v，数据返回结果 r（可能是成功或者失败）
在上图中，x 初始值为 0，客户端 C 发出一个写请求将其置为 1。在此期间，客户端 A 和 B 不断地向数据库请求 x 的最新值。试问 A 和 B 的每个读请求都会读到什么值？
客户端 A 的第一个读请求结束在 C 的写请求发出之前，所以该请求一定会返回 0。
客户端 A 的最后一个读请求开始于 C 的写请求完成之后，因此该请求一定会返回 1，当然，是在该数据库提供线性一致性保证的前提下：我们知道数据库的写操作一定发生在写请求期间的某个时间点、读操作一定也发生在读请求的某个时间点，如果读请求开始于写请求结束之后，则在数据库端，读操作一定是在写操作之后被处理的，因此该读操作一定能看到写操作所写。
其他的读请求时间条与该写请求都有交集，因此可能会返回 1，也有可能会返回 0。因为我们无从判断在数据库端，读操作和写操作的具体先后关系。从这个角度来说，这些读请求和写请求都是并发的（concurrent）。
不过，这也不足以刻画线性一致性：如果和写请求并发的多个读请求既可能会返回新值，也可能会返回旧值，则在写请求持续期间，读客户端可能会看到不断交替的新旧值。这明显不符合我们所期待的，能够提供“单数据副本”抽象的系统。
在多副本数据库中，如果要解决线性一致性，就要满足一旦某个客户端读取到新值，则其之后的读请求一定能读到该新值，而不是还可能看到旧值。这很难，由于上一章讲的时钟问题，我们甚至很难对多个客户端定义“先后”。此外，这种线性一致性的特性类似于薛定谔的猫，本来可能有多个状态，但一旦有个一个客户端进行了一次观察，就迅速的坍缩到了一个状态，其他后来者，也只能看到这一个状态。从另外一个角度理解，是读取请求塑造（seal）了并发请求的多状态边界。
为了让该系统满足线性一致性，我们需要增加一些额外限制，如下图：
在满足线性一致的系统中，写操作起止中间，必有一个时间点，使得 x 的值从 0 变为 1。因此一旦有一个读请求读到 1，之后的所有读请求都应该返回 1。即使此时，写请求可能还没有结束。
上图中使用箭头表示了这种时序依赖。客户端 A 首先读到 x 的新值 1。在 A 的读取返回之后，B 开始一个新的读。由于 B 的读请求严格在 A 的读请求之后，因此必然读到 1，尽管写下 1 的 C 的请求仍然没有返回。这和图 9-1 中的例子有点像，即在 Alice 读到世界杯结果之后，Bob 也应当能看到新消息。
我们将该时序图提炼一下，将所有请求生效时间压缩到一个点。下图中是一个更复杂一些的例子。
在上图中，我们在读和写之外，增加了第三种操作：
上图（9-4）中的所有请求都被关联上了一条竖线（在每个操作的时间条中），我们认为对应的操作在此时刻真正发生。所有的标记组成一种执行顺序，该顺序必须满足寄存器的读写特性（所有的读必须能返回最近的写）。
线性一致性要求所有操作标记组成序列是永远向前的，即满足数据新鲜度要求：一旦我们写入或者读取到某值，所有稍后的读请求都能看到该值，直到有人再次将其改写。
上图中还有一些有意思的点：
B 读到“稍后”的值。开始时，客户端 B 首先发出一个针对 x 的读请求，然后客户端 D 发出一个设置 x = 0 的写请求，紧接着，客户端 A 发出了另一个设置 x = 1 的写请求。然后 B 读到的值却是 1。这样是合法的，并且说明数据库先处理了 D（设置 x = 0）的写请求、接着处理了 A 的写请求，最后是 B 的读请求。尽管这个序列不符合请求发出的时间点先后，但这是一个可以接受的顺序，因为这三个请求本质上并发的，因此事实上谁先谁后被处理都有可能。比如，有可能是客户端 B 的请求在网络中延迟了一些，以至于在两个写之后才被处理。
客户端 A 写请求还没结束客户端 B 就读到了其写的值 1。这也是合法的：这并不是说我们在 1 写成功之前读到了，而只是说明 A 的写操作的 ok 回应回来的有一些延迟。
这个模型对隔离性没有任何假设：客户端可能在任何时刻更改值，并且能被其他客户端看到。例如，C 两次读取，第一次读到 1 第二次读到 2，这是因为两次读取间 B 修改了 x。使用原子的 CAS 操作可以在修改 x 的值时，避免被其他客户端并发的修改。B 和 C 的 CAS 请求成功了，但是 D 的 CAS 请求失败了（因为数据库处理其 CAS 时，x 的值已经不是 0 了）。
B 的最后一个读请求不满足线性一致。该请求和 C 的 CAS 写是并发的，C 的 CAS 将 x 从 2 更新到了 4。如果没有其他操作，B 读到 2 是合法的。但是客户端 A 读到了 4，并且在 B 请求开始前就返回了，因此 B 不允许读到比 A 更老的值。这个也和之前 Alice 和 Bob 的例子类似。
这就是线性一致性背后的一些直觉，参考文献（https://cs.brown.edu/~mph/HerlihyW90/p463-herlihy.pdf）中有更形式化的定义。可以（但是代价很高）通过记录系统中所有请求的时间线，并检查其能否组成合法的顺序，来测试该系统是否满足线性一致性。
线性一致性和可串行化
线性一致性（Linearizability）很容易和可串行化（serializability）相混淆，因为他们看起来都像是：可以进行拓扑化组织。但他们是不同维度的约束，我们很有必要对其进行区分：
可串行化（Serializability）。可串行化是事务的一种隔离级别。每个事务可能会涉及多个数据对象（行、文档、记录）的读写，之前有讨论过单对象和多对象。可串行化可以保证所有事务好像按某种顺序依次执行（后一个事务在前一个事务结束后才开始）。需要注意的是，如果某种串行顺序和实际执行顺序不一致也没事，只要是串行执行就行。举个例子，如果 A、B、C 三个事务并发执行，真实顺序是 A->B->C，但如果对应用层表现为 C->A->B 的执行顺序（可能由于多机时间戳不同步），也可以叫可串行化，但 C->A->B 的执行顺序在某个对象上可能不满足线性一致性。
线性一致性（Linearizability）。线性一致性是一种针对寄存器（register，单个数据对象）的读写新鲜度保证。它不会将多个操作打包成事务，因此不能避免像之前提到的写偏序等问题，除非使用某些辅助手段，如物化冲突。
一个数据库可以同时提供可串行化和线性一致性保证，我们称之为严格可串行化（strict serializability）或者单副本可串行化（strong one-copy serializability）。使用两阶段锁或者真正串行化执行实现的可串行化，通常都是线性一致的。
然而，基于快照隔离的串行化通常不是线性一致的。为了避免读写互相阻塞，所有的读取都会基于某个一致性的快照，则该快照之后的写入不会反映到读请求上，因此，快照读不满足线性一致性。
应用线性一致性
在什么场景下我们会用到线性一致性？之前提到的获取体育赛事决赛比分不是一个能凸显其重要性的例子：在该情况下延迟几分钟得到比赛结果可能并不会引起什么实质性损害。然而，在某些领域里，线性一致性是系统能够正常工作的重要依赖。
锁和主选举
在使用单主模型的系统中，需要保证任何时刻只有一个主副本，而非多个（脑裂）。一种进行主选举的方法是使用锁：每个节点在启动时都试图去获取锁，最终只有一个节点会成功并且变为主。不论使用什么方式实现锁，都必须满足线性一致性：所有节点必须就某节点拥有锁达成一致，否则这样的锁服务是不能用的。
像 Apache Zookeeper 和 Etcd 之类的协调服务（Coordination services）通常用来实现分布式锁和主选举。他们通常使用共识算法来实现线性一致性操作，并且能够进行容错。当然，在此之上，为了正确的实现锁服务和主选举，还需要讨论一些非常微妙的细节。像 Apache Curator 等库可以基于 Zookeeper 提供高层的协调服务抽象。但是，一个提供线性一致性保证的存储服务是实现这些协调任务的基础。
一些分布式数据库在更细粒度上使用了分布式锁，如 Oracle Real Application Clusters（RAC）。当有多个节点共同访问同一个磁盘存储系统时，RAC 会为每个磁盘页配一把锁。由于这些线性化的锁是事务执行的关键路径，RAC 通常将其部署在和数据节点使用专线连接起来的集群里。
约束和唯一性保证
唯一性约束在数据库中很常见：比如用户名和邮箱可以用来唯一的标识一个用户、在同一个文件系统中不可能有多个文件具有相同的路径和文件名。如果你想在数据写入时维持这些约束（比如两个人使用相同的用户名并发地创建账户，其中一个会失败而报错），你需要线性一致性。 这个情形和锁的语义非常类似：当一个用户注册时，可以认为他获得了一个和所注册的用户名关联的“锁”。这个操作很像原子的 CAS（compare-and-set）：如果该用户名没有被使用，就将其分配给该用户。
在以下几种情况也会面临类似的问题：
保证银行账户余额不会出现负值
不可能卖出比持仓多的股票数目
任意两个用户不可能同时预定到相同的航班或者剧院座位
这些约束都要求所有节点在单个最新值（账户余额、股票水位、座位预定）上达成一致。
当然，在真实场景下，有时这些约束可以被适当放宽（比如，如果机票座位被超订了，可以将其中一个用户移到其他航班，并给予适当补偿）。在这种情况下，可能不需要严格的线性一致性，稍后我们会在及时性和完整性一节讨论这些放松的约束。
但是对于像我们平时在关系型数据库中看到的严格的唯一性约束，就需要线性一致性了。数据库中其他类型的一些约束，如外键约束和属性约束，就可以不用借助线性一致性来实现了。
多渠道的时许依赖
在图 9-1 中我们可以注意到一个细节：如果 Alice 没有说出决赛结果，Bob 就不会知道他看到的是过时的结果。如果 Bob 没有从 Alice 那里事先知道结果，他可能就会过几秒再刷新一次页面，最终会看到最终分数。也就是说，因为存在一个额外的通信渠道（addional communication chanel），导致我们注意到了系统不满足线性一致性。 计算机系统中也有类似的问题。例如，我们有一个可以让用户上传照片的网站，有个后台进程会将照片进行压缩以支持快速加载（缩略图）。架构图如下：
图片调整服务（image resizer）需要显式的指定任务，任务指令是通过消息队列由 web 服务器发给图片调整服务。但由于消息队列是针对短小消息（1kb 以下）而设计的，而图片通常有数 M，因此不能直接将图片发送到消息队列。而是，首先将图片写入文件存储服务（File Storage Service），然后将包含该文件路径的调整请求发送到消息队列中。
如果文件存储服务是线性一致的，则这个系统能正常运作。但如果他不是，则可能会存在竞态条件：消息队列可能会比文件存储服务内部多副本同步要快。在这种情况下，当图片调整服务去文件存储服务中捞照片时，就会发现一个旧照片、或者照片不存在。如果调整服务看到的是旧照片，却以为是新的，然后把它调整了并且存回了存储服务，就会出现永久的不一致。
出现这种情况是因为在 web 服务器和图片调整服务中间存在两条不同的通信渠道（communication channels）：存储系统和消息队列。如果没有线性一致性提供的新鲜度保证，两条通信渠道就有可能发生竞态条件（race condition）。这也和图 9-1 的情况类似，在那个场景中，也存在着两条有竞态条件的通信渠道：数据库多副本同步渠道和 Alice 的嘴到 Bob 的耳朵的声音传播。
可线性化不是唯一避免静态条件的方式，但它是最易理解的。如果你能控制所有的通信渠道（如 9-5 中的消息队列，但 9-1 中的两人交谈就不行，因为在系统外），就可以使用类似读你所写一节中所提到的手段来解决这种竞态条件。如读走 leader、使用时间戳等等增加系统复杂度的方法来换取线性一致性。
实现线性一致的系统
我们已经看了一些依赖线性一致性的例子，接下来让我们思考下如何实现一个提供线性一致语义的系统。
线性一致性的本质是在说：系统表现得像只有一个数据副本，且所有施加于其上的操作都会原子性（瞬间）的完成。那么，我们最简单的实现方式就是真的只用一个数据副本。但其问题在于，不能容错：一旦该副本挂了，轻则长时间（重启之前）不可用、重则数据丢失。
最常用的让系统进行容错的方式就是多副本。让我们回顾下第五章的几种多副本模型，然后逐一考察下其是否能够做成可线性化的：
单主模型（Single-leader replication，potentially linearizable） 在一个单主模型的系统中，主副本服务于写请求，其他副本负责备份。如果我们让读取也走主副本，或者使用同步更新从副本的策略，则该系统有可能满足线性一致性。但是，并不是所有单主模型的数据都提供线性一致性，有时候是故意的（比如提供快照隔离），有时候是由于并发 bug。想让主副本也负责读请求，首先我们得确切知道哪一个是主副本。就像我们在“真相由多数节点定义”一节中提到的，很有可能某个节点认为他是主节点，但其事实上不是。如果这个自以为是的主节点（delusional leader）继续提供服务，则系统很可能会违反线性一致性。如果使用异步同步策略，节点宕机可能甚至会丢数据，从而不仅违反线性一致性，也违反了可持久性。
共识算法（Consensus algorithms，linearizable）后续文章会讨论到，有一些共识算法，看起来与单主模型类似。但这些共识协议有一些阻止脑裂和过期副本的手段。由于这些额外细节，共识算法可以实现安全的线性一致性存储。Zookeeper 和 etcd 就是用的这种手段。
多主模型（Multi-leader replication，not linearizable） 由于可以同时在多个节点上处理写入，并且异步同步写入数据，使用多主模型的系统通常不是线性一致的。由于上述原因，这种系统可能会产生需要手动解决的写入冲突。这种冲突便是违反线性一致性要求的一个点：表现得像一个副本。
无主模型（Leader replication， probably not linearizable） 对于使用无主模型的系统（Dynamo-style，参见前面无主模型一节）来说，厂商有时候会声称你可以通过使用法定数目读写（Quorum reads and write，w+r > n）来获得强一致性。这个说法有点模糊，并不总是正确，这取决于你对法定节点的配置，也取决于你如何定义强一致性。“后者胜”（Last write win）的冲突解决方法会依赖于多个机器的挂历时钟（time-of-day，参见依赖时钟同步），由于多机时钟存在偏差，其物理时间戳不能保证和系统事件顺序一致，因此基本上不可能做到线性一致。放松的法定策略（Quorum，见放松的 Quorum 和提示转交）也是破坏了线性一致性。即使对于严格的法定策略，非线性一致的现象也可能出现，下一节将会详细探讨。
线性一致和法定策略（Quorum）
从直觉出发，在 Dynamo 风格的系统中使用严格的 Quorum 读写应该会满足线性一致性。但在具有不确定延迟的网络中，仍然可能会出现竞态条件。如下图所示：
在图 9-6 中，x 的初始值是 0。然后一个客户端想将 x 更新为 1，然后将该写请求发送到所有三个副本（n=3, w=3）。与此同时，客户端 A 使用 r = 2 的配置进行 Quorum 读，并且看到了新值 1。稍后，客户端 B 也是用 r = 2 的配置在另外两个节点进行 Quorum 读，但却读到了旧值 0。
Quorum 的配置是严格满足 w+r>n 的，然而这个读写序列却不是线性一致的：B 的读取请求开始于 A 的读请求结束之后，却读到了比 A 旧的值。
当然，有趣的是，我们可以通过牺牲部分性能来让 Dynamo 风格的 Quorum 读写变成线性一致的：
每个读请求必须进行同步的读取修复。
发送任意写请求之前要先读取最新值。
但由于性能原因 Riak 并没有采用同步的读取修复；Cassandra 倒是会同步读取修复，但在多个请求并发写入同一个 key 时，由于采用了后者胜的策略（考虑时钟，会导致接受顺序不是真正事件发生顺序），仍然不能保持线性一致性。
此外，这种方式只能实现线性一致的读写操作，而不能实现线性一致的 CAS 操作。只有共识协议才能实现线性一致的 CAS。
总结来说，最好认为基于无主模型的 Dynamo 风格的系统不提供线性一致性保证。
线性一致性的代价
可以看出有些系统提供线性一致性保证，有一些却不提供。因此我们很容易好奇：线性一致性系统的优缺点是什么，接下来我们深入探讨一下。
在之前的文章，我们讨论了一些使用不同副本策略的实际场景。如，对于跨数据中心（详见多数据中心一节）的系统来说，多主模型通常是一个好的选择。下图是一个例子：
让我们考虑两个数据中心网络无法连通的情形。我们假设每个数据中心内部网络是连通的，且客户端也可以触达每个数据中心，仅仅是数据两个中心之间不能互相触达。
在使用多主模型的数据库中，在上述情形下，由于向其他数据中心的数据传输是异步的，每个数据中心仍能正常工作，只是由于数据中心间网络的问题，所有数据同步都被排队了起来，待到网络恢复就会重新发出。
但如果数据库使用单主模型，主节点只会存在于某个特定的数据中心。所有的写入和线性化的读都会被路由到该数据中的该主节点。对于所有直接打到从数据中心的客户端请求，都必须被通过网络同步的路由给主数据中心。
在单主模型下，如果两个数据中心间的网络断了，连接到从数据中心的客户端不能间接触达主数据中心，所有的写入都会被阻塞然后失败，所有的线性化读取自然也会。当然该客户端可以无视该中断，直接从从数据中心的从副本进行读取，但其读到的内容可能是过期（主副本接受了新的写入），也因此不满足线性一致。如果应用层要求线性一致的读写，则数据中心间的网络中断会造成服务的不可用。
如果客户端能直连主数据中心，则上述问题不存在。但如果客户端只能连接到从数据中心，就会在网络修复前经历一段时间的不可用。
CAP 定理
该问题不止是采用单主模型和多主模型的不同策略所导致的：不管其实现方式如何，任何想要提供线性一致性的系统都会面临上述取舍问题。该问题也不止局限于跨数据中心部署，即使是在一个数据中心之内，任何通过不可靠网络连接的系统都会有该问题。其背后的取舍考量如下：
如果应用层要求系统提供线性一致性，此时如果某些数据副本由于网络问题和系统其他部分断开了连接，则这些数据副本就不再能够正常地处理请求：要么等待网络恢复、要么进行报错。但这都意味着系统不可用。
如果应用不要求系统的线性一致，则即使多副本间遇到连接问题，每个副本可以独立的进行写入。从而，即使出现了网络故障，系统仍然能够保持可用，但其行为不是线性一致的。
总而言之，如果系统不提供线性一致性，就可以对网络故障更加鲁棒。该洞见常被称为 CAP 定理，于 2000 年被 Eric Brewer 提出。不过，类似的取舍考量从 1970 年代就为分布式数据的设计人员所熟知了。
CAP 最初被提出只是一个为了激发数据库取舍讨论的模糊的取舍参考，而非被精确定义的定理，Martin 还专门写过一篇文章（https://www.qtmuniao.com/2020/02/16/not-cp-or-ap/）来探讨这件事。在当时，很多分布式数据库还在着眼于基于共享存储的一组机器上提供线性一致性语义。CAP 的提出，鼓励工程师们在 share-nothing 等更广阔的设计领域进行架构探索，以找出更加适合大规模可扩展 web 服务架构。在新世纪的最初十年里，CAP 的提出见证并推动了当时数据库设计思潮从强一致系统转向弱一致系统（也被称为 NoSQL 架构）。
CAP 定理的形式化定义适用范围很窄：仅包含一种一致性模型（即线性一致性）和一种故障类型（网络分区，或者说节点存活，但互不连通）。它没有进一步说明任何关于网络延迟、宕机节点、以及其他的一些取舍考量。因此，尽管 CAP 在历史上很有影响力，但他在设计系统时缺乏实际有效指导力。
在分布式系统中有很多其他难以兼顾的有趣结果，CAP 现在已经被很多更为精确的描述所取代，因此 CAP 在今天更多的作为一个历史名词。
CAP 有时候被表述为，在做系统设计时，一致性（consistency）、可用性（Availability）、分区容错性（Partition tolerance），只能三取其二。然而，这种说法极具误导性，因为网络分区是一种故障类型，而不是一种可以取舍的选项：不管你喜欢还是不喜欢，它都在那。当然，也有人理解为用单机系统可以规避，但我们当下讨论的前提是分布式系统。
在网络正常连通时，系统可以同时提供一致性（线性一致性）和完全的可用性。当网络故障发生时，你必须在线性一致性和完全可用性之间二选一。因此，对于 CAP 更好的一个表述可能是：当网络出现分区时，一致性和可用性只能二选其一（either Consistent or Available when Partitioned）。一个可靠的网络，可以减少其上的系统该选择的次数，但无论如何，分布式系统中，该选择是无法避免的。
在有关 CAP 的讨论，有几种关于可用性的大相径庭的定义，且将 CAP 升格为定理并给出证明中的提到的形式化的可用性并非通常意义中所说的可用性。很多所谓“高可用”的系统通常并不符合 CAP 定理中关于可用性的独特（idiosyncratic）定义。总而言之，CAP 有很多容易误解和模糊不清的概念，并不能帮助我们更好的理解系统，因此最好不用 CAP 来描述一个系统。
线性一致性和网络延迟
尽管线性一致性是一个非常有用的保证，但令人惊讶的是在工程实践中，很少有系统支持真正的线性一致。甚而，即使在现代多核 CPU 体系下的 RAM 也不是线性一致的：如果一个核上的某个线程往某个内存地址中写了一个值，稍后另外核的一个线程读取该地址，并不一定能读到刚才的值。 这是因为每个 CPU 都有自己的缓存（memory cache）和缓冲区（store buffer）。一般缓存通常说的是读取，而缓冲区通常针对写入。线程的内存访问会首先落到缓存里，所有对于缓存的更新会异步同步到主存中。缓存访问的速度要（ns 级别）比内存访问（百 ns 级别）快几个数量级，由于可以用来弥合寄存器和主存的访问鸿沟，因此是现代 CPU 架构高性能的基石。但一份数据存了多个副本（比如主存中一个，一些 CPU 缓存中各有一个），且是异步更新的，导致线性一致性被破坏。
为什么会做此种取舍？当然，我们不能用 CAP 来进行考察，毕竟我们通常认为单机系统内的通信是稳定可靠的，并且某个 CPU 如果和系统其他部分断开连接也不可能独自工作。此处牺牲线性一致性的真正原因在于——性能，而不是容错。当然，单机系统都会提供一些同步手段（比如锁），来强制同步相应变量到主存。从而允许用户在关心一致性超过性能的地方，自行进行取舍。
很多分布式系统选择不提供线性一致性的原因也在于此：是为了提升系统性能而非进行容错。在任何时候，提供线性一致性都会严重拖慢系统。而非在网络故障发生时，才需要对线性一致性进行牺牲。
我们能找到一种更高效的实现来让存储服务提供线性一致吗？遗憾的是，暂时没有。Attiya 和 Welch 证明了，如果你想要保证线性一致，读写请求的响应时间是正比于网络延迟的。在一个具有高度不确定性的网络中（参见超时和无界延迟），线性化的读写请求的响应时间不可避免的会很高。提供线性一致性保证可能没有更快的算法，但是我们稍微放松一致性，就可以设计出一个更快的系统。这种取舍在对延迟敏感的系统非常重要。在第十二章中，我们会探讨一些即使不提供线性一致性，但仍然可以保证正确性的一些方法。
谢谢你读完本文(///▽///)
如果你想尝鲜图数据库 NebulaGraph，记得去 GitHub 下载、使用、(^з^)-☆ star 它 -> GitHub；如果你有更高的性能、易用性、运维实施等方面的需求，你也可以随时 联系我们，获取进一步的帮助哦~
