Go 部落格

以 math/rand/v2 來開發進化的 Go 標準函式庫

Russ Cox
2024 年 5 月 1 日

自 Go 1 於 2012 年 3 月發布 以來，標準函式庫的變更受到 Go 相容性保證 的約束。整體而言，相容性一直是 Go 使用者的一大福音，為生產系統、文件、教學課程、書籍等等提供了穩定的基礎。然而，隨著時間推移，我們發現原始 API 中無法相容修正的錯誤；在其他情況下，最佳實務和慣例已有所改變。我們需要一個計畫來進行重大變更（不保持相容性）。

這篇部落格文章是關於 Go 1.22 中新的 math/rand/v2 套件，這是標準函式庫中的第一個「v2」。它為 math/rand API 引進了必要的改進，但更重要的是，它為我們在需要時修改其他標準函式庫套件樹立了典範。

（在 Go 中，math/rand 和 math/rand/v2 是兩個不同的套件，具有不同的匯入路徑。Go 1 及其之後的每個發行版都包含 math/rand；Go 1.22 新增了 math/rand/v2。Go 程式可以匯入任一套件，或兩者都匯入。）

這篇文章討論了 math/rand/v2 中變更的具體依據，然後 回顧將引導其他套件新版本的一般原則。

偽亂數產生器

在我們探討 math/rand（一個偽亂數產生器的 API）之前，讓我們花點時間了解這是什麼意思。

一個偽亂數產生器是一個確定性程式，從一個小的種子輸入產生看似隨機數字的長序列，儘管這些數字實際上根本不隨機。在 math/rand 的情況下，種子是一個整數 int64，演算法會使用 線性回饋移位暫存器 (LFSR) 的變形產生一個 int64 序列。演算法基於 George Marsaglia 的構想，由 Don Mitchell 和 Jim Reeds 微調，Ken Thompson 進一步根據 Plan 9 和 Go 客製化。它沒有正式的名稱，因此這篇文章稱它為 Go 1 產生器。

這些產生器的目標是快速、可重複且具有足夠的隨機性以支援模擬、洗牌和其他非密碼學用例。對於像是數值模擬或隨機測試這樣的用途，可重複性尤其重要。例如，一個隨機測試器可能會選擇一個種子（可能基於目前的時間），產生一個大型的隨機測試輸入，並重複。當測試器發現一個失敗時，它只需要印出種子，就能用那個特定的大きな輸入重複測試。

重複性在時間上也很重要：在給定特定種子的情況下，新版本的 Go 需要產生與舊版本相同的值序列。當我們發布 Go 1 時，我們並沒有意識到這一點；相反地，我們以困難的方式發現了這一點，當我們嘗試在 Go 1.2 中進行更改時，收到了我們已中斷某些測試和其他用例的報告。在那個時候，我們決定 Go 1 相容性包括給定種子的特定隨機輸出，並 新增一個測試。

對於這類型的產生器，產生適合作為密碼金鑰或其他重要機密之隨機數並非其目標。由於種子僅有 63 位元長，因此無論產生器產生的輸出有多長，其也只會包含 63 位元的熵。例如，使用 math/rand 產生 128 位元或 256 位元的 AES 金鑰會是一個嚴重的錯誤，因為這種金鑰較容易透過暴力破解。對於此類用途，您需要一個密碼學上強大的隨機數產生器，例如 crypto/rand 所提供的服務。

這些背景知識已足夠讓我們繼續探討 math/rand 套件中需要修復的內容。

math/rand 的問題

隨著時間的推移，我們發現 math/rand 的問題越來越多。最嚴重的問題如下。

產生器演算法

產生器本身需要更換。

Go 的原始實作雖然已準備投入生產，但在許多方面僅是整個系統的「鉛筆素描」，功能足以作為未來開發的基礎：編譯器和執行階段程式碼是用 C 所撰寫的；垃圾收集器是保守的、單執行緒、停止世界的垃圾收集器；而程式庫在整體上採用基本的實作方式。從 Go 1 到 Go 1.5 左右，我們回頭繪製這些部分的「完全著墨」版本：我們將編譯器和執行階段程式碼轉換成 Go；我們撰寫了一個新的精準、並行、執行緒安全的垃圾收集器，具有微秒級的暫停時間；並根據需要以更精緻、最佳化的演算法取代標準程式庫的實作。

