1

有没有办法序列化矢量时钟，以便在比较 2 个矢量时钟时，我可以只比较字符串？

使用 LevelDB 时，我希望能够将矢量时钟存储为记录键的一部分，并利用 LevelDB 为我所做的数据库键排序。

4

2 回答 2

1

我认为您不能这样做，因为当且仅当整个内容相同时，字符串才比较相等，并且矢量时钟不能比较不大于或小于不完全相同的时钟。例如，时钟[2,1]必须[1,2]比较“相等”。为了在序列化为字符串时满足该条件，它们必须映射到相同的字符串。如果它们映射到相同的字符串，您将无法将它们反序列化到不同的时钟。

于 2013-08-09T02:28:49.187 回答
1

我知道我参加聚会有点晚了，但我在工作中遇到了同样的问题，并找到了解决方案。您必须稍微放宽问题的约束，但它应该足以在分布式系统中创建有效的全局排序。

在适当的矢量时钟 A 和 B 中，

  • A > B iff（当且仅当）A 中的所有元素都 >= B 中的元素
  • 如果不是，A 和 B 是并发的（A > B 或 B > A）

因此我们有三种状态——之前（<）、之后（>）和并发。对于字符串，我们只有两个有效的比较值，< 和 >。鉴于这些约束，我们可以稍微放宽约束并得到以下结果：

  • str(A) > str(B)如果（不仅在这里）A 中的所有元素都 >= B 中的元素
  • 如果 A 和 B 并发，则 str(A) > str(B) 和 str(B) > str(A) 都可以接受

有了这些约束，如果我们按照序列化的字符串值对所有事件进行排序，我们就会得到一个可能的全局排序，这与向量时钟提供的所有部分排序一致。这意味着所有事件都位于其所有原因之后和其影响之前。唯一的窍门是我们需要一个唯一的整数标识符为每个参与者，但无论如何我们都需要类似的东西用于矢量时钟。

我做了一个python库来做这个，请看一下：https ://github.com/ethanfrey/vclock

如果您只想看看我如何序列化矢量时钟，请看这里。ArrayCodec 依赖于存储为数组的 vclock，由 actor 的 id 索引。DictCodec 依赖于一个字典，其键是整数演员的 id。基本实现在一个时钟上支持 256 个参与者和 1600 万个事件，每个参与者 6 个字节，但可以通过使用更多字节进行序列化轻松扩展：

https://github.com/ethanfrey/vclock/blob/master/vclock/codec.py

于 2016-02-01T17:31:08.107 回答