本文翻译自 Cosmologically Unique IDs，原载于 Hacker News。

引言

人类是一个探索性物种,刚刚越过太阳系的边界,但也许有一天我们会回首并称我们的银河系仅为”第一个”。在星际征途上,我们需要解决许多问题,今天我们来探讨其中一个小问题:如何为设备(或任何对象)分配保证永远唯一的ID?

能够标识对象是构建其他协议的基础工具,也是制造、物流、通信和安全的基石。每艘飞船和卫星都需要ID用于交通管制和维护历史记录。每个无线电、路由器和传感器都需要ID以便数据包有源和目的地。每个制造组件都需要ID以实现可追溯性。而在规模上,数量会爆炸式增长:机器人集群、万亿级别的零件、以及在一个文明供应链中流动的集装箱海洋。

ID的核心功能之一是区分不同对象,因此我们需要确保不会分配相同的ID两次。当我们尝试在宇宙尺度上解决这个问题时,唯一ID分配就变成了一个更具挑战性的问题。

但我们不妨一试。

随机方案

第一个也是最简单的解决方案是每次设备需要ID时随机选择一个数字。

这非常简单,可能是最佳方案;你可以在任何时间、任何地点执行此操作,无需中央权威或任何协调。

但最大的问题是,两个设备可能碰巧选择相同的ID。幸运的是,我们完全可以控制随机数的大小,从而控制碰撞概率。这意味着我们可以将碰撞可能性降至功能上为零。

你可能会说”功能上为零”还不够,虽然概率很小,但并非_实际上_为零,所以你很担心。但考虑这个例子:你现在被陨石击中的概率很小但非零,你甚至可能称这是一个”合理的”(虽然偏执的)担忧。但你担心地球上每个人现在都被陨石击中吗?那个概率也是非零的,但它小到我们将其视为不可能事件。这就是我们可以将ID碰撞概率降到多小的程度。

那么这个概率需要多小我们才能放心?换个角度问问题会有帮助:在预期发生碰撞之前,我们可以生成多少个ID?

最新版本的通用唯一标识符(Universally Unique Identifiers, UUID)使用122个随机位。使用生日悖论,我们可以计算出预期碰撞前的ID数量约为 2^61。

这算高还是低?是否足够支撑人类种族的银河系扩张直到宇宙热寂?让我们通过观察宇宙的物理限制来计算一个合理的数值。

宇宙极限

论文”Universal Limits on Computation”计算出,如果整个宇宙是一个最大效率的计算机(称为computronium),它在宇宙热寂之前会有 10^120 次操作的上限。如果我们假设每次操作生成一个新ID,那么我们可以计算出需要多大的ID空间才能避免碰撞直到宇宙耗尽时间。

使用生日悖论的近似,对于 d 个值的集合中的 n 个随机数,碰撞概率为:

p(n, d) ≈ 1 - e^(-n(n-1)/2d)

我们要 p = 0.5 的概率(这是碰撞”预期”发生的近似值),对于 n = 10^120 个数字,所以我们可以解出 d:

d ≈ -(n(n-1))/(2 × ln(1 - p)) = -(10^120(10^120-1))/(2 × ln(1 - 0.5)) ≈ 10^240

这就是如果我们想避免碰撞直到宇宙热寂,ID空间必须有多大。以位为单位,这需要 log2(10^240) = 797.26,所以至少798位。

这是最极端的上限,有点过度。使用798位,我们可以为真正的一切分配ID,并且永远不会预期碰撞。每个设备、每个微芯片、每个微芯片的每个组件、每次击键、每个时钟的每个滴答、每颗恒星和每个原子,所有这些都可以使用此协议进行ID标识,我们仍然不会预期碰撞。

合理限制

一个更合理的上限可能是假设可观测宇宙中的每个原子都将获得一个ID(我们假设原子在时间上不会被分配多个ID,这是一个让步)。据估计宇宙中有 10^80 个原子。使用相同的方程,我们发现需要532位来避免(概率上)碰撞达到该点。

或者也许我们将宇宙的所有质量转换为1克纳米机器人?我们将有 1.5 × 10^56 个机器人,这将需要372位的ID。

我们现在有四种大小的ID可以选择,取决于我们的偏执程度:

• 798位 来自computronium极限
• 532位 为每个原子分配ID
• 372位 为1克纳米机器人分配ID
• 122位 来自UUID标准

