在大型分布式系统中，ObjectId与UUID的碰撞概率问题

Question

考虑到UUID rfc 4122（16字节）比MongoDB的ObjectId（12字节）要大得多，我正在尝试找出它们碰撞概率的比较。

我知道这是“相当不可能”的事情，但在我的情况下，大多数id将由大量移动客户端生成，而不是在有限的一组服务器内生成。我想知道在这种情况下是否存在合理的担忧。

与所有ID都由少数客户端生成的正常情况相比：

- 可能需要几个月才能检测到碰撞，自文档创建以来 - ID是从更大的客户端基础上生成的 - 每个客户端的ID生成速率较低

- SystematicFrank

---

为什么你允许移动客户端创建ObjectIds或任何永久Id，如果你关心数据完整性？ - WiredPrairie

客户端可能处于离线状态并存储长时间未同步的信息。我不想强制要求100%在线的移动应用程序。 - SystematicFrank

就我个人而言，我不会建立或设计一个允许客户端这样做的系统。当客户端离线时，我会为他们分配临时ID。我认为这与期望客户端不通过数据验证层直接写入MongoDb没有什么区别。 - WiredPrairie

@NeilLunn-我知道大多数客户端都默认这样做。但是离线客户端仍然可以创建它们，但在将其插入到集合中之前需要进行验证。 - WiredPrairie

这一切让我重新考虑离线客户端的UUID角色。@WiredPrairie对等待验证层的时间ID的评论似乎比仅依赖UUID更具未来保障，但也很麻烦......好吧，分区容错从来都不是一件轻松的事情。感谢提到“生日问题”。 - SystematicFrank

Answer 1

在我的情况下，大多数ID将在大量移动客户端中生成，而不是在一组有限的服务器中生成。我想知道在这种情况下是否存在合理的担忧。

那听起来对我来说是非常糟糕的架构。您使用的是两层架构吗？为什么移动客户端可以直接访问数据库？您真的希望依赖基于网络的安全性吗？

无论如何，以下是一些关于碰撞概率的考虑：

UUID和ObjectId都不依赖于它们的大小，即它们都不是随机数，而是遵循一种试图系统地降低碰撞概率的方案。在ObjectIds的情况下，它们的结构是：

• Unix纪元后4字节秒
• 3字节机器ID
• 2字节进程ID
• 3字节计数器

这意味着，与UUID不同，ObjectIds是单调的（除了在同一秒内），这可能是它们最重要的属性。单调索引将导致B-Tree更有效地填充，它允许按id进行分页并允许通过id进行“默认排序”以使游标稳定，并且当然，它们携带易于提取的时间戳。这些是您应该注意的优化，它们可能非常巨大。

从其他3个组件的结构可以看出，如果您在单个进程上执行> 1k插入/ s（实际上不可能，甚至不是从服务器），或者如果机器数量增长超过约10个（参见生日问题），或者如果单个机器上的进程数增长太大（再次说，这些不是随机数字，但它们在机器上确实是真正唯一的，但必须缩短为两个字节），则碰撞变得非常可能。

自然地，要发生碰撞，它们必须在所有这些方面匹配，因此，即使两台机器具有相同的机器哈希，仍需要客户端在完全相同的秒和相同的进程ID中使用相同的计数器值进行插入，但是是的，这些值可能会发生碰撞。

- mnemosyn

---

我们又做到了。不要说破！ - Neil Lunn

是啊...如果我没花时间去拿那杯咖啡的话... :( - mnemosyn

移动客户端将无法直接访问数据库，实际上，它们甚至可以在没有连接的情况下运行。但是，每个移动客户端迟早都需要将文档上传到主数据库。 - SystematicFrank

公平地说，我肯定曾经在我的时区里倒过酒。只要能传达意思就行，这没关系。 - Neil Lunn

从客户端生成ID是完全有效的情况，这并不意味着需要访问数据库。如果您这样做，一定不能使用ObjectIds，因为如果有数万个客户端生成它们，将会有严重的冲突问题。我不信任ObjectIds，因为即使需要特定条件，也很容易找到发生冲突的情况。 - Glenn Maynard

@mnemosyn 给出了有用的答案，但我不明白为什么每个进程每秒1k次插入操作已经成为一个问题。你会认为在同一秒内，“请求”每次增加1，下一秒开始时重置为零。但是使用3个字节，您可以表示比1k大得多的数字。我在这里错过了什么？ - alapeno

Answer 2

让我们来看一下文档中 "ObjectId" 的规范：

概述

ObjectId 是一个12字节的 BSON 类型，构造方式如下：

• 表示自 Unix 纪元以来经过的秒数的4字节值，
• 3个字节的机器标识符，
• 2个字节的进程id，和
• 以随机值开始的3字节计数器。

所以让我们从“移动客户端”的上下文考虑这个问题。

注意：这里的上下文并不意味着使用“移动客户端”直接连接数据库。这不应该这样做。但是可以非常简单地生成"_id"。

那么要点如下：

1. "自纪元以来经过的秒数" 的值对于每个请求而言都会相当随机。因此，只对该组件产生最小的冲突影响。尽管以“秒”为单位。

2. "机器标识符"。所以这是一个不同的客户端生成_id值。这消除了进一步“碰撞”的可能性。

3. "进程id"。所以如果可用来种子(并且应该是的)，那么生成的_id就有更多避免冲突的机会。

4. "随机值"。因此，另一个“客户端”以某种方式生成了与上述所有值完全相同的所有值，并且仍然成功生成了相同的随机值。

底线是，如果这个还不足以让您接受，则只需提供自己的“uuid”条目作为“主键”值。

但是，在我看来，这应该是一个相当有说服力的论点，可以考虑碰撞方面非常广泛。 至少可以这样说。

整个主题可能只是有点“过于宽泛”。 但我希望这能让人们更加远离“相当不可能”的想法，转而考虑一些更具体的东西。

- Neil Lunn