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

在具體討論之前，本文先厘清UUID（Universally Unique IDentifier）與GUID（Globally Unique IDentifier）的關(guān)系。

在分布式、網(wǎng)絡(luò)、單機(jī)環(huán)境下，為了能夠使用具有某種形式的ID唯一標(biāo)識(shí)系統(tǒng)中的任一元素，這樣的ID可以不依賴中心認(rèn)證自動(dòng)生成，于是UUID就誕生了。

UUID標(biāo)準(zhǔn)的歷史沿革和具體實(shí)現(xiàn)在RFC 4122、ITU-T Rec. X.667和ISO/IEC 9834-8:2008中均有詳細(xì)描述。ITU和ISO采用的標(biāo)準(zhǔn)和RFC 4122都是在UUID的早期版本基礎(chǔ)上完成，各版本之間具有一致性和兼容性。

因?yàn)椴荒鼙ＷCUUID的唯一性，ITU和ISO針對(duì)UUID的使用都有免責(zé)聲明。

GUID一般是指Microsoft對(duì)于UUID標(biāo)準(zhǔn)的實(shí)現(xiàn)，UUID的實(shí)現(xiàn)則多見于其他系統(tǒng)（*NIX、MAC OS等）中。在了解了這一區(qū)別后，本文將統(tǒng)一使用UUID來指代對(duì)應(yīng)的原理、算法及實(shí)現(xiàn)。

文中關(guān)于UUID的討論全部基于RFC 4122和ITU-T Rec. X.667以及OSF、IETF、ITU－T、ISO、FIPS的各種標(biāo)準(zhǔn)文檔。而UUID的細(xì)節(jié)（如結(jié)構(gòu)、表示、算法、實(shí)現(xiàn)等）均以ITU-T Rec. X667為唯一藍(lán)本，文中“本標(biāo)準(zhǔn)”即指代該藍(lán)本。

o 介紹

UUID是長(zhǎng)度為16-byte（128-bit）的ID，一般以形如f81d4fae-7dec-11d0-a765-00a0c91e6bf6的字符串作為URN（Uniform Resource Name，統(tǒng)一資源名稱）。

o 動(dòng)機(jī)

無須中心認(rèn)證，自動(dòng)生成，支持一臺(tái)機(jī)器每秒生成10M次（100納秒級(jí)，其隱含原因是指能夠區(qū)分的最小時(shí)間單位為100ns，將時(shí)間作為因子時(shí)，連續(xù)生成兩個(gè)UUID的時(shí)間至少要間隔100ns）。方便存取、分配、排序、查找。

o 結(jié)構(gòu)

   76543210765432107654321076543210
   + – - – = – - – = – - – = – - – +
15 |            TimeLow            | 12
11 |    TimeMid    |   Version..   |  8
7  |Vari.. |Clock..|     Node      |  4
3  |             Node              |  0
   + – - – = – - – = – - – = – - – +
15 – 12: TimeLow 時(shí)間值的低位
11 – 10: TimeMid 時(shí)間值的中位
09 – 08: VersionAndTimeHigh 4位版本號(hào)和時(shí)間值的高位
07: VariantAndClockSeqHigh 2位變體（ITU-T）和時(shí)鐘序列高位
06: ClockSeqLow 時(shí)鐘序列低位
05 – 00: Node 結(jié)點(diǎn)
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個(gè)域構(gòu)成，每個(gè)域編碼為若干字節(jié)，并以16進(jìn)制數(shù)表示這128位的UUID，相鄰域以減號(hào)“-”分隔 （VariantAndClockSeqHigh和ClockSeqLow對(duì)應(yīng)的兩個(gè)字節(jié)例外，如上所示）。該結(jié)構(gòu)中包含版本（Version）、變體 （Variant）、時(shí)間（Time）、時(shí)鐘序列（Clock Sequence）、節(jié)點(diǎn)（Note）信息（以無符號(hào)整型值表示）。

o 合法性

除判斷variant位設(shè)置是否正確、基于時(shí)間生成的UUID時(shí)間值是否為未經(jīng)分配的將來時(shí)間外，實(shí)際應(yīng)用中沒有其他機(jī)制可以判定UUID是否合法。

o 變體

Variant位是UUID第7字節(jié)（VariantAndClockSeqHigh）的最高3位，

7 6 5  Description
0 – –  NCS向后兼容
1 0 –  本標(biāo)準(zhǔn)
1 1 0  Microsoft向后兼容
1 1 1  ITU-T Rec. X.667保留

o 版本

UUID的生成有時(shí)間、名稱、隨機(jī)數(shù)三種策略，以第9字節(jié)（VersionAndTimeHigh）的最高4位表示。

目前UUID定義有5個(gè)版本：

7 6 5 4  Ver  Description
0 0 0 1  1    基于時(shí)間的版本（本標(biāo)準(zhǔn)）
0 0 0 0  2    使用嵌入式POSIX（DCE安全版本）
0 0 1 1  3    使用MD5哈希的基于名稱的版本（本標(biāo)準(zhǔn)）
0 1 0 0  4    基于隨機(jī)數(shù)的版本（本標(biāo)準(zhǔn)）
0 1 0 1  5    使用SHA-1的基于名稱的版本（本標(biāo)準(zhǔn)）

