CAP，ACID，我们能做什么

发表于 更新于 分类于

本文从CAP理论和ACID性质为切入点，讨论分布式（存储）系统的设计。

分布式系统，尤其是分布式存储系统，在进行设计考虑时，首先需要想到的就是CAP问题，即在C（Consistency）和A（Availability）之间如何进行取舍的问题。我在思考的过程中发现，尽管对于Consistency有着诸多分类，如Linearizability、Sequential Consistency、Causal Consistency，但是对于Availability却没有一个对应的分类。这有悖于对CAP理论的理解：我们降低了Consistency之后，能得到什么程度的Availability？更进一步的，我们降低了Consistency后，是否真的能够提高Availability？

CAP和ACID

我们之所以需要将一个单机系统扩展到分布式系统，主要原因有：

  1. 对性能的要求超过单机系统所能提供的极限

  2. 对Availability的要求超过单机系统所能提供的极限

对于前者，我们可以使用Shard的方式将负载分布到多个单机系统中。对于后者，我们在设计时必须考虑CAP理论的约束。

CAP

CAP理论的第一个较为正式的形式化表述和证明发表于论文[28]。CAP理论是针对于具有多个Replication的Single Data Object论述的，其模型类似于Distributed Shared Memory。其中P表示Network Partition Tolerance，由于目前一般的网络条件不能认为是可靠的，因此构建在这样的网络上的系统必须认为Partition是可能发生的，进而在CAP理论中不能放弃P而选择C和A，详细的论述见[55]。CAP理论中的C指Linearizability Consistency，其具体含义见下文中的Linearizability一节，我们此时先认为其是一种非常强的一致性保证。CAP理论中的A指的是100%的Read & Write Availability，非形式化的理解，在任意时刻对任意节点发起的（读或写）请求，无需等待与系统中其他节点通信的结果，即可进行“正确”响应。

由于Partition不是经常发生[11]，在这样的情况下，C和A是可以同时达到的。有趣的是，Google对于网络基础设施的持续改善，使得在他们的网络环境中，由于网络通信导致的问题的概率比由于Bug导致的问题的概率还低，此时甚至可以认为网络是可靠的[17]。但是在Partition发生时，我们必须在Linearizability Consistency和100% Availability之间进行取舍。

这样一来，就有一个关键的问题：如何判断是否正在发生Network Partition？实践中我们通常采用消息超时的机制进行判断，即如果两个节点之间的通信（即便经过一些重试）超时，则认为此时正在发生Network Partition。使用这种方法进行判断，我们会发现Latency和Availability是一回事。Latency低的时候，节点之间可以正常通信，从而提供Linearizability Consistency。Latency高的时候，我们认为发生了Network Partition，或者等待Latency降低到足以在Threshold内进行通信（Network Partition解除），即放弃100% Availability但是保证Linearizability Consistency，或者放弃节点间进行通信直接进行响应，即放弃保证Linearizability Consistency但是提供100% Availability。目前越来越多的系统即使在P没有发生时，也不提供Linearizability Consistency，其这样做是为了提供更高的性能保证。也就是说，在P发生时，我们在C和A之间进行取舍；在P没有发生时，我们在C和L（Latency）之间进行取舍。这样，CAP理论被扩展为PACELC理论（If there is a Partition, how does the system trade off Availability and Consistency; Else, when the system is running normally in the absence of partitions, how does the system trade off Latency and Consistency?），见[1]。

进一步考虑，我们之所以需要在C和A之间进行取舍，或者是在C和L之间进行取舍，其根本原因在于节点之间需要进行同步通信才能够保证C。极端情况下，我们可以使得整个系统无需进行同步通信，来达到极致的A和L。此时考虑一个写请求，在写入一个节点并收到成功确认后，如果该节点在和其他节点进行异步通信之前就发生了永久性故障，则这一写请求写入的内容将永久性的丢失。这说明Consistency和Durability在某种程度上是类似的[43]。

从一个更大的角度来看，在一个不可靠的分布式系统中，我们需要在Safety性质和Liveness性质之间进行取舍[29]。例如，Consistency是一种Safety性质，而Availability是一种Liveness性质。又例如，FLP问题[27]告诉我们在Consensus问题中如果有任意节点不可靠，则无法在保证Safety性质的同时保证Liveness性质。有关分布式系统中的Impossibility的重要问题有[15, 27, 28, 46]。

