Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

UUID算法分析

Posted on 2009-12-06 15:07 Fox 阅读(21376) 评论(2)  编辑 收藏 引用 所属分类: A算法导论
本文同步自游戏人生

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

在具体讨论之前,本文先厘清UUID(Universally Unique IDentifier)与GUID(Globally Unique IDentifier)的关系。

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

UUID标准的历史沿革和具体实现在RFC 4122ITU-T Rec. X.667ISO/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等哈希算法得到。

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


具体算法实现可以参考文档和开源代码。

Feedback

# re: UUID算法分析  回复  更多评论   

2011-05-27 15:55 by cheap oakley sunglasses
算法分析得很透彻

# re: UUID算法分析  回复  更多评论   

2012-08-17 22:11 by chanel j12
Roxie Skinner cannot resist <a href="http://www.chanelj12.org">chanel watches women</a> a bargain.

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理