通用唯一辨識碼

電腦用來識別的128位數字

通用唯一辨識碼(英語:Universally Unique Identifier,縮寫:UUID)是用於電腦體系中以辨識資訊的一個128位元識別碼。

UUID按照標準方法生成時,在實際應用中具有唯一性,且不依賴中央機構的註冊和分配。UUID重複的概率接近零,可以忽略不計[1][2]

因此,所有人都可以自行建立和使用UUID,而且幾乎可以確定其不會與既有的識別碼重複。也因為如此,在不同地方產生的UUID可以使用於同一個資料庫或同一個頻道中,而且幾乎不可能重複。

UUID的應用相當普遍,許多計算平台都提供了對於生成和解析UUID的支援。

歷史

1990年代, UUID 原本是用於阿波羅電腦網絡計算系統,後被用於開放軟件基金會分散式運算環境。分散式運算環境UUID的初始設計基於網絡計算系統UUID,其設計受 Domain/OS 中定義和使用的(64位元)唯一識別碼的啟發,這是一個也由 阿波羅電腦 設計的作業系統。後來,微軟視窗平台採用分散式運算環境設計作為全域唯一識別碼(GUID)。

2005年7月,RFC 4122 為 UUID 註冊了一個 URN 命名空間,並制定了早期的規範。當 RFC 4122 作為互聯網工程任務組標準發佈時,國際電信聯盟基於先前的標準和 RFC 4122 早期版本標準化了 UUID。

標準

UUID 由開放軟件基金會標準化,作為分散式運算環境(DCE)的一部分[3][4]

UUID 被紀錄為 ISO/IEC 11578:1996 "Information technology – Open Systems Interconnection – Remote Procedure Call(RPC)" 和後來的 ITU-T Rec. X.667 | ISO / IEC 9834-8:2005 規範的一部份[5]

互聯網工程任務組公佈了標準 RFC 4122[6],技術上等同於 ITU-T Rec. X.667 | ISO/IEC 9834-8。

格式

在其規範的文字表示中,UUID 的 16 個 8 位位元組表示為 32 個十六進制數字,由連字元 '-' 分隔成五組顯示,形式為「8-4-4-4-12」總共 36 個字元(32 個十六進制數字和 4 個連字元)。

例如:

123e4567-e89b-12d3-a456-426655440000
xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx

四位數字 M表示 UUID 版本,數字 N的一至三個最高有效位表示 UUID 變體。在例子中,M1 而且 Na10xx2),這意味着此 UUID 是「變體1」、「版本1」UUID;即基於時間的 DCE/RFC 4122 UUID。

規範的 `8-4-4-4-12` 格式字串基於 UUID 的16個位元組的「記錄佈局」:

UUID 記錄結構
名稱 長度 (位元組) 長度(16進制數字碼長) 說明
time_low 4 8 整數:低位 32 bits 時間
time_mid 2 4 整數:中間位 16 bits 時間
time_hi_and_version 2 4 最高有效位中的 4 bits「版本」,後面是高 12 bits 的時間
clock_seq_hi_and_res clock_seq_low 2 4 最高有效位為 1-3 bits「變體」,後跟13-15 bits 時鐘序列
node 6 12 48 bits 節點 ID

這些欄位對應於「版本1」和「版本2」(基於時間的)UUID中的欄位,但是「8-4-4-4-12」的表示適用於所有UUID,即使對於生成方式不同的UUID也是如此。

RFC 4122 第 3 節要求以小寫形式生成字元,同時對輸入不區分大小寫,儘管一些常用的實現違反了此規則。

Microsoft GUID有時會以大括號表示:

{123e4567-e89b-12d3-a456-426655440000}

不應將此格式與「Windows登錄檔格式」相混淆,後者指的是大括號內的格式。

RFC 4122為UUID定義了統一資源名稱(URN)命名空間。作為URN呈現的UUID如下:

urn:uuid:123e4567-e89b-12d3-a456-426655440000

編碼

UUID 的二進制編碼因系統而異。UUID的變體1是目前世界最常見的UUID,完全以大端序(big-endian)二進制儲存與傳輸 UUID 。

