Clever Geek Handbook

如何生成UUID



您可能已经在项目中使用了UUID，并认为它们是唯一的。让我们看一下实现的主要方面，并查看为什么UUID实际上是唯一的，因为出现相同值的可能性很小。



UUID的现代实现可以追溯到RFC 4122，它描述了生成这些标识符的五种不同方法。我们将逐一介绍它们，并逐步介绍版本1和版本4的实现。



理论



UUID（通用唯一IDentifier）是一个128位数字，在软件开发中用作元素的唯一标识符。它的经典文字表示形式是一系列32个十六进制字符，在8-4-4-4-12模式中由连字符分隔为五个组。



例如： 



3422b448-2460-4fd2-9183-8000de6f8343


UUID实现信息嵌入在以下看似随机的字符序列中： 



xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx


M和N位置的值分别定义UUID的版本和变体。



版



版本号由位置M上的四个最高有效位标识。今天，存在以下版本：





选项



该字段定义嵌入在UUID中的信息的模板。UUID中所有其他位的解释取决于变量的值。



我们通过位置N的前1-3个最高有效位来确定它。





如今，最常使用的选项1是MSB0equals1和MSB1equals 0。这意味着，给定的通配符-选择的比特-唯一可能的值是8，9，A或B。



备注：



1 0 0 0 = 8

1 0 0 1 = 9

1 0 1 0 = A

1 0 1 1 = B


因此，如果您在位置N看到具有此类值的UUID，则这是选项1中的标识符。



版本1（时间+唯一或随机主机ID）



在这种情况下，将这样生成UUID：将生成UUID的设备的某些标识属性添加到当前时间，最常见的是MAC地址（也称为节点ID）。



通过将48位MAC地址，60位时间戳，14位“唯一”时钟序列以及为版本UUID和变体UUID保留的6位串联起来来获得标识符。



时钟序列只是每次更改时钟时都会增加的值。


此版本中使用的时间戳是自1582年10月15日（公历起源）以来的100纳秒间隔数。



从一个纪元开始，您可能对Unix时间系统很熟悉。这只是另一种零日活动。Web上有一些服务可以帮助您将一个时间表示形式转换为另一个时间表示形式，所以我们不要就此止步。


尽管此实现看起来非常简单和可靠，但是使用在其上生成标识符的计算机的MAC地址不允许将此方法视为通用方法。特别是在安全性是主要标准时。因此，在一些实施方式中，使用6个随机字节代替节点标识符，该6个随机字节取自受密码保护的随机数生成器。



构建UUID版本1如下所示：



  1. 使用当前UTC时间戳的最低有效32位。这将是UUID [ TimeLow]的前4个字节（8个十六进制字符）。
  2. 当前UTC时间戳的中间16位被占用。这将是接下来的2个字节（4个十六进制字符）[ TimeMid]。
  3. 接下来的2个字节（4个十六进制字符）将UUID版本的4位与当前UTC时间戳的剩余12个MSB（总共60位）[ TimeHighAndVersion]相连。
  4. 接下来的1-3位定义UUID版本变体。其余位包含一个时钟序列，该时钟序列会给此实现带来少量随机性。这样可以避免在同一系统上运行多个UUID生成器时发生冲突：要么为生成器重新设置系统时钟，要么放慢时间更改[ ClockSequenceHiAndRes && ClockSequenceLow]。
  5. 最后6个字节（12个十六进制字符，48位）是“节点ID”，通常是生成器MAC地址[ NodeID]。


使用串联生成版本1 UUID： 



TimeLow + TimeMid + TimeHighAndVersion + (ClockSequenceHiAndRes && ClockSequenceLow) + NodeID


由于此实现取决于时钟，因此我们需要处理边缘情况。首先，为了最小化系统之间的相关性，默认情况下，时钟序列被视为随机数-在系统的整个生命周期中仅执行一次。由于初始时钟序列完全独立于节点ID，因此这给我们带来了额外的好处，即支持可以跨系统携带的节点ID。



请记住，使用时钟序列的主要目的是给我们的方程式增加一些随机性。时钟序列位有助于延长时间戳并适应甚至在处理器时钟更改之前就生成多个UUID的情况。这样，我们避免在时钟调回（设备关闭）或节点标识符更改时创建相同的标识符。如果将时钟调回或可能已经调回（例如，在系统关闭时），并且UUID生成器无法验证标识符的生成时间戳比指定时钟值晚，则必须更改时钟序列。如果我们知道它的先前值，则可以简单地增加它；否则，必须将其随机设置或使用高质量的PRNG。



