分布式系统数据信息唯一标识之UUID

以你之姓@ 2023-06-23 14:27 16阅读 0赞

#### 一. 何为UUID ####

UUID 是指 Universally Unique Identifier，即通用唯一识别码 。  
        UUID 的目的是让分布式系统中的所有元素都能有唯一的识别信息 。如此一来，每个业务任务都可以创建不与其它任务冲突的 UUID，就不需考虑诸如：数据库创建时的名称重复问题、分布式系统数据信息无法跟踪一条日志信息的问题 。它使用某种规则，而不是某种中心化的自增方式，来 保证这个识别码的全局唯一性。

#### 二. UUID格式及版本 ####

UUID 是由一组32位数的16进制数字所构成，所以 UUID 理论上的总数1632=2128，约等于3.4 x 10123。也就是说若每纳秒产生1百万个 UUID，要花100亿年才会将所有 UUID 用完

##### UUID的格式： #####

UUID 的十六个八位字节被表示为 32个十六进制数字，以连字号分隔的五组来显示，形式为 `8-4-4-4-12`，总共有 `36个字符`（即三十二个英数字母和四个连字号）。例如：

`123e4567-e89b-12d3-a456-426655440000`

`xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx`

数字 `M` 的四位表示 UUID 版本，当前规范有5个版本，M可选值为`1, 2, 3, 4, 5` ；

数字 `N` 的一至四个最高有效位表示 UUID 变体( variant )，有固定的两位`10xx`因此只可能取值 `8, 9, a, b`

UUID版本通过M表示，当前规范有5个版本，M可选值为`1, 2, 3, 4, 5`。这5个版本使用不同算法，利用不同的信息来产生UUID，各版本有各自优势，适用于不同情景：

*  **版本1：** 严格按照 UUID 定义的每个字段的意义来实现，使用的变量因子是 时间戳＋时钟序列＋节点信息（Mac地址）
 *  **版本2：** 基本和版本1一致，但是它主要是和 DCE（ IBM 的一套分布式计算环境）。但是这个版本在 IETF 中也没有具体描述，反而在[DCE 1.1: Authentication and Security Services][DCE 1.1_ Authentication and Security Services]这篇文档中说到了具体实现。所以这个版本现在很少使用到，并且很多地方的实现也都忽略了它。
 *  **版本3：** 基于 name 和 namespace 的 hash 实现变量因子，版本3使用的是 md5 进行 hash 算法 。
 *  **版本4：** 使用随机或者伪随机实现变量因子。
 *  **版本5：** 基于 name 和 namespace 的 hash 实现变量因子，版本5使用的是 sha1 进行 hash 算法。

使用较多的是版本1和版本4，其中版本1使用当前时间戳和MAC地址信息。版本4使用(伪)随机数信息，128bit中，除去版本确定的4bit和variant确定的2bit，其它122bit全部由(伪)随机数信息确定。

因为时间戳和随机数的唯一性，版本1和版本4总是生成唯一的标识符。若希望对给定的一个字符串总是能生成相同的 UUID，使用版本3或版本5。

##### UUID的随机重复率： #####

Java中 UUID 使用版本4进行实现，所以由`java.util.UUID`类产生的 UUID，128个比特中，有122个比特是随机产生，4个比特标识版本被使用，还有2个标识变体被使用。利用[生日悖论][Link 1]，可计算出两笔 UUID 拥有相同值的机率约为：  
                                                        ![生日悖论][2019122009583312.png]  
其中`x`为 UUID 的取值范围，`n`为 UUID 的个数。

以下是以 x = 2122 计算出n笔 UUID 后产生碰撞的机率：

换句话说，每秒产生10亿笔 UUID ，100年后只产生一次重复的机率是50%。如果地球上每个人都各有6亿笔 UUID，发生一次重复的机率是50%。与被陨石击中的机率比较的话，已知一个人每年被陨石击中的机率估计为170亿分之1，也就是说机率大约是0.00000000006 (6 x 10-11)，等同于在一年内生产2000亿个 UUID 并发生一次重复。

