分布式系统一致性的发展历史（一）

编者按：本文来自 “点融黑帮”（微信号：DianrongMafia）吴强，前盛大架构师，现在在点融网任首席社交平台架构师。专注分布式系统和移动应用，有十三年的开发经验，目前在点融做最爱的两件事情：写代码和重构代码。

分布式系统是一个非常有趣的话题, 在我之前的几年工作当中发现很多开发人员在评估和使用分布式系统的时候比较关注 benchmark 和高可用性, 但经常不太关心分布式系统的一致性问题, 所以我打算在业余时间花点时间写这样一个系列文章来帮助开发人员更好的理解一致性问题.

1. 前言

在一个理想的世界里, 我们应该只有一个一致性模型. 但是多路处理器和分布式系统中的一致性问题是一个非常难以解决的问题. 当系统大多还都是单体应用, 处理器性能提升还是靠缩小晶体管体积的年代, 一致性问题还不是一个非常大的问题, 但是从 90年 代开始, 互联网公司大量出现, 互联网公司处理的数据量远远超过了人类历史上任何一个时期的传统企业所需要处理的数据量, 大型的互联网公司甚至开始自己采购零部件自己组装服务器, 服务器市场上排名除了 IBM, HP 之外还出现了 “Others”. NoSQL 已经被互联网公司广泛接受, Micro Service 的出现让数据和计算的分布比历史上任何时期都更加的水平, 在这个背景下, 分布式系统给一致性问题带来了巨大的挑战, 理想情况下的一致性模型在分布式系统中几乎无法实现, 所以我们不得不设计应用于不同场景的各种一致性模型.

实际上在互联网蓬勃发展之前, 有些有远见的科学家们从 70年 代就开始在多路处理器级别上研究一致性模型. 过去的 10年 间, 计算机处理器的速度提升越来越困难, 摩尔在 1965年 告诉我们 12 个月晶体管密度提升一倍, 计算性能提升一倍 (1975 修正为 24 个月), 但是 2002年1月Moore 在 Intel 开发者论坛上提出 Moore’ s Law 预计会在 2017年 终结, 一旦晶体管体积进入皮米级别, 晶体管将不得不接近原子大小, 我们很快将无法突破物理的基础限制. 事实上从 2012年 开始晶体管密度和主频速度的提高速度明显放慢. 人们不得不开始转向横向伸缩, 提高处理器的并行处理能力. 下图显示了在 2012年 出现了晶体管体积缩小速度的突然放缓.

图片来源: futuretimeline.net

而这个过程中, 一致性问题逐渐愈发重要. 本文的目的就是带你回顾从 70年 代起, 到如今百花齐放的分布式系统中一致性问题的发展和演化. 你可能已经了解了某些一致性模型, 本文会帮你把它们按照发展历程穿连起来, 如果你对一致性模型了解很少, 本文可以帮助你从一千英尺的高空俯瞰一致性问题, 通过非数学的语言, 结合工程中的例子, 帮你入门. 这个系列的文章可能需要你放慢阅读速度, 如果有些地方看不明白或者想更深入的探讨, 你可以去查阅所引用的论文. 由于过程仓促, 难免有疏漏和错误, 还夹杂着个人观点, 如有错误欢迎指出: daniel.y.woo@gmail.com.

本篇文章作为本系列的第一篇文章将会介绍 1978年 提出的 Lamport Clock 对分布式系统的启发, 1979年 提出的 Sequential Consistency 和 1987年 提出的最重要的一致性模型 Linearizability.

2. 开天辟地：时间，时间和顺序，1978

