UUID详细介绍

01/26 08:20
阅读数 167

什么是UUID

UUID 是指(Universally Unique Identifier)通用唯一识别码,128位。RFC 4122描述了具体的规范实现。

现实问题

我们开发的时候,数据库表总会有一个主键,以前我们可能会使用自增的数字作为主键。这样做去确实查询的时候比较快, 但是在做系统集成或者数据迁移的的时候就麻烦了。这是id就有可能重复了。那么有什么比较好的方法解决这一问题呢? 于是jdk1.5出了UUID这个类来生成唯一的字符串标识。

UUID作用

UUID 的目的是让分布式系统中的所有元素都能有唯一的识别信息。如此一来,每个人都可以创建不与其它人冲突的 UUID,就不需考虑数据库创建时的名称重复问题。其作用视场景而定。

目前最广泛应用的 UUID,即是微软的 Microsoft's Globally Unique Identifiers (GUIDs),而其他重要的应用, 则有 Linux ext2/ext3 档案系统、LUKS 加密分割区、GNOME、KDE、Mac OS X 等等。

UUID定义

UUID使用16进制表示,共有36个字符(32个字母数字+4个连接符"-")组成,格式为8-4-4-4-12 ;【一个16进制只代表4个bit,所以是(8+4+4+4+12)*4=128位;】

是由一组32位数的16进制数字所构成,故 UUID 理论上的总数为16^{32} = 2^{128},约等于3.4 \times 10^{123}

也就是说若每纳秒产生1百万个 UUID,要花100亿年才会将所有 UUID 用完。

格式:
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

示例:
6d25a684-9558-11e9-aa94-efccd7a0659b

格式中M和N都有具体的含义

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

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

这5个版本使用不同算法,利用不同的信息来产生UUID,各版本有各自优势,适用于不同情景。具体使用的信息

  • version 1, date-time & MAC address
  • version 2, date-time & group/user id
  • version 3, MD5 hash & namespace
  • version 4, pseudo-random number
  • version 5, SHA-1 hash & namespace

故UUID每个版本不是根据精度区分的,Version5并不会比Version1精度高,在精度上,大家都能保证唯一性,重复的概率近乎于0

version 1——date-time  & MAC address

基于时间戳及MAC地址的UUID实现。它包括了48位的MAC地址和60位的时间戳,

接下来使用ossp-uuid命令行创建5个UUID v1。(在Mac安装brew install ossp-uuid)

uuid -n 5 -v1
5b01c826-9561-11e9-9659-cb41250df352
5b01cc7c-9561-11e9-965a-57ad522dee7f
5b01cea2-9561-11e9-965b-a3d050dd0f99
5b01cf60-9561-11e9-965c-1b66505f58da
5b01d118-9561-11e9-965d-97354eb9e996

肉眼一看,有一种所有的UUID都很相似的感觉,几乎就要重复了!怎么回事?

其实v1为了保证唯一性,当时间精度不够时,会使用13~14位的clock sequence来扩展时间戳,比如:

当UUID的生产成速率太快,超过了系统时间的精度。时间戳的低位部分会每增加一个UUID就+1的操作来模拟更高精度的时间戳,换句话说,就是当系统时间精度无会区分2个UUID的时间先后时,为了保证唯一性,会在其中一个UUID上+1。所以UUID重复的概率几乎为0,时间戳加扩展的clock sequence一共有74bits,(2的74次方,约为1.8后面加22个零),即在每个节点下,每秒可产生1630亿不重复的UUID(因为只精确到了秒,不再是74位,所以换算了一下)。

相对于其它版本,v1还加入48位的MAC地址,这依赖于网卡供应商能提供唯一的MAC地址,同时也可能通过它反查到对应的MAC地址。Melissa病毒就是这样做到的。

Version2(date-time Mac address)

这是最神秘的版本,RFC没有提供具体的实现细节,以至于大部分的UUID库都没有实现它,只在特定的场景(DCE security)才会用到。所以绝大数情况,我们也不会碰到它。

Version3,5(namespace name-based)

