冷饭新炒：理解JDK中UUID的底层实现

<code>UUID</code>是<code>Universally Unique IDentifier</code>的缩写，翻译为通用唯一标识符或者全局唯一标识符。对于<code>UUID</code>的描述，下面摘录一下规范文件<code>A Universally Unique IDentifier (UUID) URN Namespace</code>中的一些描述：

UUID（也称为GUID）定义了统一资源名称命名空间。UUID的长度为128比特，可以保证在空间和时间上的唯一性。

动机：

使用UUID的主要原因之一是不需要集中式管理，其中一种格式限定了IEEE 802节点标识符，其他格式无此限制。可以自动化按需生成UUID，应用于多重不同的场景。UUID算法支持极高的分配速率，每台机器每秒钟可以生成超过1000万个UUID，因此它们可以作为事务ID使用。UUID具有固定大小128比特，与其他替代方案相比，它具有体积小的优势，非常适用于各种排序、散列和存储在数据库中，具有编程易用性的特点。

这里只需要记住<code>UUID</code>几个核心特定：

全局时空唯一性

固定长度<code>128</code>比特，也就是<code>16</code>字节(<code>1 byte = 8 bit</code>)

分配速率极高，单机每秒可以生成超过<code>1000</code>万个<code>UUID</code>（实际上更高）

下面就<code>JDK</code>中的<code>UUID</code>实现详细分析一下<code>UUID</code>生成算法。编写本文的时候选用的<code>JDK</code>为<code>JDK11</code>。

前面为了编写简单的摘要，所以只粗略摘录了规范文件里面的一些章节，这里再详细聊聊<code>UUID</code>的一些定义、碰撞概率等等。

<code>UUID</code>是一种软件构建的标准，也是开放软件基金会组织在分布式计算环境领域的一部分。提出此标准的目的是：让分布式系统中的所有元素或者组件都有唯一的可辨别的信息，因为极低冲突频率和高效算法的基础，它不需要集中式控制和管理唯一可辨别信息的生成，由此，每个使用者都可以自由地创建与其他人不冲突的<code>UUID</code>。

<code>UUID</code>本质是一个<code>128</code>比特的数字，这是一个位长巨大的数值，理论上来说，<code>UUID</code>的总数量为<code>2^128</code>个。这个数字大概可以这样估算：如果每纳秒产生1兆个不相同的<code>UUID</code>，需要花费超过<code>100</code>亿年才会用完所有的<code>UUID</code>。

<code>UUID</code>标准和算法定义的时候，为了考虑历史兼容性和未来的扩展，提供了多种变体和版本。接下来的变体和版本描述来源于维基百科中的<code>Versions</code>章节和<code>RFC 4122</code>中的<code>Variant</code>章节。

目前已知的变体如下：

变体<code>0xx</code>：<code>Reserved, NCS backward compatibility</code>，为向后兼容做预留的变体

变体<code>10x</code>：<code>The IETF aka Leach-Salz variant (used by this class)</code>，称为<code>Leach–Salz UUID</code>或者<code>IETF UUID</code>，<code>JDK</code>中<code>UUID</code>目前正在使用的变体

变体<code>110</code>：<code>Reserved, Microsoft Corporation backward compatibility</code>，微软早期<code>GUID</code>预留变体

变体<code>111</code>：<code>Reserved for future definition</code>，将来扩展预留，目前还没被使用的变体

目前已知的版本如下：

空<code>UUID</code>（特殊版本<code>0</code>），用<code>00000000-0000-0000-0000-000000000000</code>表示，也就是所有的比特都是<code>0</code>

<code>date-time and MAC address</code>（版本<code>1</code>）：基于时间和<code>MAC</code>地址的版本，通过计算当前时间戳、随机数和机器<code>MAC</code>地址得到。由于有<code>MAC</code>地址，这个可以保证其在全球的唯一性。但是使用了<code>MAC</code>地址，就会有<code>MAC</code>地址暴露问题。若是局域网，可以用<code>IP</code>地址代替

<code>date-time and MAC address, DCE security version</code>（版本<code>2</code>）：分布式计算环境安全的<code>UUID</code>，算法和版本<code>1</code>基本一致，但会把时间戳的前<code>4</code>位置换为<code>POSIX</code>的<code>UID</code>或<code>GID</code>