狭义上的分布式系统是指通过网络连接的计算机系统, 每个计算节点承担独立的计算和存储, 节点之间通过网络协同工作, 因此整个系统中的事件可以同时发生. 一致性不是简单的让两个节点最终对一个值的结果一致, 很多时候还需要对这个值的变化历史在不同节点上的观点也要一致. 比如一个变量 x 如果在一个进程上看到的状态是从 1 变成 2 再变成 4, 最后变成 3, 而另外一个进程看到的状态变化是 1, 4, 3, 那么根据应用的场景, 有可能没问题, 也有可能会有严重的问题. 各个节点观察到的顺序不同是因为计算机网络绝大多数都是异步的, 尽管单个 TCP 连接内可以保证消息有序, 但是一旦网络出现问题, 你会不得不重建 TCP 连接, 而多个 TCP 连接之间的消息没有顺序约定, 异步网络的延时和顺序还是没有保证的, 你不能简单的以接受到消息的时间作为事件的顺序判断的依据. 在多路处理器上也有同样类似的一致性问题, 因为多个处理器或者处理器核心之间也需要面对不可预料的事件顺序问题. 所以, 一致性并不是一个简单的问题.

举个现实的例子, 比如你有两个数据中心, 你通过 DNS 解析把用户分别引导到离用户最近的数据中心, 然后数据中心之间做双向数据同步. 但是如果用户使用你的系统的时候前后两个写入正好发生在切换网络的时候 (或者更换了代理服务器, 或者换了手机操作, DNS 解析调整, 等等), 那么用户可能会把两个请求写入了两个数据中心. 因为两个数据中心没有办法保证时间精确同步, 网络的延迟也很大, 这两个写入操作的时间顺序就非常重要, 想要合并和同步这两个写入操作并不是那么简单的. 如果这两个操作之间是有因果关系的, 比如第二个请求是基于第一个请求的返回结果的, 那么这两个请求之间的逻辑顺序就非常重要.

要理解一致性模型, 先要理解分布式系统中的时间, 事件和顺序, 我们先来介绍事件发生的物理时间 (physical time), 逻辑时间 (logical time).

事件不是一个瞬间的事情, 它有一个起始和结束的时刻, 由于这个特性, 事件之间会有部分重叠. 比如下图中, A 和 B 两个进程或者节点分别对一个队列 enqueue 了 x 和 y, 然后再分别 dequeue. 你可以看到 enqueue 操作虽然是 A 先开始, B 后发生, 但是在时间上他们有重叠, 这就是并行, 二者之间的物理时间上顺序可以说是不分先后的, 但是两个 dequeue 的物理时间上一定是发生在两个 enqueue 之前的.

物理时间虽然很重要, 但是在分布式系统中物理时间很难同步, 有时候我们更关心程序的逻辑顺序. 从物理角度看当然事件 A 和 B 总是有先后顺序或者同时发生, 但是在分布式系统中你非常难判断两个事件发生的先后顺序, 无论是 NTP 还是原子钟, 都存在误差, 你永远无法同步两台计算机的时间, 不考虑重力和加速度对时间的影响, 在同一个物理时刻 t 发生了一个事件 x, A 节点在他的时间参考系内可能会认为 x 发生在 t – 1ns, 而 B 节点可能认为在它自己的时间参照系里 x 发生在 t+1ns 的时刻. 这 2ns 就是 A 和 B 不同步造成误差. 假设我们把模型缩小到单个计算机, 想象一下两颗 CPU 在主板上的距离如果有 3CM, 假设信号可以通过接近光速传递, 那么两颗处理器之间这 3CM 就要传输任何信息至少有 1ns 的延迟, 而两个处理器分别会有自己的时间参考系, 二者之间必然有差别, 从更宏观的角度来看, 在一个分布式系统中一个节点看到另外一个节点的计算结果, 就像我们通过天文望远镜看其他星系一样, 那已经是几亿年之前的历史了, 我们永远无从得知现在那个星系是什么样子, 甚至是否还存在. 所以依赖于物理时间我们是很难找到事件的顺序的. 两个事件的先后关系在分布式系统或者多路处理器系统中只能退化为先后顺序的偏序关系 (partital order), 有时候只要能找出两个事件的因果关系就行, 并不需要物理时钟, 有时候甚至因果关系 (causal relation) 都不重要, 本系文章后面要介绍的 PRAM 和 Weak Consistency 就不需要因果关系.