例如,00112233-4455-6677-8899-aabbccddeeff 編碼為位元組 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff

其他系統,特別是 Microsoft 在其 COM/OLE 庫中對 UUID 的字串表示,使用混合端格式,其中 UUID 的前三組是小端序/小尾序(little-endian),後兩組是 大端序/大尾序(big-endian)。

例如,00112233-4455-6677-8899-aabbccddeeff 編碼為位元組 33 22 11 00 55 44 77 66 88 99 aa bb cc dd ee ff

變體

UUID的變體(variant)欄位,佔1到3位元。RFC 4122定義了4種變體:

  • 變體 0 (最顯著位為0,二進制為0xxx2,十六進制表示為016到716) 用於向下相容已經過時的1988年開發的 Apollo 網絡計算系統(NCS)1.5 UUID 格式。 前6位元組是48位元時間戳(從1980年1月1日UTC開始的4微秒的滴答數),隨後2個位元組保留,再1個位元組是地址族(address family,使用了0..13個情形),最後7個位元組是主機ID。這類似於UUID的版本1.[7]
  • 變體 1 (二進制為10xx2,十六進制為816到b16),定義在RFC 4122/DCE 1.1 UUIDs, 或"Leach–Salz" UUID。它是按照大端序作為二進制儲存與傳輸。
  • 變體 2 (二進制為110x2,十六進制為c16或d16),RFC稱「保留,微軟公司向下相容」。早期的Microsoft Windows平台的GUID使用該格式。和完全使用大端序的變體 1 不同,變體 2 其中一部份按照小端序作為二進制儲存與傳輸。
  • 形如111x2保留未使用。

目前的UUID規範使用變體1和2。在文字表示上,兩種變體只有代表變體的位元不同[6]。上面的欄位也定義了兩種變體之間的位元組轉換。前三個欄位是無正負號的32和16位元數字,需要進行轉換,而後兩個欄位是由未解釋的位元組組成,不需要進行轉換。這種轉換同樣適用於版本3、4和5,其中的規範欄位與UUID的內容無關[6]

雖然一些重要的GUID名義上是變體2的UUID,例如元件對象模型(Component Object Model)IUnknown介面的識別碼,但是在微軟Windows軟件中所生成和使用的、被稱為「GUID」的許多識別碼是使用標準的變體1的RFC 4122/DCE 1.1大端序UUID。目前,Microsoft guidgen工具軟件產生變體1的結果。某些微軟文件[8]稱GUID與UUID是同義詞,如同RFC 4122中表示UUID「也被稱作GUID」。這些檔案表明了雖然「GUID」最初指代微軟所使用的其中一種UUID變體,但現在已經成為UUID的另一個名稱,含括變體1和2。

版本

對於「變體(variants)1」和「變體2」,標準中定義了五個版本(versions),並且在特定用例中某些版本可能比其他版本更合適。

版本由字串中的 M 指示。

版本1的UUID是根據時間和節點ID(通常是MAC地址)生成;版本2的UUID是根據識別碼(通常是組或用戶ID)、時間和節點ID生成;版本3、版本5透過對命名空間(namespace)識別碼和名稱進行雜湊生成確定性的UUID;版本4的UUID則使用隨機性偽隨機性生成。

Nil UUID

Nil UUID是一個特例,值為 00000000-0000-0000-0000-000000000000 ;也就是說,所有位都設置為 0。

版本1(日期時間和MAC地址)

版本1的UUID,是根據 60-bit 的時間戳和節點(生成UUID的電腦)的48-bit MAC地址而生成的。

時間戳的是這樣計算的:自公曆首次於天主教會和教皇國以外的地方使用的日期,也就是協調世界時(UTC)1582年10月15日午夜算起,每經過100納秒時間戳加1。RFC 4122聲明時間值在公元3400年左右算術溢位[6]:3,取決於所使用的演算法,代表此 60-bit 時間戳是有符號數量。但是,某些軟件(如libuuid庫)將時間戳視為無符號,把溢位時間推遲至公元5236年[9]。ITU-T Rec. X.667所定義的溢位時間為公元3603年[10]:v