版本2（分布式计算环境的安全性）



该版本与前一个版本的主要区别在于，此处不是使用时钟序列最低有效位形式的“随机性”，而是使用了系统的标识符特征。通常，这只是当前用户的ID。版本2的使用频率较低，与版本1的差异很小。因此，让我们继续。



版本3（名称+ MD5哈希）



如果命名或命名信息需要唯一的标识符，则通常使用UUID版本3或版本5，



它们将任何“命名”实体（站点，DNS，纯文本等）编码为UUID值。最重要的是，将为相同的名称空间或文本生成相同的UUID。



请注意，名称空间本身是一个UUID。 



let namespace = “digitalbunker.dev”
let namespaceUUID = UUID3(.DNS, namespace)

// Ex: 
UUID3(namespaceUUID, “/category/things-you-should-know-1/”) 
4896c91b-9e61-3129-87b6-8aa299028058

UUID3(namespaceUUID, “/category/things-you-should-know-2/”) 
29be0ee3-fe77-331e-a1bf-9494ec18c0ba

UUID3(namespaceUUID, “/category/things-you-should-know-3/”) 
33b06619-1ee7-3db5-827d-0dc85df1f759


在此实现中，UUID命名空间被转换为与输入名称连接的字节字符串，然后用MD5散列，从而为UUID生成128位。然后，我们重写一些位以准确地复制版本和版本信息，而其余部分保持不变。



重要的是要了解，不能基于UUID计算名称空间和输入名称。这是不可逆的操作。唯一的例外是当攻击者已经知道其中一个值（命名空间或文本）时的暴力破解。



使用相同的输入，生成的版本3和5的UUID将是确定的。



版本4（PRNG）



最简单的实现。



6位保留用于版本和变体，还剩下122位。该版本仅生成128个随机位，然后用版本和版本数据替换其中的6个。



这样的UUID完全取决于PRNG（伪随机数生成器）的质量。如果其算法过于简单或缺少初始值，则重复标识符的可能性会增加。



在现代语言中，UUID版本4是最常用的，



其实现非常简单：



  1. 我们生成128个随机位。
  2. 用正确的版本和版本信息重写一些位：



    1. 取第七位并0x0F与以消除高位字节。然后使用0x40OR分配版本4。
    2. 然后我们取第九个字节，0x3F对c执行AND操作，并对c执行0x80OR操作。
  3. 将128位转换为十六进制并插入连字符。


版本5（名称+ SHA-1-hash）



与版本3的唯一区别是我们使用的是SHA-1哈希算法，而不是MD5。此版本优于第三个版本（SHA-1> MD5）。



实践



UUID的重要优点之一是其唯一性不取决于中央授权机构或不同系统之间的协调。任何人都可以创建UUID，并确信在可预见的将来没有其他人会产生此值。



这使得有可能在一个数据库中组合由不同参与者创建的标识符，或者在数据库之间移动标识符的可能性很小。



UUID可以用作数据库中的主键，可以用作上载文件的唯一名称，也可以用作任何Web源的唯一名称。您不需要中央授权机构即可生成它们。但这是一个双重解决方案。由于缺少控制器，因此无法跟踪生成的UUID。



还有其他一些缺点需要解决。固有的随机性增加了安全性，但使调试更加困难。同样，在某些情况下，UUID可能是冗余的。假设使用128位来唯一标识总大小小于128位的数据是没有意义的。



独特性



似乎，如果您有足够的时间，您可以重复一些价值。特别是在版本4的情况下，但实际上并非如此。如果您要在100年内每秒产生十亿个UUID，那么其中一个值重复出现的机会约为50％。鉴于PRNG提供了足够量的熵（真实随机性），否则翻倍的可能性会更高。一个更说明性的例子：如果生成了10万亿个UUID，则出现两个相同值的概率为0.00000006％。



对于版本1，仅在3603中时钟会重置为零。因此，如果您不打算一直保持服务运行到1583年，那么您就很安全。



但是，出现双出现的可能性仍然存在，某些系统尝试将其考虑在内。但是在大多数情况下，UUID可以被认为是完全唯一的。如果需要更多证据，这里是实际中碰撞概率的简单可视化。


More articles:


All Articles