分布式数据库数据一致性

1. CAP定理

CAP定理是2000年，由 Eric Brewer 提出来的。Brewer认为在分布式的环境下设计和部署系统时，有3个核心的需求，以一种特殊的关系存在。这里的分布式系统说的是在物理上分布的系统，比如我们常见的web系统。

Consistency: 一致性，在分布式系统中的所有数据备份，在同一时刻是否同样的值。(所有的节点上的数据时刻保持同步)

Availability: 可用性，在集群一部分节点出现故障知乎，集群整体是否还能响应客户端的读写请求。(每个请求都能接受到一个响应，无论响应成功或失败)

Partition Tolerance: if the network stops delivering messages between two sets of servers, will the system continue to work correctly(系统应该能持续提供服务，即使系统内部有消息丢失（分区）)。

高可用、数据一致是很多系统设计的目标，但是分区又是不可避免的事情：

CA without P：如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。

CP without A：如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

CAP原理的关系与相关的产品如下图所示

CAP

下面是对于P的一点讨论，在Seth Gilbert and Professor Nancy Lynch 论文中，Partition Tolerance的定义如下所示

"The network will be allowed to lose arbitrarily many messages sent from one node to anothe"

由此可见，分区容忍性并不是分布式应用的属性，而是承载分布式应用的网络的属性，这是比较容易让人误解的情况。分区容忍不是我们设计分布式系统的一个选择，笔者理解是设计分布式系统必须考虑分区的问题。在一个网络中如果有分区（网络故障或机器软硬件故障），则会失去一致性C（因为允许更新分区的两侧）或者可用性A （因为您检测到错误并关闭系统，直到错误条件解决）。分区容忍意味着通过选择其他系统属性中的哪一个来简单地开发应对策略。
如果一个网络存在信息丢失，那么在此网络上构建的分布式系统的可用性和一致性只能满足一个。

2. 数据一致性模型

强一致性： 要求无论更新操作实在哪一个副本执行，之后所有的读操作都要能获得最新的数据。

弱一致性：用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。

最终一致性：是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新。

3. 数据一致性实现

1. Quorum系统NRW策略
这个协议有三个关键字N、R、W。

• N代表数据所具有的副本数。
• R表示完成读操作所需要读取的最小副本数，即一次读操作所需要参与的最小节点数目。
• W表示完成写操作所需要写入的最小副本数，即一次写操作所需要参与的最小节点数目。
  则 N 和 R+N的关系有三种情况

N < R+W ,保证强一致性

N=3，W=2，R=2，那么表示系统中数据有3个不同的副本，当进行写操作时，需要等待至少有2个副本完成
了该写操作系统才会返回执行成功的状态，对于读操作，系统有同样的特性。由于R + W > N，因此该系统
是可以保证强一致性的。因为读取数据的节点和被同步写入的节点是有重叠的。

N >= R+W , 只能保证最终一致性

这时读取和写入操作是不重叠的，系统只能保证最终一致性，而副本达到一致的时间则依赖于系统异步更新
的实现方式，不一致性的时间段也就等于从更新开始到所有的节点都异步完成更新之间的时间。

R 和 W 比例关系

1. 当W=1,R=N时，系统对写操作有较高的要求，但读操作会比较慢，若N个节点中有节点发生故障，那么读
操作将不能完成。
2. 当R=1,W=N时，系统对读操作有较高性能、高可用，但写操作性能较低，用于需要大量读操作的系统，
若N个节点中有节点发生故障，那么些操作将不能完成。
3. 当R=Q,W=Q(Q=N/2+1)时，系统在读写性能之间取得平衡，兼顾了性能和可用性。

2. 两阶提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中
只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可
以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下
所述：

阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将
告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事
务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者
发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不
同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：

首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、
C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去
爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的
邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和
D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其
结合的原理如下：

客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度
信息，请求修改数据，该消息是1阶段的请求消息。
存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。如
果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的
提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交
消息。该消息是2阶段的提交消息。
存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修
改数据还原为修改前，然后回应取消修改OK的消息。
客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，
都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回
复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。
缺点：单个A是个严重问题：没有热备机制，A节点宕机了或者链接它的网络坏了会阻塞该事务；吞吐量不
行，没有充分发动更多A的力量，一旦某个A第一阶段投了赞成票就得在它上面加独占锁，其他事务不得接
入，直到当前事务提交or回滚。

参考文献

1. 浅析数据一致性 http://www.importnew.com/20633.html
2. CAP理论 http://blog.csdn.net/chen77716/article/details/30635543
3. CAP Confusion: Problems with ‘partition tolerance’ https://blog.cloudera.com/blog/2010/04/cap-confusion-problems-with-partition-tolerance/