遺憾的是，math/rand 中的可重複性需求表示我們無法更換產生器，否則會破壞相容性。我們被困在 Go 1 產生器中，它的速度相當快（在我的 M3 Mac 上每產生一個數字約 1.8ns），但維護著幾乎 5 千位元組的內部狀態。相對地，Melissa O’Neill 的 PCG 產生器系列 每個數字的執行時間約 2.1ns，但僅有 16 位元組的內部狀態，而且能產生更佳的隨機數。我們也想嘗試使用 Daniel J. Bernstein 的 ChaCha 串流密碼 作為產生器。一則 後續文章 特別探討這種產生器。

資源介面

rand.Source 介面是錯誤的。該介面定義一種產生非負 int64 值的低階隨機數產生器概念

% go doc -src math/rand.Source
package rand // import "math/rand"

// A Source represents a source of uniformly-distributed
// pseudo-random int64 values in the range [0, 1<<63).
//
// A Source is not safe for concurrent use by multiple goroutines.
type Source interface {
    Int63() int64
    Seed(seed int64)
}

func NewSource(seed int64) Source
%

(在說明文件註解中，「[0, N)」表示 半開區間，表示範圍包含 0，但在 2⁶³ 之前結束。)

rand.Rand 類型包裝一個 Source 以實作更豐富的操作組，例如產生 0 到 N 之間的整數，產生 浮點數，等等。

我們定義 Source 介面回傳一個縮短的 63 位元值，而不是 uint64，因為那是 Go 1 產生器和其他廣泛使用的產生器所產生的，而且這符合 C 標準程式庫所設定的慣例。但這是一個錯誤：較現代的產生器會產生全寬的 uint64，那是更便利的介面。

另一個問題是 Seed 方法硬編碼一個 int64 種子：有些產生器會被更大的值做為種子，而且這個介面並沒有提供處理這件事的方法。

種子責任

Seed 有個更大的問題，那就是對全域產生器做種子的責任不明確。大多數使用者並沒有直接使用 Source 和 Rand。相反地，math/rand 套件提供了一個全域產生器，可由頂層函式存取，例如 Intn。遵循 C 標準程式庫，全域產生器預設在啟動時執行 Seed(1) 的行為。這對可重複性來說很好，但對於想要讓他們的隨機輸出在每次執行時都不一樣的程式來說很不好。套件文件建議在這種情況下使用 rand.Seed(time.Now().UnixNano())，讓產生器的輸出取決於時間，但哪個程式碼應該這麼做？

math/rand 的種子很可能應該由主程式包負責：如果導入的程式庫自己設定全域狀態，是很不幸的，因為他們的選擇可能會與其他程式庫或主程式包發生衝突。但是，如果一個程式庫需要一些隨機資料，而且想要使用 math/rand 呢？如果主程式包甚至不知道 math/rand 正在被使用呢？我們發現，在實務上許多程式庫都會加入 init 函式，使用目前時間為全域產生器做種子，「以策安全」。

程式庫套件自己為全域產生器做種子會造成一個新問題。假設主程式包導入了兩個都使用 math/rand 的套件：套件 A 認為全域產生器會由主程式包做種子，但套件 B 在 init 函式中為其做種子。而且假設主程式包沒有自己為產生器做種子。現在，套件 A 正確的運作取決於一個巧合，也就是套件 B 也被程式導入了。如果主程式包停止導入套件 B，套件 A 就會停止取得隨機值。我們在實務上觀察到這件事發生在大型的程式碼庫中。

回顧過去，遵循 C 標準程式庫顯然是一個錯誤：自動為全域產生器做種子會消除由誰做種子的混淆，而且當使用者不想要可重複的輸出時，使用者就不會再因為可重複的輸出而感到驚訝了。

