矩阵时钟解决了什么问题，而向量时钟不能解决？

Question

我理解在键值存储更新中，标量逻辑时钟无法提供足够的信息以判断是否存在更新冲突，因此需要向量时钟。

但是我不确定向量时钟无法解决什么问题，而更笨重的矩阵时钟则能够解决这个问题？

- Lazer

Answer 1

在事件一致性环境中，系统创建的所有消息都需要保留，直到每个对等节点都接收到该消息（==事件一致性）。但是您不想永久保留消息，因此您需要一种方法来告诉哪些消息已被所有节点接收并且可以删除，这就是为什么使用矩阵时钟。

矩阵时钟是矢量时钟列表，因此您知道系统中每个节点的当前状态。基于此，您可以知道每个对等方已经接收了哪些消息。当您与系统中的另一个节点交换消息时，您会比较矩阵时钟，并始终记住每个节点的最高值。然后，您可以删除之前发送的消息，因为节点必须已经接收到它们。

这是TSAE（时间戳反熵）协议的简要描述。您可以在Richard Andrew Golding于1992年撰写的论文项目《弱一致性组通信和成员资格》中了解更多信息（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.7385&rep=rep1&type=pdf），从第5章开始。

- peter

---

是的，您需要与每个点对点通信以获取其向量时钟并了解它们所知道的内容。矩阵时钟可以为您提供与每个节点通信的信息。 - peter

有没有任何真实世界的系统使用矩阵时钟来实现最终一致性？或者新的最终一致性系统是否采用了不同的方法？ - Chee Loong Soon

似乎对于这种方法能够在动态进出一个最终一致的系统的进程数量下工作，需要有一些进程发现算法来让每个主机知道哪些主机已经关闭并且不再需要保留在“字典（而不是向量）时钟”中。 - Chee Loong Soon

如果我们采用节点与每个其他节点进行通信来获取它们的向量时钟，那么每个主机仍需要在等待来自过时主机的更新时本地缓存它们，从而根据定义创建矩阵时钟。因此，与其与每个节点进行通信，不如仅向少数对等节点发送矩阵时钟，使信息能够传递地传播得更快。 - Chee Loong Soon

我还没有遇到过使用矩阵时钟的真实世界系统。这些高可用的分布式系统只有在所有并发消息都是可交换的情况下才能工作。如果系统中有足够多的参与者，大多数消息将与其他消息并发，基本上所有消息都必须是可交换的，以确保每个人最终达到相同的状态。而这很难实现。你可以尝试使用CRDTs，但你不能用CRDTs来建模所有东西。 - peter

Answer 2

Lamport时钟（标量逻辑时钟）, 向量时钟和矩阵时钟的区别在于它们表示不同级别的“知识”。对于站点 $i$ 中的向量时钟 $vt_i[1 \ldots n]$, 条目 $vt_i[k]$ 表示站点 $S_i$ 对站点 $S_k$ 的知识。这种知识的形式为“$i$ 知道 $k$ $\ldots$”。对于站点 $S_i$ 中的矩阵时钟 $mt_i[1 \ldots n, 1 \ldots n]$，条目 $mt_i[k,l]$ 表示站点 $S_i$ 对站点 $S_l$ 的知识，该知识由站点 $S_k$ 关于站点 $S_l$ 的知识组成。这里的知识形式为“$i$ 知道 $k$ 知道 $l$ $\ldots$”。直观地说，我们能够通过更多的知识做更多的事情。

以下描述主要引用自 [1]: 向量时钟和矩阵时钟广泛用于异步分布式消息传递系统。一些使用向量时钟的示例领域包括检查点、因果记忆、维护复制文件的一致性、全局快照、全局时间近似值、终止检测、有界多写者共享变量构造、互斥和调试（谓词检测）。一些使用矩阵时钟的示例领域包括设计容错协议和分布式数据库协议，包括在分布式数据库中丢弃过时信息的协议以及解决复制日志和复制字典问题的协议。

对于矩阵时钟，我们注意到 $min_k(mt_i[k,i]) \ge t$ 表示站点 $S_i$ 知道每个其他站点 $k$ 的进度直到其本地时间 $t$。正是这个属性使得一个站点不再需要发送本地时间 $\le t$ 的信息或丢弃过时信息。

[1] Concurrent Knowledge and Logical Clock Abstractions Ajay D. Kshemkalyani 2000

- hengxin