Leslie Lamport 是分布式系统一致性研究的早期科学家, 图灵奖获得者, 他在 1978年 的论文中提出了一个分辨分布式系统中的事件因果关系的算法, 后来大家把它叫做 Lamport Timestamp 或者 Lamport Clock. Lamport Clock 是一种表达逻辑时间的逻辑时钟 (logical clock), 它让我们能够把所有的历史事件找到偏序关系, 而且不仅在各自节点的逻辑时间参考系内顺序一致, 全局上的顺序也是一致的. 有人会问, 我用一个全局的锁服务来协同处理不就好了么, 干嘛搞一个这么复杂的东西, 其实不然, 全局协同服务有单点故障的问题, 另外全局锁是通过互斥 (mutal exclusion) 让整个系统串行化, 但是这样子整个系统就失去了并发能力, 而且某个进程的失效可能会导致整个系统进入等待状态. 那么有人问了, 如果允许并发不用互斥, 但是让一个全局的 scheduler 作为法官来根据他自己对整个系统的观察来决断事件的历史顺序可以么? 答案是, 也不行. 举个例子, 下图中 P0 假设是全局的 scheduler, 他作为法官一样来解读系统中事件的顺序. P1 如果发了一个事件消息 A 给 P0, 然后再发一个事件消息 B 给 P2, P2 接收到 B 之后再发一个事件消息 C 给 P0, 我们用 X->Y 来表示” X 早于或者同时于 Y” 的偏序关系,那么从 P0 的角度来看 A->C, 从 P1 看起来是 A->B, P2 看到的是 B->C, 由偏序关系的传导性, 我们知道事件的全局顺序应该就是 A->B->C, 没有冲突矛盾, 很不错对吧.

但是消息的传递在分布式系统中要经过网络, 在多路处理器中要经过 cache coherence 协议, 如果 A 消息耗时比较久, 在 C 之后才到达 P0 呢?

这时候, 从 P0 的角度来看 C->A, 从 P1 的角度来看 A->B, 从 P2 的角度来看 B->C, 看出来没, P1 和 P2 的观点还好, 但是 P0 和 P2 的观点就互相矛盾了. 如果 P0 和 P1 是正确的, 因为 C->A 并且 A->B, 根据传导性, 那么应该有 C->A->B, 也即是 C->B, 而 P2 看来 B->C, 他们的观点互相矛盾了, 结点彼此看到的全局顺序的不一致了. 有些应用场景可以接受这种情况, 但是有些应用场景是不能接受这种情况的.

由于网络是异步的, 系统之间的物理时钟是不能精确同步的, 所以这里的 P0 作为全局的 scheduler 永远无法知道基于物理时间的全局顺序是怎样的. 用一个 scheduler 就可以解决事件的全序集问题了么? 显然, 不行.

扩展一下这个例子到在实际应用, 你把 P0 想象成为一个 NoSQL 数据库的后端存储节点, P1 和 P2 作为客户端, 如果 P1 写入一个数据 A 到 P0, 然后 P1 又发消息 B 通知 P2 做一个耗时的计算, 让 P2 去把 A 消息经过一系列计算来验证 A 是否被篡改或者损坏过. 如果 P2 的验证计算结果表明 A 是正确的, 那么 P2 什么也不用做, 否则要去把 A 修复的结果作为 C 消息存储到 P0, 那么由于网络的延迟, 如果 P0 先收到了 C 消息, 后来才收到 A 消息, P0 按照时间顺序操作那么就会把错误的 A 替换掉正确的 C. 聪明的读者可能会想到 Riak 的 Vector Clock, 但是在那之前, 我们先来看看 Lamport Clock.

