閒談軟體設計：再聊 UUID

這是 UUID 三部曲的第二部曲，主要是聊怎麼讓 UUID 變的更短一點，想了解 UUID 的原理可以參考 閒談軟體設計：UUID，接下來第三部曲會聊特殊應用，以及如何善用變形。

前言

這文章是因為過去使用大量的 UUID，但 UUID 有個致命的缺點是，它實在太長了，128 bits 用 Hex 表示法，至少要 32 個字元，如果再加上分隔符號，就要 36 個字元，把這放在面向使用者者的頁面上，應該不會有人會記得住吧！但 UUID 就真的只能這麼長嗎？其實是可以再短一點的。

開始變短

剛剛才說到目前的表示法是 Hex (十六進制)，也就是將 128 bits 每 4 bits 為一組，然後用 0 到 F，分別表示 0 (0000) 到 15 (1111)，這也就是為什麼長度會是 32 個字元 (128 / 4)，所以想要更短，最簡單的作法是 5 bits 為一組用 32 個字母來表示，或是用 6 bits 為一組用 64 個字母來表示，這時長度也就可以縮短到 26 (ceil(128 / 5)) 字元或 22 (ceil(128 / 6)) 字元了。用 7 bits 一組也不是不行，只是找到易讀的 128 個字母就是件困難的事了。

這次文章的範例和往常用 Java 不同，是用 Kotlin，但我還是盡量讓程式碼簡單一點。首先，我們先替既有的 Java 類別 UUID 加上一個 extension method [關於 extension 我個人比較喜歡 Swift 的寫法]，能給定一組字母，然後用這組字母來編碼 UUID。

由於剛剛提到，是用幾個 bits 為一組 (事實上這非強制性，只是在解釋上比較方便)，因此我們先檢查給定的字母數量是否為 2 的次方，於是第一個版本就出來了，還沒有功能，單純檢查輸入是否合法，另外 Kotlin 支援預設參數，我順便加上由 0 到 9，大小寫的英文字母及兩個特殊符號的字母組合。

然後寫個測試，驗證一下是否真的會拋出例外：

接著，我們是希望變短，而不是變長，因此字母不該小於 2⁴ 個，因此再加上一個指數不得小於 4 的限制：

然後再補上一個測試案例：

到這邊，我個人是覺得這些檢查佔據太多行數，抽象層級和接下來要專注的內容不同，所以直接將驗證的邏輯抽成一個函式，這時主函式就清爽多了。如果要再增加對參數檢查的邏輯 (例如，不可有重複的字母)，也是寫在剛抽出去的函式中，增加可讀性。

有一點二進制基礎的大概都知道將 10 進制的數字轉換成 2 進制，就是一直除以 2 取餘數 (或是用位元運算往右 shift 取被 shift 的那個 bit)，同理，假設是 5 bits 一組，那就是取 32 的餘數 (或是往右 shift 5 bits)。

但 UUID 長達 128 bits，多數語言是沒有內建型別可以表達這麼長的數，Java 的 long 也才 64 bits (事實上 UUID 內部就是用兩個 long 表達)，那怎麼把個 long 一起取餘數或是 shift 呢？這時候可以靠 BigInteger 了，有個建構子可以從指定的 ByteArray 建立 BigInteger 物件。

因此，接下來就是將 UUID 轉成 ByteArray，因此新增一個 toBytes 的extension method，由於 Java 沒有正整數的型別，所以 UUID 類別的兩個成員 mostSignificantBits 和 leastSignificantBits 都有可能是負數，因此像 BigInteger("${mostSignificantBits}${leastSignificantBits}") 這樣的寫法是會出錯的。這裡採用保守的作法，建立一個 17 bytes 的 buffer，然後依序放入 0、 mostSignificantBits 和 leastSignificantBits，第一個 0 確保整個 17 bytes 被視為正整數處理。

再來就是很單純地取餘數，拿餘數查表，將查到的字母接在 buffer 的後面，最後記得將整個字串反轉 (因為計算過程是將低位串到高位)。BigInteger 其實支援左移或是右移等運算，速度應該比較快，但不熟位元運算的人閱讀起來可能需要花點時間，所以這裡還是用取餘數的方式。

驗證結果