<code>namespace name-based MD5</code>（版本<code>3</code>）：通过计算名字和命名空间的<code>MD5</code>散列值得到。这个版本的<code>UUID</code>保证了：相同命名空间中不同名字生成的<code>UUID</code>的唯一性；不同命名空间中的<code>UUID</code>的唯一性；相同命名空间中相同名字的<code>UUID</code>重复生成是相同的

<code>random</code>（版本<code>4</code>）：根据随机数，或者伪随机数生成<code>UUID</code>。这种<code>UUID</code>产生重复的概率是可以计算出来的，还有一个特点就是预留了<code>6</code>比特存放变体和版本属性，所以随机生成的位一共有<code>122</code>个，总量为<code>2^122</code>，比其他变体的总量要偏少

<code>namespace name-based SHA-1</code>（版本<code>5</code>）：和版本<code>3</code>类似，散列算法换成了<code>SHA-1</code>

其中，<code>JDK</code>中应用的变体是<code>Leach-Salz</code>，提供了<code>namespace name-based MD5</code>（版本<code>3</code>）和<code>random</code>（版本<code>4</code>）两个版本的<code>UUID</code>生成实现。

在规范文件描述中，<code>UUID</code>是由<code>16</code>个<code>8</code>比特数字，或者说<code>32</code>个<code>16</code>进制表示形式下的字符组成，一般表示形式为<code>8-4-4-4-12</code>，加上连接字符<code>-</code>一共有<code>36</code>个字符，例如：

其中<code>4</code>比特长度的<code>M</code>和<code>1</code>到<code>3</code>比特长度的<code>N</code>分别代表版本号和变体标识。<code>UUID</code>的具体布局如下：

属性

属性名

长度（<code>bytes</code>）

长度（<code>16</code>进制字符）

内容

时间戳低位

代表时间戳的低<code>32</code>比特的整数表示

时间戳中位

代表时间戳的中间<code>16</code>比特的整数表示

<code>time_hi_and_version</code>

时间戳高位和版本号

高位<code>4</code>比特是版本号表示，剩余是时间戳的高<code>12</code>比特的整数表示

<code>clock_seq_hi_and_res clock_seq_low</code>

时钟序列与变体编号

最高位<code>1</code>到<code>3</code>比特表示变体编号，剩下的<code>13</code>到<code>15</code>比特表示时钟序列

节点ID

<code>48</code>比特表示的节点ID

基于这个表格画一个图：

严重注意，重复三次：

上面提到的<code>UUID</code>的具体布局只适用于<code>date-time and MAC address</code>（版本<code>1</code>）和<code>date-time and MAC address, DCE security version</code>（版本<code>2</code>），其他版本虽然采用了基本一样的字段分布，但是无法获取时间戳、时钟序列或者节点<code>ID</code>等信息

JDK中只提供了版本3和版本4的实现，但是java.util.UUID的布局采用了上面表格的字段

<code>UUID</code>的总量虽然巨大，但是如果不停地使用，假设每纳秒生成超过<code>1</code>兆个<code>UUID</code>并且人类有幸能够繁衍到<code>100</code>亿年以后，总会有可能产生重复的<code>UUID</code>。那么，怎么计算<code>UUID</code>的碰撞几率呢？这是一个数学问题，可以使用比较著名的生日悖论解决：

上图来源于某搜索引擎百科。刚好维基百科上给出了碰撞几率的计算过程，其实用的也是生日悖论的计算方法，这里贴一下：

上面的碰撞几率计算是基于<code>Leach–Salz</code>变体和版本<code>4</code>进行，得到的结论是：

<code>103</code>万亿个<code>UUID</code>中找到重复项的概率是十亿分之一

要生成一个冲突率达到<code>50%</code>的<code>UUID</code>至少需要生成<code>2.71 * 1_000_000^3</code>个<code>UUID</code>

有生之年不需要担心<code>UUID</code>冲突，出现的可能性比大型陨石撞地球还低。

基本所有需要使用全局唯一标识符的场景都可以使用<code>UUID</code>，除非对长度有明确的限制，常用的场景包括：

日志框架映射诊断上下文中的<code>TRACE_ID</code>

<code>APM</code>工具或者说<code>OpenTracing</code>规范中的<code>SPAN_ID</code>

特殊场景下数据库主键或者虚拟外键

交易<code>ID</code>（订单<code>ID</code>）

等等......