可擴充性

整體發生器擴充性也不夠。由於諸如 rand.Intn 的頂層函式可以同時從多個 goroutine 呼叫，因此實作需要鎖住來保護共用發生器狀態。在平行使用中，取得和釋放這個鎖的成本高於實際發生。取而代之的是每個執行緒有各自的發生器狀態才合理，但這麼做會破壞沒有同時使用 math/rand 程式中的可重複性。

Rand 實作缺少重要的最佳化

rand.Rand 類型 封裝一個 `Source` 來實作更多功能。舉例來說，以下為 Go 1 實作的 `Int63n`，會傳回 [0, n) 範圍內的隨機整數。

func (r *Rand) Int63n(n int64) int64 {
    if n <= 0 {
        panic("invalid argument to Int63n")
    }
    max := int64((1<<63 - 1)  - (1<<63)%uint64(n))
    v := r.src.Int63()
    for v > max {
        v = r.Int63()
    }
    return v % n
}

實際轉換很容易：v % n。不過，除非 2⁶³ 是 n 的倍數，否則沒有演算法能將 2⁶³ 個機率相等的數值轉換為 n 個機率相等的數值：否則某些輸出勢必比其他輸出更常出現。（用一個簡單的例子來說，試試把 4 個機率相等的數值轉換成 3 個。）這個程式碼會計算出一個 max 值，使得 max+1 是小於或等於 2⁶³ 的最大 `n` 倍數，然後迴圈會移除大於或等於 max+1 的隨機數。移除這些太大的數值可以確保所有 n 個輸出機率相等。對於較小的 n，幾乎不需要移除任何數值；移除動作會隨著數值變大而變得更常見且更重要。就算沒有移除迴圈，兩個（緩慢的）模數運算也會讓轉換比原本產生隨機數值 v 更耗效能。

在 2018 年，Daniel Lemire 找到了一個演算法，幾乎可以在所有情況下避免除法（請同時參閱他在 2019 年的部落格文章）。在 math/rand 中，採用 Lemire 的演算法會讓 `Intn(1000)` 快上 20-30%，但我們不能這麼做，因為採用較快速的演算法會產生和標準轉換不同的數值，造成可重複性的問題。

其他方法的執行速度也比可能的速度還要慢，這是受到可重複性的限制所致。舉例來說，如果我們可以變更產生的數值串流，那麼 Float64 方法的執行速度便可以輕易地加快約 10%。（這是我們在 Go 1.2 中嘗試變更，但之後又還原的動作，前面已經提過。）

Read 錯誤

如同之前提過的，math/rand 沒有要產生密碼金鑰，也不適合產生密碼金鑰。crypto/rand 套件可以用來進行此動作，其基本原語為 Read 函式 和 Reader 變數。

2015 年，我們接受了使 rand.Rand 連同新增頂層 Read 函式的實作 io.Reader 的建議。當時看來這似乎很合理，但回顧起來我們沒有對此變更的軟體工程層面給予足夠的關注。現在，如果你想要讀取隨機資料，你有兩個選擇：math/rand.Read 和 crypto/rand.Read。如果資料將用於金鑰資料，使用 crypto/rand 非常重要，但現在有可能誤用 math/rand，而潛在造成毀滅性的後果。

諸如 goimports 及 gopls 等工具有一個特殊案例，確保優先使用 crypto/rand 中的 rand.Read，而非 math/rand，但這並不是一個完整的修正。移除 Read 會更好。

直接修正 math/rand

對套件建立一個新且不相容的主要版本從來都不是我們的首選：新版本只會對切換至新版本的程式帶來好處，卻會讓舊版主要版本的所有既有使用方式不再適用。相反地，修正既有套件中的問題會產生更大的影響，因為它可以修正所有既有的使用方式。在尚未盡可能修正 v1 的情況下，我們絕對不應該建立 v2。就 math/rand 而言，我們能夠部分地解決上文所述的幾個問題。

