数据一致性策略

在数据一致性的最终实现上，不同的系统采用不同的策略。

包括：Quorum的NWR策略、两阶段提交协议、Paxos、时间戳、向量时钟等，本章只列举了其中的一部分，现实中还有更多的实现。

但是这些系统或者模型均以CAP理论为基石，并依据不同的情况作出权衡，例如Paxos具有较强的一致性，但是系统延迟较大。

此外，很多系统中采用多种策略的结合，例如，NWR策略经常与向量时钟一同使用，用以解决数据的一致性问题。

时间戳策略

摘自《大数据挑战与NoSQL数据库技术》 2.4.3 时间戳策略

在关系数据库中有广泛的应用，该策略主要用于关系数据库日志系统中记录事务操作，以及数据恢复时的Undo/Redo等操作。

在并行系统中，时间戳策略有更加广泛的应用。

从较高的层次来说，时间戳策略可用于SNA架构或并行架构系统中的时间、数据的同步。

在并行数据存储系统或并行数据库中，由于数据时分散存储在不同的节点上的，那么对于不同节点上的数据如何区分它们的版本信息将成为比较繁琐的事情，该问题将涉及到不同节点之间的同步问题。

若使用时间戳策略将能够很好地缓解这一境况，例如，我们可以为每一份或一组数据附加一个时间戳标记。

在进行数据版本比较或数据同步的时候只需要比较其时间戳就可以区分他们之间的版本。但是分布式系统中不同节点之间的物理时钟可能会有偏差，这样就可能导致交完更新的数据其时间戳却比较晚。

全局时钟

因此我们设置一个全局时钟来进行时间同步。

当一份数据更新之后，该数据所在节点向全局时钟请求一个时间戳。

那么，此时新的问题将出现：1）该全局时钟同步开销过大，影响系统效率；2）该全局时钟出现宕机，整个系统将无法工作。

因此，该系统时钟将成为系统效率和可用性的瓶颈。

时间戳策略

使用时间戳的策略将能够很好地解决这一问题。

时间戳策略不依赖于任何单个的机器，也不依赖于物理是综合能够。

该时间戳为逻辑上的时钟，并且通过时间戳版本的更新可以在系统中生成一个全局有序的逻辑关系。

下面我们将简单介绍该策略的核心思想。

时间戳

时间戳最早用于分布式系统中进程之间的控制，用于确定分布式系统中事件的先后关系，可用于协调分布式系统中的资源控制。

我们假设发送或接受消息是进程中的一个事件，下面我们来定义分布式系统事件集中的先后关系，用【→】符号来表示。

例如：若事件a发生在事件b之间，那么有a→b。

该关系需要满足下列三个条件：

1) 如果事件a和事件b是同一个进程中的事件，并且a在b之前发生，那么有a→b；

2) 如果事件a是某消息发送方进程中的事件，事件b是该消息接收方进程中接收该消息的事件，那么有a→b；

3) 对于事件a、事件b和事件c,如果有a→b和b→c，那么a→c。

如果两个不同的事件a和事件b，既不能得出a→b也不能得出b→a，那么有事件a和事件b同时发生。

如图1所示，下面我们通过该图说明系统中可能存在的事件先后关系。

事件先后关系

在图1中，纵向代表事件轴，虚线表示进程之间的消息通信。

在该模型中，如果存在着一个从a到b的时间或消息的先后关系，那么有a→b。

例1：在同一进程P中，事件p2发生在事件p1之后，因此有p1→p2。

例2：对于事件q1和时间p3，由于存在从q1到p2的消息传递，因此有q1→p2，同时在同一进程P中，我们知道p2→p3，因此根据该模型，有q1→p3。

例3：对于事件p3和事件q3，在逻辑上，我们不能确定p3是否在q3之前发生（只能得出p3在q1之前发生），也不能确定q3是否在p3之前发生（只能得出）q3在p1之前发生。尽管在物理时间上，q3要先于p3发生，但是我们不能确定两事件在该模型下的逻辑关系，因此我们说p3和q3同时发生。

逻辑时钟

现在我们将时钟引入到系统中。

