向量时钟解决数据一致性

向量时钟解决数据一致性

向量时钟简介

向量时钟，最早是用于分布式系统中进程间的时间同步。由于在分布式系统中没有一个直接的全局逻辑时钟。在一个由n个并发进程构成的系统中，每个事件的逻辑时钟均由一个n维向量（n元组）构成，其中第i维（分量）对应于第i个进程的逻辑时钟Vi

向量时钟的维护方法：

*初值

*第i个进程在事件发生时，继承上一事件的逻辑时钟并将自身所对应的分量Vi增加一个步长

*任何进程Pi在发出任何消息m时都要将自己当前的逻辑时钟分量Vi一起发送出去

*如果是接收事件，且发送方为j，则比较自己继承的Vj和收到的逻辑时钟，并取其中较大者为自己的Vj

形式化表示如下：

在向量时钟方法中，每个进程Pi和一个向量LCi[1...n]相关联，其中

* LCi[i]描述了进程Pi，即自身进程

* LCi[j]表示Pi关于Pj进程的知识

* LCi[1...n]组成Pi对于逻辑全局时间的局部视图

对每一个进程LCi的更新规则如下

*规则1：在发生一个事件（一个外部发送或内部事件）之前，我们更新LCi[i]:

LCi[i] := LCi[i] + d (d > 0)

*规则2：每个消息捎带发送方在发送时的向量时钟。当接收到一个消息（m, LCj, j）时，Pi执行更新：

LCi[k] := max(LCi[k], LCj[k]), 1<=k<=n

LCi[i] := LCi[i]+d

下图为增量值d=1，初始值init=0时的示例图

数据一致性（Quorum）

定义

N：系统中数据的备份数

R：读取操作最小成功数

W：写操作最小成功数

要求：R+W>N

配置

R+W>N，保证读操作至少能读取到一个最新数据

读写速度受性能最差的节点影响

R和W越小，系统的响应越快

W越大，数据的一致性，可用性越强

通常：N=3， R=W=2

时钟向量与数据冲突处理

*将上述向量时钟应用到解决数据一致性的问题上来

*向量时钟在分布式环境中表示对象或事件的逻辑关系

*分布式系统中每个消息都附加Vector Clock的信息

*当某个节点内部处理一个事件时，将其自身对应的counter加1

*节点发送一个消息前，将其自身对应的counter加1

*节点收到一个消息时，将其自身对应的counter加1；同时，根据消息中的Vector Clock信息更新所有其他counter

在Dynamo系统中为了可用性，所以对一致性的约束做了妥协。使得整个系统对“写”一直是可用的，而将数据不一致性的处理部分放到了客户端程序读数据时再进行处理。

在客户端使用get获取数据时，coordinator对node返回数据依据时钟向量进行version处理。如果数据一致则将取得的值返回给客户端。如果数据冲突，则将所有数据返回给客户端，由客户端进行解决。