分布式学习：Sequential 和 Linearizability
概述
在分布式理论学习中碰到这几个名词：顺序一致性（Sequential Consistency）、因果一致性（Causality Consistency）、线性一致性（Linearizability Consistency）。这些名词除了读起来拗口外，理解起来也容易不明所以，很容易混淆。
本文是一篇读书笔记，目的是尝试说清楚这些概念的前因后果。
正确性和一致性模型
程序正确性（Correctness）研究
初学计算机时就接触了程序是数据结构加算法这个概念，认识了堆栈（Stack）和队列（Queue）各自特性和用法，并习以为常。从未对其正确性思考过。后来才慢慢发现这些都是由很多计算机科学家一步步探索证明过来。先从一个有趣的观点开始。算法可以描述为有限状态机，它有自己的初始状态（数据），能接受一些输入（操作）然后变成另外一种状态。Dijkstra在理论上分析证明在满足一定条件下，多种条件算法和循环算法等能够将初始状态推进到某个确定的状态。他认为程序的正确性是可以在不运行的前提下就能证明的。计算机硬件的发展比软件快，有关并行的研究先是硬件方面的。如就多核CPU从内存取数据策略的研究。支持多进程（包括多线程）让编程的复杂度变得很大，有关在并发下程序的正确性研究也多起来。
Sequential 和 Linearizability 概念开始都是跟并发（Concurrency）编程有关的，这些结论同样适用于分布式下。
一致性模型（Consistency Mode） Read Your Write
正确性是对算法的要求，首先是从符合人的认知开始的。比如程序有段代码逻辑是向一个变量写入一个值，然后读取它还是不是刚才写入的值。大部分人的直觉就是必须是，否则程序岂不是乱套（不可靠）。这个直觉认知就是我们对计算机的一种认知模型（也叫一致性模型），这里是READ YOUR WRITE（简称RYW），指写入一个值随后能够读出该值。我们认为应该如此，但实际计算机未必如此。是否如此是由人设计的。而实际上在多核CPU架构下这个代码未必就符合RYW。其原因是多核CPU时，计算在执行程序指令（机器指令）时可能会存在一个CPU在执行写指令时要等待，另外一个CPU就执行了下一个读指令。（这是因为内存有多个Port，每个Port服务其中一个CPU，CPU对内存的请求并不是严格顺序处理的。）
RYW 是一种一致性模型。当我们要求程序符合RYW时，实际结果分析也是这样的，那么我们就说这个程序是正确的。RYW一致性的关键就是执行指令时是顺序的。所以要满足这个一致性模型是要对底层内存模块提要求的。比如说临时禁止CPU指令读取优化，或者强制CPU对内存请求走FIFO队列完成等。所以一致性模型就是一种要求或者标准，方便计算机的上层应用在实现自己逻辑时不用考虑不符合当前期望的场景。
可线性化（Linearizability）
操作（Operation）
操作可以是具体的方法、一句代码或者指令。上面在讨论读写操作的时候，是把它当成瞬时完成，但实际上操作的执行都有一定时间。最快的是CPU的指令消耗时间，可能1ns不到，其他就在几十ns或者ms以上。在单进程下，可以忽略操作的时间；但是多进程并发下，这个就不能忽略。
所以操作会有两个特性：
每个操作会有请求（Invocation）和响应（Response)两个事件，并且Invocation发生时间一定比Response小。
每个操作生效时间会在Invocation和Response之间。
操作是跟对象（数据结构）有关的，有这两个特性就可以对多个对象上发生的多个操作的行为特征进行推理。以队列（Queue）为例，FIFO，有操作入列（Enqueue）和出列（Dequeue）。如先入列一个x再出列，两个操作记为：Q Enq(x); Q OK(); Q Deq(); Q OK(x)。其中Q 是对象名， OK 是Respnse事件（不考虑操作失败情形），操作（）里是参数。
操作在物理层面不一定是原子的（Atomic）。C语言一行代码可能会被编译为多个汇编代码，一行汇编代码可能是多个CPU指令。在最底层硬件会提供原子特性的操作（不管它是一个指令还是多个指令操作）。但是在效果上，每个操作是原子的。Atomic也算是一种一致性模型，是上层所有模块正确性最基础的保障。
顺序操作（Sequential Operations）
两个操作是顺序操作的条件是两个操作是顺序执行的，形式化描述是前一个操作的响应时间小于或等于后一个操作的请求时间。顺序操作之间没有重叠。
并发操作（Concurrent Operations）
当两个操作不是线性操作的时候，就是并发操作。此时操作之间有重叠。由于每个操作的生效时间是处于其Invocation时间和Response时间之间，并发操作的困难就在于难以确认操作生效时间的先后关系。
历史（History）
一序列操作的Invocation和Response事件就组成一个历史（History），History是操作事件的集合。引入集合概念是为了方便后面分析History的特性。历史中如果涉及到多个进程P1,2，则用 H|P1表示其中一个子历史（Subhistory）。
根据操作的特点，历史也分为两类。
顺序历史（Sequential History）
顺序历史指历史中的操作都是顺序操作（有先后关系）。形式化描述就是两个条件：
历史的第一个事件是Invocation事件。
每个Invocation事件后跟着对应操作的Response事件，每个Response事件后跟着后续操作的Invocation事件。
条件2的前一半是在说调用一个操作时一定会等这个操作结束才会继续执行。表面上看这简直就是一句废话，实际上这也是计算机正确性的一个保障。这里描述的一致性模型就是顺序一致性（Sequential Consistency）。
如果历史H的某个事件是Invocation但缺Response事件，则补齐一个Response事件，形成新的历史H‘。这个主要是方便后期分析。
并发历史（Concurrent History）
一个历史中存在并发操作则是并发历史。还是这个图。
H 不满足顺序一致性，但是H|P1和H|P2满足；反过来说就是即使两个历史满足顺序一致性，它们的组合不一定满足顺序一致性。这就是顺序一致性模型的局限性。
合法的顺序历史（Legal Sequential Histories）
一个顺序历史如果结果违背常识则是非法的。如发生在队列（Queue）上的历史，其特点应该是先入先出。如果不符合这个特点就是非法的。
表 1: FIFO队列上的合法顺序历史 H1 和不合法的顺序历史H2.
Sequential History H1 (legal) | Sequential History H2 (illegal) | |
q Enqueue(x) | q Enqueue(x) | |
q Ok() | q Ok() | |
q Enqueue(y) | q Enqueue(y) | |
q Ok() | q Ok() | |
q Dequeue() | q Dequeue() | |
q Ok(x) | q Ok(y) （非法） |
单看历史H1和H2都是顺序历史。H2最后应该返回x。
这里会有个疑惑，为什么会出现不合法的顺序历史？这个就跟Dequeue实现有关。Dequeue的内部逻辑至少包含两步，一是读取最后一个位置，二是清理并返回最前面一个位置的内容。在并发下实现方法有问题就可能导致这个结果。具体什么问题可能不同的操作会不一样，在理论上都统一称为不合法的历史。
历史中的偏序关系
偏序是集合论里的概念。
在集合A里的一个二元关系R，若对A 里任意两个元素x，y，都有xRy或者yRx成立，则称R是全序关系。若在A里只有部分元素x，y有xRy或yRx成立，则称R是偏序关系。比如说实数集合里的小于或等于关系就是全序关系，而复数集合里小于或等于关系就是偏序关系。下图中节点间有箭头表示有关系。
在一个并发历史里，可以衡量先后关系是全序还是偏序。还是下面这幅图
A和B的生效时间谁先谁后是不确定的，所以A和B 没有先后关系，但是A和C有先后关系，A比C先发生（Happened Before），表示为A->C。同样也有B->C。也有的文章表示方式是： A <H C, B <H C
对于一个并发历史，我们不能对全部操作排序（分出先后），但至少能对部分操作排序。偏序关系就是用来描述这个特征的。
假设我们能对并发历史的全部操作排序（分出先后），则这个关系在这个H 中就是全序关系。
可线性化（Linearizable）
一个并发历史H，如果满足下面两个条件，则称H为可线性化（Linearizable），或者H满足线性一致性（Linearizability）
历史H的补全历史H‘ 等价于某个合法的顺序历史S 。
<H ⊆ <S
S 也称为H的一个线性化历史（Linearization）。
条件1表示一个H可能线性化为多个不同的S，只要是合法的顺序化历史即可。而之所以可能线性化为多个合法的S，就因为该并发历史H可能是个偏序集合，其中有些并发操作的先后顺序可以有两种情况。如果H’是全序集合，则H也就不是并发历史，其自身就是个顺序历史。（关于等价原文没有给出定义）
条件2表示H中的偏序关系在S中依然存在。这个意思是对于H中那些确定先后关系的操作，在线性化历史S 里其先后关系依然是保持的。
可线性化（Linearizability）就是并发历史正确性的一个重要条件，或者是很强的一致性模型。
Linearization例子
还是上面那个并发历史的图，有两种线性化历史（Linearization），都是合法的正确的。
假设A和B 操作是Enqueue，C操作是Dequeue。
Linearization 1 | Linearization 2 | |
q Enqueue(x) P1 | q Enqueue(y) p2 | |
q Ok() P1 | q Ok() P2 | |
q Enqueue(y) P2 | q Enqueue(x) P1 | |
q Ok() P2 | q Ok() P1 | |
q Dequeue() P2 | q Dequeue() P2 | |
q Ok(x) P2 | q Ok(y) P2 |
虽然线性化（Linearization）存在着不确定性的部分，但它有着确定的特点，所以在并发编程里推断正确性有用。
可线性化的特点
Local 特性
Local指如果一个整体的每个局部模块都有某个属性，则这个整体也具备这个属性。可线性化也具备这个特性。
如果一个历史H的每个对象 H|x 都是可线性化的，则这个历史H就是可线性化的；反之亦然。Local的意义在于程序都是模块化开发，如果每个模块都是可线性化的，则这些模块的集合也是可线性化的。
非阻塞特性（NonBlocking）
在线性化（Linearization）中操作之间不会出现阻塞，一个请求不需要等待另外一个请求结束。
在原论文里这两个特性都给出了证明。
Linearizability 跟 Sequential Consistency区别
从Linearizability定义看，Linearizability多了一个特性就是保持了原历史H 中的偏序关系，即保持了非并发操作在全局中的顺序。而Sequential Consistency则没有这个要求。
不过在性能上Linearizability不一定总比Sequential Consistency差。
Linearizability 跟Serializability 区别
Linearizability的定义里有顺序化（Sequential），Serializability的定义里有串行化（Serial），导致这两个概念容易混淆。
Serializability是事务（ACID）特性的隔离（Isolation）级别，事务是有可能会读写多个对象的。Serializability保证不同事务在执行的效果跟串行化执行时一样的（前一个事务结束了后一个事务才开始，没有重叠）。Serializability没有local特性，不可组装。不保证事务彼此的顺序。它只是一个保证数据库正确性条件。
Linearizability是并发（Concurrent）或分布式中的概念，描述的针对单个共享对象的并发读写的正确性条件，它没有事务的概念，保证并发操作的真实顺序。
Linearizability中的操作都有原子一致性（Atomic Consistency，不允许操作并发），并且是CAP理论中的C（注意CAP理论在出现早期对推动分布式理论技术有帮助，在后期随着相关研究的深入，CAP理论存在很多问题）。Linearizablity还有local特性，是可模块化组装的。
尽管二者不是同一个领域，但是可以将Linearizability特性和Serializability组合一起提供一个最强的事务隔离级别 Strict Serializability。既保证了数据库事务的串行致性，又保证事务的真实顺序。 Herlihy and Wing 说Linearizability可以看作是一种特殊的Strict Serializablity，那时事务被抽象为一个对象上的单个操作。
然而除了Google Spanner声称实现了Strict Serializability特性外其他数据库还不支持这个。甚至连Serializability的支持不同数据库的实现细节和功能都不一样。
在数据库里还有个隔离级别是Serializable Snapshot Isolation。由于它读的时候读取的是快照（历史陈旧数据），所以它不是可线性化（Lineariazable）的。
无论是实现Linearizability还是Serializability，都是需要有协调，在性能上并不是很好。多核处理器默认也不是可线性化的，但是提供可线性化途径。
Linearizability 跟 Causality 区别
前面介绍的“先于发生”（Happened Before）的关系就是一种因果关系（Causality），是偏序关系。两个操作如果是并发的，则没有因果关系。Causality会在操作上加一个排序操作，但是并不要求所有操作排序，只是要求有因果关联的操作排序。对于没有因果关系的操作之间的顺序是任意的，所以Causality是比Sequential限制更少的一种一致性模型。
Linearizability比Causality限制更强，是全序关系，它蕴含了Causality，保证因果关系。但是Linearizablity并不是唯一可以保证因果性的方式。鉴于Linearizablity的实现成本，有些数据库实际实现的是因果一致性，这个通常也满足业务需求。在前文《数据库事务开发》中提到的WRITE SKEW现象就是违背了因果关系，Causality一致性是解决WRITE SKEW问题的另一种方法。
Linearizability在数据库中用途
本节是对Linearizablity另外一个角度（数据库角度）的分析总结，前面主要是并发角度的分析。两者可以独立理解，如果感觉混淆了那以前面的观点为主。
多副本与Linearizablity
Martin Kleppmann对Linearizability的介绍是从保证数据多副本强一致性的角度出发，要求当对一个数据修改提交后，随后所有的读操作都应该能读到这个数据。Linearizability是数据最新的保证，应用程序不需要担心读到陈旧数据。
先看一个数据库里不符合Linearizable的例子。
这实际是数据库中一主两备读写分离常用的方法。主副本写入一笔数据提交了，但是两个备副本同步数据的速度有快有慢，导致一个后发起的查询反而看不到已经提交的数据，从而跟另外一个查询结果不一致，也跟写的结果不一致。这个就是违背Linearizability。不过并不是所有的多副本同步都是这样，取决于同步使用的协议。
数据库中的并发
Linearizablity在数据库里要求很简单，就是当一个写提交后，随后的读操作都能读出最新值。当一个读操作读出了一个记录的最新值时，随后的读操作就不允许读到陈旧的值，除非是在它读到之前数据又被写回老值了。否则就是违背Linearizable。
如上图，读写操作也都是需要时间的。当操作是并发的时候，并不能确定两个并发操作的生效时间的先后顺序。但我们知道实际肯定会有个生效时间。途中的线条就是实际生效时间的先后顺序图。这样的一个顺序就是这组操作历史H的一个Linearization。
备注：1. 图中的cas是一个compare-and-set操作。2. 图中每个操作都是独立事务。3. Client B最后一个读操作读到了旧值（Stale），这个不符合Linearizable。
跟前面一样，这里在提操作先后和生效时间先后时只是说了一种结果，并没有说怎么判断。这涉及到分布式中另外一个重要话题——时间和事件顺序。以后再单独总结。
数据库中Linearizability例子
数据库中有一些对象和操作的设计体现了Linearizable特性。尤其是在分布式数据库下，支持Linearizable技术上会变得复杂。
锁和选主
锁的设计必须是Linearizable的，通俗的解释是锁是加在最新数据上的，加锁是顺序执行的。（当然数据库发展了很多可以彼此兼容的锁，以尽可能的提高读的操作并行。但是对写操作还必须是线性化的）。
唯一约束和唯一索引
唯一约束和唯一索引要保证数据唯一，也必须在最新数据（包括未提交）判断。所以唯一约束和唯一索引也要可线性化。
后记
程序从单进程顺序执行到并发执行，可能会出现多种结果不可预期。各种一致性模型就是为了从其中梳理出符合我们特定期望的模型。这些模型在特定场景下都是正确的。Linearizablity是一种要求很强的一致性模型。理解这个目的是为了识别应用和数据库中哪些设计是符合Linearizable，哪些是不符合的，以便应用用最小成本实现业务需求，同时又规避问题（BUG）。
本文中在总结偏序关系时并没有说明怎么判断分布式下不同节点的操作之间的先后顺序。这个涉及到分布式中很重要的概念——时间。后面有时间再总结。
参考
Dijkstra. “EWD249_Notes on structured programming“
Leslie Lamport. "Time, Clocks, and Ordering of Events in a Distributed System"
Leslie Lamport. "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs"
Herlihy, Maurice P.; Wing, Jeannette M. (1990). "Linearizability: A Correctness Condition for Concurrent Objects"
Peter Bailis，"Linearizability versus Serializability"，"http://www.bailis.org/blog/linearizability-versus-serializability/"
http://www.calebgossler.com/notes/
Martin Kleppmann. “Designing Data-Intensive Applications”
推荐阅读：说说数据库事务开发（上）