注意,这假设生成随机数时使用真正的随机性,但这有时是一个挑战。许多随机数生成器将使用具有非随机种子的伪随机数生成器。你需要确保你的硬件能够引入真正的随机性,例如来自量子源,或使用加密安全的伪随机数生成器(CSPRNG)。如果这不可用,使用传感器数据、时间戳或其他非确定性源可以帮助增加额外的随机性,但它不会是纯随机性,因此会增加ID碰撞的概率。禁止”常见”ID可能是个好主意,例如来自每个知名伪随机生成器的前1,000个ID、全零ID、全一ID等。

但如果我们异常偏执并__要求__ID在理论上保证唯一呢?不要这些概率性废话。这将带我们踏上一段旅程。

确定性方案

像往常一样,让我们从最简单的解决方案开始。

让我们创建一个使用计数器分配ID的单一中央计算机。当有人请求ID时,它分配其计数器的值,然后递增计数器,以便下一个ID将是唯一的。这个方案很好,因为它保证唯一性,并且ID的长度尽可能慢地增长:对数增长。

如果所有1克纳米机器人都从这个中央计算机获得ID,最长的ID将是 log2(1.5 × 10^56) = 187 位。实际上,由于编码可变长度值时的开销,它会稍微长一点。我们暂时忽略这一点。

好吧,这个解决方案有严重的问题。我看到的主要问题是访问。如果你在一个遥远的行星上,没有与中央计算机的通信怎么办?或者也许你的行星离计算机太远,获取ID需要数天时间。这是不可接受的。

为了解决这个问题,我们可能会开始向每个方向发送可以分配唯一ID的卫星。想象一下,我们发送ID为0的第一颗卫星,然后是ID为1的下一颗,并持续递增。现在人们只需要从最近的卫星请求ID,他们将获得看起来像A.B的ID,其中A是卫星的ID,B是卫星上的计数器。例如,第四颗卫星分配其第十个ID将发出3.9。这确保每个ID都是唯一的,并且获取ID更加容易访问。

但为什么止步于卫星?为什么不let任何具有ID的设备都能够分配新ID?

例如,想象一艘殖民飞船被建造并从卫星13获得第六个ID,所以它现在的ID是13.5。殖民者将这艘飞船带到外边缘,太远而无法与任何人通信。当他们到达他们的星球时,他们建造需要新ID的建筑机器人。他们无法从卫星请求ID,因为他们太远了,但他们可以从他们的飞船请求ID。建筑机器人获得ID 13.5.3 和 13.5.4,因为飞船在此之前已经分配了3个ID,其计数器处于3。现在这些机器人也可以分配ID了!

这确实假设你附近总是至少有一个能够分配ID的设备。但是,如果你处于创建新设备的条件下,那么你附近可能至少有一个预先存在的设备。

让我们称这个命名方案为Dewey。

Dewey方案

Dewey与随机ID在所需位方面相比如何?

如果ID的形式为A.B. … .Z,那么我们可以使用Elias omega编码对其进行编码。现在我们将忽略编码的小开销,并假设每个数字使用其二进制值完美表示,但我们稍后会加回来。这意味着ID 4.10.1 将具有二进制表示100.1010.1,它有8位。我们可以看到ID中的每个值如何对数增长,因为计数器对数增长。

ID随时间的增长取决于ID分配的顺序。让我们看一些例子。

如果每个新设备都去原始设备,创建一个扩展的子树,那么ID将按对数增长。这正是我们之前考虑的中央计算机模型。

如果我们采取另一个极端,每个新设备从最近的设备请求ID,那么我们形成一个链。在这种情况下,ID将线性增长。

或者如果每个新设备随机选择一个设备来请求ID呢?增长应该介于线性和对数之间。我们稍后会详细讨论这一点。

我们还可能会问,这个方案的最佳情况和最坏情况分配树是什么?我们可以运行模拟并选择最佳或最差的下一个节点,看看会发生什么。请注意,有多种方法可以显示最佳情况和最坏情况,因为许多ID具有相同的长度,所以我们一次任意选择一个,但树的整体形状将是相同的。还要注意,这使用单节点前瞻,这对于更复杂的方案可能会失败,但在这里是有效的。

我们看到一个最坏情况树是链。Dewey的最佳情况树似乎每个节点都加倍其子节点,然后重复。这导致它很快变宽。这表明如果我们期望新设备主要从已经有许多子节点的节点请求ID,这个方案会很棒,但如果我们期望新设备从其他较新的设备请求ID(链是这方面的极端例子),则不太好。