13-bit 或 14-bit「無統一」(uniquifying)時鐘序列擴充了時間戳,以便處理處理器時鐘不能足夠快地前進的情況,或者每個節點有多個處理器和 UUID 生成器的情況。對於每個「版本1」UUID 對應於空間(節點)和時間(間隔和時鐘序列)中的單個點,兩個正確生成的「版本1」UUID 無意中相同的可能性實際上為零。由於時間和時鐘序列總共74位元,每個節點 id 可以生成    或 18 sextillion)個「版本1」UUID,每個節點 id 的最大平均速率為每秒 1630 億[6]

與其他 UUID 版本相比,基於來自網卡的 MAC 地址的「版本1」和「版本2」UUID,部分依賴於由中央序號產生器構發佈的識別碼,即由 IEEE 發佈給網絡裝置製造商的 MAC 地址的組織唯一識別碼(OUI)[11]。基於網卡MAC地址的「版本1」和「版本2」UUID 的唯一性還取決於網卡製造商正確地為其卡分配唯一的MAC地址,這與其他製造過程一樣容易出錯。此外,某些作業系統允許終端用戶自訂MAC地址,例如OpenWRT[12]

使用節點的網絡MAC地址作為節點ID,代表可以透過版本1的UUID逆向找到建立它的電腦。透過在檔案中嵌入UUID,可以實現追蹤到創建或修改這些檔案的計算機。在定位 Melissa 病毒的建立者時就使用了這個私隱漏洞[13]

如果節點沒有或不希望暴露MAC地址,RFC 4122 確實允許「版本1」(或2)UUID 中的 MAC 地址被隨機的48位元節點ID替換。在這種情況下,RFC要求節點ID的第一個八位位元組的最低有效位應設置為1[6],這對應於MAC地址中的多播位,設置它是用於區分隨機生成節點ID的UUID和基於來自網卡的MAC地址的UUID,網卡通常具有單播MAC地址[6]

版本2(日期時間和MAC地址,DCE安全版本)

RFC 4122 保留了版本2的UUID用於「DCE security」;但並沒有提供任何細節。因此,許多 UUID 實現省略了「版本2」。但是,「版本2」UUID 的規範由 DCE 1.1 身份驗證和安全服務規範提供[4]

「版本2」UUID 類似於「版本1」,除了時鐘序列的最低有效8 bits 被「本地域(local domain)」號替換,並且時間戳的最低有效32 bits 由在指定本地域內有意義的整數識別碼替換。在 POSIX 系統上,本地域號 0 和 1 分別用於用戶 ID(UIDs)和組 ID(GIDs),其他本地域號用於站點定義[4]。在非 POSIX 系統上,所有本地域號都是站點定義的。

在 UUID 中包含 40 位元的域或識別碼(domain/identifier)是有代價的。一方面,40 位元允許每個節點ID有大約1兆個域或識別碼的值。另一方面,由於時鐘值被截斷為28個最高有效位,有別於版本1中的60位元,版本2的UUID中的時鐘也改成每429.49秒跳動(tick)一次,略多於7分鐘,而不是版本1中的每100納秒;並且,版本2的時鐘序列僅有6位元,版本1中則有14位元;每7分鐘時鐘周期內,每個節點、域或識別碼只能生成64個唯一的UUID,而版本1的時鐘序列值為16,384個[14]。因此,版本2可能不適合用於以節點、域或識別碼在約7秒以上1次的速率下生成 UUID 的情況。

版本3和版本5(基於命名空間名稱)

「版本3」和「版本5」的 UUID 透過雜湊(hashing)命名空間識別碼和名稱生成。版本3使用 MD5 作為雜湊演算法,版本5則使用 SHA1[6]

名稱空間識別碼本身就是一個 UUID。該規範提供了 UUID 用來表示命名空間為了統一資源定位符(URLs),完整域名、對象識別碼和 X.500;但任何所需的UUID都可以用作命名空間指示符。

要確定與給定命名空間和名稱對應的版本3的UUID,命名空間的 UUID 將轉換為位元組串,後面加上輸入名稱,然後用 MD5 進行雜湊,產生 128 位元。然後將六或七位替換為固定值,即 4 位元的版本號(例如「版本3」的 0011),以及 2 或 3 位元的 UUID 變體號(例如 10 代表RFC 4122的UUID,或 110 代表傳統 Microsoft GUID)。由於預定了6到7位元,因此只有121或122位元用於維持 UUID 的唯一性。