综上所述，产生重复 UUID 并造成错误的情况非常低，是故大可不必考虑此问题。

机率也与随机数产生器的质量有关。若要避免重复机率提高，必须要使用基于密码学上的强伪随机数产生器来生成值才行。

#### 三. Java怎么实现UUID ####

Java中 UUID 对版本4进行了实现，原理是由强伪随机数生成器生成伪随机数。

*  Java 8中 `java.util.*` 包对UUID的生成：

/** * 使用静态工厂来获取版本4（伪随机数生成器）的 UUID * Static factory to retrieve a type 4 (pseudo randomly generated) UUID. * 这个UUID生成使用了强加密的伪随机数生成器(PRNG) * The {@code UUID} is generated using a cryptographically strong pseudo * random number generator. * * @return A randomly generated {@code UUID} */
        public static UUID randomUUID() { 
            // 与Random(弱伪随机数生成器)不一样，SecureRandom是强伪随机数生成器，结果不可预测
            // 使用SecureRandom生成随机数，替换version和variant就是 UUID
            SecureRandom ng = Holder.numberGenerator;
    
            byte[] randomBytes = new byte[16];
            ng.nextBytes(randomBytes);
            randomBytes[6]  &= 0x0f;  /* clear version */
            randomBytes[6]  |= 0x40;  /* set to version 4 */
            randomBytes[8]  &= 0x3f;  /* clear variant */
            randomBytes[8]  |= 0x80;  /* set to IETF variant */
            return new UUID(randomBytes);
        }
    
        /** * 对版本3的实现，对于给定的字符串（name）总能生成相同的UUID * Static factory to retrieve a type 3 (name based) {@code UUID} based on * the specified byte array. * * @param name * A byte array to be used to construct a {@code UUID} * * @return A {@code UUID} generated from the specified array */
        public static UUID nameUUIDFromBytes(byte[] name) { 
            MessageDigest md;
            try { 
                md = MessageDigest.getInstance("MD5");
            } catch (NoSuchAlgorithmException nsae) { 
                throw new InternalError("MD5 not supported", nsae);
            }
            byte[] md5Bytes = md.digest(name);
            md5Bytes[6]  &= 0x0f;  /* clear version */
            md5Bytes[6]  |= 0x30;  /* set to version 3 */
            md5Bytes[8]  &= 0x3f;  /* clear variant */
            md5Bytes[8]  |= 0x80;  /* set to IETF variant */
            return new UUID(md5Bytes);
        }

*  调用Java-API生成随机数：

// Java语言实现
    import java.util.UUID;
    
    public class UUIDProvider{ 
        public static String getUUID(){ 
            return UUID.randomUUID().toString().replaceAll("-", "");
        }
        public static void main(String[] args) { 
            // 利用伪随机数生成版本为4,变体为9的UUID
            System.out.println(UUID.randomUUID());
            
            // 对于相同的命名空间总是生成相同的UUID,版本为3,变体为 8
            // 命名空间为"mwq"时生成的UUID总是为06523e4a-9a66-3687-9334-e41dab27cef4
            System.out.println(UUID.nameUUIDFromBytes("mwq".getBytes()));
        }
    }

参考：  
\[1\]. [什么是UUID？][UUID]  
\[2\]. [理解UUID][UUID 1]  
\[3\]. [Leaf——美团点评分布式ID生成系统][Leaf_ID]

[DCE 1.1_ Authentication and Security Services]: http://pubs.opengroup.org/onlinepubs/9668899/chap1.htm
[Link 1]: https://baike.baidu.com/item/%E7%94%9F%E6%97%A5%E6%82%96%E8%AE%BA/2715290?fr=aladdin
[2019122009583312.png]: https://img-blog.csdnimg.cn/2019122009583312.png
[UUID]: https://www.jianshu.com/p/da6dae36c290
[UUID 1]: http://wsfdl.com/algorithm/2013/09/05/%E7%90%86%E8%A7%A3UUID.html
[Leaf_ID]: https://tech.meituan.com/2017/04/21/mt-leaf.html