閒談軟體設計：UUID 之三部曲

這是 UUID 三部曲的最後一部，主要探討 UUID 的一些特殊應用，若想了解更多關於 UUID 的內容，可以參考 閒談軟體設計：UUID 及 閒談軟體設計：再聊 UUID。

駭客任務其實已經有四集了 XD

背景

ㄟ~好啦，我知道離上一篇《閒談軟體設計：再聊 UUID》，沒多久再聊一次 UUID 有點怪，但這個使用情境其實挺有意思的，您是否有過以下情境：

• 不想保存個資，苦於無法使用 email 之類的資料作為 ID
• 網路爬蟲爬了一堆資料，卻不知道怎麼識別

其實上述的情境都能用雜湊 (Hash) 解決，例如，使用者用 abc@123.xyz 註冊一個帳號，在資料庫中可以用 SHA-1 的結果作為 ID：

17597a5e728f17ed90d9e3b5380596184d9d1146

有人可能會問，如果系統沒有儲存 email，那要怎麼實現忘記密碼這個功能 (重設密碼並將新密碼寄到 email 信箱)？這基本上不是個問題啊，因為要觸發忘記密碼這個功能，使用者就要先提供帳號，這時不就有 email 了，不需要從系統讀取 email 喔。

又或者是用爬蟲去爬銀行帳戶的資訊 (要先處理登入問題，不然什麼都爬不到)，爬到一筆這樣的交易紀錄 (不用瞎猜了，這不是我的薪資，數字是亂編的)

這時我們可以將日期、摘要、單筆金額 (支出或存入)、結餘組成字串後，取 SHA-1 雜湊得到一組可以作為 ID 的字串，這好處是，下次再爬到同一筆交易紀錄，我們就可以知道這筆已經在我們的系統中了。

9ff6b42d95e1a84bfd20d49a093e4839bfa069b6

用雜湊的好處是無法回推原始的資料是什麼，或是嚴謹來說，是不容易回推原始的資料是什麼，雖然目前已知的 MD5、SHA-1 都已經被找到可在合理時間內計算出碰撞的演算法，但畢竟我們是拿雜湊值作為 ID，而不是更敏感的密碼比對，以上述的例子來說，交易紀錄則是原本就會儲存在系統中的，從雜湊回推有點多此一舉，比較糟糕的情境，應該是原本不希望曝光的 email 被用碰撞的方式曝光了。

UUID 特殊用法

那... 不就解決了，跟 UUID 有什麼關係？在首部曲 閒談軟體設計：UUID 有提到：

若看 Wikipedia 上對 UUID 的描述可以知道 UUID 目前有 5 個版本，詳細的產生方式可以在 RFC 4122 文件的第四節找到，其中版本 3 和版本 5 比較特殊，是以名字產生 UUID，差別是以 MD5 演算法或 SHA-1 進行 hash，在特定條件下，每次產生的 UUID 都應該是一樣的 (用以識別是否為相同節點)，比較不適合用在我們討論的情境中。

當時的情境用不到 v3 或 v5，但現在的情境就非常合適用 v3 或 v5 了，因為我們希望的是對同一筆資料，不管是 email 或是交易紀錄，都可以產生同樣的 UUID。而實際上，Java 原生就有提供 UUID v3 的生成方式，給定一位元陣列，該函式會用 MD5 的方式取雜湊值，然後將版號設為 3 (用 &= 0x0f 保留第六個 byte 的低位四個 bits，清除高位四個 bits，並用 |= 0x30 設定為 3)，並將 variant 設為 2 (用 &= 0x3f 保留低位六個 bits，清除高位兩個 bits，用 |= 0x80 設定為 2)，結果就是一個 v3 的 UUID 了。

也就是說，v3 的 UUID 可以視作修改後的 MD5，要回推更是不可能了，因為雜湊值在設定 version 及 variant 的過程中已經遺失部分資訊了，以上述的例子來說，是更適合的 ID 產生方式。

可惜的是，Java 原生並沒有 UUID v5 的生成方式，但有了上述的範例，要產生 UUID v5 並不難，首先先定義介面，這裡參考一個 JavaScript 套件 uuid 的設計。

第一個參數是真正用來產生 ID 的字串，第二個參數是 namespace，預設是空字串，第三個參數可以決定是否偽裝成 UUID v4，第三個參數後面再來說，先說第二個參數。

namespace 其實蠻好用的，例如上述的交易紀錄的例子，如果好死不死，交易日期一樣 (很多銀行的網頁只提供日期，沒有交易 ID 與時間)，單筆金額一樣，餘額也一樣，那以剛剛的方式會產生相同的雜湊，此時，不同的銀行用不同的 namespace (更好的 namespace 是帳號)，就會產生不同的雜湊了。

