Consistency Tradeoffs in Modern Distributed Database System Design

CAP理论深刻地影响了分布式数据库的设计，另外一个方面，一致性和延迟之间的权衡也对现在的数据库产生了直接的影响。未来融合这个两者，一个新的理论PACELC[2]被提出。DDBSs正在正在变得越来越”大”, 2个主要的原因促使了这种变化，第1个是现在的应用需要越来越多的数据和越来越高的事务处理能力，第2个是因为增长的跨国企业的需要在全球范围内开展业务，需要将数据中心建立在靠近客户的地方。在过去10年开发的DDBSs都具有高可用性或(和)全球范围内范围的能力，比如SimpleDB/DynamoDB，Cassandra，Voldmort，HBase/BigTable,MongoDB，VoltDB/H-Store以及Megastore等。

DDBSs是一个复杂的系统，开发这样一个系统是非常困难的。DDBS的设计是一门权衡的艺术，其中CAP理论是很重要的一个部分。虽然CAP很重要，但是论文[1]认为CAP被滥用了，仅仅只考虑C A P之间的权衡是不够的。实际上，CAP讨论的是故障复发生之后的一些限制。正常情况下，更为常见的权衡是一致性和延时之间的权衡，它也深刻地影响了DDBS的设计。PACELC被提出统一这些权衡，PACELC的含义为: P then AC else LC，意为在网络分区发生的时候系统需要在可用性和一致性之间做出权衡，而没有网络分区的情况下，系统需要在一致性和延时之间做出权衡。

CAP是关于故障的

由于CAP理论中三个最多只能取其二，只有以下几种类型的系统是可能的: CA，没有网络分区；CP，不能保证高可用；AP，不能保证一致性。现在很多的DDBS(默认情况下)都不保证C，比如SimpleDB/Dynamo, Cassandra等。早期的DDBS的研究的关注点在一致性，很自然的认为CAP是影响数据库架构的主要因素。DDBS是必须要能容忍出现网络分区的，这样的话，DDBS这能在A和C之间做出选择。对于可靠性有高要求的应用就只能舍弃C。看上去这里是没有问题的。但是实际上还是有一些瑕疵，这个观点不仅仅是一致性和可用性之间的权衡，而且还包括了网络分区和网络分区的存在这个件事情。也就是，这里只是简单地认为网络分区的存在得让我们在一致性和可用性之间做出选择。但是网络分区可能性是多种原因决定的: 系统在WAN上运行？或者知识一个局部的集群？使用了什么样的硬件？等等。通常网络分区是很少见的，发生的频率低于系统中的其它类型的故障。在没有网络分区的情况下，CAP允许系统完整的实现ACID的前提下也实现高可用性。CAP理论不是这些在正常的情况下减弱一致性的理由(比如SimpleDB/Dynamo, Cassandra等)。

一致性和延时之间的权衡

理解现代一些DDBS的设计要先了解它们面向的使用场景，现在的很多DDBS(比如SimpleDB/Dynamo, Cassandra等)面向的使用场景是在线活动，对交互的延时比较敏感，延时多上100ms可能就导致用户的流失。不幸的是，在一致性、可用性和延时之间存在基本的权衡，即使没有网络分区，这种权衡也会存在，这种权衡与CAP无关。及时如此，这张权衡也是这些系统设计的关键因素。高可用性机遇就意味着复制数据。为了实现尽可能高的可用性，DDBS就得在WLN复制数据，防治一个数据中心因为某些原因被整个损坏(比如地震、飓风)等。当出现数据复制时，就会有一致性和延时之间的权衡。只有3种方法来实现数据复制: 1. 系统同时发送更新给所有副本；2. 发送给特殊的master节点；3. 随机发送给一个节点。无论哪一种方法，都存在一致性和延时之间的权衡。

同时发送给所有副本