V3和V5都是通过hash namespace的标识符和名称生成的。V3使用MD5作为hash函数,V5则使用SHA-1

因为里面没有不确定的部分,所以当namespace与输入参数确定时,得到的UUID都是确定唯一的。比如:

uuid -n 3 -v3 ns:URL http://www.baidu.com
2f67490d-55a4-395e-b540-457195f7aa95
2f67490d-55a4-395e-b540-457195f7aa95
2f67490d-55a4-395e-b540-457195f7aa95

可以看到这3个UUID都是一样的。

具体的流程就是

  1. 把namespace和输入参数拼接在一起,如"http/http://wwwbaidu.com" ++ "/query=uuid";
  2. 使用MD5算法对拼接后的字串进行hash,截断为128位;
  3. 把UUID的Version和variant字段都替换成固定的;
  4. 如果需要to_string,需要转为16进制和加上连接符"-"。

把V3的hash算法由MD5换成SHA-1就成了V5。

Version4(random)

这个版本使用最为广泛:

uuid -n 5 -v4
a3535b78-69dd-4a9e-9a79-57e2ea28981b
a9ba3122-d89b-4855-85f1-92a018e5c457
7c59d031-a143-4676-a8ce-1b24200ab463
533831da-eab4-4c7d-a3f6-1e2da5a4c9a0
def539e8-d298-4575-b769-b55d7637b51e

其中4位代表版本,2-3位代表variant。余下的122-121位都是全部随机的。即有2的122次方(5.3后面36个0)个UUID。一个标准实现的UUID库在生成了2.71万亿个UUID会产生重复UUID的可能性也只有50%的概率:

 

这相当于每秒产生10亿的UUID,持续85年,而把这些UUID都存入文件,每个UUID占16bytes,总需要45 EB(exabytes),比目前最大的数据库(PB)还要大很多倍。

UUID的重复概率

Java中 UUID 使用版本4进行实现,所以由java.util.UUID类产生的 UUID,128个比特中,有122个比特是随机产生,4个比特标识版本被使用,还有2个标识变体被使用。利用生日悖论,可计算出两笔 UUID 拥有相同值的机率约为



其中x为 UUID 的取值范围,n为 UUID 的个数。

以下是以 x = 2^{122} 计算出n笔 UUID 后产生碰撞的机率:

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

Java实现

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

    /**
     * 使用静态工厂来获取版本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);
    }

生成 UUID

// 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,变体为9
        // 命名空间为"mwq"时生成的UUID总是为06523e4a-9a66-3687-9334-e41dab27cef4
        System.out.println(UUID.nameUUIDFromBytes("mwq".getBytes()));
    }
} 

总结

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

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

  • 如果只是需要生成一个唯一ID,你可以使用V1或V4。

    - V1基于时间戳和Mac地址,这些ID有一定的规律(你给出一个,是有可能被猜出来下一个是多少的),而且会暴露你的Mac地址。
    - V4是完全随机(伪)的。


  • 如果对于相同的参数需要输出相同的UUID,你可以使用V3或V5。

    - V3基于MD5 hash算法,如果需要考虑与其它系统的兼容性的话,就用它,因为它出来得早,大概率大家都是用它的。
    - V5基于SHA-1 hash算法,这个是首选。



参考

【1】什么是UUID

【2】uuid如何保证一致性

【3】https://www.ietf.org/rfc/rfc4122.txt

【4】https://www.zhihu.com/question/34876910/answer/88924223

【5】https://en.wikipedia.org/wiki/Universally_unique_identifier#Encoding

扩展阅读

SecureRandom 版本4的UUID生成原理,与Random的区别等
https://resources.infosecinstitute.com/random-number-generation-java/
https://www.saowen.com/a/d2f3430d15558a740d95b76ff04b242d59b08ea44847ff5941a9ded0e08a65c1
http://yizhenn.iteye.com/blog/2306293
mysql UUID
https://dev.mysql.com/doc/refman/8.0/en/miscellaneous-functions.html#function_uuid
Leaf——美团点评分布式ID生成系统





 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部