Lamport 在他的论文中举了一个例子, 下面的图中 P/Q/R 是三个进程 (这里的进程可以是多路处理器系统其中的一个处理器, 也可以是分布式系统中的一个节点), 从下往上代表物理时间的流逝, p1, p2, q1, q2, r1, r2 …. 表示事件, 严格讲这些事件因为有起始和结束过程, 应该是沿着时间线的一段加粗线, 这里为了简化, 缩小到了一个点. 波浪线表示事件的发送, 比如 p1->q2 表示 P 把 p1 事件发送给了 Q, Q 接受此消息作为 q2 事件. 假设 C 是 Lamport Clock, 并且是一个单调递增的计数器函数, 那么 C 应该满足任何两个事件 a, b, 如果存在偏序关系 (a 先于或同时于 b 发生) a->b, 必然有 C (a) < C (b).

图片来源: Time, Clocks, and the Ordering of Events in a Distributed System

为了满足这个 Clock 我们需要两个条件:

C1. 对于单个进程 Pi, 如果 a 发生早于 b, 那么 Ci (a) < Ci (b)C2. 对于跨进程的情况, 如果 Pi 发送 a 到 Pj 作为 b, 那么 Ci (a) < Ci (b)

要满足第一个条件 C1, 很简单, 只要 Pi 每次两个连续事件发生中都要递增 Ci 即可. 要满足第二个条件, 稍微麻烦点, 就是要 Pi 把 a 附带上自己的 Ci 传递给 Pj, 然后 Pj 要递增到 max (Ci, Cj) + 1.

这样刚才的图就可以变成下面的图:

图片来源: Time, Clocks, and the Ordering of Events in a Distributed System

横向虚线就变成了全局的 clock tick, 而每个进程的 clock 都是一致的. Lamport Clock 的作用就是找到 causally related 关系, 之后 1988年 出现的 Vector Clock 是一个更加实用的算法. 关于 Vector Clock, Riak 的工程师有两篇非常好的文章大家可以去看看 Why Vector Clocks Are Easy 和 Why Vector Clocks Are Hard). 这里受制于篇幅此处不再详细描述, 在后继介绍 Casual Consistency 的时候会给大家详细介绍. 对于 1978年 这篇论文有兴趣的同学可以去检索 Time, Clock, and Ordering of Events in a Distributed System. 这篇论文被认为是分布式系统的一致性问题的开山之作, 其中 max (Ci, Cj) + 1 这个单调递增的 timestamp 后来影响了很多的设计, 比如 Vector Clock, 比如一些 Conflict-free Replicated Data Types, Paxos 和 Raft 等. 这篇论文也是 Leslie Lamport 被引用最多的文章, 按照 Lamport 自己的说法, 这篇论文影响了后人对于分布式系统的一致性问题的思考方式, 而后基于人们对一致性, 性能, 实现难度之间的平衡, 产生了很多不同的一致性模型.

3. 理想的一致性模式

对于一致性, 我们需要不同的模型, 不同的级别. 理想的情况下任何事件都准确无误的” 瞬时” 对其他进程或者节点可见. 比如, 一个服务节点对某个状态的写入, 瞬时可以被另外一个服务器同步复制, 因为” 瞬时” 的要求, 即便是 Lamport Clock 本质上是个 Logical Clock, 而非 Physical Clock, 所以也达不到这个要求. 如果存在这样的模型, 我们不需要通过 Logical Clock 去找事件之间的因果关系 (causality), 事件的结束时间就可以解决事件的全序关系了. 有人称作这种模型叫做 strict consistency. 实际上, 这在现实世界上根本不存在这样理想的模型, 两个服务器无论是通过金属电路还是光学载体连接, 都会有传输延迟, 这是物理决定的, 物理时间在分布式系统中永远不可能同步, 因此我们对于一致性的时间要求必须降低, 比如 Linearizability (strong consistency) 或者 Sequential consistency. 实际中我们经常比较关心两个有因果关系的事件的顺序而对于可以并行无因果关系的事件我们不太关心他们的顺序, 再考虑到并发能力和实现难度. 我们需要多种不同的一致性模型.

4. Sequential Consistency, 1979

Leslie Lamport 在 Lamport Clock 之后第二年1979年 提出了 Sequential Consistency, Leslie Lamport 的定义如下:

这看起来很晦涩, 我们用通俗但不严谨的语言来表述, 他蕴含了两个部分, 第一是事件历史在各个进程上看全局一致, 第二是单个进程的事件历史在全局历史上符合程序顺序 (program order).

