The Go Blog

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 は、異なるインポートパスを持つ 2 つの異なるパッケージです。Go 1 とそれ以降のすべてのリリースには math/rand が含まれています。Go 1.22 で math/rand/v2 が追加されました。Go プログラムはどちらのパッケージも、あるいは両方ともインポートできます。)

この投稿では、math/rand/v2 の変更の具体的な根拠について説明し、次に他のパッケージの新しいバージョンを導く一般的な原則を考察します。

擬似乱数生成器

擬似乱数生成器の API である math/rand を見ていく前に、それが何を意味するのかを理解しておきましょう。

擬似乱数生成器は、小さなシード入力から一見ランダムな数の長いシーケンスを生成する決定論的なプログラムですが、実際にはこれらの数はまったくランダムではありません。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 で記述され、ガベージコレクターは保守的なシングルスレッドの stop-the-world コレクターであり、ライブラリは全体を通して基本的な実装を使用していました。Go 1 から Go 1.5 あたりまで、これらのそれぞれを「完全にインクを塗った」バージョンに書き直しました。コンパイラとランタイムを Go に変換し、新しい正確で並列な、同時ガベージコレクションをマイクロ秒のポーズ時間で記述し、標準ライブラリの実装を必要に応じてより洗練された最適化されたアルゴリズムに置き換えました.

残念ながら、math/rand の再現性の要件により、互換性を損なうことなくジェネレーターを交換することができませんでした。Go 1 ジェネレーターに固執していましたが、これは reasonably 高速です (私の M3 Mac では数値あたり約 1.8ns) が、ほぼ 5 キロバイトの内部状態を維持しています。対照的に、Melissa O'Neill のPCG ジェネレーターファミリは、わずか 16 バイトの内部状態の数値あたり約 2.1ns で、より優れた乱数を生成します。また、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 までの整数の生成、浮動小数点数の生成など、より豊富な操作セットを実装します。

Go 1 ジェネレーターや他の広く使用されているジェネレーターが生成するものであり、C 標準ライブラリによって設定された規則と一致するため、Source インターフェースを uint64 ではなく短縮された 63 ビット値を返すように定義しました。しかし、これは間違いでした。最新のジェネレーターは、より便利なインターフェースであるフル幅の uint64 を生成します。

もう 1 つの問題は、Seed メソッドが int64 シードをハードコーディングしていることです。一部のジェネレーターはより大きな値によってシードされ、インターフェースはその処理方法を提供していません.

シードの責任

Seed のより大きな問題は、グローバルジェネレーターのシードの責任が不明確だったことです。ほとんどのユーザーは Source と Rand を直接使用しません。代わりに、math/rand パッケージは、Intn などのトップレベル関数によってアクセスされるグローバルジェネレーターを提供します。C 標準ライブラリに従って、グローバルジェネレーターは、起動時に Seed(1) が呼び出されたかのように動作するようにデフォルト設定されています。これは再現性には適していますが、出力の実行ごとに異なるようにしたいプログラムには適していません。パッケージドキュメントでは、その場合は rand.Seed(time.Now().UnixNano()) を使用して、ジェネレーターの出力を時間依存にすることを提案していますが、どのコードがこれを行うべきでしょうか？

おそらく、メインパッケージが math/rand のシード方法を担当する必要があります。インポートされたライブラリがグローバル状態を自分で設定するのは、他のライブラリやメインパッケージの選択と競合する可能性があるため、適切ではありません。しかし、ライブラリがランダムデータを必要とし、math/rand を使用したい場合はどうでしょうか？メインパッケージが math/rand が使用されていることさえ知らない場合はどうでしょうか？実際には、多くのライブラリが「念のため」現在の時刻でグローバルジェネレーターをシードする init 関数を追加していることがわかりました。

ライブラリパッケージがグローバルジェネレーターを自分でシードすると、新しい問題が発生します。パッケージ main が math/rand を使用する 2 つのパッケージ A と B をインポートするとします。パッケージ A はグローバルジェネレーターがパッケージ main によってシードされると想定していますが、パッケージ B は init 関数でシードします。また、パッケージ main がジェネレーター自体をシードしないとします。 अब पैकेज A का सही संचालन इस संयोग पर निर्भर करता है कि पैकेज B को भी प्रोग्राम में इम्पोर्ट किया गया है। यदि पैकेज main पैकेज B को इम्पोर्ट करना बंद कर देता है, तो पैकेज A को रैंडम वैल्यू मिलना बंद हो जाएगा। हमने बड़े कोडबेस में व्यवहार में ऐसा होते देखा है।

振り返ってみると、ここで C 標準ライブラリに従ったのは明らかに間違いでした。グローバルジェネレーターを自動的にシードすると、誰がシードするかについての混乱がなくなり、ユーザーは望まないときに再現可能な出力に驚くことがなくなります.

