最近仔细研究了下CockroachDB的相关文档和paper，感觉在市场上众多的NewSQL分布式数据库系统中，它对于数据的一致性追求应该是最为极致的，由此也回顾了下分布式系统下，所谓的一致性相关概念，由于每次思考起这个东西总感觉有些烧脑，经常会反复走入同一个思维误区，这里感觉记录下自己当前的理解，个人感觉应该是准确的，如果大家看到不对的地方欢迎指正。
背景
历史上，数据库和分布式系统是两个不同的研究群体，他们各自形成了对于数据一致性(Consistency)的不同理解，这也是为什么大家会经常感到迷惑的原因。这里先大概说一下
- 数据库研究群体主要关注的是在单个主机的情况下，多个并发事务同时操作的情况下，如果保证数据库系统中数据项的一致性，包括：物理上数据不被破坏，数据的约束（唯一性约束，引用约束），或者业务约束（x + y == 10) 不被破坏。
- 分布式系统主要关注在跨网络相互连接，且数据有多副本复制的集群中，对于逻辑上单个数据项（可能有多个物理副本）的操作，能否和单机系统中对于单个数据项操作的效果一样，始终看到正确的符合操作顺序的数据结果。
随着互联网和大数据的兴起，这两个研究群体在不断融合，而关于数据一致性的问题又进一步变复杂了，现在问题变成了，在一个分布式集群中，并发执行若干事务（多个数据项的操作集合），系统最好能同时满足以上两类一致性的要求。
这篇文章会先从分布式系统的一致性说起，我们先简化问题，考虑单个数据项（比如单个Key)的操作，再扩展到事务系统，最后看下业界不同系统实现的情况。
分布式系统的一致性问题
在单机环境下，如果有两个线程并发操作同一个内存地址的数据（对齐读写保证操作原子性），底层的操作系统内核和硬件协同可以保证，对于该数据的并发写入不会冲突，且两个写操作的执行顺序和他们在物理时间上的顺序一致。这一点非常重要，正是有了这种操作原子性和顺序性的保证，程序员在编写代码时可以做出一些很明确的假设：
假设线程1先执行 x = 2，线程2后执行x = 3，最后线程3读取x一定得到3。
可以看到先 -> 后 -> 最后这个几个关键字，这隐含表示了操作间的顺序和物理时间顺序是一致的！！
到了分布式系统中，前面这种看起来想当然的事情就不那么容易了，因为节点之间产生了通信，而通信是要有时间消耗的：
如果光具有无限大的速度，我们可以认为任何通信都在瞬间完成，那么可以达成和前面单机中一样的效果：
t1下发的 x = v1的操作瞬间完成并返回了，t2、t3时刻也依次完成了操作，很明显操作执行的顺序和物理时间顺序是一致的。
不幸的是，现实情况可能是这样：
从start -> end之间的锥形（参见DDIA）描述了操作的发起和响应过程。可以看到操作1的[start1 -> end1] 和 操作2的[start2 -> end2]之间是有重叠的，由于网络延迟等因素，根本无法确定两个操作的先后顺序，但是[start1 -> end1] 和操作3的[start3 -> end3]之间则没有overlap，很明确的是，物理时间上操作3一定是在操作1完成后才发生的，那么作为最接近单机一致性的要求，我们可以要求操作3产生的效果也一定在操作1之后，这个要求就是所谓的线性一致性(linearizability)，即：如果一个操作op2的开始是在另一个操作op1的结束之后，则系统应该观察到的效果是op1先生效，op2后生效。
上面的例子是针对单个key值的，但线性一致的定义并不限于只对同一个key的操作，比如操作1是针对key1，操作3针对key3，以上的要求仍然需要成立。
线性一致性是分布式系统所能达到的最接近单机系统的最强一致性模型(单机或者理想分布式（瞬间通信）下，操作是[t1 -> t1] [t2 -> t2]，不会重叠)。
注意这里有个思维陷阱：
从系统自身的角度，它看到了v2的写入是先于v1的，但由于实际的操作间隔有重叠，这两个操作的顺序并没有要求，也就是说，对于系统来说，并不是要求所有操作的顺序都和达到系统的物理时间顺序一致，只是操作1和操作3这两个事件之间由于有因果关系，顺序是要有保证的！
那么怎么能知道操作之间是否存在因果关系呢？答案是，系统无法知道，但它又被要求不能破坏这种因果顺序，因此系统能做的是，反向保守处理，通过避免操作的潜在重叠可能来建立所有操作间的全序，这么说可能有些抽象，看了下面的spanner和cockroachDB的例子就应该清楚了。
分布式系统的时间概念
很明显线性一致性和物理时间有着紧密的关联，而麻烦的是，一旦涉及到分布式系统，时间的概念就不再准确了，因为所有的节点并不共享一个全局的物理时钟，假设每个node都能看到一个假想的，挂在某个位置的时钟，那跨越节点界定不同事件的实际顺序也非常容易，但这东西并不存在，不过思路确实是朝着这个方向的，人们希望能有方法尽量接近“全局统一时钟”。
Timestamp Oracle
这是最显而易见的思路，也是最简单的，任何操作都要先到一个统一的节点上获取时间戳，只要这个节点可以保证自身分配的时间戳单调递增，那它就是那个“全局共享时钟”，但缺点也很明显，首先是单点瓶颈，其次任何操作都要先和它交互，这会增加round trip的延迟，如果这个全局唯一节点是部署在不同region，这个延迟在实际应用中很难接受。
TrueTime
这个google spanner采用的方案，倚仗google强大的软硬件基础设施能力，利用原子钟和gps交叉同步，google建立了人类最接近“全局共享时钟”的分布式时钟机制，不同节点上的时间戳的偏差最大只有7ms。
软件同步时钟
TrueTime是硬件保障的时钟同步机制，而如NTP或者Amazon Time Sync Service这样的软件同步机制，虽然远远达不到相同的误差精度，但其思路也还是一致的：尽可能使各节点上的时钟偏差在一个有界的范围内。
一旦有了某种形式的时钟，我们就可以结合MVCC为数据的操作打上一个时间戳(timestamp），不同操作产生不同版本的数据，用这个时间戳描述数据的产生时间，从而界定操作之间的顺序和数据的可见性。
扩展到数据库系统
前面已经描述了分布式系统下，单个数据库对象的操作语义，而且数据库领域，事务是针对多个数据项的操作的集合，事务的ACID特性要求每个事务的操作要么全部发生，要么全部不发生。
对于事务来说，可串行化(serializability)是最为严格的一致性语义，即事务的执行虽然实际是并发的，但其执行效果等价于事务以某种串行的顺序依次发生。可串行化可以阻止所有并发事务造成的异常情况(anomalies)，从而保证数据的正确性（一致性）。
那么在分布式数据库系统中，涉及到分布式环境下的最强的一致性定义又是什么呢？首先我们仍然需要串行化的隔离级别，这样可以保证每个事务就可以视作是原子性的操作。然后就是事务（原子性操作）之间的顺序又该怎么规定呢？和单对象操作一样，如果事务1结束后，事务2才开始，那么可以系统要求看到的操作顺序也是： 先看到事务1生效，再看到事务2生效。但如果两个事务的执行间隔是有重叠的（从发起者的角度，类似上图的[start1, end1]和[start2, end2]），则对两者的执行顺序不做要求。
这里我觉得CockroachDB的strict serializability是一个非常不错的术语，感觉linearizability更适合描述传统分布式系统中单对象的操作行为，而strict serializability更接近事务serializability的含义，在可串行化调度的基础上，进一步约束的事务的具体顺序与物理时间之间的关系，但本质上两个术语可以认为是等价的。
业界各类实现方案
TiDB
TiDB采用了最为简单的Timestamp Oracle的方案，因此在扩展性和跨地域部署上受到了很大限制，目前TiDB5.0的全球数据库并不具有真正意义上的跨地域写入能力。
Spanner
Spanner自然采用了TrueTime的基础设施，由于不同节点间，在时间戳上的最大误差就是7ms，因此其采用了commit wait的方式，来保证完全的strict serializability。（google称为外部一致性，表示系统能够遵从系统外部的因果事件的先后顺序，也是很贴切的术语）
commit wait的原理其实很简单，如下图：
假设事务1在t1这个时间戳时可以提交了，由于节点上的时间戳是有不确定区间的，实际的物理时钟可能在第1个区间内的任意点上，那么如果在t1时间戳上立即向客户端返回commit成功，客户端收到后立即下发第二个事务，那么从线性一致的角度，这个事务2的时间戳一定要大于t2，这样系统才能判断出事务2是在事务1之后。
为了避免出现图中虚线的情况，事务1在t1确定提交后，要等待一段时间，也就是到t2这个时间戳，这时再向客户端返回committed消息，这样后续新到达的事务，其时间戳一定在t2之后，避免了不确定区间的交集，保证系统可以正确判定事务1/2的先后顺序。
CockroachDB
CRDB没有google那么强大的财力和基础设施，采用了NTP这种“穷人版”的TrueTime + HLC的混合时钟方案，关于HLC这里不具体展开，有兴趣的同学可以去参考其paper和相关资料，HLC可以提供几个重要的特性：
- 本质上仍是lamport时钟，通过交互消息，保证节点上的时间戳可以捕获系统内事件的因果关系
- 保证每个节点上的时间戳是单调递增的
- 保证不同节点间的时间误差是有界的，只不过这个误差很大，默认是500ms
由于误差区间（不确定区间）太大了，如果也采用commit wait，明显是无法接受的，因此CRDB做了些妥协，不再追求全局范围内strict serializability，但可以保证针对单个key（对象）操作的linearizability，具体如下：
对某个数据项K的设置，先后由两个gateway node(用户请求的接收节点）来执行，这里假设node2是在用户受到操作1的结果后才发起的，也就是两个操作间具有因果关系，顺序必须是操作1 -> 操作2，但由于前后两次操作来源于不同节点node1,node2，其上的时间戳t1,t2可能存在不确定性，具体来说：
t1对应的真实时间区间是[t1 , t1 + max_offset]， t2的真实区间是[t2, t2 + max_offset]
- t2 > t1 + max_offset，则可以确定t2对应的物理时间一定在t1之后，其顺序满足操作1,2之间的因果关系
- t2 <= t1 + max_offset，则无法确定t2和t1在物理时间上的先后，此时CRDB的处理方式是，把操作2的时间戳向后推迟到不确定区间之后，从而保证操作2一定被系统视为在操作1之后，保证了操作的因果顺序。当然如果操作2是在一个更大的事务内部，则这种推迟还可能有其他副作用，但单就这个写操作来说，这样并没有问题，本质上等价于以新的时间戳重新执行了这个操作。
- t2 < t1，显然只要node1/2之间的时钟误差在0 -> max_offset这个范围之内，这种情况不会发生
通过以上的分析，我们可以看到CRDB可以保证单个key操作的线性一致性，即使系统中各节点间存在一定的时钟误差。这其实已经做到了在CAP理论中所描述的Consistency的要求，也就是对于数据的读取是no stale read的。
推广到多key操作的事务，由于CRDB只采用了serializability这种最强的隔离级别，每个事务都具有唯一的读写时间戳，这个时间戳也决定了事务串行化执行的顺序，那么如果两个事务操作的read/write set在key上有交集，由于以上的机制在该key上成立，就保证了这两个事务的时间戳也满足线性一致的要求。
虽然已经非常接近了，但这还不是全局的strict serializability，一旦两个事务在读写集合上没有交集，就无法对他们的时间戳建立约束，因此无法保证其因果顺序不被破坏，例如如下例子：
- client3 发起事务 select * from t1，未得到结果
- client1 执行事务 insert into t1 values(1)，然后commit成功返回
- client2 执行事务 insert into t1 values(2)，然后commit成功返回
- client3 的执行结果返回
由于client1 / 2的操作没有交集，他们的事务顺序在系统内无法保证和物理时间顺序（因果顺序）一致，而client3的读操作又和事务1/2之间没什么因果关系，因此client3读到什么结果都是有可能的（只有1 只有2 都没有 1,2都有）
但如果是如下执行序列：
- client1 执行事务 insert into t1 values(1)，然后commit成功返回
- client2 执行事务 insert into t1 values(2)，然后commit成功返回
- client3 发起事务 select * from t1 并得到执行结果
虽然1,2之间没有顺序保证，但读事务3与1,2各自有数据交集且有因果顺序，因此可以保证：3一定读到1且3一定读到2。
考虑到CockroachDB作为一款跨地域部署的分布式OLTP数据库系统，其对数据的正确性和一致性的追求还是非常值得敬佩的，而且也采用了大量的技术优化来提升事务的吞吐，降低延迟，这样就在保证了尽可能强的一致性语义的前提下，尽可能的给出最佳扩展性和性能。
总结
基本描述了我对分布式系统的线性一致性的理解还有如何扩展到具有事务语义的数据库系统中，也大概介绍了下现在主流的几种OLTP系统的具体实现方案，包括时钟方案和提供的一致性语义级别，如果有理解不正确的地方，希望大家帮忙指正。
综合来看，小强DB在没有任何强大的硬件时钟方案的情况下实现了非常接近线性一致性的语义，可以说是非常牛逼了。