这是更大规模的最佳情况,以便更直观地了解图形如何增长。我们关心的事实是它是一个相当密集的图形,这意味着如果人类使用少量节点来请求ID,这个方案将是最佳的。

节点链导致ID线性增长很烦人。我们能设计一个更好的ID分配方案,对于链也是对数的吗?

Binary方案

这是ID分配方案的另一种尝试,让我们看看它是否会增长得更慢。

将整个ID空间可视化为二叉树。每个设备将在此树上的某处有一个ID。为了分配新ID,设备将获取其下方的列(对于每个设备,列从左侧或右侧交替),并分配该列中的ID。使用此方案,每个节点都有一个唯一ID,并且还有一个无限ID列表可供分配(图中的蓝色轮廓),其中每个ID也有一个无限ID列表可供分配,依此类推。

现在我们可以看看它如何在子树和链之间增长。

两种情况都线性增长。这不是我们要找的。现在值得问一下:这个方案总是比Dewey方案差吗?

如果我们看看这个方案的最坏情况和最佳情况,我们会注意到最佳情况的增长与Dewey不同。

以及更大规模的最佳情况。

它在所有方向上大致相等地增长。最佳情况树的深度比Dewey增长得更快,这意味着对于新节点同样可能从较旧节点和较新节点请求的增长模型,此方案会更好。具体而言,最佳情况树通过向树中的每个节点添加子节点然后重复来增长。

所以对于某些树,这个方案可以比Dewey更好。让我们继续探索。

实际上,有一个看起来不同但增长与此相同的方案。

2进赋值(2-Adic Valuation)

如果每个ID是整数,那么具有ID n 的节点将为其第 i 个子节点分配ID 2^i(2n+1)。本质上,每个子节点将使ID从上一个子节点加倍,第一个子节点从其父节点获得ID 2n+1。这是基于2进赋值的构造。

你可以使用算术基本定理证明这会生成唯一ID。

你可以通过使用 (i, n) 作为ID而不是 2^i(2n+1) 来相当容易地更改此方案的内存布局。现在节点的顺序子ID将对数增长而不是线性增长。这感觉非常类似于Dewey。

这有点复杂,但本质上我们可以说这是我们已经看过的Binary方案的替代表示。但我们想探索可能具有更好内存增长特征的新方案。

Token方案

让我们尝试逆向工程一个可以为链树对数增长的方案。

我们知道计数器对数增长,所以理想情况下,ID只会在添加新节点时递增计数器。

一个想法是拥有一个带有跳数附加的令牌传递给子节点。但是当设备收到新的ID请求并且它没有令牌可以传递时会发生什么?我们将有一个令牌索引,每次父节点必须创建新令牌时递增。新令牌将被附加到父ID。所以三个链看起来像 [], [(0,0)], [(0,1)],因为根节点没有令牌,然后第一个子节点导致根节点生成令牌,然后下一跳获得传递给它的令牌并带有递增的跳数。如果根节点还有两个ID请求,它将生成 [(1,0)] 和 [(2,0)],递增第一个值以生成唯一令牌。每个ID都是(令牌索引,跳数)对的列表,按创建排序。让我们通过查看模拟更好地了解这看起来像什么。

这里我们有扩展子树、链和一个最佳情况。

我们可以看到ID通常更长一些,因为每个ID中有更多信息,但至少在我们的极端情况下它对数增长。

链的这种对数增长反映在更大规模的最佳情况图中,我们看到从根增长的长链。

但这有点像谎言。链是对数的,但如果我们向任何节点添加哪怕一个子节点,方案就开始线性增长。如果我们的图在深度和宽度上一起增长甚至一点点,我们就会发现自己回到了线性状态。我们没有生成上面的最坏情况图,因为我们的模拟使用贪婪搜索算法,最坏情况需要两步来识别。真正的最坏情况是硬编码的,如下所示,我们可以看到它确实线性增长。

所以我们还没有找到在所有情况下都对数增长的算法。是否甚至可能设计一个即使在最坏情况下也总是对数增长的方案?

不幸的是没有。这是证明我们开发的任何方案在最坏情况下总是线性的证明。

为了证明任何方案必须增长多快,我们将看看随着节点添加,可能ID的数量增长多快。这将需要迭代每个可能的分配历史,然后计算所有可能分配历史空间中有多少个唯一可能ID。