スケーラビリティ

グローバルジェネレーターも十分にスケールしませんでした。rand.Intn などのトップレベル関数は複数のゴルーチンから同時に呼び出すことができるため、実装では共有ジェネレーター状態を保護するロックが必要でした。並列使用では、このロックの取得と解放は、実際の生成よりもコストがかかりました。代わりに、スレッドごとのジェネレーター状態を持つ方が理にかなっていますが、そうすると、math/rand を同時使用しないプログラムでは再現性が損なわれます.

`Rand` 実装に重要な最適化が欠けていました

rand.Rand 型は、Source をラップして、より豊富な操作セットを実装します。たとえば、[0, n) の範囲のランダムな整数を返す Int63n の Go 1 実装を次に示します。

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+1が2⁶³以下のnの最大の倍数になるようにmaxを計算し、ループはmax+1以上の乱数を拒否します。これらの大きすぎる値を拒否することで、n個のすべての出力が等確率になることが保証されます。nが小さい場合、値を拒否する必要があることはまれです。拒否は、値が大きくなるほど一般的になり、重要になります。拒否ループがなくても、2つの（遅い）剰余演算により、変換は乱数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年に、トップレベルのRead関数を追加することに加えて、rand.Randにio.Readerを実装させる提案を受け入れました。これは当時合理的と思われましたが、振り返ってみると、この変更のソフトウェアエンジニアリングの側面に十分な注意を払っていませんでした。現在、ランダムデータを読み取るには、math/rand.Readとcrypto/rand.Readの2つの選択肢があります。データが鍵素材に使用される場合、crypto/randを使用することが非常に重要ですが、代わりにmath/randを使用することが可能になり、潜在的に壊滅的な結果をもたらす可能性があります。

goimportsやgoplsなどのツールには、math/randではなくcrypto/randのrand.Readを優先して使用することを保証するための特別なケースがありますが、それは完全な解決策ではありません。Readを完全に削除する方が良いでしょう。

`math/rand`を直接修正する

パッケージの互換性のない新しいメジャーバージョンを作成することは、決して私たちの最初の選択肢ではありません。その新しいバージョンは、それに切り替えたプログラムにのみメリットをもたらし、古いメジャーバージョンの既存のすべての使用法はそのまま残されます。対照的に、既存のパッケージの問題を修正すると、既存のすべての使用法が修正されるため、はるかに大きな影響があります。v1を可能な限り修正せずにv2を作成するべきではありません。math/randの場合、上記の問題の一部に部分的に対処することができました。

Go 1.8では、Uint64メソッドを持つオプションのSource64インターフェースが導入されました。SourceがSource64も実装している場合、Randは適切な場合にそのメソッドを使用します。この「拡張インターフェース」パターンは、事後にインターフェースを改訂するための互換性のある（少しぎこちない場合もありますが）方法を提供します。
Go 1.20はトップレベルジェネレーターを自動的にシードし、rand.Seedを非推奨にしました。出力ストリームの再現性に焦点を当てていることを考えると、これは互換性のない変更のように思えるかもしれませんが、私たちは、初期化時または計算内でrand.Intを呼び出したインポートされたパッケージは出力ストリームも目に見えるように変更し、そのような呼び出しの追加または削除は重大な変更とは見なされないはずです。そして、それが事実であれば、自動シードはさらに悪くはなく、将来のプログラムにとってこの脆弱性の原因を排除します。また、GODEBUG設定を追加して、古い動作に戻すこともできます。その後、トップレベルのrand.Seedを非推奨としてマークしました。（シードされた再現性が必要なプログラムは、グローバルなものを使用する代わりに、rand.New(rand.NewSource(seed))を使用してローカルジェネレーターを取得できます。）
グローバル出力ストリームの再現性を排除したため、Go 1.20は、rand.Seedを呼び出さないプログラムでグローバルジェネレーターのスケーラビリティを向上させ、Go 1ジェネレーターをGoランタイム内で既に使用されている非常に安価なスレッドごとのwyrandジェネレーターに置き換えることもできました。これにより、グローバルミューテックスが削除され、トップレベル関数のスケーラビリティが大幅に向上しました。rand.Seedを呼び出すプログラムは、ミューテックスで保護されたGo 1ジェネレーターにフォールバックします。
GoランタイムでLemireの最適化を採用することができ、Lemireの論文が発表された後に実装されたrand.Shuffle内でも使用しました。
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ジェネレーターを完全に削除し、2つの新しいジェネレーター、PCGとChaCha8に置き換えました。新しい型は、アルゴリズムの名前が付けられています（汎用名`NewSource`は避けています）。そのため、別の重要なアルゴリズムを追加する必要がある場合、命名スキームによく適合します。