版本5的UUID 和上面類似,但使用 SHA1 而不是 MD5。由於 SHA1 生成 160 位元的摘要,因此在替換版本號和變體號之前會把摘要截斷為 128 位元。

版本3和版本5的UUID具有一個特性:相同名稱空間和名稱將對映到同一個UUID;然而,即使已知其中一項,也無法透過暴力搜尋之外的方法從UUID逆向推導出另外一項。RFC 4122 推薦使用版本5(SHA1)而不是版本3(MD5),並建議不要使用任一版本的 UUID 作為安全憑證[6]

版本4(隨機)

版本4的UUID是隨機生成的。與其他 UUID 一樣,其中4位元用於代表「版本4」,2到3位元代表變體號(102 或 1102 分別用於變體 1 和 2)。因此,對於變體1(即大多數 UUID),隨機生成的版本4的UUID會保留6位元用於表示變體號和版本號,其餘122位元用於隨機生成,故版本4變體1的UUID共計有   (5.3 undecillion)個。版本4變體2的UUID(傳統GUID)則為變體1的一半,因為可用的隨機位少一個,變數消耗 3 位元。

一些偽亂數發生器缺少必要的熵來產生足夠的偽亂數。例如,使用偽亂數生成器的 WinAPI GUID 生成器已被證明可生成遵循可預測模式的 UUID。 RFC 4122 建議「在各種主機上生成 UUID 的分散式應用程式必須願意依賴所有主機上的亂數源。如果這不可行,則應使用名稱空間變體。」

衝突

當多次生成相同的 UUID 並將其分配給不同的指示對象時,就會發生衝突。對於使用來自網卡的唯一MAC地址的標準版本1和2的UUID,只有當實施與標準不同時才可能發生衝突,無論是無意還是故意。

與使用MAC地址生成的版本1和版本2相比,使用隨機生成的節點ID的版本1和版本2、基於雜湊的版本3和版本5,以及隨機生成的版本4的UUID,即使實現上沒有問題也可能發生衝突,但可能性很小,通常可以忽略。可以基於對生日問題的分析來精確地計算該概率[15]

例如,如果要有50%的概率至少發生一次衝突,需要生成至少 個版本4的UUID,計算如下[16]

 

這個數字相當於每秒產生 10 億個 UUID 持續 85 年。每個 UUID 長度為 16 位元組,這麼多 UUID 的檔案大小約為 45 艾位元組(EB),比目前存在的最大數據庫大很多倍,它們都在數百PB的數量級。

若要使發生衝突的概率為p,至少必須生成多少個版本4的UUID可由下式近似計算:

 

因此,在 103 萬億個版本4 UUID 中找到重複的概率是  (十億分之一)。

使用

檔案系統

