C++,python,热爱算法和机器学习
全部博文（1214）
分类：
2011-07-04 20:07:41
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 基于时间的UUID生成算法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等哈希算法得到。
其他关于密码学随机数的描述，我曾在这篇文章中简单提到。
具体算法实现可以参考文档和开源代码。