• Go 1.8 引入了選用的Source64 介面，其中包含一個 Uint64 方法。如果 Source 也實作 Source64，則 Rand 會在適當時機使用該方法。這種「延伸介面」模式可提供一個相容（雖然有點彆扭）的方式在事後調整介面。

• Go 1.20 自動對頂層產生器設定種子和取消支援 rand.Seed。儘管考量到我們的焦點在於輸出串流的可重複性，這可能看似是無法相容的變更，但 我們推論，在初始化時機或任何運算中呼叫 rand.Int 的任何匯入套件也都會明顯改變輸出串流，而且新增或移除這樣的呼叫肯定不能被視為重大變更。而如果這是對的，那麼自動設定種子並不會更糟，而且會為將來的程式消除這項易碎性來源。我們也新增了一個 GODEBUG 設定 來選擇回到舊有行為。然後我們將頂層的 rand.Seed 標記為 已取消支援。（需要設定種子可重複性的程式仍然可以使用 rand.New(rand.NewSource(seed)) 來取得一個本機產生器，而非使用全域產生器。）

• 在消除全局輸出串流的可重複性後，Go 1.20 也能使不呼叫 rand.Seed 的程式中的全局產生器具有更佳的可擴充性，以現有的便宜 per-thread wyrand 產生器 取代 Go 1 產生器，該產生器已在 Go 執行期內使用。這移除了全球互斥體，使頂層函數能以更佳方式擴充。呼叫 rand.Seed 的程式則採用受互斥體保護的 Go 1 產生器。

• 我們能在 Go 執行期中採用 Lemire 的最佳化，並在 rand.Shuffle 中使用，這是 Lemire 的論文發表後實作的。

• 雖然我們無法完全移除 rand.Read，Go 1.20 標記為 已棄用 以利於 crypto/rand。我們已聽聞有人發現他們在密碼內容中意外使用 math/rand.Read 是他們的編輯器標示出已棄用函數的使用時。

這些修正不完美且不完整，但也是真實的進步，有助於協助所有現有 math/rand 套件使用者。為了更完整的修正，我們需要將注意力轉移到 math/rand/v2。

修正 math/rand/v2 中的其餘問題

定義 math/rand/v2 需要大量的規劃，接著是 GitHub 討論，然後是 提議討論。它與 math/rand 相同，其中的重大變更會針對上述提及的問題進行調整

• 我們完全移除 Go 1 產生器，並用兩個新產生器，PCG 和 ChaCha8 取代。新類型是用他們的演算法命名的（避免使用通用名稱 NewSource），因此如果需要新增其他重要的演算法，會適當地符合命名慣例。

  採用提議討論中的建議，新的類型實作 encoding.BinaryMarshaler 和 encoding.BinaryUnmarshaler 介面。

• 我們變更 Source 介面，並用 Uint64 方法替換 Int63 方法，並刪除 Seed 方法。支援種子的實作可以提供其自己的具體方法，例如 PCG.Seed 和 ChaCha8.Seed。請注意，這兩者採用不同的種子類型，而兩者都不是單一的 int64。

• 我們已移除最上層的 Seed 函式：目前只能在自動種子形式中使用 Int 等全域函式。

• 移除最上層的 Seed 也使我們將可擴充、每個執行緒產生器的使用硬性編碼到最上層的方法，避免在每次使用時檢查 GODEBUG。

• 我們已為 Intn 和相關函式實作 Lemire 的最佳化。具體的 rand.Rand API 現在已鎖定到該值串流，因此我們將無法利用任何尚未發現的最佳化，但至少我們又更新一次。我們還實作想要在 Go 1.2 中使用的 Float32 和 Float64 最佳化。

• 在建議討論期間，一位貢獻者指出 ExpFloat64 和 NormFloat64 實現中可偵測到的偏差。我們已修正該偏差並鎖定新的值串流。

• Perm 和 Shuffle 使用不同的改組演算法並產生不同的值串流，因為 Shuffle 排在第二個，而且使用較快的演算法。完全刪除 Perm 會讓使用者較難進行轉移。反之，我們用 Shuffle 的方式實作 Perm，這仍然讓我們可以刪除實作。