重要用途包括 ext2/ext3/ext4 檔案系統用戶空間工具(e2fsprogs 使用 util-linux 提供的 libuuid)、LUKS 加密分區、GNOME、KDE 和 Mac OS X,其中大部分源自 曹子德(Theodore Ts'o)的實現[9]

Solaris 中 UUID 的一種用途(使用開放軟件基金會的實現)是辨識正在執行的作業系統實例,以便在內核崩潰的情況下將故障轉儲數據與故障管理事件配對[17]

分區標籤和分區UUID都儲存於超區塊中。兩者皆為檔案系統的一部份,而不是分區的一部份。例如,ext2-ext4包含UUID,而NTFS或FAT32則沒有。

超區塊是檔案系統的一部份,因此被完全包含在分區中,因此如果你執行dd if=/dev/sda1 of=/dev/sdb1,sda1和sdb1都會擁有相同的標籤和UUID。

COM

Microsoft的組件對象模型(COM)中使用了幾種GUID :

  • IID - 介面識別碼;(在系統上註冊的介面識別碼儲存在Windows登錄檔中的[HKEY_CLASSES_ROOT\Interface][18]
  • CLSID - 類識別碼;(儲存在[HKEY_CLASSES_ROOT\CLSID]
  • LIBID - 類型庫識別碼;(儲存於[HKEY_CLASSES_ROOT\TypeLib][19]
  • CATID - 類別識別碼;(它在一個類中的存在將其辨識為屬於某些類別類別,列於[HKEY_CLASSES_ROOT\Component Categories][20]

作為資料庫主鍵

UUID 通常用作資料庫表中的唯一鍵。

Microsoft SQL Server 版本4 Transact-SQL 中的 NEWID 函數會返回標準隨機版本4的UUID,而 NEWSEQUENTIALID 函數返回類似於 UUID 的 128 位識別碼,這些 UUID 會依序遞增,直到下次系統重啟[21]

另一方面,儘管名稱如此,但 Oracle Database SYS_GUID 函數不會返回標準 GUID;相反,它根據主機識別碼和行程或線程識別碼返回一個16位元組的 128 位 RAW 值,有點類似於 GUID[22]

PostgreSQL 包含一個 UUID 資料類型[23],並且可以通過使用模組中的函數生成大多數版本的UUID[24][25]

MySQL 提供了一個 UUID 函數,它生成標準的版本1 UUID[26]

當 UUID 用作主鍵時,版本3、4和5 UUID 的隨機性以及 版本1和2 UUID 內的欄位的排序可能會產生資料庫定位或效能問題。例如,2002年 Jimmy Nilsson 報告說,當用作主鍵的版本4 UUID 被修改為包含基於系統時間的非隨機字尾時,Microsoft SQL Server的效能顯着提高。Nilsson 承認,這種所謂的「COMB」(組合時間和GUID)方法使UUID非標準並且更有可能被複製,但 Nilsson 僅要求在應用程式中的唯一性[27]。透過重新排序和編碼版本1和版本2的UUID,將時間戳放在最前面,可以避免插入所造成的效能損失[28]

諸如Laravel這樣的部分網絡框架支援「時間戳優先」的UUID,可以將UUID有效儲存於索引資料庫中。這種UUID是版本4格式的COMB UUID,但其中前48位元組成了一個時間戳,就像版本1的UUID一樣[29][30]。其他基於COMB UUID概念的指定格式包括:

  • ULID,其拋棄了用於表示版本4的4位元,並且預設使用base32編碼[31]
  • UUID版本6到8是三種COMB UUID格式的正式提議。

參見

參考文獻

  1. ^ Universally Unique Identifiers (UUID). H2. [21 March 2021]. (原始內容存檔於2006-07-09). 
  2. ^ ITU-T Recommendation X.667頁面存檔備份,存於互聯網檔案館): Generation and registration of Universally Unique Identifiers (UUIDs) and their use as ASN.1 Object Identifier components. Standard. October 2012.
  3. ^ CDE 1.1: Remote Procedure Call. The Open Group. 1997 [2022-10-17]. (原始內容存檔於2010-07-07). 
  4. ^ 4.0 4.1 4.2 DCE 1.1: Authentication and Security Services. The Open Group. 1997 [2022-10-17]. (原始內容存檔於2010-12-07). 
  5. ^ ITU-T Study Group 17 - Object Identifiers (OID) and Registration Authorities Recommendations. ITU.int. [2016-12-20]. (原始內容存檔於2010-08-20). 
  6. ^ 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 Leach, P.; Mealling, M.; Salz, R.. A Universally Unique IDentifier (UUID) URN Namespace. Internet Engineering Task Force. 2005 [2017-01-17]. RFC 4122. 
  7. ^ uuid.c. [2020-10-09]. (原始內容存檔於2021-02-24). 
  8. ^ Globally Unique Identifiers. Microsoft Developer Network. Microsoft. [2020-10-09]. (原始內容存檔於2019-02-13). 
  9. ^ 9.0 9.1 ext2/e2fsprogs.git - Ext2/3/4 filesystem userspace utilities. Kernel.org. [9 January 2017]. [失效連結]
  10. ^ Recommendation ITU-T X.667. www.itu.int. October 2012 [19 December 2020]. (原始內容存檔於2022-10-17). 
  11. ^ Registration Authority. IEEE Standards Association. [2022-10-17]. (原始內容存檔於2018-03-05). 
  12. ^ MAC Address Setup. OpenWRT. 15 September 2021 [2022-10-17]. (原始內容存檔於2022-10-18). 
  13. ^ Reiter, Luke. Tracking Melissa's Alter Egos. ZDNet. 1999-04-02 [2017-01-16]. (原始內容存檔於2012-10-21). 
  14. ^ Kuchling, A. M. What's New in Python 2.5. Python.org. [23 January 2016]. (原始內容存檔於2021-02-07). 
  15. ^ Jesus, Paulo; Baquero, Carlos; Almaeida, Paulo. ID Generation in Mobile Environments (PDF). Repositorium.Sdum.Uminho.pt. [2022-10-17]. (原始內容存檔 (PDF)於2022-10-17). 
  16. ^ Mathis, Frank H. A Generalized Birthday Problem. SIAM Review. June 1991, 33 (2): 265–270. CiteSeerX 10.1.1.5.5851 . ISSN 0036-1445. JSTOR 2031144. OCLC 37699182. doi:10.1137/1033051. 
  17. ^ Crashdump Restructuring in Solaris. Blogs.Oracle.com. Oracle. [9 January 2017]. (原始內容存檔於2016-06-29). 
  18. ^ Interface Pointers and Interfaces. Windows Dev Center - Desktop app technologies. Microsoft. [15 December 2015]. (原始內容存檔於2017-07-06). You reference an interface at run time with a globally unique interface identifier (IID). This IID, which is a specific instance of a globally unique identifier (GUID) supported by COM, allows a client to ask an object precisely whether it supports the semantics of the interface, without unnecessary overhead and without the confusion that could arise in a system from having multiple versions of the same interface with the same name. 
  19. ^ Registering a Type Library. Microsoft Developer Network. Microsoft. [15 December 2015]. (原始內容存檔於2017-09-28). 
  20. ^ Categorizing by Component Capabilities. Windows Dev Center - Desktop app technologies. Microsoft. [15 December 2015]. (原始內容存檔於2017-11-22). A listing of the CATIDs and the human-readable names is stored in a well-known location in the registry. 
  21. ^ NEWSEQUENTIALID (Transact-SQL). Microsoft Developer Network. Microsoft. 2015-08-08 [2017-01-14]. (原始內容存檔於2010-06-06). 
  22. ^ Oracle Database SQL Reference. Oracle. [2022-10-17]. (原始內容存檔於2022-10-17). 
  23. ^ Section 8.12 UUID Type. PostgreSQL 9.4.10 Documentation. PostgreSQL Global Development Group. 13 February 2020 [2022-10-17]. (原始內容存檔於2018-03-09). 
  24. ^ uuid-ossp. PostgreSQL: Documentation: 9.6. PostgreSQL Global Development Group. 12 August 2021 [2022-10-17]. (原始內容存檔於2018-03-09). 
  25. ^ pgcrypto. PostgreSQL: Documentation: 9.6. PostgreSQL Global Development Group. 12 August 2021 [2022-10-17]. (原始內容存檔於2018-03-09). 
  26. ^ Section 13.20 Miscellaneous Functions. MySQL 5.7 Reference Manual. Oracle Corporation. [2022-10-17]. (原始內容存檔於2022-11-06). 
  27. ^ Nilsson, Jimmy. InformIT. InformIT. 2002-03-08 [2012-06-20]. (原始內容存檔於2010-08-26). 
  28. ^ Storing UUID Values in MySQL. Percona. 2014-12-19 [2021-02-10]. (原始內容存檔於2020-11-29). 
  29. ^ Helpers - Laravel - The PHP Framework For Web Artisans. Laravel.com. [2022-10-17]. (原始內容存檔於2022-10-21). 
  30. ^ Cabrera, Italo Baeza. Laravel: The mysterious "Ordered UUID". Medium. 31 January 2020 (英語). 
  31. ^ Universally Unique Lexicographically Sortable Identifier. GitHub. ULID. 10 May 2021 [2022-10-17]. (原始內容存檔於2022-12-22).