第一个要求比较容易理解, 给个例子: 假设有四个进程 P0, P1, P2, P3 分别读取和写入一个变量 x, 横轴从左往右表示物理时间的流逝. 对于下图中 A 的情况这就是大家比较容易理解的情况, 这就是 Sequential Consistency. B 图中你可能觉得, 好像 P2 和 P3 读出来的 x 变量顺序和物理时间不一致了么, 但是对于 P2 和 P3 来说, 他们虽然对 x 的历史的顺序和真实物理时间不一致, 但是 P2 和 P3 至少” 错的一致” 啊, 所以只要 P0, P1, P2, P3 全体都认为 x 是先被 P2 写入的 2, 后被 P0 写入的 1, 那么我们认为这种情况仍然是一致的. 这样的一致性模型就是 Sequential Consistency.

如果像下面这样, 那么 P3 和 P2 互相就不一致了, 这就不能满足 sequential consistency 了.

如果对于 x 的两次写入都是发生在同一个进程, 比如 P0, 那么前面 B 的情况也不符合 Sequential Consistency 了. 为什么呢? 因为这样此 P0 就不符合 program order 了. 我们来看 Lamport 的定义中第二个方面关于 program order 的解释.

第二个方面对于没有多线程开发经验的工程师稍微难理解一些. 比如两个进程 P1, P2 上发生的事件分别是 1,2, 3, 4 和 5, 6, 7, 8, 如下图所示. 那么从全局来看我们必须要让事件交错成一个有序的集合. 从下图右边 global-1 的观点来看这样的交错和 P1/P2 是符合 Sequential Consistency 的, 但是 global-2 就不是, 其中 1,4,3,2 的顺序并不是 P1 的” program order”. 第一种情况中 P1 和 P2 的原始顺序在交错中仍然得到了保留, 这个过程叫做 arbitrary order-preserving interleaving.

不熟悉多线程编程的工程师可能会问, 为什么 P1 和 global-2 中对于 3 和 2 的顺序有不同的观点? 为什么 program order 还会变? 我这里稍微解释一下 CPU 读写内存的工作原理, 熟悉 C++/Java 内存模型的程序员可以跳过这部分.

下面是典型的志强两路处理器的样子. 每个处理器的每个 core 有自己的 L1/L2 cache, 所有的 core 共享 L3 cache, 然后两颗处理器之间通过环形 QPI 通道实现 cache coherence. 这样, 整个 cache 系统就成为了所有处理器核心看内存的窗口, 或者说是唯一事实.

处理器的一个 cycle 很快, 1ns 都不到, 而内存访问很慢, 需要几百个 cycle 了, 就算是最快的 L1 的访问也需要三个 cycle, 只有寄存器能跟得上 CPU cycle, 所以为了充分利用处理器, 在 core 和 L1 之间插入了接近寄存器速度的 Load Buffer 和 Store Buffer.

LB 和 SB 有多重方式可以提高处理器整体性能. 比如你对一个线程间的共享变量做密集的循环, 这个变量的 i++ 可能是发生在寄存器内或者 store buffer 内, 当循环结束的时候才写入 L1 cache, 然后通过 QPI 让另外的处理器看到变化, 在这个密集循环过程中另外一个处理是看不到这个变量的变化历史的. 还有就是如果你对三个变量写入, 那么三次内存访问需要大概 900 个 cycle, 如果这三个变量地址连续, 那么很有可能他们碰巧在同一个 cache line 里, 那么处理器可能会把三个变量先写入 store buffer, 稍后合并成一次写操作回到 L1 cache, 这就只需要 300 个 cycle, 这种优化叫做 write combine. Store Buffer 提升了处理器利用率但是会导致一个 CPU 的内存写入对另外一个 CPU 的读取显现出延迟或者不可见. Java 里面 volatile 就是放了一个 full memory fence 等待 write buffer flush 到缓存系统处理结束. (很多 Java 程序员认为 volatile 是让 CPU 直接访问主存来避免 visibility 问题, 这是错误的观点).

