游戏人生

Writen by Fox(yulefox.at.gmail.com)

在具体讨论之前，本文先厘清UUID（Universally Unique IDentifier）与GUID（Globally Unique IDentifier）的关系。

在分布式、网络、单机环境下，为了能够使用具有某种形式的ID唯一标识系统中的任一元素，这样的ID可以不依赖中心认证自动生成，于是UUID就诞生了。

UUID标准的历史沿革和具体实现在RFC 4122、ITU-T Rec. X.667和ISO/IEC 9834-8:2008中均有详细描述。ITU和ISO采用的标准和RFC 4122都是在UUID的早期版本基础上完成，各版本之间具有一致性和兼容性。

因为不能保证UUID的唯一性，ITU和ISO针对UUID的使用都有免责声明。

GUID一般是指Microsoft对于UUID标准的实现，UUID的实现则多见于其他系统（*NIX、MAC OS等）中。在了解了这一区别后，本文将统一使用UUID来指代对应的原理、算法及实现。

文中关于UUID的讨论全部基于RFC 4122和ITU-T Rec. X.667以及OSF、IETF、ITU－T、ISO、FIPS的各种标准文档。而UUID的细节（如结构、表示、算法、实现等）均以ITU-T Rec. X667为唯一蓝本，文中“本标准”即指代该蓝本。

o 介绍

UUID是长度为16-byte（128-bit）的ID，一般以形如f81d4fae-7dec-11d0-a765-00a0c91e6bf6的字符串作为URN（Uniform Resource Name，统一资源名称）。

o 动机

无须中心认证，自动生成，支持一台机器每秒生成10M次（100纳秒级，其隐含原因是指能够区分的最小时间单位为100ns，将时间作为因子时，连续生成两个UUID的时间至少要间隔100ns）。方便存取、分配、排序、查找。

o 结构

   76543210765432107654321076543210
   + – - – = – - – = – - – = – - – +
15 |            TimeLow            | 12
11 |    TimeMid    |   Version..   |  8
7  |Vari.. |Clock..|     Node      |  4
3  |             Node              |  0
   + – - – = – - – = – - – = – - – +
15 – 12: TimeLow 时间值的低位
11 – 10: TimeMid 时间值的中位
09 – 08: VersionAndTimeHigh 4位版本号和时间值的高位
07: VariantAndClockSeqHigh 2位变体（ITU-T）和时钟序列高位
06: ClockSeqLow 时钟序列低位
05 – 00: Node 结点
hexOctet = hexDigit hexDigit
hexDigit =
“0″ / “1″ / “2″ / “3″ / “4″ / “5″ / “6″ / “7″ / “8″ / “9″ /
“a” / “b” / “c” / “d” / “e” / “f” /
“A” / “B” / “C” / “D” / “E” / “F”
UUID =
TimeLow
“-” TimeMid
“-” VersionAndTimeHigh
“-” VariantAndClockSeqHigh ClockSeqLow
“-” Node

UUID由上述6个域构成，每个域编码为若干字节，并以16进制数表示这128位的UUID，相邻域以减号“-”分隔 （VariantAndClockSeqHigh和ClockSeqLow对应的两个字节例外，如上所示）。该结构中包含版本（Version）、变体 （Variant）、时间（Time）、时钟序列（Clock Sequence）、节点（Note）信息（以无符号整型值表示）。

o 合法性

除判断variant位设置是否正确、基于时间生成的UUID时间值是否为未经分配的将来时间外，实际应用中没有其他机制可以判定UUID是否合法。

o 变体

Variant位是UUID第7字节（VariantAndClockSeqHigh）的最高3位，

7 6 5  Description
0 – –  NCS向后兼容
1 0 –  本标准
1 1 0  Microsoft向后兼容
1 1 1  ITU-T Rec. X.667保留

o 版本

UUID的生成有时间、名称、随机数三种策略，以第9字节（VersionAndTimeHigh）的最高4位表示。

目前UUID定义有5个版本：

7 6 5 4  Ver  Description
0 0 0 1  1    基于时间的版本（本标准）
0 0 0 0  2    使用嵌入式POSIX（DCE安全版本）
0 0 1 1  3    使用MD5哈希的基于名称的版本（本标准）
0 1 0 0  4    基于随机数的版本（本标准）
0 1 0 1  5    使用SHA-1的基于名称的版本（本标准）

o 时间

时间是一个60位的整型值（除4位版本号外的前8字节），对应UTC（格林尼治时间1582年10月15日午夜始）的100ns时间间隔计数。

对于ver 4和5，该值分别对应一个随机数和一个全局唯一的名称。

o 时钟序列

对基于时间的UUID版本，时间序列用于避免因时间向后设置或节点值改变可能造成的UUID重复，对基于名称或随机数的版本同样有用：目的都是为了防止UUID重复。

如果前一时钟序列已知，通过自增实现时钟序列值的改变；否则，通过密码学（伪）随机数设置新的时钟序列值。

o 节点

对基于时间的UUID版本，节点由48位的单播MAC地址构成。对于没有MAC地址的系统，节点值为一个密码学（伪）随机数（为防止与MAC地址发生碰撞，需设置多播位）。

o 确定UTC时间（60位 Time）和时间序列值（14位 ClockSequence）；

o 设置TimeLow（对应Time的31-0位）；

o 设置TimeMid（对应Time的47-32位）；

o 设置VersionAndTimeHigh（4位版本号及Time的59-48位）；

o 设置VariantAndClockSeqHigh（变体位及对应ClockSequence的13-8位）；

o 设置ClockSeqLow（对应ClockSequence的7-0位）；

o 设置Node（对应48位MAC地址）。

o 基于名称的UUID生成算法

o 针对相应的命名空间（如DNS、URL、OID等）分配一个UUID作为所有UUID的命名空间标识；

o 将名称转换为字节数列；

o 使用MD5或SHA-1算法对与名称关联的命名空间标识进行计算，产生16字节哈希结果；

o 设置TimeLow（对应哈希值的3-0字节）；

o 设置TimeMid（对应哈希值的5-4字节）；

o 设置VersionAndTimeHigh（对应哈希值的7-6字节），以相应版本号重写对应位（第9字节的高4位）；

o 设置VariantAndClockSeqHigh（对应哈希值的第8字节），重写变体对应位（第7字节的高2位，本标准对应值为10）；

o 设置ClockSeqLow（对应哈希值的第9字节）；

o 设置Node（对应哈希值的15-10字节）。

由 于MD5碰撞问题，MD5只用于向后兼容的UUID生成，不再被推荐使用。由于SHA-1哈希结果为160位（20字节），本算法中，需要将FIPS PUB 180-2中的SHA-1算法的哈希值字节顺序反转（字节内顺序不变），UUID使用其15-0字节，19-16字节被丢弃。

o 基于随机数的UUID生成算法

o 设置VariantAndClockSeqHigh的变体位值为10；

o 设置VersionAndTimeHigh的4位版本号；

o 设置剩余位为随机值。

本文中讨论的密码学随机数，主要根据系统可以提供的信息（内存、硬盘、句柄、程序运行的线程、进程、句柄、堆栈等），利用SHA-1等哈希算法得到。

其他关于密码学随机数的描述，我曾在这篇文章中简单提到。