如果更新不经过预处理合作其它的协议，因为每个副本得到的更新的顺序可能是不同的，这样就会导致明显的缺失一致性。而如果经过预处理合作通过其它协议来保证副本应用更新的顺序，这样的话，这些操作就是延时的来源。如果使用的是使用某种协议的方法，那么协议本身就是一种延时的来源。在使用预处理方法的情况下，主要有两个延时的来源，第一个是附加的预处理会增加延时，第二，预处理器由几台机器或者一台机器组成，多台机器的情况下又需要某种协议来保证更新的顺序，一台机器的情况下任何位置的更新都得像这个单一的节点请求更新。

数据更新发送到一个商定的位置

这个商定的位置可以称为master。Master节点所有的请求然后更新数据。由于只由master来处理请求，所以更新执行的顺序是可以保证的。Master执行玩操作后，会复制到其它的节点。这个复制有3种不同的选项

1. 同步复制: Master节点会一直等待知道所有的副本都已经复制完成。这样一致性是有保障的，但是延时不可避免地会增大。
2. 异步复制: 系统会认为在复制完成之前就认为更新已经完成。通常会保证更新的数据以及被持久化保存，但不保证更新已经同步到所有的节点，这种情况下，一致性和延时的权衡取决于系统如何读取: 如果读取请求全部有master节点处理，那么不会有一致性的问题，但是这种方法可能造成2个延时:
  * 发送读取请求的客户端可能距离master节点很远，即可可能存在离这个客户端很近的副本，但是不能使用;
  * 如果master节点负载过高或者失败，则客户端必须等待master节点负载降低或者从失败中恢复，缺乏负载均衡会增加延时。
  * 如果可以由任意的节点上读取，则会带来一致性的问题，因为节点之间的数据可能是一致的。虽然可以实现sequential/timeline一致性或者read-your-writes一致性，也是一致性的降低。 此外，接受写入请求的节点
  * 在物理上原理写入请求的发起者也会增加延时。
 3. 结合同步和异步复制: 系统也可以结合1和2，将更新同步发送给系统的子集，然后异步发送给剩余的部分。这种情况下一致性和延时的权衡也取决于系统如何处理读取: 假设至少有一个节点已经应用更新，那么在W + R > N 的情况下，一致性是可以保障的，前面讲过的延时增加的问题依然存在。
   * 当 W + R <= N的情况下，客户端可能读取不到一些更新的数据，就会造成一致性的问题。

数据更新发送带一个随机的位置

这种做法的主要区别在发送更新的位置，这种方法下发送的目的位置是不确定的。如果同步复制更新，照样会存在上面讲到的延时增加的问题。如果是一步的，同理，一致性的问题也照样存在。

PACELC

所以，可以将CAP重新表示为PACELC来实现更为完整的描述：如果存在分区（P），则系统如何权衡可用性和一致性（A 和C）,else（E）当系统在没有分区的情况下正常运行时，系统如何权衡延迟（L）和一致性（C）。 ELC部分只使用与数据复制的系统。Dynamo, Cassandra和Riak默认情况下是一个PA/EL的系统，在没有网络分区的情况下，会选择降低一致性来实现更低的延时，在发生网络分区的情况下，会选择放弃一致性来实现高可用。完整支持ACID的系统，比如oltDB/H-Store和Megastore 是一个PC/EC的系统，它们没有放弃一致性，所以在可用性和延时上做了付出了一些代价。MongoDB可以认为是PA/EC的系统，在正常的情况下，系统可以保障一致性，但是在出现Master不可用或者网络分区是，就会产生一致性的问题。 PNUTS是一个PC/EL的系统，看起来有些困惑，在正常的情况下不能保证一致性，而在网络分区的情况下能保证一致性？？不过，这里的PC/EL一个理解为在正常的情况下选择更低的延时，而网络的分区的情况下，PC不能代表完全一致，而是不选择降低一致性，而是选择降低可用性。

参考

Consistency Tradeoffs in Modern Distributed Database System Design: http://dl.acm.org/citation.cfm?id=2360959
PACELC theorem: https://en.wikipedia.org/wiki/PACELC_theorem