从另外一个角度看, 读取也有 stale 的问题. 因为解析地址和读取内存也是非常慢, 总共要几百个 cycle, 所以处理器会使用 speculative read, 说白了就是打乱指令顺序提前发 fetch 到内存, 然后干别的事情去了, 这样读出来的内容放在 load buffer 里, 处理器稍后真用这个变量的时候再去 load buffer 读取. 但是这样你会读到过期的数据. 要读到最新的数据, 也需要一个 memory fence 让之前 load buffer 内的数据被处理完.

所以, 处理器之间的可见性问题和乱序问题, 会让每个处理器对历史事件产生不同的观点. write combine 和 speculative read 再加上其他的优化会让处理器执行产生 reordering. (memory fence 会打破处理器的 pipeline 产生 stall, 目前的主流服务器处理器有 48 个 pipeline stages, 产生一次 stall 的代价非常高. 这就是为什么我们需要共享控制变量或者变量之间存在因果关系的时候我们才需要 memory fence, 这也是为什么我们需要将来会介绍的 Causal Consistency 和 Weak Consistency 模型.)

好了, 你现在明白了为什么 program order 会被 reorder, 现在回过来看看 Lamport 在他的论文中为了阐述 Sequential Consistency 而提出的这个有趣的小例子, 从一个更高层的角度, 程序员的角度来看第二个条件.

这看起来像是 Dekker 的 Mutual Exclusion 算法去掉 turn 变量的简化版, a 和 b 初始为 0, 分别是两个进程的控制变量来阻止对方进入 critical section, 如果系统满足 sequential consistency, 那么 process 1 和 2 是不能同时进入 critical section 的. 这两个进程可能都无法进入, 但是最多有一个进程可以进入. 但是如果系统不满足 sequential consistency 的第二个条件, 那么有可能两个进程同时进入这段 critical section. 你可能会问, 怎么可能? 如果你看明白了上面关于处理器访问内存的原理, 你会知道有可能进程 1 写入 a=1 被 write combine 延迟了, 或者判断 b=0 的那个读取被 speculative read 了, 那么两个进程就会同时进入 critical section.

Leslie Lamport 为此提出了如何实现 sequential consistency 的内存访问:

1) Each processor issues memory requests in the order specified by the program.

2) Memory requests to any individual memory module are serviced from a single FIFO queue.

第一点就是禁止 reordering, 第二点就是 FIFO 的内存控制器. 这样的系统可想而知, 会比我们今天使用的系统慢几百倍, 没有任何一款主流处理器能够达到 sequential consistency. 所以为了换取效率, 维护数据一致性变成了开发人员的责任, 系统只提供给你 memory fence, CAS, LL/SC 之类的基础工具. 无论你是 C++ 还是 Java 开发人员都要非常小心的使用线程, 其实即便是非常有经验的开发人员有时候也会在线程上犯错, 近年来出现的 lock-free 和 wait-free 的数据结构比基于锁的实现运行期更加动态, 更加难以正确实现, 出现了 bug 之后非常难解决. 所以我们必须深入理解一致性, 在设计的时候想清楚各种边际条件来避免多线程的问题.

早期一致性问题都是在多路处理器级别研究的, 但是往更宏观的分布式系统来看, 多个服务器节点的写操作也经常会有本地 buffer, 也会产生类似 write combine 的副作用, 这些问题在不同规模上看都是类似的.

大家或许注意到了, Sequential Consistency 对于时间不敏感, 只要存在一致的全序关系即可, 所以又出现了对时间敏感, 一致性强于 Sequential Consistency 的 Linearizability.

5. Linearizability, 1987

