冷饭新炒：理解JDK中UUID的底层实现 |
您所在的位置：网站首页 › uuid生成多少位 › 冷饭新炒：理解JDK中UUID的底层实现 |
冷饭新炒：理解JDK中UUID的底层实现
|
前提
UUID是Universally Unique IDentifier的缩写，翻译为通用唯一标识符或者全局唯一标识符。对于UUID的描述，下面摘录一下规范文件A Universally Unique IDentifier (UUID) URN Namespace中的一些描述： UUID（也称为GUID）定义了统一资源名称命名空间。UUID的长度为128比特，可以保证在空间和时间上的唯一性。 动机： 使用UUID的主要原因之一是不需要集中式管理，其中一种格式限定了IEEE 802节点标识符，其他格式无此限制。可以自动化按需生成UUID，应用于多重不同的场景。UUID算法支持极高的分配速率，每台机器每秒钟可以生成超过1000万个UUID，因此它们可以作为事务ID使用。UUID具有固定大小128比特，与其他替代方案相比，它具有体积小的优势，非常适用于各种排序、散列和存储在数据库中，具有编程易用性的特点。 这里只需要记住UUID几个核心特定： 全局时空唯一性 固定长度128比特，也就是16字节(1 byte = 8 bit) 分配速率极高，单机每秒可以生成超过1000万个UUID（实际上更高）下面就JDK中的UUID实现详细分析一下UUID生成算法。编写本文的时候选用的JDK为JDK11。 再聊UUID前面为了编写简单的摘要，所以只粗略摘录了规范文件里面的一些章节，这里再详细聊聊UUID的一些定义、碰撞概率等等。 UUID定义UUID是一种软件构建的标准，也是开放软件基金会组织在分布式计算环境领域的一部分。提出此标准的目的是：让分布式系统中的所有元素或者组件都有唯一的可辨别的信息，因为极低冲突频率和高效算法的基础，它不需要集中式控制和管理唯一可辨别信息的生成，由此，每个使用者都可以自由地创建与其他人不冲突的UUID。 UUID本质是一个128比特的数字，这是一个位长巨大的数值，理论上来说，UUID的总数量为2^128个。这个数字大概可以这样估算：如果每纳秒产生1兆个不相同的UUID，需要花费超过100亿年才会用完所有的UUID。 UUID的变体与版本UUID标准和算法定义的时候，为了考虑历史兼容性和未来的扩展，提供了多种变体和版本。接下来的变体和版本描述来源于维基百科中的Versions章节和RFC 4122中的Variant章节。 目前已知的变体如下： 变体0xx：Reserved, NCS backward compatibility，为向后兼容做预留的变体 变体10x：The IETF aka Leach-Salz variant (used by this class)，称为Leach–Salz UUID或者IETF UUID，JDK中UUID目前正在使用的变体 变体110：Reserved, Microsoft Corporation backward compatibility，微软早期GUID预留变体 变体111：Reserved for future definition，将来扩展预留，目前还没被使用的变体目前已知的版本如下： 空UUID（特殊版本0），用00000000-0000-0000-0000-000000000000表示，也就是所有的比特都是0 date-time and MAC address（版本1）：基于时间和MAC地址的版本，通过计算当前时间戳、随机数和机器MAC地址得到。由于有MAC地址，这个可以保证其在全球的唯一性。但是使用了MAC地址，就会有MAC地址暴露问题。若是局域网，可以用IP地址代替 date-time and MAC address, DCE security version（版本2）：分布式计算环境安全的UUID，算法和版本1基本一致，但会把时间戳的前4位置换为POSIX的UID或GID namespace name-based MD5（版本3）：通过计算名字和命名空间的MD5散列值得到。这个版本的UUID保证了：相同命名空间中不同名字生成的UUID的唯一性；不同命名空间中的UUID的唯一性；相同命名空间中相同名字的UUID重复生成是相同的 random（版本4）：根据随机数，或者伪随机数生成UUID。这种UUID产生重复的概率是可以计算出来的，还有一个特点就是预留了6比特存放变体和版本属性，所以随机生成的位一共有122个，总量为2^122，比其他变体的总量要偏少 namespace name-based SHA-1（版本5）：和版本3类似，散列算法换成了SHA-1其中，JDK中应用的变体是Leach-Salz，提供了namespace name-based MD5（版本3）和random（版本4）两个版本的UUID生成实现。 UUID的格式在规范文件描述中，UUID是由16个8比特数字，或者说32个16进制表示形式下的字符组成，一般表示形式为8-4-4-4-12，加上连接字符-一共有36个字符，例如： ## 例子 123e4567-e89b-12d3-a456-426614174000 ## 通用格式 xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx其中4比特长度的M和1到3比特长度的N分别代表版本号和变体标识。UUID的具体布局如下： 属性 属性名 长度（bytes） 长度（16进制字符） 内容 time_low 时间戳低位 4 8 代表时间戳的低32比特的整数表示 time_mid 时间戳中位 2 4 代表时间戳的中间16比特的整数表示 time_hi_and_version 时间戳高位和版本号 2 4 高位4比特是版本号表示，剩余是时间戳的高12比特的整数表示 clock_seq_hi_and_res clock_seq_low 时钟序列与变体编号 2 4 最高位1到3比特表示变体编号，剩下的13到15比特表示时钟序列 node 节点ID 6 12 48比特表示的节点ID基于这个表格画一个图：
严重注意，重复三次： 上面提到的UUID的具体布局只适用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本虽然采用了基本一样的字段分布，但是无法获取时间戳、时钟序列或者节点ID等信息 上面提到的UUID的具体布局只适用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本虽然采用了基本一样的字段分布，但是无法获取时间戳、时钟序列或者节点ID等信息 上面提到的UUID的具体布局只适用于date-time and MAC address（版本1）和date-time and MAC address, DCE security version（版本2），其他版本虽然采用了基本一样的字段分布，但是无法获取时间戳、时钟序列或者节点ID等信息JDK中只提供了版本3和版本4的实现，但是java.util.UUID的布局采用了上面表格的字段 UUID的碰撞几率计算UUID的总量虽然巨大，但是如果不停地使用，假设每纳秒生成超过1兆个UUID并且人类有幸能够繁衍到100亿年以后，总会有可能产生重复的UUID。那么，怎么计算UUID的碰撞几率呢？这是一个数学问题，可以使用比较著名的生日悖论解决：
上图来源于某搜索引擎百科。刚好维基百科上给出了碰撞几率的计算过程，其实用的也是生日悖论的计算方法，这里贴一下：
上面的碰撞几率计算是基于Leach–Salz变体和版本4进行，得到的结论是： 103万亿个UUID中找到重复项的概率是十亿分之一 要生成一个冲突率达到50%的UUID至少需要生成2.71 * 1_000_000^3个UUID有生之年不需要担心UUID冲突，出现的可能性比大型陨石撞地球还低。
基本所有需要使用全局唯一标识符的场景都可以使用UUID，除非对长度有明确的限制，常用的场景包括： 日志框架映射诊断上下文中的TRACE_ID APM工具或者说OpenTracing规范中的SPAN_ID 特殊场景下数据库主键或者虚拟外键 交易ID（订单ID） 等等...... JDK中UUID详细介绍和使用这里先介绍使用方式。前面提到JDK中应用的变体是Leach-Salz（变体2），提供了namespace name-based MD5（版本3）和random（版本4）两个版本的UUID生成实现，实际上java.util.UUID提供了四种生成UUID实例的方式： 最常见的就是调用静态方法UUID#randomUUID()，这就是版本4的静态工厂方法 其次是调用静态方法UUID#nameUUIDFromBytes(byte[] name)，这就是版本3的静态工厂方法 另外有调用静态方法UUID#fromString(String name)，这是解析8-4-4-4-12格式字符串生成UUID实例的静态工厂方法 还有低层次的构造函数UUID(long mostSigBits, long leastSigBits)，这个对于使用者来说并不常见最常用的方法有实例方法toString()，把UUID转化为16进制字符串拼接而成的8-4-4-4-12形式表示，例如： String uuid = UUID.randomUUID().toString();其他Getter方法： UUID uuid = UUID.randomUUID(); // 返回版本号 int version = uuid.version(); // 返回变体号 int variant = uuid.variant(); // 返回时间戳 - 这个方法会报错，只有Time-based UUID也就是版本1或者2的UUID实现才能返回时间戳 long timestamp = uuid.timestamp(); // 返回时钟序列 - 这个方法会报错，只有Time-based UUID也就是版本1或者2的UUID实现才能返回时钟序列 long clockSequence = uuid.clockSequence(); // 返回节点ID - 这个方法会报错，只有Time-based UUID也就是版本1或者2的UUID实现才能返回节点ID long nodeId = uuid.node();可以验证一下不同静态工厂方法的版本和变体号： UUID uuid = UUID.randomUUID(); int version = uuid.version(); int variant = uuid.variant(); System.out.println(String.format("version:%d,variant:%d", version, variant)); uuid = UUID.nameUUIDFromBytes(new byte[0]); version = uuid.version(); variant = uuid.variant(); System.out.println(String.format("version:%d,variant:%d", version, variant)); // 输出结果 version:4,variant:2 version:3,variant:2 探究JDK中UUID源码实现java.util.UUID被final修饰，实现了Serializable和Comparable接口，从一般理解上看，有下面的特定： 不可变，一般来说工具类都是这样定义的 可序列化和反序列化 不同的对象之间可以进行比较，比较方法后面会分析下面会从不同的方面分析一下java.util.UUID的源码实现： 属性和构造函数 随机数版本实现 namespace name-based MD5版本实现 其他实现 格式化输出 比较相关的方法 属性和构造函数前面反复提到JDK中只提供了版本3和版本4的实现，但是java.util.UUID的布局采用了UUID规范中的字段定义，长度一共128比特，刚好可以存放在两个long类型的整数中，所以看到了UUID类中存在两个long类型的整型数值： public final class UUID implements java.io.Serializable, Comparable { // 暂时省略其他代码 /* * The most significant 64 bits of this UUID. * UUID中有效的高64比特 * * @serial */ private final long mostSigBits; /* * The least significant 64 bits of this UUID. * UUID中有效的低64比特 * * @serial */ private final long leastSigBits; // 暂时省略其他代码 }从UUID类注释中可以看到具体的字段布局如下： 高64比特mostSigBits的布局 字段 bit长度 16进制字符长度 time_low 32 8 time_mid 16 4 version 4 1 time_hi 12 3低64比特leastSigBits的布局 字段 bit长度 16进制字符长度 variant 2 小于1 clock_seq 14 variant和clock_seq加起来等于4 node 48 12接着看UUID的其他成员属性和构造函数： public final class UUID implements java.io.Serializable, Comparable { // 暂时省略其他代码 // Java语言访问类，里面存放了很多底层相关的访问或者转换方法，在UUID中主要是toString()实例方法用来格式化成8-4-4-4-12的形式，委托到Long.fastUUID()方法 private static final JavaLangAccess jla = SharedSecrets.getJavaLangAccess(); // 静态内部类确保SecureRandom初始化，用于版本4的随机数UUID版本生成安全随机数 private static class Holder { static final SecureRandom numberGenerator = new SecureRandom(); } // 通过长度为16的字节数组，计算mostSigBits和leastSigBits的值初始化UUID实例 private UUID(byte[] data) { long msb = 0; long lsb = 0; assert data.length == 16 : "data must be 16 bytes in length"; for (int i=0; i 位置[19,22] formatUnsignedLong0(lsb >>> 48, 4, buf, 19, 4); // msb的低16位转换为16进制格式写入到buf中 - time_high_and_version => 位置[14,17] formatUnsignedLong0(msb, 4, buf, 14, 4); // msb的中16位转换为16进制格式写入到buf中 - time_mid => 位置[9,12] formatUnsignedLong0(msb >>> 16, 4, buf, 9, 4); // msb的高32位转换为16进制格式写入到buf中 - time_low => 位置[0,7] formatUnsignedLong0(msb >>> 32, 4, buf, 0, 8); // 空余的字节槽位插入'-'，刚好占用了4个字节 buf[23] = '-'; buf[18] = '-'; buf[13] = '-'; buf[8] = '-'; // 基于处理好的字节数组，实例化String，并且编码指定为LATIN1 return new String(buf, LATIN1); } else { byte[] buf = new byte[72]; formatUnsignedLong0UTF16(lsb, 4, buf, 24, 12); formatUnsignedLong0UTF16(lsb >>> 48, 4, buf, 19, 4); formatUnsignedLong0UTF16(msb, 4, buf, 14, 4); formatUnsignedLong0UTF16(msb >>> 16, 4, buf, 9, 4); formatUnsignedLong0UTF16(msb >>> 32, 4, buf, 0, 8); StringUTF16.putChar(buf, 23, '-'); StringUTF16.putChar(buf, 18, '-'); StringUTF16.putChar(buf, 13, '-'); StringUTF16.putChar(buf, 8, '-'); return new String(buf, UTF16); } } /** * 格式化无符号的长整型，填充到字节缓冲区buf中，如果长度len超过了输入值的ASCII格式表示，则会使用0进行填充 * 这个方法就是把输入长整型值val，对应一段长度的位，填充到字节数组buf中，len控制写入字符的长度，offset控制写入buf的起始位置 * 而shift参数决定基础格式，4是16进制，1是2进制，3是8位 */ static void formatUnsignedLong0(long val, int shift, byte[] buf, int offset, int len) { int charPos = offset + len; int radix = 1 >>= shift; } while (charPos > offset); } 比较相关的方法比较相关方法如下： // hashCode方法基于mostSigBits和leastSigBits做异或得出一个中间变量hilo，再以32为因子进行计算 public int hashCode() { long hilo = mostSigBits ^ leastSigBits; return ((int)(hilo >> 32)) ^ (int) hilo; } // equals为实例对比方法，直接对比两个UUID的mostSigBits和leastSigBits值，完全相等的时候返回true public boolean equals(Object obj) { if ((null == obj) || (obj.getClass() != UUID.class)) return false; UUID id = (UUID)obj; return (mostSigBits == id.mostSigBits && leastSigBits == id.leastSigBits); } // 比较规则是mostSigBits高位大者为大，高位相等的情况下，leastSigBits大者为大 public int compareTo(UUID val) { // The ordering is intentionally set up so that the UUIDs // can simply be numerically compared as two numbers return (this.mostSigBits < val.mostSigBits ? -1 : (this.mostSigBits > val.mostSigBits ? 1 : (this.leastSigBits < val.leastSigBits ? -1 : (this.leastSigBits > val.leastSigBits ? 1 : 0)))); }所有比较方法仅仅和mostSigBits和leastSigBits有关，毕竟这两个长整型就存储了UUID实例的所有信息。 小结纵观UUID的源码实现，会发现了除了一些精巧的位运算，它的实现是依赖于一些已经完备的功能，包括MD5摘要算法和SecureRandom依赖系统随机源产生安全随机数。UUID之所以能够成为一种标准，是因为它凝聚了计算机领域前辈钻研多年的成果，所以现在使用者才能像写Hello World那样简单调用UUID.randomUUID()。 参考资料： RFC 4122 维基百科 - Universally unique identifier JDK11相关源码留给读者的开放性问题： UUID是利用什么特性把冲突率降到极低？ 人类有可能繁衍到UUID全部用完的年代吗？（本文完 c-2-w e-a-20210129） |
【本文地址】
今日新闻 |
推荐新闻 |