此 uuid 套件是完全照 RFC 4122 的 4-3 節所描述的，用附錄 C 預先指定的 UUID 作為 namespace，也就是

• 若 name 是網域，namespace 是 6ba7b810–9dad-11d1–80b4–00c04fd430c8
• 若 name 是網址，namepsace 是 6ba7b811–9dad-11d1–80b4–00c04fd430c8 (差異在第一節的最後一個數字)

另外還有定義 ISO OID 及 x.500 DN 所用的 namepsace，但我過去在使用這套件覺得有點麻煩，為了產生 v3 或 v5 的 UUID，得再產生一個 UUID 作為 namespace。故這次介面的設計，沒有將第二個參數的型別定義成 UUID，只要演算法的結果不違反 4-3 節的幾點要求，我覺得就算 ok

• 不論時間，在同個 namespace 底下同個 name 所產生的 UUID 必相同
• 同個 namespace 底下不同 name 所產生的 UUID 需不同 (機率上來說)
• 同個 name 在不同的 namespace 所產生的 UUID 需不同 (機率上來說)
• 兩個相同的 UUID，應該來自同個 namespace 底下的同個 name (機率上來說)

先看第一個版本，這版本有點想得太簡單了，將 name 及 namespace 串起來算 SHA-1，設定 version 與 variant 後產生取高位的 128 bits 作為 UUID，但這個版本有問題，先想想看問題是什麼？等等再往後看答案吧！

這邊要注意的是 MD5 雜湊值長度為 128 bits，跟 UUID 在長度上剛好一樣，沒什麼問題，但 SHA-1 雜湊值長度是 160 bits，所以得思考怎麼取 128 bits 出來，這裡取高位元是因為，我印象中高位元的的亂數分布比較好 (別問我數學證明，因為我也不確定是否真是如此)。

先檢驗一下，由於是用 SHA-1 計算雜湊，也沒有時間戳記或亂數，不管怎麼算，都不受時間影響，滿足第一點。不同的 name 在同個 namespace 底下，串起來的字串就會不一樣，基本上得到相同的雜湊值機率極低，因此滿足第二及第三點。但卻無法滿足第四點，很明顯也很容易發現，"abc@123.xyz" 加 "" 和 "abc" 加 "@123.xyz" 會產生相同的 UUID，卻來自不同的 name 與 namespace：

所以第二個版本，修改不大，個別先取 name 與 namespace 的 SHA-1 後，合在一起再取一次 SHA-1，但效果很明顯。

從測試案例可以看到，計算出來的結果天差地遠，卻仍能夠滿足第一點到第四點的要求：

總結

就這樣，我們有一個可以簡單產生 UUID v5 的工具。那回頭看一下第三個參數，到目前為止，我們都是乖乖牌，按照 RFC 4122 標準，將 version 設為 5，但若不想讓看到的人知道這是從 name 和 namespace 產生出來的呢？那就只好偽裝了，所以第三個參數就是提供偽裝成 v4 的功能。

雖然說第二個版本是 name 與 namespace 先取一次 SHA-1 後，合起來再取一次 SHA-1，理論上來說要產生碰撞會比單取一次 SHA-1 要難上許多，加上已經將 version 與 variant 所在的 bits 破壞掉了，讓難度再往上提升，可是如果在一開始就讓人誤以為這個 UUID 是純粹亂數產生的 UUID v4，自然可以降低一些人想要嘗試碰撞的機會。

當然，如果搭配閒談軟體設計：再聊 UUID使用，不僅可以有更短的表示法，也不容易猜出是 UUID v5 了，好啦！UUID 的第三部曲就到此結束，至於會不會再有第四部曲？我覺得是很難了...

後記：這裡要抱怨一下 Kotlin 的設計，我知道 static 變數是不好的東西，但直接從語言中把所有 static 移除是不是太過了些，然後為了一些明明用 static 就很容易解決的情境，加一個很不直覺的 companion object，以這次的 UUID 為例，若用 Swift 的 extension 來完成，整個就很漂亮。

在使用上，可以延續 UUID 的類別名稱，不用另外加一個 NamedUUID 類別 (Kotlin 並未替所有的 Java 原生類別都加上預設的 companion object，所以無法用 extension 的方式替 UUID 加上 factory method)。

對了，本文的 NamedUUID 可以在這個 repo 找到完整的程式碼 (懶得再開一個新的，所以就沿用 short-uuid 了)：