前幾天,「系統產生的 GUID 是否可能發生重複?」在辦公室引起熱議。我主張:GUID 透過網卡 MAC 地址、產生時間以及一些機制(防止同時間點產生兩筆或時鐘往回調)確保世上任何電腦都不會產生相同 GUID,只要所有電腦的 MAC 地址沒有亂來,理論上不可能發生重複。這說法挺有說服力,解除了大家心中的疑慮。

BUT,禁不住好奇爬了文,這才發現「我錯了!」

倒不是不該信任 GUID 永不重複,而是我們現在使用的 GUID 早已不是依據 MAC 及時間產生,而是靠隨機亂數產生。

GUID(Globally Unique Identifier)是微軟依據 UUID(Universally Unique Identifier)規範實作的唯一識別碼。至於 UUID 的演算法主要有四種:(Version 2 極罕用,直接忽略)

Version 1

使用 Timestamp 與網卡 MAC 網址確保唯一性,這就是我原本認知的做法。Version 1 將結構分成:

  1. 60 位元的時間戳記(Timestamp)
  2. 4 位元的演算法識別碼,固定為 0001(Algorithm 1),只要各演算法保證自己不產生重複值,不同演算法間也不會重複
  3. 14 位元的緊急識別位元(Emergency Uniquifier Bits)
    由於 UUID 依賴時間產生唯一性,當同一時間要產生多筆 UUID 時或時鐘被調回過去,藉著會遞增的 Uniquifier 確保時間相同 UUID 也不致重複
  4. 2 位元保留值,固定為 01
  5. 48 位元為產生該 UUID 電腦的識別碼,通常使用網卡的 MAC 地址;若沒有網卡,則第一個位元設為 1其餘 47 位元為亂數。(網卡 MAC 的第一位元永遠為 0,故不會跟無網卡的亂數識別重複)

60 + 4 + 14 + 2 + 48 = 128 位元,完整 UUID 是唯一的,但只擷取其中部分就不保證。

Version 3 & Version 5

依據 Namespace 及 Name 字串雜湊碼(Vesrion 3 用 MD5、Version 5 用 SHA1)產生,固定輸入將產生一致的 UUID。

Version 4

由 4 位元版號及 2位元 UUID Variant 加上 122 位元亂數產生,主要靠 Pseudorandom Number Generator(PRNG,仿隨機數字產生器)產生具有唯一性的亂數(但不保證不可預測性)。

Version 1 就是我小時候學過 GUID 保證不重複的原理依據。不過,因為有洩露 MAC 地址的安全疑慮(當年這個漏洞還被用來追查梅麗莎病毒來源),微軟從 Windows 2000 起便改用 Version 4 ,以隨機亂數產生 GUID:參考

With Windows 2000, Microsoft switched to version 4 GUIDs, since embedding the MAC address was viewed as a security risk.

不信?你可以產生一堆 NewGuid() 試試,看看第三節數字的第一位是否永遠為 4?這個 4 即代表它是 Version 4 的 UUID!

 

【結論】

好,所以現在我們知道了!GUID 已不是靠 MAC 地址及時間確保唯一性,而是靠隨機亂數產生,靠著 122 位元數夠多讓重複機率趨於0。那那那,GUID 有沒有可能重複?當然有可能,但機率有多低呢?依據維基百科,預估的機率是 2.71 * 10^18 分之一,若每秒產生 10 億個 UUID 連續 85 年,將有 50% 的機率至少發生一次重複。如果你很想目睹 GUID 強碰,必須產生 103 百萬兆個 UUID,才會有 10 億分之一的重複機率

這下麻煩了,只是機率極低而非全無可能,那我們可不可以說「GUID 永遠唯一」?

我的看法是「因人而異」!

如果你常擔心走在路上會被隕石爆頭,再不然就是明天有外星艦隊攻打地球,常煩惱要是回家路上撿到彩券中樂透,該不該馬上辭掉工作四海雲遊?那麼你應該不介意再多操煩一件芝麻小事:「靠北!要是 GUID 重複系統崩潰該怎麼辦?」。

不然的話,我建議大家學我一樣,別想太多,大聲說「別擔心,GUID 永遠不重複!」就好。

要是真遇上了,我誠心道歉並恭賀閣下獲得老天爺對人品至高無上的肯定。

【參考資料】


Comments

# by 阿修

太好笑了XDDDD

# by 765

中樂透機率很低, 被雷打到機率很低, 但每天世界各地都還是有人中樂透, 還是有人被雷劈...

# by wellxion

以前好奇有翻過資料 很早就知道這件事了 不過我很好奇 在big data領域 有沒有人能藉此證實UUID或GUID真的會發生重複XDD?

# by otaku119

>>當年這個漏洞還被用來追查梅麗莎病毒來源 連結跑去wiki的「全局唯一識別元」?

# by Jeffrey

to otaku119, 「全局唯一識別元」維基文件有提到此事。為求精準,我找到另一篇更詳細的故事,謝謝你的回饋。

# by 越野兔

以前 macOS 10.6(或更久的年代,忘了),我公司經常發現重覆的 UUID,最後發現原來當時 Mac 的實作有 bug,如果用 fork process 的話,UUID 有很低的機率會重覆,害我們花了很多時間耶

# by jason

以全世界所有的電腦若每秒產生 10 億個是可能的數量,以原子數量計算這個UUID算太小

# by japhen

就算會重覆好了,那 UUID + UUID 連生兩組串在一起,那機率基本上是比連結10天被雷打到還低了

# by Jy

擔心重複,可以試試: https://github.com/PomeloFoundation/Pomelo.EntityFrameworkCore.MySql/blob/ebe011a6f1b2a2a9709fe558cfc7ed3215b55c37/src/EFCore.MySql/ValueGeneration/Internal/MySqlSequentialGuidValueGenerator.cs

Post a comment