这里先介绍使用方式。前面提到<code>JDK</code>中应用的变体是<code>Leach-Salz</code>（变体<code>2</code>），提供了<code>namespace name-based MD5</code>（版本<code>3</code>）和<code>random</code>（版本<code>4</code>）两个版本的<code>UUID</code>生成实现，实际上<code>java.util.UUID</code>提供了四种生成<code>UUID</code>实例的方式：

最常见的就是调用静态方法<code>UUID#randomUUID()</code>，这就是版本<code>4</code>的静态工厂方法

其次是调用静态方法<code>UUID#nameUUIDFromBytes(byte[] name)</code>，这就是版本<code>3</code>的静态工厂方法

另外有调用静态方法<code>UUID#fromString(String name)</code>，这是解析<code>8-4-4-4-12</code>格式字符串生成<code>UUID</code>实例的静态工厂方法

还有低层次的构造函数<code>UUID(long mostSigBits, long leastSigBits)</code>，这个对于使用者来说并不常见

最常用的方法有实例方法<code>toString()</code>，把<code>UUID</code>转化为<code>16</code>进制字符串拼接而成的<code>8-4-4-4-12</code>形式表示，例如：

其他<code>Getter</code>方法：

可以验证一下不同静态工厂方法的版本和变体号：

<code>java.util.UUID</code>被<code>final</code>修饰，实现了<code>Serializable</code>和<code>Comparable</code>接口，从一般理解上看，有下面的特定：

不可变，一般来说工具类都是这样定义的

可序列化和反序列化

不同的对象之间可以进行比较，比较方法后面会分析

下面会从不同的方面分析一下<code>java.util.UUID</code>的源码实现：

属性和构造函数

随机数版本实现

namespace name-based MD5版本实现

其他实现

格式化输出

比较相关的方法

前面反复提到<code>JDK</code>中只提供了版本<code>3</code>和版本<code>4</code>的实现，但是<code>java.util.UUID</code>的布局采用了<code>UUID</code>规范中的字段定义，长度一共<code>128</code>比特，刚好可以存放在两个<code>long</code>类型的整数中，所以看到了<code>UUID</code>类中存在两个<code>long</code>类型的整型数值：

从<code>UUID</code>类注释中可以看到具体的字段布局如下：

高<code>64</code>比特<code>mostSigBits</code>的布局

字段

<code>bit</code>长度

<code>16</code>进制字符长度

<code>version</code>

低<code>64</code>比特<code>leastSigBits</code>的布局

<code>variant</code>

小于1

<code>clock_seq</code>

<code>variant</code>和<code>clock_seq</code>加起来等于4

接着看<code>UUID</code>的其他成员属性和构造函数：

私有构造<code>private UUID(byte[] data)</code>中有一些位运算技巧：

输入的字节数组长度为<code>16</code>，<code>mostSigBits</code>由字节数组的前<code>8</code>个字节转换而来，而<code>leastSigBits</code>由字节数组的后<code>8</code>个字节转换而来。中间变量<code>msb</code>或者<code>lsb</code>在提取字节位进行计算的时候：

先进行左移<code>8</code>位确保需要计算的位为<code>0</code>，已经计算好的位移动到左边

然后右边需要提取的字节<code>data[i]</code>的<code>8</code>位会先和<code>0xff</code>（补码<code>1111 1111</code>）进行或运算，确保不足<code>8</code>位的高位被补充为<code>0</code>，超过<code>8</code>位的高位会被截断为低<code>8</code>位，也就是<code>data[i] & 0xff</code>确保得到的补码为<code>8</code>位

前面两步的结果再进行或运算

一个模拟过程如下：

以此类推，这个私有构造函数执行完毕后，长度为<code>16</code>的字节数组的所有位就会转移到<code>mostSigBits</code>和<code>leastSigBits</code>中。

构造函数分析完，接着分析重磅的静态工厂方法<code>UUID#randomUUID()</code>，这是使用频率最高的一个方法：

关于上面的位运算，这里可以使用极端的例子进行推演：

关于<code>UUID</code>里面的<code>Getter</code>方法例如<code>version()</code>、<code>variant()</code>其实就是找到对应的位，并且转换为十进制整数返回，如果熟练使用位运算，应该不难理解，后面不会分析这类的<code>Getter</code>方法。

