A Tree clock data structure(1)

介绍

论文提出了树时钟（Tree Clock）是一种用于替代传统向量时钟的新数据结构。目的是高效的维护执i行中的因果顺序。

$C_{t_1}(t_2)=i$表示。线程$t_1$的向量时钟中，关于$t_2$的当前分量为$i$。（你这个线程在我视角中的时间）
分量：Component指的是向量时钟中，对某个特定线程（或进程）的逻辑时间计数器。

对于向量时钟$\mathbb{C}_{t_1}$它与线程$t_1$相关，如果$C_{t_1}(t_2)=i$,那么意味着在偏序关系中，线程$t_1$的最新事件会被排序在$t_2$的前$i$个事件之后。

$ \mathbb{C}_{t_{1}} \leftarrow \mathbb{C}_{t_{1}} \sqcup \mathbb{C}_{t_{2}} $,表示将${t_{1}}$的向量时钟$\mathbb{C}_{t_{1}}$与线程$t_2$的向量时钟$\mathbb{C}_{t_{2}}$进行合并，将结果赋值给$\mathbb{C}_{t_{1}}$，这里的符号$\sqcup $表示按分量取最大值的合并操作。
向量时钟仅能检测到冲突，无法自动解决数据不一致，需要依赖应用层策略。
$\Theta$和O都可以用来表达时间复杂度。O表示的上届，即最坏的情况下不超过。$\Theta$表示紧确届。

向量时钟的基本操作是逐点加入$ \mathbb{C}_{t_{1}} \leftarrow \mathbb{C}_{t_{1}} \sqcup \mathbb{C}_{t_{2}} $，操作上，通过合并$ \mathbb{C}_{t_{1}}(t) \leftarrow \max\left(\mathbb{C}_{t_{1}}(t), \mathbb{C}_{t_{2}}(t)\right) $于每个线程$t$，并且捕获因果顺序的传递性：当$t_1$了解$t_2$时，它也学到了$t_2$对于其他线程的知识。请注意，如果$t_1$意识到$t$的后续时间（$t_1$知道的分量很大），则此操作是无效的。在$k$个线程中，向量时钟合并需要进行$\Theta(k) $，并且在$k$适中的情况下迅速成为瓶颈。这引发了如下问题，通过主动避免变量更新来加速是可行的吗？这种任务的挑战来自链接操作本身的效率，因为它只需要与向量大小时间的线性时间，任何改善操作都必须在亚线性时间（sub-linear time）进行，即甚至都不必触碰向量时钟的某些项。我们用一个具体的例子来说明这个算法，并提出了这项工作的关键见解。

图中每次发生一个event对应线程的时钟就向前进，比如e1->e3对$t_1$来说发生了一次事件，所以左数组中的第一个版本就向前走一位。

图1描述了在俩线程中向量时钟的合并操作的效果$ \mathbb{C}_{t_{1}} \leftarrow \mathbb{C}_{t_{1}} \sqcup \mathbb{C}_{t_{2}} $。时间戳中第j个条目对应于线程$t_j$.红色的条目保持不变，正如$t_1$已经知道稍后的时间。右边的树代表时钟$\mathbb{C}_{t_{2}}$,该结构编码了传递性。深灰色的标记表示其适中在$\mathbb{C}_{t_{2}}$中（相较于$\mathbb{C}_{t_{1}}$）已经处理适中的线程（即仅$t_2$）。浅灰色标记了执行链接操作时需要检查的节点。

考虑图1中的例子。它展示了分布式系统中6个线程的部分轨迹，以及每个事件的向量时间。当事件2由于同步而排在事件$e_3$之前时，$t_2$的向量时钟$\mathbb{C}_{t_{2}}$和$\mathbb{C}_{t_{1}}$的向量时钟进行合并，即$\mathbb{C}_{t_{1}}$的第$t_j$个条目会被更新为$\mathbb C_{t_1}(t_j)$和$\mathbb C_{t_2}(t_j)$的最大值。现在假设线程$t_2$已经通过$t_3$学习到了$t_3,t_4,t_5,t_6$的当时间。因此第事件$e_1$的向量时间的第$t_3$分量比比事件$e_2$的对应分量要大。$t_1$不可能通过事件$e_3$上执行的合并了解到关于$t_4,t_5,t_6$的任何新信息。因此简单的点更新对于$j=\{3,4,5,6\}$来说是多余的。不幸的是，向量时钟的平面操作不适合这种推理，不能避免这些冗余操作。

为了缓解这个问题，我们提出了新的层级树型数据结构来管理乡里时间，叫做tree clock。图1右描述了一个简单的树时钟编码的$\mathbb C_{t_2}$。子树的根在线程$t_3$,将$t_2$已经通过$t_3$学习了$t_4,t_5,t_6$这一个事实进行进行编码。为了执行合并操作$ \mathbb{C}_{t_{1}} \leftarrow \mathbb{C}_{t_{1}} \sqcup \mathbb{C}_{t_{2}}$, 我们从$\mathbb C_{t_2}$的根开始，然后向下面这样遍历树。给定一个当前节点$u$,当且仅当$u$表示的时间不被$t_1$所知道。因此在例子中，加入操作现在将只访问树的浅灰色的部分，导致链接操作的运行时间呈现亚线性。

上述的原则，我们称之为直接但掉性，是树时钟的俩个关键探索之一。另一个是间接单调性。开发树时钟结构关键的技术挑战在于

使用直接的单调性和间接的单调性来执行有效的更新
执行这些更新，以便为将来的操作保留直接和间接单调性

我们的贡献如下

我们介绍了树时钟，一个新的用来管理并行执行的逻辑时间的数据结构。与传统的向量时钟不同，树时钟动态层次结构自然的模拟进程之间的临时通讯模式。相应的，这允许合并和复制操作运行在亚线性时间。作为一个数据结构，树时钟提供了多个功能它们可以用来计算多个不同的排序关系。
我们证明了树时钟是HB的最优数据结构，在某种意义上，对于每个输入跟踪，总计算时间不能通过用任何其他数据结构替换来改进。而向量时钟没有这种作用。
我们通过提出MAZ和SHB的偏阶的基于树时钟的算法来说明树中功能的多样性。
我们执行了大规模的实验评估树中数据结构来计算MAZ，SHB和HB偏序，并且比较它们的执行和向量时钟进行对比。我们的结果表明了，通过树钟替换向量时钟，计算提升了2.97倍。鉴于我们的实验结果，我们相信用基于部分顺序的算法中的树时钟代替矢量时钟可以在许多应用中带来显着的改进。我们提供了理论的证明和辅助展示在技术报告39中展示。

A Tree clock data structure(1)