问题标签 [vector-clock]

我们有一个大型的高性能软件系统，它由多个交互的 Java 进程（不是 EJB）组成。每个进程可以在同一台机器上，也可以在不同的机器上。

某些事件在一个进程中生成，然后以不同的方式传播到其他进程以进行进一步处理等等。

出于基准测试的目的，我们需要创建每个事件何时通过“检查点”的日志，最终将这些日志组合起来以获得每个事件如何通过系统传播以及延迟多少的时间线（当然，进程切换和 IPC 添加延迟，没关系）。

当然，问题在于时钟同步。所以这是我的问题：

1）如果所有进程都在同一台机器上，是否保证 currentTimeMilis 在调用时是准确的？ITP的错误有一定的界限吗？

2）如果某些进程可能在不同的机器上，是否有用于时钟同步的现成解决方案（也是免费或开源的）？我最好寻找一种可以绕过操作系统（Windows 或 Linux）并直接从 Java 工作的解决方案。我还理想地寻找可以以微秒精度运行的东西。我考虑过 NTP，但我不确定它是否可以通过 Java 而不是通过操作系统获得，而且我不确定它的复杂性。

3）有没有办法确定在特定配置（或我最终使用的任何解决方案）中使用 NTP 的误差范围，以便我可以在计算延迟时给出误差范围？

谢谢！

对于在不同设备上运行的代码，我需要确定在这些设备之间发送的消息的顺序。因此，我想使用矢量时钟，因为我阅读矢量时钟允许对事件进行排序。

是否有任何已建立的框架/公共 API 可供我使用？或者参考实现=或者我必须从头开始编码吗？

感谢您的任何参考和提示

我有一堆日志文件，其中包含事件日志及其中记录的矢量时钟。现在在比较任意两个事件的矢量时钟时，对矢量时钟的每个分量的平方和求根并用结果与另一个比较，然后得出结论是否正确较小的值先于另一个？

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

但是我不确定向量时钟仍然没有解决什么问题，然后由更庞大的矩阵时钟解决？

我一直在阅读CvRDT，我知道 Riak 已经在 Riak 2 中添加了一些。

gcounter我的问题是：当听起来vclock与每个对象关联的底层都记录相同的信息时，为什么 Riak 会实现 a ？结果不是用 agcounter存储vclock，每个都包含相同的基本信息吗？

我现在唯一的猜测是，Riak 可能会垃圾收集对vclocksa 的目的实际上很重要的修剪信息gcounter（即增量的数量）。

我不能很好地阅读 Erlang，所以我可能错误地认为 Riakvclocks使用这些特殊数据类型进行存储。然而，这个问题仍然适用于在标准 Riak 之上编写的本土解决方案vclocks（因此继承每个持久的对象）。

编辑：

从那以后，我写了以下文章来帮助以更实用的方式解释 CvRDT。本文还涉及我上面强调的冗余：

无冲突的复制数据类型 (CRDT) - 一种易于理解的解释，数学较少。

众所周知，Vector时钟检测事件之间的因果依赖关系，但有不同的实现方法。之间有什么区别（优点/缺点）：

• 仅在发送（之前）时打勾。
• 仅在发送（之后）时打勾。
• 接收时打勾，发送前打勾
• 接收时打勾和发送后打勾

我有一个关键代码路径，其中线程使用整数上的原子增量来计算全局发生的事件数。这是相当快的，但仍然需要保存整数的缓存行在内核之间反弹。在 NUMA 系统中，这会产生大量的 MESI 流量。

hot pat 的伪代码是所有线程都这样做：

计数器是单调递增的，它必须达到的值是预先知道的。

至少一个线程必须断定全局计数器CHECK_VALUE在递增后已达到counter。多个线程得出该结论是可以接受的（我总是可以在那时同步它们 - 因为那不再是热门路径）。

counter如果我知道它是单调的并且最终值已知，是否有可能比使用原子增量来跟踪值更好？

I've been using MongooseJS's revisionKey for a while now - the __v field that it includes with documents, by default. I understand what the purpose of the revision number is, and generally when it is updated.

I was recently speaking with a friend about the idea of a "vector clock" and I mentioned MongoDB and MongooseJS having this __v field. At the time, it sounded like this could be a vector clock. But having read a little bit about vector clocks, now I'm not sure.

So I'm wondering: Can the versionKey attribute of MongooseJS, and the __v field that it produces by default, be considered a vector clock? Yes, or no, and why?

我的想法是实现一个基本的“矢量时钟”，其中时间戳是基于时钟的，始终向前并保证是唯一的。

例如，在一个简单的表中：

我使用触发器在插入之前设置时间戳值。当两个插入同时到达时，它基本上只是进入未来：

然后我在两个单独的客户端中运行大量插入：

正如预期的那样，我遇到了碰撞：

@rach 建议current_clock()与对象混合SEQUENCE，但这可能意味着摆脱TIMESTAMP类型。即使我真的无法弄清楚它如何解决隔离问题......

有没有共同的模式来避免这种情况？

谢谢你的见解:)

我正在为具有多个节点的应用程序使用动态矢量时钟。每个节点都有一个唯一的 ID，该 ID 与它的时钟一起存储在矢量时钟中。我需要将矢量时钟转换为文本表示。我目前的解决方案是对作为矢量时钟一部分的所有 id 构建哈希。然而，这需要我在所有节点名称的产品空间中搜索匹配的哈希。

例如，我有 3 个节点（简化）ID 为“a”、“b”和“c”，时钟为 3、6 和 4。不要将它们存储为“a:3-b:6-c:4” ，我将 ID 加入“a\nb\nc”并从中创建散列。最后，我有一个带有“hash:3-6-4”的字符串，以保持向量时钟的简短，即使有很多节点也是如此。

随着时间的增加，这个动态矢量时钟应该能够添加新节点。例如，如果我们将“d:1”添加到上面的矢量时钟，我将“a\nb\nc\nd”的哈希值加入到“hash:3-6-4-1”中。

如果我现在在任何节点上接收到这个向量时钟，我希望能够从哈希中重建 ID，以便在本地使用它们。我目前的实现不适用于一次超过 15 个节点，因为从散列重建 ID 太昂贵了。

是否有任何有效的算法或数据结构可以让我更智能地解决这个问题？

非常感谢您的意见。