o 時(shí)間

時(shí)間是一個(gè)60位的整型值（除4位版本號(hào)外的前8字節(jié)），對(duì)應(yīng)UTC（格林尼治時(shí)間1582年10月15日午夜始）的100ns時(shí)間間隔計(jì)數(shù)。

對(duì)于ver 4和5，該值分別對(duì)應(yīng)一個(gè)隨機(jī)數(shù)和一個(gè)全局唯一的名稱。

o 時(shí)鐘序列

對(duì)基于時(shí)間的UUID版本，時(shí)間序列用于避免因時(shí)間向后設(shè)置或節(jié)點(diǎn)值改變可能造成的UUID重復(fù)，對(duì)基于名稱或隨機(jī)數(shù)的版本同樣有用：目的都是為了防止UUID重復(fù)。

如果前一時(shí)鐘序列已知，通過自增實(shí)現(xiàn)時(shí)鐘序列值的改變；否則，通過密碼學(xué)（偽）隨機(jī)數(shù)設(shè)置新的時(shí)鐘序列值。

o 節(jié)點(diǎn)

對(duì)基于時(shí)間的UUID版本，節(jié)點(diǎn)由48位的單播MAC地址構(gòu)成。對(duì)于沒有MAC地址的系統(tǒng)，節(jié)點(diǎn)值為一個(gè)密碼學(xué)（偽）隨機(jī)數(shù)（為防止與MAC地址發(fā)生碰撞，需設(shè)置多播位）。

o 確定UTC時(shí)間（60位 Time）和時(shí)間序列值（14位 ClockSequence）；

o 設(shè)置TimeLow（對(duì)應(yīng)Time的31-0位）；

o 設(shè)置TimeMid（對(duì)應(yīng)Time的47-32位）；

o 設(shè)置VersionAndTimeHigh（4位版本號(hào)及Time的59-48位）；

o 設(shè)置VariantAndClockSeqHigh（變體位及對(duì)應(yīng)ClockSequence的13-8位）；

o 設(shè)置ClockSeqLow（對(duì)應(yīng)ClockSequence的7-0位）；

o 設(shè)置Node（對(duì)應(yīng)48位MAC地址）。

o 基于名稱的UUID生成算法

o 針對(duì)相應(yīng)的命名空間（如DNS、URL、OID等）分配一個(gè)UUID作為所有UUID的命名空間標(biāo)識(shí)；

o 將名稱轉(zhuǎn)換為字節(jié)數(shù)列；

o 使用MD5或SHA-1算法對(duì)與名稱關(guān)聯(lián)的命名空間標(biāo)識(shí)進(jìn)行計(jì)算，產(chǎn)生16字節(jié)哈希結(jié)果；

o 設(shè)置TimeLow（對(duì)應(yīng)哈希值的3-0字節(jié)）；

o 設(shè)置TimeMid（對(duì)應(yīng)哈希值的5-4字節(jié)）；

o 設(shè)置VersionAndTimeHigh（對(duì)應(yīng)哈希值的7-6字節(jié)），以相應(yīng)版本號(hào)重寫對(duì)應(yīng)位（第9字節(jié)的高4位）；

o 設(shè)置VariantAndClockSeqHigh（對(duì)應(yīng)哈希值的第8字節(jié)），重寫變體對(duì)應(yīng)位（第7字節(jié)的高2位，本標(biāo)準(zhǔn)對(duì)應(yīng)值為10）；

o 設(shè)置ClockSeqLow（對(duì)應(yīng)哈希值的第9字節(jié)）；

o 設(shè)置Node（對(duì)應(yīng)哈希值的15-10字節(jié)）。

由 于MD5碰撞問題，MD5只用于向后兼容的UUID生成，不再被推薦使用。由于SHA-1哈希結(jié)果為160位（20字節(jié)），本算法中，需要將FIPS PUB 180-2中的SHA-1算法的哈希值字節(jié)順序反轉(zhuǎn)（字節(jié)內(nèi)順序不變），UUID使用其15-0字節(jié)，19-16字節(jié)被丟棄。

o 基于隨機(jī)數(shù)的UUID生成算法

o 設(shè)置VariantAndClockSeqHigh的變體位值為10；

o 設(shè)置VersionAndTimeHigh的4位版本號(hào)；

o 設(shè)置剩余位為隨機(jī)值。

本文中討論的密碼學(xué)隨機(jī)數(shù)，主要根據(jù)系統(tǒng)可以提供的信息（內(nèi)存、硬盤、句柄、程序運(yùn)行的線程、進(jìn)程、句柄、堆棧等），利用SHA-1等哈希算法得到。

其他關(guān)于密碼學(xué)隨機(jī)數(shù)的描述，我曾在這篇文章中簡(jiǎn)單提到。