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.8 納秒），但維護著近 5 千位元組的內部狀態。相比之下，Melissa O’Neill 的PCG 生成器家族以約 2.1 納秒每數的速度生成更好的隨機數，並且內部狀態只有 16 位元組。我們還想探索使用 Daniel J. Bernstein 的ChaCha 流密碼作為生成器。一篇後續博文專門討論該生成器。

Source 介面

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這樣的頂層函式可以同時從多個 goroutines 呼叫，因此實現需要一個鎖來保護共享的生成器狀態。在並行使用中，獲取和釋放這個鎖比實際生成要昂貴。更好的做法是擁有一個每執行緒的生成器狀態，但這會破壞在沒有併發使用 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.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 也實現 io.Reader 介面，並新增一個頂層 Read 函式。當時這看起來很合理，但回想起來，我們沒有充分關注這一更改的軟體工程方面。現在，如果您想讀取隨機資料，您有兩種選擇：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。儘管考慮到我們對輸出流可重複性的關注，這可能看起來像一個不相容的更改，但我們認為，任何在 init 時間或任何計算內部呼叫rand.Int的匯入包也會明顯改變輸出流，而且新增或移除這樣的呼叫肯定不能被視為破壞性更改。如果這是真的，那麼自動播種也不會更糟，並且它將消除未來程式的這種脆弱性來源。我們還添加了一個GODEBUG 設定以選擇回到舊的行為。然後我們將頂層 rand.Seed 標記為已棄用。（需要播種可重複性的程式仍然可以使用 rand.New(rand.NewSource(seed)) 來獲得本地生成器，而不是使用全域性生成器。）

• 消除了全域性輸出流的可重複性後，Go 1.20 還能夠在不呼叫 rand.Seed 的程式中提高全域性生成器的可伸縮性，用 Go 執行時內部已經使用的非常廉價的每執行緒wyrand 生成器替換了 Go 1 生成器。這移除了全域性互斥鎖，使頂層函式的伸縮性大大提高。呼叫 rand.Seed 的程式則回退到受互斥鎖保護的 Go 1 生成器。

• 我們能夠在 Go 執行時中採用 Lemire 的最佳化，並且還在 rand.Shuffle 中使用了它，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 介面，將 Int63 方法替換為 Uint64 方法，並刪除了 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 生成器。