兩天前，Mike Malone 在 Medium 上發表了一篇有趣的文章，談到 V8 中 Math.random() 的實作，以及所用 PRNG 的品質有多差：http://bit.ly/1SPDraN。

這篇文章今天登上了 Hacker News 的熱門榜單。從 Math.random() 為何失效、又該如何修正的角度來看，它寫得相當清楚、資訊也很充足，所以就這個主題本身，我沒有什麼要補充的。不過，由於作者是在產生大量、理論上不會碰撞的 ID 的情境下發現 PRNG 的弱點，我想和大家分享一個自己過去多次使用過的替代方案，它既快速又極度可靠。

唯一 ID 的難題

理論上，如果你想產生唯一 ID，就必須保存某種狀態來確保同一個 ID 不會重複出現。最簡單的情況，你可以用一個單純的計數器。然而，前一次產生的 ID 必須以一致的方式被儲存起來。如果系統重新啟動，絕不能因為儲存的計數器沒有正確地寫入磁碟，就再次產生出相同的 ID。

如果想用多個行程同時產生唯一 ID，每個行程都必須確保在自己的 ID 前面加上一個專屬的前綴，而且這個前綴永遠不會與其他行程的前綴衝突。這同樣很難管理。光是必須以可靠的方式儲存舊的 ID 這件事本身，當你想每秒產生大量 ID 時，就會非常耗時。

幸好有個簡單的解法。在 0 到 N 之間隨機產生一個數字，讓 N 大到使碰撞的機率小到在任何實際應用中都可以忽略不計。這個方法的前提是，產生的數字在 0 到 N 之間是均勻分布的。只要這個前提成立，我們就可以利用生日悖論來計算碰撞的機率。

只要使用足夠的位元數，就算每秒產生數百萬個 ID、持續數百年，要發生碰撞的機率也能輕易做到比小行星撞擊地球還低上數十億倍。如果你覺得這樣的餘裕還不夠，只要再多加幾個位元，就能輕鬆讓 ID 空間大到超過宇宙中的原子總數。

這種產生方式有個很大的優點：它是完全無狀態的。多個節點可以同時產生 ID，而不需要彼此交換訊息。而且不需要把任何東西存到磁碟上，所以速度能有多快，完全取決於你的 CPU 有多快。運算量小到完全可以放進 CPU 快取中。因此它非常快速、也非常方便。

Mike Malone 用的就是這個想法，他利用 PRNG 來建立一個由一組字元組成的 ID，其中每個字元都是 64 種可能字元之一。為了產生每個字元，他使用了有缺陷的 V8 PRNG，結果造成了碰撞。別忘了，我們一開始的假設是，每個新 ID 都必須在 0 到 N 的空間中被均勻地選出。

你可以用更強的 PRNG 來修正這個問題，但這需要對 PRNG 進行分析。另一個問題是種子設定，重新啟動後要如何再次啟動流程，才能確保不會又選到相同的 PRNG 初始狀態？否則，你真正的 ID 空間會受限於 PRNG 的種子，而不是輸出空間本身。

基於以上種種原因，我想向你展示一個能避開大多數這類問題的簡單技巧。

使用加密雜湊函式來產生唯一 ID

加密雜湊函式是將一串位元轉換為固定長度位元序列的不可逆函式。它們被設計來抵抗各種攻擊，不過在這個應用中，我們只依賴它的一項特性：輸出的均勻性。只要改變雜湊函式輸入中的一個位元，輸出的每一個位元就都有 50% 的機率會跟著改變。

為了取得可靠的種子，我們向作業系統求助，透過讀取 /dev/urandom。為產生器設定種子時，我們真的需要一些外部亂數，否則很可能會犯下嚴重的錯誤，產生出完全相同的序列。

作為加密雜湊函式的範例，我們會使用廣為人知的 SHA1，它的輸出為 160 位元。請注意，在這個應用中你甚至可以使用 MD5：它本身的弱點對我們這裡的使用方式並沒有影響。

我們先建立一個種子，從 /dev/urandom 讀取 160 位元。用虛擬碼表示大概會是這樣：

seed = devurandom.read(160/8)

我們同時初始化一個計數器：

counter = 0

接下來，這就是每次產生新 ID 的函式：

function get_new_id()
    myid = SHA1(string(counter) + seed)
    counter = counter + 1
    return myid
end

基本上，我們有一個固定的字串，也就是我們的種子，然後將它與遞增的計數器一起做雜湊，所以如果我們的種子是「foo」，輸出的新 ID 就是：

SHA1(“0foo”)
SHA1(“1foo”)
SHA1(“2foo”)

這樣對我們的使用情境來說就已經很好了。不過，我們可能還會需要讓 ID 不容易被預測。想讓 ID 變得非常難以預測，只要在 get_new_id() 函式中改用 SHA1_HMAC() 就好，其中種子作為密鑰，計數器則作為 HMAC 的訊息。

這個方法速度很快，能保證良好的分布，因此碰撞的難度就如同生日悖論所預測的那樣，不需要對 PRNG 進行任何分析，而且完全無狀態。

我在自己的 Disque 專案中使用這個方法，在分散式系統的多個節點之間產生訊息 ID。

Hacker News 討論串在此：https://news.ycombinator.com/item?id=10606910