Linearizability 模型的一致性高于 sequential consistency, 有时候也叫做 strong consistency 或者 atomic consistency, 可以说是我们能够实现的最高的一致性模型. 它是 Herlihy and Wing 在 1987年 提出的. 通过前面的讨论我们现在知道 sequential consistency 只关心所有进程或者节点的历史事件存在唯一的偏序关系, 它不关心时间顺序. 而 linearizability 相当于在 sequential consistency 的基础上再去关心时间顺序, 在不依赖物理时钟的前提下, 区分非并发操作的先后. Linearizability 是一个很重要的概念, 如果你不了解它你就无法真正理解 Raft 算法等.

我们可以用一个高等数据结构比如队列来描述 Linearizability 的定义 (来源于 Herlihy & Wing). 假设 Enq x A 表示 A 进程开始尝试把 x 加入队列尾部, OK A 表示操作结束, Deq A 表示 A 进程开始从队列头部取出一个元素, OK y A 表示取出了 y 并操作结束. 下面左边是物理时间上的操事件顺序, 那么我们如果再最后面加一个 OK A 那么, 你会发现所有的事件的起始 / 结束都是成对的.

Enq x A, OK A, Deq B, OK x B, Enq y A

如果 H 能够通过追加 0 到 1 个事件成为 H’, 并且 H’ 中的事件是起始 / 结束成对的 (H’ 是 H 的完整历史), 那么 H’ 可以线性化为全序关系 S, 使得

1). S 中所有的事件起始 / 结束是” 紧挨着” 的, 事件具有原子性不可拆开.2). 并且一个事件 e0 的结束早于 e1 的开始, 那么这个全序关系在 S 中仍然存在.

那么在不违背队列的正确行为的前提下, S 就是 H 的一个 linearization. 下面的例子中, 最左边是物理时间上发生的 H, 中间是补齐成对之后的 H’, 右边是 H’ 的一个 linearization.

用通俗但是不严谨的话来说, Linearization 蕴含了两个特性, 第一, S 中的事件起始 / 结束是” 紧挨着” 的表示粒度上必须是整个事件, 事件之间不能交错, (就是假设一个调用的结束事件返回之前我们就认为事件已经完成了, 把并发的调用时间缩短来产生顺序关系). 第二, H 中全序关系延续到 S 中, 说明 S 仍然存在原始事件的物理时间的顺序. 如果你没看明白这么拗口的定义, 没关系, 看看下面这个图你就很容易明白了.

并不是所有的情况都是 Linerizable 的, 比如我们的队列行为是这样的:

1. Enq x A
2. OK A
3. Enq y B
4. Deq A
5. OK B
6. OK y A

因为 OK A 早于 Enq y B, 那么接下来的事件历史中 x 就应该比 y 早出来, 而这个例子中 y 先出来了, 这违背了队列这种数据结构的定义, 除非程序写错了否则不应该有这样的历史. 如果我们尝试满足那两个条件, 那么这个历史有两种排法:

Enq x A -> OK A -> Deq A -> OK y A -> Enq y B -> OK B

Enq x A -> OK A -> Enq y B -> OK B -> Deq A -> OK y A

但是这两个排法都违背了队列的 FIFO 行为, 这样的事件顺序不符合 Linearizable.

再给一个例子, 这个是可以的

1. Enq x A
2. Deq B
3. OK x B

首先补齐结尾的 OK A 变成 H’, 然后可以把 S 排成:

Enq x A -> OK A -> Deq B -> OK x B

你要是觉得这种定义很晦涩, 没关系, 用通俗的语言来讲, 就是 A 写入了 x 结束后, 接下来 B 一定能读出来, 这虽然不严谨, 但是确实是 Linearizability 的本质. 下图中从左往右是物理时间, 长条是指我们观察到的一个事件的开始和结束, 其中 P0 把 x 的值从 0 改写为 1. 长条是一个事件的时间窗口. 这个过程中如果 P1 去读取 x, 如果 P1 的读和 P0 的写在时间上有重叠, 二者是并发的, 那么 P1 读出来的无论是 0 还是 1, 都算符合 linearizability, 你认为 P1 的读事件发生在 P0 的写事件之前或者之后,都可以. P2 和 P0 之间也是这样. 但是如果 P2 的个读也发生在 P1 上, 那么两个读的结果必须要么 0-0, 要么 0-1, 要么 1-1, 但是不能是 1-0. 最后的 P3 因为起始晚于 P0 的结束, 所以要符合 linerizability 就只能读出 x=1 才行, 我们必须认为 P3 的读事件发生在 P0 的写事件之后.