随机数版本实现强依赖于<code>SecureRandom</code>生成的随机数（字节数组）。<code>SecureRandom</code>的引擎提供者可以从<code>sun.security.provider.SunEntries</code>中查看，对于不同系统版本的<code>JDK</code>实现会选用不同的引擎，常见的如<code>NativePRNG</code>。<code>JDK11</code>配置文件<code>$JAVA_HOME/conf/security/java.security</code>中的<code>securerandom.source</code>属性用于指定系统默认的随机源：

这里要提一个小知识点，想要得到密码学意义上的安全随机数，可以直接使用真随机数产生器产生的随机数，或者使用真随机数产生器产生的随机数做种子。通过查找一些资料得知非物理真随机数产生器有：

<code>Linux</code>操作系统的<code>/dev/random</code>设备接口

<code>Windows</code>操作系统的<code>CryptGenRandom</code>接口

如果不修改<code>java.security</code>配置文件，默认随机数提供引擎会根据不同的操作系统选用不同的实现，这里不进行深究。在<code>Linux</code>环境下，<code>SecureRandom</code>实例化后，不通过<code>setSeed()</code>方法设置随机数作为种子，默认就是使用<code>/dev/random</code>提供的安全随机数接口获取种子，产生的随机数是密码学意义上的安全随机数。一句话概括，<code>UUID</code>中的私有静态内部类<code>Holder</code>中的<code>SecureRandom</code>实例可以产生安全随机数，这个是<code>JDK</code>实现<code>UUID</code>版本<code>4</code>的一个重要前提。这里总结一下随机数版本<code>UUID</code>的实现步骤：

通过<code>SecureRandom</code>依赖提供的安全随机数接口获取种子，生成一个<code>16</code>字节的随机数（字节数组）

对于生成的随机数，清空和重新设置<code>version</code>和<code>variant</code>对应的位

把重置完<code>version</code>和<code>variant</code>的随机数的所有位转移到<code>mostSigBits</code>和<code>leastSigBits</code>中

接着分析版本<code>3</code>也就是<code>namespace name-based MD5</code>版本的实现，对应于静态工厂方法<code>UUID#nameUUIDFromBytes()</code>：

它的后续基本处理和随机数版本基本一致（清空版本位的时候，重新设置为<code>3</code>），唯一明显不同的地方就是生成原始随机数的时候，采用的方式是：基于输入的<code>name</code>字节数组，通过<code>MD5</code>摘要算法生成一个<code>MD5</code>摘要字节数组作为原始安全随机数，返回的这个随机数刚好也是<code>16</code>字节长度的。使用方式很简单：

<code>namespace name-based MD5</code>版本<code>UUID</code>的实现步骤如下：

通过输入的命名字节数组基于<code>MD5</code>算法生成一个<code>16</code>字节长度的随机数

<code>namespace name-based MD5</code>版本的<code>UUID</code>强依赖于<code>MD5</code>算法，有个明显的特征是如果输入的<code>byte[] name</code>一致的情况下，会产生完全相同的<code>UUID</code>实例。

其他实现主要包括：

格式化输出体现在<code>UUID#toString()</code>方法，这个方法会把<code>mostSigBits</code>和<code>leastSigBits</code>格式化为<code>8-4-4-4-12</code>的形式，这里详细分析一下格式化的过程。首先从注释上看格式是：

和前文布局分析时候的提到的内容一致。<code>UUID#toString()</code>方法源码如下：

比较相关方法如下：

所有比较方法仅仅和<code>mostSigBits</code>和<code>leastSigBits</code>有关，毕竟这两个长整型就存储了<code>UUID</code>实例的所有信息。

纵观<code>UUID</code>的源码实现，会发现了除了一些精巧的位运算，它的实现是依赖于一些已经完备的功能，包括<code>MD5</code>摘要算法和<code>SecureRandom</code>依赖系统随机源产生安全随机数。<code>UUID</code>之所以能够成为一种标准，是因为它凝聚了计算机领域前辈钻研多年的成果，所以现在使用者才能像写<code>Hello World</code>那样简单调用<code>UUID.randomUUID()</code>。

参考资料：

RFC 4122

维基百科 - Universally unique identifier

JDK11相关源码

留给读者的开放性问题：

<code>UUID</code>是利用什么特性把冲突率降到极低？

人类有可能繁衍到<code>UUID</code>全部用完的年代吗？

（本文完 c-2-w e-a-20210129）