《分布式原理（4）--逻辑时钟》表明逻辑时钟不能表达因果关系，而因果关系是一个偏序关系。而分布式环境下，尤其多的是因果关系，因此需要一个能表达因果关系的时钟。

Vector clocks，向量时钟，简写VC，是在Lamport时间戳基础上演进的另一种逻辑时钟方法，它通过向量（vector）结构记录本节点的Lamport时间戳，同时也记录其他节点的Lamport时间戳，因此向量时钟可以表达因果序即偏序关系。

向量时钟模型，用VC(a)来表示事件a的Vector Clock，根据如下规则可有如下性质：如果VC(a) < VC(b)，则事件a发生在事件b之前。

其规则表示方式如下：

1.为每个进程/节点Pi维护一个向量VC，即Pi的向量时钟，其如下属性：

a)VCi[i]：表示自身情况，到目前为止进程Pi自身上发生的事件的次序/个数。

b)VCi[j]：表示其他进程/节点情况，进程Pi知道的其他进程Pj上发生的事件的次序/个数。

c)例如，有三个节点，则各个向量时钟的表示方式为：

i.           VC_A： [A:0, B:0, C:0]

ii.           VC_B： [A:0, B:1, C:0]

iii.           VC_C： [A:1, B:0, C:6]

2.每个进程/节点的VC可以通过以下规则进行维护：

a)进程/节点Pi每次执行一个事件（发送、接收）之前，将VCi[i]加1，即将自身的次序/个数递增。

b)当Pi发送消息m给Pj时，在消息m上附带上VCi，即进程Pi的向量时钟。

c)当接收进程/节点Pj接收到Pi的发送的消息时，对于所有的k更新自己的VCj[k] = max{VCj[k], VCi[k]}，k是向量维度，表示系统内有多少个向量需要建立偏序关系，如3个副本每个进程/节点则有3个向量，更新的则是VCj[1]、VCj[2]、VCj[3]。

d)上述操作的目的，是建立进程/节点之间的偏序关系。

e)但是，当接收进程/节点Pj接收到Pi的发送的消息时，如果消息带来向量和本地向量产生冲突，则存在不一致的现象，规则如下：

a)对于n维向量而言，使得Vi > Vj，需要保证对于任意k（1≤k≤n）均有Vi[k] > Vj[k]。

b)如果Vi既不大于Vj且Vj也不大于Vi，这说明在并发的操作中发生了冲突，需要解决不一致现象，比如事务处理机制中需要回滚某个事务。

向量时钟用在分布式环境中为各种操作或事件产生偏序值，可检测操作或事件的并行冲突，用来保证操作的有序性和数据的一致性。

向量时钟保证数据的一致性，主要是指用来解决不同副本更新操作所需要确保的数据一致性问题。这种方式，不需要在数据项上保存向量时钟的值，但进程/节点需要维护向量时钟。例如在单调读一致性模型中，客户端需要维护上次读取到的数据的向量时钟，下次读取到的数据所在节点/进程维护的向量时钟则要求比来自客户端的向量时钟大才能读取比较新的数据[1]。

但是向量时钟的痕迹如果保留在数据项上（写操作发生），然后依据向量时钟进行数据读取的时候（读操作发生），可以确定分布式系统内部的因果序，即满足读一致（在读取的时候，获得满足因果序的一致的数据）。例如文献《Dynamo: Amazon’s Highly Available Key-value Store》给出的Dynamo中借鉴了向量时钟的版本向量（Version vector）可提高分布式系统的高可用性，使得在出现网络分区或者机器宕机时，分布式系统依然可读可写。当网络分区恢复之后，多个副本同步数据出现数据不一致的情况时，可用于检测数据冲突。这使得向量时钟在高分布式系统高可用性方面能有所作为。

另外，全序多播（totally ordered multicasting）中对向量时钟添加约束条件是一种比较好的一致性达成方式。

相对于其他方法，向量时钟的主要优势在于：

1.节点之间不需要同步时钟，即不需要全局时钟，这在去中心化环境下有用。

2.某些应用下不需要在所有节点上存储、维护一段数据的版本数；某些应用下载数据项上需要维护向量时钟值。

但是，逻辑时钟可能造成人在物理视角理解事件/事务顺序的不一致性，因此基于逻辑时钟的向量时钟依旧不能解决全部问题。

另外，使用向量时钟，还存在一些问题需要解决。诸如文献《Resetting Vector Clocks in Distributed Systems》讨论了如何重置向量时钟。在使用向量时钟时，很难确定用于实现时钟值的整数变量的最佳位数。如果数字太小，会发生溢出；如果数字太大，存储和维护时钟的额外成本将变得无法忍受。一个简单的策略可以让我们从这样的困境中解脱出来，那就是粗略估计必要的比特数，并在每一个进程的任何一个即将溢出时重置向量时钟。本文的目的是为正确的时钟重置建立必要和充分的条件，以保持矢量时钟的功能。我们的结果表明，对于某些应用程序，通过仔细选择启动时钟重置协议的条件，可以完全避免潜在的时钟溢出。

脚注文献：

[1] 该方法被一些系统采用，以解决Session内因果一致性问题，如MongoDB。

扫码加关注，知数行云，专业有深度

声明：本文禁止用于开发“任何软件程序,包括但不限于训练机器学习或人工智能(AI)系统”。