《云数据管理：挑战与机遇》2.1 向量时钟

本节书摘来自华章出版社《云数据管理》一书中的第2章，第1节，作者迪卫艾肯特·阿格拉沃尔，更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.1.2　向量时钟

逻辑时钟可以捕获潜在的因果关系，但是，这并不意味着一定有因果关系，逻辑时钟条件只是一个必要条件，并不是充分条件。分布式系统中的所有事件可能需要一个更强的时钟条件：

e→f当且仅当clock(e)<clock(f)。

该条件可按如下方式实现：为每一进程i赋一个长度为n的向量vi，n是系统中所有进程的数量。每一个执行的事件都被赋一个本地向量。

每个向量都初始化为0，即：vi[j] = 0，其中i, j

= 1, …, n。进程i在每一个事件之前增加本地向量元素的值，vi[j] = vi[j] +1。当进程i发送消息的时候，会将本地向量vi和消息一起发送。当进程j接收消息时，会将接收向量和本地向量的元素逐个进行比较，并将本地向量设置为两者之中较大的值，vj[i] = max(vi[i], vj[i]), i = 1, …, n。

给定两个向量v和v'，v=v'当且仅当v[i] = v'[i], i = 1, …, n，并且v≤v'当且仅当v[i]≤v'[i], i = 1, …, n。如果至少存在一个j(1≤j≤n)，使得v[j]<v'[j]，并且，对所有的i≠j，其中，1≤i≤n，v[i]≤v'[i]，则v<v'。对任意两个事件e和f，e→f当且仅当v(e)<v(f)。如果既不满足v(e)<v(f)，又不满足v(f)<v(e)，那么两个事件是并发的。

图2-3中，我们为图2-1示例中的所有事件都赋了向量时间值。

图2-3　向量时钟

虽然向量时间可以准确地捕获因果关系，但是向量的大小是网络大小的函数，可能非常大，并且每一个消息都需要携带额外的向量