这里我们并不关心时钟值是如何产生的，他可以通过本地时钟产生，也可以为有序的数字。

这里我们为每一个进程Pi定义一个时钟Ci，该时钟能够为任意一个事件a分配一个时钟值：Ci〈a〉。

在全局上，同样存在一个时钟C，对于事件b，该时钟能够分配一个时钟值C〈b〉，并且如果事件b发生在进程i上，那么有 C〈b〉=Ci〈b〉。

我们的系统并不依赖于物理时钟，因为物理时钟可能会出现错误，因此我们要求

时钟条件：如果对于事件a和事件b，有a→b，那么C〈a〉< C〈b〉。

但是，事件a的逻辑时钟值小于事件b的逻辑时钟值并不意味着有a->b，因为可能有事件a与事件b同时发生（见例3）。

另外，在图2-X中我们可以得到p2与q3同时发生，p3与q3也同时发生，那么这意味着p2与p3同时发生。

但是这与实际情况相违背，因为p2→p3。

同时发生的限定条件

因此，我们给出下面两个限制条件：

（1）如果事件a和事件b是同一个进程Pi中的事件，并且a在b之前发生，那么有：

Ci〈a〉< Ci〈b〉

（2）如果 a 为进程 Pi 上某消息发送事件， b为进程 Pj 上该消息接收事件，那么有：

Ci〈a〉< Ci〈b〉

时钟走表

现在我们可以进一步考虑下“时钟走表”的概念，若事件a发生在事件b之前，有C〈a〉< C〈b〉。

例如C〈a〉= 4，C〈b〉=7，那么在事件a和事件b之间存在4到5，5到6和6到7三个时间间隔。

也就是说存在先后顺序的事件之间一定至少存在至少一个时间间隔。

那么C1意味着，同一个进程中的两个事件之间一定存在至少一个时间间隔；C2意味着，每一条消息一定跨越了至少一个时间间隔。

根据以上规则，我们为存在事件间隔的事件或消息之间添加一条灰色的事件线来表示时间间隔的存在，那么图2-X可以转换为图2，如下所示：

时间线

实际应用

下面，我们可以假定进程为分布式存储系统或并行数据库系统中的不同节点。

下面我们将时钟的概念引入到并行系统中。

在系统中，每一个节点i均包含一个时钟Ci，系统中包含两类事件，一种为节点上的数据更新；另一类为节点之间的消息通信（或数据同步）。

下面我们来说明，该系统是如何满足C1和C2条件的。

对于 C1 条件来说，系统需要满足下面的实现规则：

IR1：对于同一节点上任意的连续事件来说，该节点上的时钟只需要保证较晚发生事件的时钟值要大于较早发生事件的时钟值即可。

对于 C2 条件来说，当节点发送消息 m 时，该消息需要同时携带发送时刻的在该节点产生的时间戳。

在接收方收到该消息 m 之后，接收方节点所产生的时间戳要大于消息 m 所携带的时间戳。

例子

但是仅仅如此还是不够的，例如：

假设某节点A向节点B发送消息m，在发送消息时刻节点A的本地事件为：15:33:30，那么该m所携带的时间戳可能为Tm_a=153330。

节点B在接收到m后，可能设置该事件的时间戳Tm_b为153400。

但是由于机器之间的时间误差，本地时间可能为：15:50:05。

并且，在该接收m事件事前15:45:15时刻，节点B上发生数据更新事件，该事件戳为Tm_b’=154515。

显然，将Tm_b设置为153400将会引起逻辑上的错误。

额外的约定

那么，为了满足C2约束，则需要满足下面的规则：

IR2：

（a）如果事件a代表节点Ni发送消息m，那么消息m将携带时间戳Tm，且Tm=Ci〈a〉；

（b）当节点Nj接收到消息m后，节点将设置该事件的时钟Cj大于等于该节点上一事件的时钟并且大于等于Tm。

 该理论为时间戳策略的基本理论，具体的系统和实现要根据当前环境来决定。

拓展阅读

CAP 理论

Raft 算法

Paxos 算法

二阶段提交

NWR 读写模型、Quorum 机制

参考资料

一致性算法之四: 时间戳和向量图