寫完後當然要寫個測試驗證一下對不對，既然要測試，就得先找出正確解，所以文章一開始的圖片就是解釋：怎麼從一個 UUID 找出編碼後的結果。這裡是每 6 bits 一組，綠色是高位元的 64 bits，紫色則是低位元的 64 bits，會發現有個 a 是由高位元的最小 2 bits 搭配低位元的最高 4 bits 組成的，這也是為什麼需要兩個 Long 一起運算的原因了，因為除非是 4 bits 或 8 bits 一組，不然無法整除 Long，一定會發生要向另一個 Long 借位的情形發生 [不借位其實也是可行的，只是編碼出來的長度會再加 1]。

從測試案例就可以看出來長度明顯縮短不少：

53e6693a-0aaa-4e94-a116–2a397fc89975 (一般形式)
53e6693a-0aaa4e94a1162a397fc89975 (去除分隔符號)
1jVCAW2GFeBa4mazB-O9BR (短模式)

既然能夠編碼，那是否可以解回來呢？當然也是可以，這裡就替 String 增加一個 fromShortId 的 extension method，一樣可以指定字母表，只是程式會檢查給定的字母數量是否足以解碼 (這裡就偷懶沒將驗證抽出去成獨立的函式了)，後續的邏輯就很簡單，依序查字母所在的 index，乘上倍數後加上 index，最後一樣要記得處理一下正負數 (line 14) 就完成了。

當然，也是要寫個測試驗證一下解碼對不對：

最後再加上個測試案例，不是用預設的字母表，這裡使用的是 0 到 9，以及大小的 A 到 Z，排除掉容易跟 1 搞混的 I，以及和 0 搞混的 O 和 Q 後共 32 個字母，從測試案例就可以看出，有縮短但幅度就沒那麼明顯了。

fbcf8ca0-a0b7–4e8c-8a05-f0be7c72f022 (一般形式)
fbcf8ca0a0b74e8c8a05f0be7c72f022 (去除分隔符號)
7USX6A185P9T68L1FGPSX75V12 (base 32)

好啦，有人會說，這不就是 Base64 和 Base 32 嗎？是也不是，因為我寫的演算法跟標準不太一樣，只是用這麼編碼方式來呈現 UUID 是較少見的 [維基百科：在 Java 持久化系統 Hibernate 中，就採用了 Base64 來將一個較長的唯一識別碼 (一般為128-bit的 UUID) 編碼為一個字串，用作 HTTP 表單和 HTTP GET URL 中的參數]，原因為何我就不清楚了。

邊解碼效能測試

順手寫了個簡單的程式測一下兩者的效能差距，由於單獨一個 toString() 或是 shortId() 的執行時間很短，所以程式是每十萬次為單位量測時間，大家有興趣可以跑跑看。

我想從圖表就看的出來，雖然程式還有優化的可能 (把除法改成位元運算)，但那個差距是相當明顯 (單位是 ms)。

更短？

說真的，即便將長度從 36 個字元縮短到本文中的 22 或 26 個字元，仍然是一個很長的 ID，一般來說，人的短期記憶力有所謂七加減二的說法，也就是能記住五至九個字元的片段，太長就記不住了，用 UUID 或是較短的其他 ID 產生器，這就得有些取捨了。

以五個字元來說，數字加上英文字母大小寫，最多就 62 的五次方種組合，也就是 916,132,832 個組合，又或是不分大小寫並排除易混淆字母只用 32 個字元，也就是 32 的五次方共 33,554,432 個組合，碰撞機率還是有的，可搭配資料庫紀錄已配發的 ID，或加上 namespace 來避免重複。

當長度增加到九個字元，這時 62 的九次方 (13,537,086,546,263,552) 或是 32 的九次方 (35,184,372,088,832)，這時碰撞的機率非常的低，也就是說一次的 Random.nextLong() 加上指定的編碼就能產生指定長度的 ID，算是相當快速 (UUID 需要兩次的 random) 且方便的，果不其然，可以在 GitHub 的專案看到相似的概念：

題外話，這次的 short UUID 其實在GitHub 也能找到類似的專案：

文中的範例我放在 GitHub 上，想優化或修改可以去下載。目前 GitHub 的版本跟本文有點不一樣，演算法沒變，主要是用了 Kotlin 的 companion object 稍微改寫一下。