重要的是要注意,每条路径必须产生不同的ID。如果任何两条路径产生相同的ID,那意味着可能生成两个具有相同ID的节点。

为了获得我们的基础,让我们首先考虑包含所有可能4节点路径的树。我们一会儿就会看到使用1索引的Dewey系统标记每个节点会很有用。标签不是ID(我们正在尝试编写关于任何可能ID方案的证明),标签只是对于讨论路径和节点很有用。

我们看到到达第四个节点的每个可能序列(仅考虑沿着该节点路径的节点)在上面突出显示。所以现在我们可以计算在具有4个节点的树中,对于这4个节点的任何分配顺序,我们需要多少个可能ID。

我们看到树中有16个节点,所以无论我们构建什么ID分配方案,都必须在添加四个节点时考虑16个唯一ID。

一般来说,注意每次我们添加新ID时,我们都会向所有可能路径的树中的每个节点添加一个新叶子。这意味着我们需要考虑的ID数量对于 n 个节点增长为 2^(n-1)。

我们也可以通过查看标签得出这个结论。标签中值的总和将等于添加该节点的迭代。反方向也是正确的: n 个节点的所有可能路径可以通过查看最多 n 的数字的所有可能和来生成,尽管它们必须大于0,和的顺序很重要。这些被称为整数组合,它们产生我们从上面看到的结果, n 个节点有 2^(n-1) 条路径。

这是一个问题。即使在我们使用计数器标记所有历史空间中每个可能节点的理想情况下(这实际上是一个有效的ID分配方案并生成我们已经看过的2进赋值方案),计数器的内存对数增长。无论我们使用什么方案,内存必须至少以 log2(2^(n-1)) = n-1 的顺序增长,即线性。

虽然我们已经证明我们想出的任何方案在最坏情况下都是线性的,但似乎合理的是,某些算法对于不同的增长模型表现更好。如果我们能为人类扩展到宇宙找到合理的增长模型,那么我们应该能够逆向工程最佳算法。

空间定居模型

让我们考虑近似人类如何扩展到宇宙的不同模型。

小规模

第一个也是最简单的考虑模型是随机父节点选择。每次添加设备时,它将从前面的所有设备中随机选择以请求ID。这将产生所谓的随机递归树(Random Recursive Tree)。我们还将在小规模上运行它,最多约2,048个节点。我们实际上将使用Elias omega编码,以便我们可以获得与随机ID分配位使用更具可比性的结果。

最佳方案是Binary,其次是Dewey,Token是最差的。这有一定道理,因为随机树将以大致相等的速率在深度和宽度上增长,这是Binary的最佳情况。Dewey和Token更难推理,但我们怀疑Dewey对于高宽度树表现最佳,Token对于高深度树表现最佳。

例如,我们可以查看优先附着随机图,其中节点更有可能连接到具有更多连接的节点,这是许多现实世界网络遵循的模型。树的宽度将主导深度,所以我们可能期望Dewey胜出。具体而言,优先附着选择一个节点由度(边数)加权来选择父节点,这增加了该父节点的度,创建正反馈。让我们看看每个ID分配方案如何处理这个新增长模型。

我们看到Dewey表现最佳,其次是Token,然后是Binary,差距很大。

虽然,设备变得更受欢迎是因为它们分配更多ID似乎不现实。似乎合理地相信某些设备比其他设备更受欢迎,但这种流行度不取决于其历史。卫星相对于灯泡将非常受欢迎,不是因为卫星过去碰巧分配了更多ID,而是因为其固有的属性如其位置和可访问性使其更容易从其请求ID。我们可以使用适应性模型,其中每个节点使用确定其受欢迎程度的适应性分数进行初始化。适应性分数从指数分布中采样。

似乎Dewey和Binary表现同样好,Token产生最差ID。虽然这看起来与纯随机图非常相似。

我们需要为大量节点运行大量模拟,看看是否有一致的模式。

中规模

下面我们为每个增长模型运行1,000次模拟,构建一个最多约一百万(2^20)个节点的图。我们绘制图的最大ID随时间的变化。每次运行显示为一条线,然后x轴变为指数,因为我们怀疑ID随着节点计数的对数增长,这在指数x轴上更容易看到。

那是一些相当干净的结果!我们看到大多数图都有大致直线(例外是Binary对于优先增长模型和适应性增长模型,它弯曲一小部分)。直线是ID增长实际上是对数的强烈指示,我们可以拟合一条曲线。为了检查其他ID分配方案的优先模型,让我们再次绘制它而不包括Binary。