Paxos算法可以容忍系统中少数集合中的节点失效，直觉上，我们认为Paxos算法在系统级别提供高可用服务，同时提供了Linearizability Consistency。这似乎与CAP理论相违背。考虑CAP理论对于Availability的定义，要求对任意节点的请求都能立刻（read-time）得到回应。假设由于网络分区将系统分为了一个多数集和一个少数集，对于Paxos算法，尽管多数集中的节点仍然可以正确且立即回复请求，但是少数集中的节点不能。CAP理论这样定义有一定道理，因为在网络分区发生时，有可能客户端并不能访问多数集中的节点。

[37]提出了对CAP理论的一些批评和改进。考虑这样一个事实，Availability是服务的一个观测结果（Metric）而非系统的一个属性，而Consistency和Partition是系统模型，这两者并不能统一起来，CAP理论中对于Availability的定义是不严格的。Brewer在[16]中（非形式化的）提出，Availability和Consistency在CAP理论中并不是一个非0即1的离散变量，而是从0%至100%连续变化的变量。这与[28]中形式化描述CAP理论的工作是相违背的。这意味着我们有必要重新思考CAP理论的精确定义（形式化描述）。[37]中将CAP中的A定义为算法对Latency的敏感程度，将C定义为算法所使用的并发一致性模型，将P定义为Latency的突发增长。这样一来，A不再是对服务的一个观测结果，而是算法的一个本质属性；P的定义也能和A相结合。在这样一种框架下，最终一致性模型也能很好的进行建模和推理，最终得出结论，最终一致性的Replica算法在Partition永久性的发生时仍然能够停机。这与我们的直觉，使用最终一致性协议可以提高Availability一致。文中还进一步总结了达成三种一致性模型所需时间的下界（不确定是否是下确界），假设消息传播时间为\(d\)，见下表：

Consistency Level Write latency Read latency

Linearizability

\(\mathcal{O}(d)\)

\(\mathcal{O}(d)\)

Sequential Consistency

\(\mathcal{O}(d)\)

\(\mathcal{O}(1)\)

Causal Consistency

\(\mathcal{O}(1)\)

\(\mathcal{O}(1)\)

其中Sequential Consistency的读写延迟可以互换。

ACID

ACID性质指的是并行执行多个事务（Transaction）时需要保证的性质[33]：

  • Transaction Atomicity：组成事务的多个事件（Event）要么都成功要么都失败（all-or-nothing）

  • Database Consistency：执行事务的前后，数据库的状态保持（应用程序层面）一致

  • Isolation：并发执行的事务之间不互相影响

  • Durability：已经提交的事务中的事件不会丢失

ACID中的Atomicity和Concurrent Programming领域中的Atomicity意义完全不同，为了区分这一点我将ACID中的A称为Transaction Atomicity。同样的，ACID中的Consistency和Concurrent Programming领域中的Consistency也完全不同，但是ACID中的Isolation和Concurrent Programming领域中的Consistency有一定相关性。这里将ACID中的Consistency称为Database Consistency是因为ACID中的A、I、D是更底层的性质，而C是上层应用的性质，具体见[38]中的第7章。

两者区别

CAP理论更多的关注于分布式共享内存模型下对象的一致性问题和可用性问题，是传统Concurrent Programming领域在不可靠系统下的问题。传统Consistency的分类在[51]中有一个总结，其中比较常见的几种一致性模型从弱到强如下：

  • Read-your-writes/Monotonic Reads/Monotonic Writes

  • PRAM（即FIFO，等于上面三者的和）

  • Causal（等于PRAM和Writes-follow-reads）

  • Sequential

  • Linearizability

ACID性质是数据库系统中并发执行多个事务时的问题，是数据库领域的传统问题。ACID性质中的Isolation从弱到强有以下几个常见级别[12]：

  • Read Uncommitted

  • Read Committed

  • Cursor Stability

  • Repeatable Read

  • Snapshot Isolation

  • Serializable

Linearizability和Serializability

Linearizability是Concurrent Programming中Consistency的最终目标，Serializability是数据库事务中Isolation的最终目标，两者均在分布式存储系统中起到了重要的作用。

Linearizability

Linearizability是在具有多个副本的单个对象的情况下，对于并发操作的执行顺序约束。也可以认为是在给定的并发操作历史下，对于单个操作返回结果的约束。

Linearizability的原始论文为[35]，但是个人认为[45]的第16章更容易理解，此外[38]的第9章也给出了Linearizability的非形式化解释。

Linearizability的形式化定义如下[35]：