提案の議論からの提案を採用し、新しい型はencoding.BinaryMarshalerおよびencoding.BinaryUnmarshalerインターフェースを実装します。
Sourceインターフェースを変更し、`Int63`メソッドを`Uint64`メソッドに置き換え、`Seed`メソッドを削除しました。シードをサポートする実装は、PCG.SeedやChaCha8.Seedのように、独自の具体的なメソッドを提供できます。2つは異なるシード型を取り、どちらも単一の`int64`ではありません。
トップレベルの`Seed`関数を削除しました。`Int`などのグローバル関数は、自動シード形式でのみ使用できるようになりました。
トップレベルの`Seed`を削除することで、トップレベルメソッドによるスケーラブルなスレッドごとのジェネレーターの使用をハードコードできるようになり、使用ごとにGODEBUGチェックを回避できました。
`Intn`および関連関数にLemireの最適化を実装しました。具体的な`rand.Rand` APIは、その値ストリームにロックインされているため、まだ発見されていない最適化を利用することはできませんが、少なくとも再び最新の状態になります。また、Go 1.2で使用する予定だった`Float32`と`Float64`の最適化も実装しました.
提案の議論中に、貢献者は`ExpFloat64`と`NormFloat64`の実装における検出可能なバイアスを指摘しました。そのバイアスを修正し、新しい値ストリームをロックインしました。
`Perm`と`Shuffle`は異なるシャッフルアルゴリズムを使用し、異なる値ストリームを生成しました。これは、`Shuffle`が2番目に発生し、より高速なアルゴリズムを使用したためです。`Perm`を完全に削除すると、ユーザーの移行が難しくなります。代わりに、`Perm`を`Shuffle`で実装しました。これにより、実装を削除できます。
`Int31`、`Int63`、`Intn`、`Int31n`、`Int63n`の名前を`Int32`、`Int64`、`IntN`、`Int32N`、`Int64N`に変更しました。名前の31と63は不必要に pedantic で紛らわしく、大文字のNはGoの名前の2番目の「単語」にはより慣用的です.
`Uint`、`Uint32`、`Uint64`、`UintN`、`Uint32N`、`Uint64N`のトップレベル関数とメソッドを追加しました。コアの`Source`機能に直接アクセスできるようにするために`Uint64`を追加する必要があり、他の機能を追加しないのは一貫性がないように思われました。
提案の議論からの別の提案を採用し、`Int64N`または`Uint64N`と同様ですが、任意の整数型で機能する新しいトップレベルの汎用関数`N`を追加しました. 古いAPIでは、最大5秒のランダムな期間を作成するには、次のように記述する必要がありました。
```
d := time.Duration(rand.Int63n(int64(5*time.Second)))
```
（コード例省略）
```
d := rand.N(5 * time.Second)
```
`N`はトップレベル関数のみです。Goにはジェネリックメソッドがないため、`rand.Rand`には`N`メソッドはありません。（ジェネリックメソッドは将来もそうなる可能性は低いです。インターフェースとひどく競合し、完全な実装にはランタイムコード生成または遅い実行が必要です。）
暗号化コンテキストでの`math/rand`の誤用を改善するために、`ChaCha8`をグローバル関数で使用されるデフォルトのジェネレーターにし、Goランタイムもそれを使用するように変更しました（wyrandを置き換えます）。プログラムは、暗号化シークレットを生成するために`crypto/rand`を使用することを強くお勧めしますが、誤って`math/rand/v2`を使用しても、`math/rand`を使用する場合ほど壊滅的な結果にはなりません。`math/rand`でも、グローバル関数は、明示的にシードされていない場合は`ChaCha8`ジェネレーターを使用するようになりました。

Go標準ライブラリの進化のための原則

この投稿の冒頭で述べたように、この作業の目標の1つは、標準ライブラリのすべてのv2パッケージにどのようにアプローチするかについての原則とパターンを確立することでした。次のいくつかのGoリリースでは、v2パッケージが大量に発生することはありません。代わりに、一度に1つのパッケージを処理し、今後10年間続く品質基準を設定するようにします。多くのパッケージは、v2をまったく必要としません。しかし、必要なパッケージの場合、私たちのアプローチは3つの原則に要約されます。

まず、パッケージの互換性のない新しいバージョンは、標準ライブラリの外部にあるv2モジュールと同様に、セマンティックインポートバージョニングに従って、インポートパスとして`that/package/v2`を使用します。これにより、元の pakketと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ジェネレーターについてより詳細に説明しています。

次の記事：Go 1.22の安全な乱数
前の記事：Go開発者調査2024年上半期結果
ブログインデックス