我们仍然看到指数图上的线性趋势,这表明Dewey和Token方案仍然对数增长。

以下是我对为什么图是对数的最佳解释。

在随机增长模型中,每个节点在统计上与其他节点无法区分,所以我们应该期望每个节点随时间看到相同的平均子树。在分布中,根下的子树应该看起来类似于第百万个节点下的子树,只是规模较小。这表明我们可以使用这些子树之间的递归关系来推断整体缩放定律。

假设我们模拟1,000节点树的增长,并观察到最大ID长度增加了约34位(这正是我们为Dewey看到的)。然后我们取这1,000个节点中具有最长ID的节点,并概念上重新运行1,000节点模拟,此节点充当根。因为随机模型对称地对待所有节点,我们期望此节点的子树以与原始根子树统计相似的方式增长。由于我们所有的ID分配方案在祖先上都有加性ID长度,将此子树增长到1,000个节点应该使最大ID长度再增加大约34位。

然而,此子树嵌入在完整树中。到此节点累积1,000个后代时,我们应该期望原始树中的所有其他节点平均也累积了约1,000个后代。换句话说,每次我们模拟孤立的1,000节点子树时,完整树大小增长1,000倍,而最大ID长度增加大约恒定量。在实践中,我们观察到增加接近38位而不是34位,这可能是由于噪声、小(n)效应、编码开销或此启发式中的缺陷。

这意味着ID长度线性增长,而节点总数指数增长。在这个例子中,最大ID长度函数满足形式为 T(n · 1000^d) ≈ T(n) + 34 d 的递归,这只有通过对数函数才能满足。明确写出,我们得到 T(n) ∝ log(n)(在这种情况下基数约为1.225,由观察到的常数设置)。

这种分析更难应用于适应性和优先模型,因为节点在这些方案中彼此不同。但图确实表明它可能仍然是真的。可能是分析对于这些方案平均上仍然正确,因此关于不同节点的更精细细节在扩展时被冲走,但我对该论点不太自信。更大的模拟可能有助于识别趋势是否实际上非对数。

未来的模拟可能还会考虑设备有生命周期(节点在一段时间后消失),这可以显著改变分析。具有恒定生命周期的初始测试(相对于添加了多少节点)显示ID随时间线性增长。这是有道理的,因为它本质上强制一个宽链,我们知道对于我们所有的ID分配方案,宽链线性增长。这是一个合理的假设吗?如果设备更受欢迎则寿命更长,那会如何改变结果?

现在我们将使用上述模拟作为我们模拟梯子的第一级,使用这些结果插入更大的模型,然后再插入更大的模型。

大规模

为了确定这些方案可能需要多少位用于宇宙范围的人类,我们需要评估ID如何在世界之间增长的模型。

我们将使用百万节点模拟的适应性增长模型来模拟行星表面前几年的ID分配。要扩展到数百年来的完整行星,我们可以对数曲线拟合我们的适应性模型并外推。

对于此分析,我们将选择Dewey ID分配方案,因为它似乎在所有增长模型中表现良好。

当我们将对数曲线拟合到适应性增长模型中Dewey ID分配的最大ID长度时,它拟合曲线 (6.5534 ± 0.2856) ln(n)(其中 0.2856 是标准偏差)。这个方程现在允许我们在任意数量的设备后紧密近似最大ID长度。

我们有了行星扩展的模型,现在我们需要人类如何从一个行星传播到下一个行星的模型。我们真的不知道当/如果我们扩展到宇宙时会是什么样子,但人们肯定尝试过。以下是一些模拟人类如何扩展到宇宙的论文,从中我们可以尝试创建我们自己更与我们分析相关的最佳猜测模型。

• Galactic Civilizations: Population Dynamics and Interstellar Diffusion, by Newman and Sagan. 本质上,穿过银河系的扩张是缓慢的,因为只有新定居的行星有助于进一步传播,每个行星在出口殖民者之前必须经历本地人口增长,在银河系中产生缓慢而恒定的扩张波前。

• The Fermi Paradox: An Approach Based on Percolation Theory, by Geoffrey A. Landis. 本质上,使用渗透理论和一些”合理”的传播到新行星的速率和生存率值,本文发现一些波前会消亡而其他存活,意味着我们将以分支形式缓慢穿过银河系。