当事件之间没有重叠, 中间有个” 小间隔” 的时候, Linearizability 必须给出明确的先后顺序. 而前面介绍的 sequential consistency 则不需要这样的要求, 如果上面的例子中如果 P3 读出来是 0, 那么也是符合 Sequential Consistency 的.

当多个事件之间有重叠, 他们实际是并行的, Linearizability 要求不管是不是并行的事件, 所有进程都必须给出一致的事件顺序, 这样所有进程都会对事件历史有完全同样的线性观点, 这就像是一个消除并行的过程, 所叫我们称之为做 Linearization. 一个历史可以有多种 Linearziation, 比如前面的例子中 P0 和 P1 的事件是并行的, 可以互换顺序, 所以这个历史至少可以有两种 linearization. 要所有进程都全局一致还需要其他的条件, 本系列文章后面要介绍的 Paxos 算法就是这样一个例子.

下面是 Herlihy 和 Wing 的论文中给出的例子, 大家可以看看, 哪些是符合 Linearizability 的?

图片来源: Linearizability : A Correctness Condition for Concurrent Objects

Linearizability 的两个很好的特性 Locality 和 Non-blocking, 有兴趣的同学可以自己去看看, 限于篇幅本文不再介绍了. 如果你的理解还有点不清晰, 下一篇文章中我们介绍 Paxos 算法的时候你应该能更好的理解它.

Linearizability 和 Sequential Consistency 你可以把它们想象成一个烧烤架, 上面有很多烤串, 你不可以把肉和洋葱在一个烤叉上互换位置 (单个进程需要符合 program order), 但是你可以拨动所有烤叉上的肉和洋葱, 让他们从左往右排列出来一个先后顺序. 不管是 Linearizability 还是 Sequential Consistency, 那么下面 A 和 C 谁在前面都可以, 因为 A 和 C 是并行的, 但是 C 和 B 在 Linearizabiltiy 中必须 C 在前 B 在后, 而 Sequential Consistency 中 B 和 C 的顺序可以互换.

这么看 Linearizability 和 Sequential Consistency 是不是很像? 过去绝大多数人会认为 Linearizability 的定义只是比 Sequential consistency 多了一个物理时间先后的约束, 所以认为他们很像, 甚至认为它们基本是一个东西, 性能也应该差不多. 但是后来以色列科学家 Hagit Attiya 和 Jennifer Welch 在 1994年 发表的论文让大家意识到他们其实是完全不同的概念, 性能差别很大. (Sequential Consistency versus Linearizabiltiy, ACM Transactions on Computer Systems, Vol 12, No 2, May 1994, Pages 91-122) 过去人们在探讨这两种一致性模型的时候没有真正分析过他们的理论上的性能差别, Attiya 第一次给出了具体的分析.

假设我们的网络延迟有一个上限 d (尽管现实中不可能, 这里纯粹做理论分析用), 那么最慢和最快的请求波动在 u 以内. 论文证明了下图中上半部分绿色四边形是 Linearizability 的性能根据读写比例从 u/4 到 u/2, 下面黄色三角形是 Sequential Consistency 的性能, 最糟糕不会超过 d * 2. 从性能角度来看, 二者的差别还是巨大的.

至于 Linearizability 的实现, 可以说是所有一致性模型里最丰富的了, 我们会在本系列下一篇文章中介绍.

如果你耐心看到这里了, 至此, 我们已经开了一个好头, 你一定是对分布式系统的一致性问题很感兴趣, 在本系列下一篇文章中我们将会提到 Linearizability 和 Sequential Consistency 的一些应用. 将来我们还会继续介绍 Casual Consistency, PRAM, Eventual Consistency 这些性能更好但是一致性更弱的模型, 所以, stay tuned!