閒談軟體設計：UUID
這是 UUID 三部曲的首部曲，接下來陸續更新第二部與第三部，首部曲先聊聊 UUID 的前世今生，二部曲會聊聊如何縮短 UUID 的長度，第三部曲則是聊聊特殊應用，希望能幫助到大家。
ID 的重要性
今天聊點不一樣的東西，有點不起眼卻很重要的小玩意：UUID (或是微軟的 GUID)。
不管在什麼系統中，資料最終都要寫入到儲存裝置中，不論是用 RDBMS、 NoSQL，或是直接寫入檔案，都需要一個 ID 識別，以便事後需要時能取回單一筆資料，為了避免衝突 (多筆資料使用同一 ID)，怎麼產生唯一的 ID？
學資料庫時可能會學到 (1) 用在現實社會中唯一的 ID (例如：身份證字號或是 email)，這類的方法比較適合用來辨別使用者，對於更大層級的資料量 (訂單、訊息) 就不適合了；(2) 使用 RDBMS 提供的 auto increment primary key，比較簡單方便，而且產生的結果可以用來排序。
沒錯，能排序在資料庫應用中很重要，想像一下，若做一個 IM 系統，每次開啟都取回上次更新過後的訊息，直覺的想法會是取回 x 時間點之後的所有訊息，多數的 IM 後台 (有興趣可以參考 Openfire 的 XMPP 實作) 都會儲存訊息的時間戳記 (timestamp) 作為排序之用，但也因為要排序，需要對時間戳記的欄位進行索引 (indexing)，然而過多的索引不但不會提高搜尋的速度，有時甚至對效能是有害的。若 ID 本身是有順序性的，那上述的問題就會變成取回 ID 是 n 以後的所有訊息。
個人曾搜尋過 UUID 是否是有順序性的，答案等等再說，在搜尋的過程中找到一篇有趣的文章《細聊分散式 ID 生成方式》，裡面探討到如何有效率地產生有順序性的全域唯一 ID，以及一些目前既有方式的優缺點，像是 auto increment primary key 只能依賴唯一一個 RDBMS instance，無法擴展，成為效能的瓶頸；若以時間戳記為 ID，系統時間的顆粒度 (一般來說 Java 的 System.currentTimeMillis()顆粒度只到 10~20 ms) 會影響到短時間大量產生的 ID 是否唯一，此外，在分散式節點的情況下重複的可能性更高。
UUID
回到 UUID，當初搜尋時是想知道 UUID 是否有順序性，而該篇文章中提到 UUID 的缺點有二個：(1) 無法保證趨勢遞增，以及 (2) 長度過長 (128 bit，超過一般程式語言int或是long的長度，CPU 運算上較難最佳化，若以字串處理，效能不如int或long等資料型態)，但 UUID 實際上是有一個版本是在特定時間區間內是有順序性的。
若看 Wikipedia 上對 UUID 的描述可以知道 UUID 目前有 5 個版本，詳細的產生方式可以在 RFC 4122 文件的第四節找到，其中版本 3 和版本 5 比較特殊，是以名字產生 UUID，差別是以 MD5 演算法或 SHA-1 進行 hash，在特定條件下，每次產生的 UUID 都應該是一樣的 (用以識別是否為相同節點)，比較不適合用在我們討論的情境中。
版本 4 是全部以亂數組成，若在 Java 使用UUID.randomUUID()產生 UUID，可能會得到像這樣的字串04060e46-a46c-4165–9afb-0352bc2aabd8，其中4165的4代表的正是版本 4，若看原始碼，會看到 Java 用較安全的SecureRandom產生 16 bytes 的亂數後，設定 version 和 variant 就完成了，效率相當好，但也就不用期待有順序性了。
除了上述三個外，版本 1 和版本 2 都是以時間為基礎產生的，版本 2 是 DCE 專屬，不去管它。版本 1 將時間戳記 (和一般 UNIX 時間戳記有點不一樣，是 1582 年 10 月 15 至今每 100 奈秒為一次的計數，簡單說是取得奈秒後除以 100) 及該節點的 MAC address (若沒有 MAC address 可以用 48-bits 的亂數取代) 以指定的方式排列。若時間戳記以 unsigned 表示，大概可以用到西元 5236 年，每個節點平均每秒可以產生 163 百萬個 UUID。
版本 1 的 UUID 可到這裡看，每更新畫面一次，會發現最後面的 12 個字母(92361f002671) 都是固定的 (照標準是該伺服器的 MAC address，但實作上可能會 hash 過)，而最前面的 8 個字母會一直跳動且是有順序性的，下一個 4 字母組合則大概每 7 分鐘 (2³² * 100 奈秒) 會變動一次，下一個 4 字母中，第一個字母1代表這個 UUID 是 version 1，後續三個字母則大概每 10 個月(2⁴⁸ * 100 奈秒) 跳動一次。
那不就好棒棒！有順序性又有唯一性，但如果真的要進行排序，您會發現有問題，如果看 Java 在 UUID 的compareTo實作，先比較最高的 64 bits (正好是long長度，比對可以優化)，相同才比最低的 64 bits，也就是說第n+8分鐘產生的 UUID 可能在排序時排在第n分鐘之前，因為前 8 個字母代表的是時間戳記中最低的 32 bits，也就是說大概每 7 分鐘，就可能從0重新開始計數，但卻放在最高的 32 bits 中，讓該一直遞增的數會週期性變小後再遞增。
客製化 UUID
那怎麼辦？在 RFC 4122 文件中，其實有保留改變數字排列 (layout) 解讀的方式，也就是 variant bits，視情況 1 ~ 3 bits，一般 UUID 的實作是10x(x表示0或1皆可)，110則是微軟保留，0xx則是 NCS 保留，111則是尚未使用，透過設定不同的 variant 是可以讓解讀的人知道您產生的 UUID 並不是照目前的標準排列，但若沒有將您的排列方式送交 RFC 或其他標準化單位，也不會有人知道該怎麼解讀您的 UUID。
另外，也可以自訂新的 version 達到相同的目的，例如將版本 1 的 UUID：12adde00-f100–11e6-bc64–92361f002671調整排列順序，並將其中的版本改為 6，同時將 variant 改為 7 就會得到1e6f1001–2add-6e00-fc64–92361f002671，若將這 UUID 交給 Java，是可以解讀出對的版本與 variant，而且這個 UUID 在排序時，會是依時間遞增的。
有順序的 UUID 除了排序時方便，在當作 MySQL 的主鍵 (primary key)，也有很好的 performance 表現，在《Store UUID in an optimized way》可以看到量測的數據，在 insert 的時間上，與 auto increment 是差不多的，而產生的資料大小也與 auto increment 相近，索引的資料大小則是最小的，重點是都比版本 1 的 UUID 要好，當然這量測數據會因為使用的引擎有所差異，但這裡只是想表示 ID 的產生方法確實會影響效能。
然而有順序的 UUID 不見得適用在所有的情境上，例如在 AWS S3 反而建議 object key 的前四個字元越是亂數分佈越好，根據《AWS S3 Performance Tuning》的說法，AWS S3 是用前四個字元作為檔案分配到哪台機器的重要指標，若以我們修改的 UUID 來說，前四個字元在相當長的一段時間內都會是一樣的12ad，這導致所有的檔案都被丟到同一台機器，讓 AWS S3 分散式架構的好處無法發揮出來。
從上述二個例子可以發現 UUID 是可以視需求，選擇用版本 1 或版本 4，甚至是像上面的例子修改 UUID 版本 1 的產生方式，要產生類版本 1 的 UUID 還有二個問題要處理，也就是 clock sequence 與 node 如何產生，先看 clock sequence，假設不與標準衝突 (避開被保留的0、2與6)，暫時將 variant 設為 7 也就是111，那 clock sequence 就會是 13 bits 長度 (如下圖，粗黑框線是連字號 hyphen 的位置)，可以參考版本 4 直接用亂數，算是比較簡單。
UUID Layout when variant = 7
UUID 的其他變形
而 node 的 48 bits，在 server 上相對容易，而且在多節點環境還更有利於避免產生的 UUID 會重複，也就是直接取得 MAC address，但要注意，基於安全考量，不希望暴露實際的 MAC address 的話，是可以加上 salt 後用 MD5 或 SHA-1 進行 hash 取出其中的 48 bits，如此相同的節點就會有相同的 48 bits node。
但在 client 上就不見得能取得 MAC address， 像是開發 iOS App，基於安全考量，SDK 並沒有提供取得 MAC address 的 API，雖然說也是可以參考版本 4 用亂數取代，但這會導致即使相同的裝置，產生出來的 48 bits node 都不一樣，這是否是個問題要視應用而定，若想識別是哪個裝置產生的，那就不適合用這方式。在這情況下，可以用 server 配發的帳號 ID (又是一個 UUID 也沒關係) 再次 hash 過取出 48 bits 也是一種方法。
UUID 排序效能測試
前面有提到 UUID 若以字串的方式做比較，效能會比較差，但實際上到底會差多少？用想的不如就做實驗吧，下面的 Java 程式用迴圈，對 1,000,000 個 UUID 物件陣列或是 UUID 字串陣列進行排序，重複 100 次，每次都會重新產生新的 1,000,000 個 UUID 物件或 UUID 字串。
每次執行結果以逗號分隔，再將結果貼到 Excel 繪製圖表，水平軸是執行的次數，垂直軸是該次所花的時間，單位是 ms，以平均來看，排序 1,000,000 個 UUID 物件需要 352 ms，而排序 1,000,000 個 UUID 字串則是 679 ms，我想這差距應該十分明顯了。
UUID 物件與 UUID 字串的排序時間比較
所以若選擇 UUID 作為 ID，記得要從該資料庫系統支援的資料格式中，選擇合適的格式儲存 UUID。
總結
UUID 是蠻常見的 ID 生成方法，像是 MongoDB 也支援 UUID 作為 ID，在不同應用下，也可以客製化 UUID 的演算法，不過要注意的是，UUID 還是有可能重複，只是機率非常非常的低，比中樂透還低 (詳細的機率請參考 Wikipedia)，任何的客製化都可能會影響到重複的機率，在設計時要多加考慮。然後，不論使用標準的 UUID 或是客製的 UUID，都避免不掉它 128 bits 長度所帶來的缺點，使用前，需衡量是否必要，或是使用其他像是 snowflake 等方案。
延伸閱讀
The 2¹²⁰ Ways to Ensure Unique Identifiers 介紹 Firebase 如何產生唯一且遞增的 ID，Firebase 的 ID 不是 UUID，長度為 120 bits，由 48 bits 的時間戳記，加上 72 bits 的亂數，並用調整過的 Base 64 編碼讓編出來的字元數更短，並保證遞增性 (ordered lexicographically)。