• The Fermi Paradox and the Aurora Effect: Exo-civilization Settlement, Expansion and Steady States. 本质上,将太阳系建模为气体,定居作为取决于行星之间距离、行星生活条件和文明生命周期的过程,他们发现宇宙的遥远星团将陷入被定居的稳态。

我们将使用以恒定速度扩展的扩张波前在银河系之间的行星进行建模,该波前定居任何可居住的行星,其中新行星从最近的定居行星获得随机ID种子。我们将使用相同的模型在银河系之间的扩张。

这将产生ID长度的线性增长,因为波前向外移动。随着每个行星重新启动ID分配过程,它将导致ID长度根据我们为第一个行星看到的相同曲线变得更大。

我们粗略估计银河系中可能有大约400亿颗可居住行星,最新估计认为可观测宇宙中有大约2万亿个星系。

如果我们假设行星在银河系中接近均匀定位,并且银河系大致呈球形(许多星系实际上是圆盘,但它不会改变最终结论),那么我们可以预期银河系的半径以行星跳数计算可以使用球体体积方程求解。以行星跳数为单位的半径可以近似为 ∛(3V/4π) = ∛(3·40·10^9/4π) ≈ 2121。

如果我们假设每个行星在定居下一个最近行星之前产生大约10亿个ID,那么我们可以计算出到达银河系边缘时的ID长度。这将是每个行星最长ID增加的量(我们假设10亿次分配)乘以这发生的次数,即我们到达银河系边缘跳到的行星数。这听起来不太好。

6.5534 · ln(10^9) · 2121 ≈ 288048

那是很多位。而且它只会变得更糟。我们将使用与行星相同的近似来处理星系。

再次假设星系均匀填充空间,作为一个球体,我们得到星系之间的跳数为 ∛(3·2·10^12/4π) ≈ 7816。使用上面的 288048 作为每个星系ID增加的长度,我们得到:

288048 · 7816 = 2251383168

这是一个异常大的位数。仅将ID存储在内存中就需要大约 281.4 MB。

与随机解决方案相比,这个确定性解决方案非常糟糕,即使在最偏执的情况下,随机解决方案也只使用798位。

我们可能会看到这一点并尝试思考解决方案。也许我们规定定居者必须从其父行星带来几千个他们能找到的最短ID到新行星,这将每个行星的ID长度减少大约一半。但除非我们找到一种在行星和星系之间对数增长ID的方法,否则它甚至不会接近(记住,2121 · 7816 = 16577736 总共的行星跳数)。

所以现在看来,普遍唯一ID最安全的选择是具有足够大范围的随机数,使得碰撞概率在功能上为零。但考虑如何将该概率实际上降至零很有趣:设计不同的ID分配方案、运行模拟以及建模人类在宇宙中的扩张。

总结与思考

这篇文章深入探讨了一个看似简单但实际复杂的问题:如何在宇宙尺度下生成全局唯一ID。作者从两个方向进行了探索:

关键要点

1. 随机方案实用性: 在大多数场景下,使用足够位数的随机ID(如122位的UUID v4)是最佳选择,碰撞概率可以低到忽略不计。

2. 物理极限作为参考: 798位足以覆盖整个宇宙计算极限,这为”偏执”场景提供了上限参考。

3. 确定性方案的代价: 虽然理论上保证唯一性,但在宇宙尺度扩展时,Dewey等方案会产生数百万位的ID,这在实践中不可行。

4. 增长模型很重要: 不同的ID分配方案在不同网络增长模型下表现差异很大,选择方案需要考虑实际应用场景。

个人见解

从工程实践角度,我更倾向于推荐随机方案。原因如下:

• 简单性: 无需协调,任何设备可独立生成
• 可扩展性: 不受网络拓扑限制
• 实用性: UUID v4已被广泛验证和采用

确定性方案虽然理论上优雅,但作者的分析清楚地展示了其在大规模场景下的局限性。对于需要因果关系的特殊场景(如分布式事务),可以考虑混合方案:使用随机UUID作为全局唯一标识,同时维护局部序列号用于因果追踪。

文章的模拟方法和数学推导都很严谨,对理解分布式系统中ID生成的权衡很有帮助。

所有可视化、模拟和分析的代码可以在作者的GitHub仓库找到。

这是一次非常探索性的研究,还有许多路径未被探索,如果你探索了其中之一并想讨论它,请联系作者。

感谢Kevin Montambault和Jacob Hendricks乐于与我谈论这些奇怪的兴趣爱好长达数小时。我感到感激和荣幸能有如此深厚好奇心的朋友。