兩天前，Mike Malone（麥克·馬隆）在 Medium 上發表了一篇有趣的文章，談論 Math.random() 的 V8 實作，以及所使用的 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 之間均勻分布時才有效。如果這個前提成立，我們就能利用 birthday paradox(生日悖論) 來計算碰撞的機率。

只要使用足夠的位元數，即使我們以每秒數百萬個 ID 的速度持續產生數百年，也能輕易讓碰撞的機率比小行星撞擊地球的機率還要低數十億倍。如果這樣的餘裕對你來說還不夠，只要再增加位元數，就能輕易讓 ID 空間大到超過宇宙中的原子總數。

這種產生方式有一個很大的優點：它是完全無狀態的。多個節點可以同時產生 ID，而無需交換訊息。此外，也沒有任何東西需要儲存到磁碟，因此我們可以跑到 CPU 速度的極限。運算也能輕易在 CPU 快取中完成。所以它非常快速又方便。

麥克·馬隆當時就是運用這個想法，利用 PRNG 來建立由一組字元組成的 ID，其中每個字元都是 64 種可能字元之一。為了產生每個字元，他使用了有缺陷的 V8 PRNG，因而導致了碰撞。請記得，我們最初的假設是每個新 ID 都必須在 0 到 N 的空間中被均勻地選出。

你可以透過使用更強大的 PRNG 來修正這個問題，但這需要對 PRNG 進行分析。另一個問題是 seeding(播種)，重新啟動後，你要如何再次啟動行程，以確保不會再次選到 PRNG 的初始狀態？否則，你真正的 ID 空間會受限於 PRNG 的 seeding，而非其輸出空間本身。

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

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

Cryptographic hash function(密碼雜湊函式) 是不可逆的函式，能將一串位元轉換成固定長度的位元序列。它們被設計用來抵禦各種攻擊，不過在這個應用中，我們只仰賴它們所具備的一項特性：輸出的均勻性。改變 hash function 輸入的一個位元，會使輸出的每一個位元都有 50% 的機率跟著改變。

為了擁有可靠的 seed(種子)，我們會藉助作業系統，透過查詢 /dev/urandom 來取得。在為產生器進行 seeding 時，正是我們非常需要外部熵的時刻，否則我們真的有可能犯下嚴重的錯誤，再次產生相同的序列。

作為 crypto hash function 的一個範例，我們將使用眾所周知的 SHA1，其輸出為 160 位元。請注意，你甚至可以在這個應用中使用 MD5 總和：它所具有的弱點在我們此處的用途中不會造成任何影響。

我們先建立一個 seed，方法是從 /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

基本上，我們有一個固定的字串，也就是我們的 seed，並將它與一個遞增的計數器一起進行雜湊，因此如果我們的 seed 是「foo」，我們輸出的新 ID 就會是：

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

這對我們的使用情境來說已經很好了。不過，我們可能還需要讓 ID 不易被預測。為了讓 ID 變得非常難以預測，與其在 get_new_id() 函式中使用 SHA1，不如改用 SHA1_HMAC()，其中 seed 是密鑰，而 counter 則是 HMAC 的訊息。

這個方法速度很快，能保證良好的分布，因此碰撞的難度將如 birthday paradox 所預測的那般困難，無需對 PRNG 進行分析，而且是完全無狀態的。

我在我的 Disque 專案中使用它，以便在分散式系統的多個節點之間產生訊息 ID。

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