• 我們已將 Int31、Int63、Intn、Int31n 和 Int63n 改名為 Int32、Int64、IntN、Int32N 和 Int64N。名稱中的 31 和 63 過於繁瑣，容易混淆，而大寫的 N 在 Go 的名稱中更像是一個第二個「字」。

• 我們已新增 Uint、Uint32、Uint64、UintN、Uint32N 和 Uint64N 最上層函式與方法。我們需要新增 Uint64 以提供對核心 Source 功能的直接存取，而且不新增其他功能會顯得不一致。

• 根據建議討論中的另一個建議，我們已新增一個新的最上層共用函式 N，它類似於 Int64N 或 Uint64N，但適用於任何整數型別。在舊的 API 中，若要建立最長 5 秒的隨機時間長度，必須寫入

  d := time.Duration(rand.Int63n(int64(5*time.Second)))
  

  使用 N，等效的程式碼為

  d := rand.N(5 * time.Second)
  

  N 僅為最上層函式；rand.Rand 上沒有 N 方法，因為 Go 中沒有共用方法。（在未來也可能不會有共用方法；它們與介面衝突嚴重，而且完整的實作需要執行時間的程式碼產生或緩慢執行。

• 為了改善在加密環境中錯誤使用 math/rand，我們已讓 ChaCha8 成為全域函式中使用的預設產生器，並且也已變更 Go 執行時期以使用它（取代 wyrand）。我們仍然強烈建議程式使用 crypto/rand 產生加密機密，但意外使用 math/rand/v2 並沒有像使用 math/rand 那麼具災難性。即使在 math/rand 中，當未明確設定種子時，全域函式也會使用 ChaCha8 產生器。

Go 標準程式庫進化原則

如同這篇文章開頭所述，這項工作的目標之一是建立原則和方法，說明我們如何處理標準函式庫中的所有 v2 套件。在接下來的幾個 Go 版本中，不會大量出現 v2 套件。相反地，我們會一次處理一個套件，確保我們設定的品質標準將延續十年之久。許多套件根本不需要 v2。但對於那些需要的套件，我們的作法歸結為三個原則。

首先，套件的新不相容版本將會使用 that/package/v2 作為其匯入路徑，遵循 語義匯入版本控制，就像標準函式庫外的 v2 模組一樣。這允許原始套件和 v2 套件同時存在於同一個程式中，這對於 逐漸轉換 至新 API 至關重要。

其次，所有變更都必須基於對現有用法和使用者群的尊重：我們不能夠引入多餘的波動，無論是以不必要的變更到現有套件的形式，或者必須另外學習全新套件的形式。在實際操作中，這表示我們以現有套件為起點，只進行有充分動機的變更，並且提供足以證明使用者更新成本合理的價值。

第三，v2 套件不能遺棄 v1 使用者。理想情況下，v2 套件應當能夠做 v1 套件所有能做的事情，並且當 v2 發佈時，v1 套件應當改寫成 v2 的一個精簡封裝。這將確保 v1 的現有用法持續受益於 v2 中的臭蟲修復和效能最佳化。當然，由於 v2 會引入破壞性變更，這並不總是可行，但這永遠都是需要仔細考量的事情。對於 math/rand/v2，我們安排自動種子 v1 函數來呼叫 v2 產生器，但由於重複性違反，我們無法分享其他程式碼。歸根究底，math/rand 並沒有太多程式碼，且不需要定期維護，因此可以管理重複。在其他情況，投入更多工作來避免重複可能是值得的。例如，在 encoding/json/v2 設計（仍在進行中） 中，儘管預設語意和 API 有變更，但套件提供設定旋鈕，讓實作 v1 API 成為可能。當我們最終發布 encoding/json/v2，encoding/json (v1) 將會變成它的精簡封裝，確保沒有從 v1 中遷移的使用者仍然可以從 v2 中的最佳化和安全性修復中受益。

後續部落格文章更詳細介紹 ChaCha8 產生器。