A history \(H\) induces an irreflexive partial order \(<_{H}\) on operations:

\[e_{0} <_{H}e_{1}\ \text{if}\ res(e_{0})\ \text{precedes}\ inv(e_{1})\ \text{in}\ H\]

A history \(H\) is linearizable if it can be extended (by appending zero or more response events) to some history \(H'\) such that:

  • \(complete(H')\) is equivalent to some legal sequential history \(S\)

  • \(<_{H} \subseteq <_{S}\)

直觉上理解，Linearizability执行的结果，等价于按照真实时间顺序，依次（非并发的）执行这些事件（Event，在此理解为读或写操作）。

Serializability

Serializability是数据库事务并发执行的约束。一个数据库事务由涉及到多个对象（也可以只是一个对象）的多个操作（也可以只是一个）组成。Serializability要求这些事务执行的结果，等价于这些事务依次（非并发的）执行的结果。值得注意的是，Serializability并没有对这些事务的执行顺序做出约束。

Serializability的具体描述见[13]的第2章。

两者区别

Linearizability主要应用于分布式共享内存模型下，对于单个对象的单个操作返回什么样的值合法做出限制。Linearizability是一种对Recency的限制，要求历史上并行操作的执行顺序必须反映他们的Real-Time顺序。此处Real-Time指的并非实时系统领域的Real-Time，而是对应于全局时钟而言的真实时间这一概念。

Serializability是数据库事务并行执行时的Isolation要求，其约束了并行事务执行的结果等价于这些事务“一条接一条”的执行的结果，但是没有限定这些并行事务的执行顺序。数据库事务通常涉及对多个对象的多个操作。

Serializability和Linearizability结合称为Strict Serializability或One-copy Serializability。

对于两者的比较也可以参考[39]。

我们能做什么

理清了CAP理论和ACID，我们来考虑一下分布式系统设计中能做到什么，以及如何进行取舍：

  1. 在满足传统数据库的强一致性约束下，我们能做到多高的可用性，以及多低的延迟？

  2. 在满足100% Read Write Availability的约束下，我们能做到多高的一致性？

  3. 在这两者之间还存在什么？

对于这些问题，我们总是从最简单的模型入手，即多副本的Key-Value Store开始，然后再考虑如何加上分布式事务。当然对于一个分布式数据库而言，我们至少还应该有Secondary Index，Data Constraint Check，等等功能，但是不在本文中进行进一步展开。

强一致性约束下的分布式系统

我们的目标是实现一个Linearizability Consistency的Key-Value Store，同时支持Serializability Isolation Level的分布式事务。

Linearizability Consistency的实现方法

我们的目标是实现一个Linearizability Consistency的Key-Value Store。由于Linearizability具有Local Property，我们可以将问题进一步简化。首先我们考虑如何实现一个Atomic Read/Write Register。更具体的，应该是MRMW Atomic Register（Multi-Reader Multi-Writer Atomic Register）。

[38]的P333对于Replication方式是否能实现Linearizability有一个总结：

  • Single-leader replication (potentially linearizable)

  • Consensus algorithms (linearizable)

  • Multi-leader replication (not linearizable)

  • Leaderless replication (probably not linearizable)

[45]的第16章第4节对于如何实现Linearizability也有一个总结：

  • Atomicity Based on a Total Order Broadcast Abstraction

  • Atomicity of Read/Write Objects Based on Server Processes

    • Atomicity Based on a Server Process and Copy Invalidation

    • Atomicity Based on a Server Process and Copy Update

总的来说，分为这样几种思路：

  1. Total Order Broadcast

  2. Quorum read/write

  3. Write-invalidate & Read-through

  4. Write-through

Total Order Broadcast保证每个replication以相同的顺序接收到全序排列的消息，显然，这符合Linearizability Consistency的定义。使用Consensus算法，例如Raft、ZAB等，相当于先在Leader节点上定序，然后再将消息和这一顺序本身传播给所有的replication，实际上等同于Total Order Broadcast。关于Total Order Broadcast的分类和实现方法见[23]。

使用Quorum方式实现Linearizability，需要在每次Read/Write操作的之前都进行一次Repair，见[38]的P334，[20]的第4章，以及[4]。需要注意的是，只有Read/Write操作能够以这种方式实现，Compare-And-Set之类的操作不能以这种形式实现，而必须使用分布式共识（Consensus）算法，具体见[34]的Fig 1。

Read-through和Write-through的方式主要适用于Cache场景，在分布式存储场景下使用这样的方法有较大的丢失数据的风险。

达成Linearizability的代价为Client到Leader的延迟加上Leader到多数集中最慢的节点的延迟。

Serializability Isolation事务的实现方法

在已经有了分布式Key-Value Store的情况下，我们接下来的目标是实现一个Serializability Isolation Level的分布式事务。

在单机数据库系统中实现Serializability Isolation Level事务的方法（按照Scalability从弱到强）主要有：

  1. 真实（单线程）Serialize执行

  2. Strict 2 Phase Locking

  3. Serializable Snapshot Isolation Algorithm

其中，Serialize execute和Strict 2PL（Strict 2 Phase Locking）属于悲观并发，SSI（Serializable Snapshot Isolation）属于乐观并发。SSI的原理大致是使用Snapshot Isolation但是在提交前检查是否有已知的写操作与当前事务的读操作在Serializability语义下冲突，如果有的话就Abort，没有的话就可以Commit并且保证Serializability了[21]。

实现分布式事务所需要解决的主要问题是Atomic Commitment，即多个节点all-or-nothing的决议commit或abort一个transaction的问题。Atomic Commitment分为Blocking和Non-blocking两种。Blocking Atomic Commitment问题可以转化为Consensus问题[31]。Blocking Atomic Commitment的一个典型的实现方法是2 Phase Commit，但是我觉得应该使用Paxos Commit Algorithm[31]。Non-blocking Atomic Commitment问题严格的比Consensus问题难[32]，一个典型的实现方法是3PC（3 Phase Commit），但是由于3PC不能在节点失效时保证正确性，所以几乎没有人在实际环境中使用3PC。

对于一个Linearizability Consistency的系统，我们无需关注每个Shard的多个副本（Replication）之间的一致性，因此对于没有跨越Shard的事务的实现方法和单机数据库事务的实现方法一致。对于跨越Shard的事务的实现方法，一个可行的方案是使用Paxos Commit Algorithm协调多个Shard，每个Shard使用Strict 2PL。除了需要额外的外部组件记录整个系统中事务和锁的关系以便进行死锁检测和处理，这个方案基本上和传统数据库的事务处理一致。SSI的实现需要解决一个重要问题，即如何跨越Shard生成一致的Snapshot。关于这方面我的经验不多，希望能在以后阅读了[26, 36, 48, 49, 53]后在补完这一部分内容（也有可能挖坑不埋）。

强一致性系统的问题

Linearizability Consistency虽然使得我们可以像是对待只有一份副本系统一样使用这一系统，但是代价不仅是算法的Network Latency Sensitive，还有Scalability下降。对于一个Linearizability Consistency的系统，不能够通过增加副本来提高系统的性能。Linearizability Consistency代价非常高，即便是多核CPU也没有使用Linearizability Consistency[47]。因此，我们应该只在必要的时候提供Linearizability Consistency，例如使用额外的系统（Zookeeper）。

Strict 2PL的并发度也比较低，带来的问题是事务处理的性能低。SSI的并发度尽管比Strict 2PL要高，但是在高并发场景下Abort的概率也比较高。

高可用性约束下的分布式系统

从[3, 37]中总结的结论，若想实现一个100% Read & Write Available的系统（或者说，读写操作的时间复杂度不受节点间通信网络延迟的影响），最高只能支持Causal Consistency。特别的，考虑到Version Vector的大小，甚至可能不支持完全的Causal Consistency。另一方面 ，从[8]中的结论来看，对于分布式事务的支持最高也只能达到RC（Read Committed），MAV（Monotonic Atomic View）或P-CI（Predicate Cut Isolation）。

这里故意避开了Eventual Consistency的概念，因为目前还没有统一的对于Eventual Consistency的形式化的定义，分歧主要集中在How Eventual和What Consistency两方面。[19, 51]中通过将Linearizability Consistency中的全序关系扩展到偏序关系，并且分解为Visible和Arbitration两个维度，来统一的描述多种Consistency。特别的，只出现在Arbitration关系中，但是没有出现在Visible关系中的事件相当于丢失了或被覆盖了。

Causal Consistency对于很多场景都具有很高的价值。例如在社交网络中，A说自己的小孩走丢了（a1），A又发消息说小孩找到了（a2），B评论说太好了（b）。如果此时C只能看到消息a1和b，就会产生问题。从Causal Relation上看，a1→a2→b，一个Eventual Consistency的系统不提供Causal Relation的保证，但是Causal Consistency必须保证这一点。

尽管如此，目前主流的NoSQL只实现了Eventual Consistency[22]。这是因为实现一个通用的Causal Consistency的代价比较高，例如某个Client先读取大量的数据然后进行了一次写入，一个通用的系统不能知道这个写入只是Causal依赖其中的哪些读取操作，进而必须捕获所有的读取操作。即便是让用户显式指定其写操作依赖于哪些读操作，还需要考虑Causal Relation的传递性（transitive），即读操作又依赖于那些读操作，等等。

Causal Consistency的实现方法

Single Object（或者说Per-Key）的Causal Consistency是容易实现的，使用MVCC等技术可以同时存储对象的多个版本，在写入时只需指定其依赖于哪一个版本，即可实现Single Object的Causal Consistency。需要注意的是，为了维持Session Level Guarantees，需要在Session维持期间只与同一个副本进行通信。个人认为，一般情况下，系统应该提供Single Object的Causal Consistency，这一负担并不重。

可惜的是，不像Linearizability Consistency，Causal Consistency不具有Locality性质。即使实现了Single Object的Causal Consistency，也不能使得整个系统能够满足Causal Consistency。

目前，如何实现Causal Consistency是学术上的一个热点[2, 6, 22, 24, 25, 40–42, 54]，一方面因为Causal Consistency是维持100% Availability情况下所能支持的最高的一致性级别，另一方面是因为Eventual Consistency提供的保证实在是太少了[10, 30]。

高可用分布式事务的实现方法

尽管[8]指出，在保证高可用的情况下，分布式事务最高能支持RC（Read Committed），MAV（Monotonic Atomic View）或P-CI（Predicate Cut Isolation），但是在其中并没有指出可以使用什么样的算法来做到这一点。特别的，[8]指出他们之所以写这篇论文，就是因为尽管很多算法实现了这些分布式事务，但是并没有支持高可用，很多系统虽然宣称自己是高可用的，但是用了这些不是高可用的算法后，也就不是严格意义上的高可用系统。

[18]提出了一种无需Coordinator的分布式事务的实现方法，[7]对Coordination Avoidance进行了进一步的论述。Eiger系统分别提供了低延迟的只读事务和只写事务[41]，但是仍然需要进一步的仔细检查，才能知道其是否是高可用的。Anna系统号称实现了Read Committed级别的跨越Shard的分布式事务[54]，但是没有披露更多的技术细节。其作者还发布过RAMP事务[9]，提供了低延迟的Read Atomic Isolation分布式事务。总的来说，高可用的分布式事务的实现还是一个开放问题。

其他

[7]对什么样的约束检查需要进行Coordination进行了形式化的论述。总的来说，无需Coordination的约束检查只能检查具有Locality性质的约束，而不能检查全局约束（例如非负计数器，自增主键等等）。

目前仍需探索的一个方向是如何在不同级别的Consistency和Isolation Level之间切换[50]。

Recommend Readings

在撰写本文时，我阅读了大量的相关资料，在此给出一个文献的建议阅读顺序。

首先应该阅读[38]中的第5章、第7章和第9章，这些章节分别介绍了Replication的方法，数据库事务，Consistency和Consensus及它们之间的关系。这使得读者对于CAP理论，数据库事务，Concurrent Programming中的一致性模型，分布式系统的共识问题，有一个初步的理解。

然后建议阅读[22]，对当前流行的NoSQL系统有一个初步的认识。

对于CAP理论相关的文献，建议首先阅读[28]，对于普遍认识中的CAP理论有非形式化和形式化的定义和证明。然后强烈建议阅读[37]，其作者也是[38]的作者，在这篇论文中提出了对CAP理论现有工作的一些批评和改进，这些批评和改进非常具有启发性和实用性。然后可以在以下列表中挑选感兴趣的内容阅读：

  • [16]为CAP理论的提出者Brewer在12年后对CAP理论的回顾和补充

  • [1]这篇论文将CAP理论扩展为PACELC理论，将Latency纳入对Availability的解释中

  • [29]这篇论文将CAP理论扩展为Safety性质和Liveness性质的Impossibility问题

  • [55]解释了在CAP理论中P是不可舍弃的（应该作为算法设计模型的一部分），这一问题在[37]中也略有涉及

  • [51]对于Consistency进行了非常详尽的形式化的总结，但是强烈建议先看完[19]再看这个，因为其描述方法是沿用[19]中的方式，否则容易看不懂

  • [52]对Eventual Consistency有一个简略的介绍和总结

  • [30]对于Eventual Consistency的Eventual有一个略微深入的展开

  • [19]是一个对Eventual Consistency非常详尽和形式化的总结

关于Linearizability Consistency，建议阅读[45]的第16章，其原始论文为[35]，关于其性能的一些讨论可以在[5]中找到。关于Eventual Consistency，建议阅读[10, 14, 52]，关于其一些形式化的描述，建议阅读[19, 51]。

关于Serializability建议阅读[13]的第2章。

关于Concurrent Programming中的Consistency，建议阅读

对于（单机）数据库事务，建议阅读[38]的第7章。关于Serializable Snapshot Isolation，见[21, 44]。关于实现单机数据库事务的新方法，见[53]。

分布式事务的一致性和分布式共识问题有很强的相关性，建议阅读[38]中的第9章，以及Lamport写的[31]。关于Non-blocking Atomic Commitment，建议阅读[32]。

References

[1] Abadi, D. 2012. Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story. Computer. 45, 2 (2012), 37–42. DOI:https://doi.org/10.1109/MC.2012.33.

[2] Akkoorath, D.D. et al. 2016. Cure: Strong Semantics Meets High Availability and Low Latency. 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) (Jun. 2016), 405–414.

[3] Attiya, H. et al. 2017. Limitations of Highly-Available Eventually-Consistent Data Stores. IEEE Transactions on Parallel and Distributed Systems. 28, 1 (2017), 141–155. DOI:https://doi.org/10.1109/TPDS.2016.2556669.

[4] Attiya, H. et al. 1995. Sharing memory robustly in message-passing systems. Journal of the ACM. 42, 1 (1995), 124–142. DOI:https://doi.org/10.1145/200836.200869.

[5] Attiya, H. and Welch, J.L. 1994. Sequential consistency versus linearizability. ACM Transactions on Computer Systems. 12, 2 (1994), 91–122. DOI:https://doi.org/10.1145/176575.176576.

[6] Bailis, P. et al. 2013. Bolt-on causal consistency. Proceedings of the 2013 international conference on Management of data - SIGMOD ’13. (2013), 761. DOI:https://doi.org/10.1145/2463676.2465279.

[7] Bailis, P. et al. 2015. Coordination Avoidance in Database Systems. Pvldb. 8, 4 (2015), 185–196. DOI:https://doi.org/1402.2237v2.

[8] Bailis, P. et al. 2013. Highly Available Transactions: Virtues and Limitations. Proceedings of the VLDB Endowment. 7, 3 (2013), 181–192. DOI:https://doi.org/10.14778/2732232.2732237.

[9] Bailis, P. et al. 2014. Scalable atomic visibility with RAMP transactions. Proceedings of the 2014 ACM SIGMOD international conference on Management of data - SIGMOD ’14. (2014), 27–38. DOI:https://doi.org/10.1145/2588555.2588562.

[10] Bailis, P. and Ghodsi, A. 2013. Eventual consistency today. Communications of the ACM. 56, 5 (2013), 55. DOI:https://doi.org/10.1145/2447976.2447992.

[11] Bailis, P. and Kingsbury, K. 2014. The Network is Reliable. Queue. 12, 7 (2014), 20:20-20:32. DOI:https://doi.org/10.1145/2639988.2639988.

[12] Berenson, H. et al. 1995. A critique of ANSI SQL isolation levels. ACM SIGMOD Record. 24, 2 (1995), 1–10. DOI:https://doi.org/10.1145/568271.223785.

[13] Bernstein, P.A. et al. 1987. Concurrency Control and Recovery in Database Systems. Addison-Wesley Pub. Co.

[14] Bernstein, P.A. and Das, S. 2013. Rethinking eventual consistency. Proceedings of the 2013 international conference on Management of data - SIGMOD ’13. (2013), 923. DOI:https://doi.org/10.1145/2463676.2465339.

[15] Borowsky, E. and Gafni, E. 1993. Generalized FLP impossibility result for t-resilient asynchronous computations. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC ’93. 5, (1993), 91–100. DOI:https://doi.org/10.1145/167088.167119.

[16] Brewer, E. 2012. CAP twelve years later: How the “rules” have changed. Computer. 45, 2 (2012), 23–29. DOI:https://doi.org/10.1109/MC.2012.37.

[17] Brewer, E. 2017. Spanner, TrueTime & The CAP Theorem. White Papers. 2015, 4/4/2015 (2017), 1–7.

[18] Burckhardt, S. et al. 2012. Eventually Consistent Transactions. Proceedings of the 22n European Symposium on Programming (ESOP). Springer. 67–86.

[19] Burckhardt, S. 2014. Principles of Eventual Consistency. Foundations and Trends® in Programming Languages. 1, 1–2 (2014), 1–150. DOI:https://doi.org/10.1561/2500000011.

[20] Cachin, C. et al. 2011. Introduction to reliable and secure distributed programming. Springer.

[21] Cahill, M.J. et al. 2009. Serializable isolation for snapshot databases. ACM Transactions on Database Systems. 34, 4 (Dec. 2009), 1–42. DOI:https://doi.org/10.1145/1620585.1620587.

[22] Davoudian, A. et al. 2018. A Survey on NoSQL Stores. ACM Computing Surveys. 51, 2 (Apr. 2018), 1–43. DOI:https://doi.org/10.1145/3158661.

[23] Défago, X. et al. 2004. Total order broadcast and multicast algorithms: Taxonomy and Survey. ACM Computing Surveys. 36, 4 (Dec. 2004), 372–421. DOI:https://doi.org/10.1145/1041680.1041682.

[24] Didona, D. et al. 2017. Okapi: Causally Consistent Geo-Replication Made Faster, Cheaper and More Available. (Feb. 2017).

[25] Du, J. et al. 2014. GentleRain : Cheap and Scalable Causal Consistency with Physical Clocks. SOCC ’14 Proceedings of the ACM Symposium on Cloud Computing. (2014), 1–13. DOI:https://doi.org/10.1145/2670979.2670983.

[26] Dutta, P. et al. 2005. How fast can eventual synchrony lead to consensus? Proceedings of the International Conference on Dependable Systems and Networks. March (2005), 22–27. DOI:https://doi.org/10.1109/DSN.2005.54.

[27] Fischer, M.J. et al. 1983. Impossibility of distributed consensus with one faulty process. Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems - PODS ’83 (New York, New York, USA, Apr. 1983), 1–7.

[28] Gilbert, S. and Lynch, N. 2002. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News. 33, 2 (2002), 51. DOI:https://doi.org/10.1145/564585.564601.

[29] Gilbert, S. and Lynch, N. 2012. Perspectives on the CAP Theorem. Computer. 45, 2 (2012), 30–36. DOI:https://doi.org/10.1109/MC.2011.389.

[30] Golab, W. et al. 2014. Eventually consistent: not what you were expecting? Communications of the ACM. 57, 3 (2014), 38–44. DOI:https://doi.org/10.1145/ 2576794.

[31] Gray, J. and Lamport, L. 2004. Consensus on Transaction Commit. 1, April 2004 (2004). DOI:https://doi.org/10.1145/1132863.1132867.

[32] Guerraoui, R. 1995. Revisiting the relationship between non-blocking atomic commitment and consensus. Distributed Algorithms (1995), 87–100.

[33] Haerder, T. and Reuter, A. 1983. Principles of transaction-oriented database recovery. ACM Computing Surveys. 15, 4 (1983), 287–317. DOI:https://doi.org/10.1145/289.291.

[34] Herlihy, M. 1991. Wait-free synchronization. ACM Transactions on Programming Languages and Systems. 13, 1 (1991), 124–149. DOI:https://doi.org/10.1145/114005.102808.

[35] Herlihy, M.P. and Wing, J.M. 1990. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems. 12, 3 (Jul. 1990), 463–492. DOI:https://doi.org/10.1145/78969.78972.

[36] Jung, H. et al. 2011. Serializable Snapshot Isolation for Replicated Databases in High-Update Scenarios. PVLDB. 4, 11 (2011), 783–794.

[37] Kleppmann, M. 2015. A Critique of the CAP Theorem. (2015).

[38] Kleppmann, M. 2017. Designing data-intensive applications. O’Reilly Media, Inc.

[39] Linearizability versus Serializability: 2014. http://www.bailis.org/blog/linearizability-versus-serializability/. Accessed: 2018-05-08.

[40] Lloyd, W. et al. 2011. Don’t Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. Proceedings of the Symposium on Operating Systems Principles. (2011), 1–16. DOI:https://doi.org/10.1145/2043556.2043593.

[41] Lloyd, W. et al. 2013. Stronger Semantics for Low-Latency Geo-Replicated Storage. Proceedings of the Symposium on Networked Systems Design and Implementation. April (2013), 313–328. DOI:https://doi.org/10.1145/2602649.2610533.

[42] Mehdi, S.A. et al. 2017. I Can’t Believe It’s Not Causal! Scalable Causal Consistency with No Slowdown Cascades. 14th {USENIX} Symposium on Networked Systems Design and Implementation, {NSDI} 2017, Boston, MA, USA, March 27-29, 2017. (2017), 453–468.

[43] On Consistency and Durability: http://www.bailis.org/blog/on-consistency-and-durability/. Accessed: 2018-05-08.

[44] Ports, D.R.K. and Grittner, K. 2012. Serializable snapshot isolation in PostgreSQL. Proceedings of the VLDB Endowment. 5, 12 (Aug. 2012), 1850–1861. DOI:https://doi.org/10.14778/2367502.2367523.

[45] Raynal, M. 2013. Distributed Algorithms for Message-Passing Systems. Springer, Berlin, Heidelberg.

[46] Saks, M. and Zaharoglou, F. 1993. Wait-free k-set agreement is impossible. Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC ’93. (1993), 101–110. DOI:https://doi.org/10.1145/167088.167122.

[47] Sewell, P. et al. 2010. X86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors. Communications of the ACM. 53, 7 (Jul. 2010), 89. DOI:https://doi.org/10.1145/1785414.1785443.

[48] Shao, J. et al. 2016. Read Consistency in Distributed Database Based on DMVCC. 2016 IEEE 23rd International Conference on High Performance Computing (HiPC). (Dec. 2016), 142–151. DOI:https://doi.org/10.1109/HiPC.2016.11.

[49] Sovran, Y. et al. 2011. Transactional storage for geo-replicated systems. Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles - SOSP ’11. (2011), 385. DOI:https://doi.org/10.1145/2043556.2043592.

[50] Tripathi, A. and Thirunavukarasu, B.D. 2015. A transaction model for management of replicated data with multiple consistency levels. 2015 IEEE International Conference on Big Data (Big Data) (Oct. 2015), 470–477.

[51] Viotti, P. and Vukolić, M. 2016. Consistency in Non-Transactional Distributed Storage Systems. ACM Computing Surveys. 49, 1 (Jun. 2016), 1–34. DOI:https://doi.org/10.1145/2926965.

[52] Vogels, W. 2008. Eventually Consistent. Queue. 6, 6 (2008), 14. DOI:https://doi.org/10.1145/1466443.1466448.

[53] Wang, T. et al. 2016. Efficiently making (almost) any concurrency control mechanism serializable. The VLDB Journal. 26, 4 (May 2016), 537–562. DOI:https://doi.org/10.1007/s00778-017-0463-8.

[54] Wu, C. et al. 2018. Anna : A KVS For Any Scale. 34th IEEE International Conference on Data Engineering. (2018).

[55] You Can’t Sacrifice Partition Tolerance: 2010. https://codahale.com/you-cant-sacrifice-partition-tolerance/. Accessed: 2018-04-17.

后记

可以看得出，本文后期的内容比较杂乱，实际上没有达到我心中的效果。这是因为本人对于如何实现一个Causal Consistency存储系统并没有一个非常清晰的认识。我写这篇文章的初衷是理清CAP理论和ACID性质之间的关系，为分布式存储系统的设计找到一个清晰的脉络。在查资料的过程中，发现CAP理论的描述并不清晰，大家对此也各有纷争。ACID性质本身也不是很清晰，而且扩展到分布式环境中又带来一些新的问题。一些新的数据库事务的实现方法，也没有很好的对应于ACID性质中去。Non-blocking的分布式系统也是一个新兴领域，目前尽管有一些理论准备，但是算法和实现上还没有一个清晰的思路。

对于分布式存储系统，首先要考虑在性能和一致性之间权衡。考虑的顺序应该如下：

  1. Per-key Consistency

  2. Multi-key Consistency

  3. Transaction Consistency

偏重一致性的应用应该考虑支持Linearizability Consistency，但是同时也要考虑是否能够接受随之而来的Latency和Scalability的下降。需要高性能或高可用的应用应当考虑使用Eventual Consistency，因为Causal Consistency相关理论目前还不够成熟。但是在需要的时候，也可以探索Causal Consistency的高可用实现。对于事务的支持，如果没有实现Linearizability Consistency的话，可以考虑只支持单机事务，或者多机只读、只写事务。