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で書かれていました。ガベージコレクタは、保守的でシングルスレッドのストップ・ザ・ワールドコレクタでした。そして、ライブラリは全体的に基本的な実装を使用していました。Go 1からGo 1.5頃まで、私たちはこれらのそれぞれの「完全にインクで描かれた」バージョンに戻り、コンパイラとランタイムをGoに変換し、マイクロ秒の一時停止時間を持つ新しい正確で並列な同時ガベージコレクションを作成し、必要に応じて標準ライブラリの実装をより洗練された最適化されたアルゴリズムに置き換えました。

残念ながら、math/randにおける再現性要件は、互換性を損なわずにジェネレーターを置き換えることができないことを意味しました。私たちはGo 1ジェネレーターに固執することになりました。これは合理的に高速ですが（私のM3 Macでは1桁あたり約1.8ナノ秒）、約5キロバイトの内部状態を維持します。対照的に、Melissa O'NeillのPCGファミリーのジェネレーターは、わずか16バイトの内部状態でおよそ1桁あたり2.1ナノ秒でより良い乱数を生成します。また、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までの整数を生成したり、浮動小数点数を生成したりするなど、より豊富な操作セットを実装します。

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

もう一つの問題は、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はグローバルジェネレーターがパッケージmainによってシードされると仮定していますが、パッケージBはinit関数でシードしています。そして、パッケージmainがジェネレーター自体をシードしないとします。今やパッケージAの正しい動作は、パッケージBもプログラムにインポートされているという偶然に依存しています。もしパッケージmainがパッケージBのインポートを停止すると、パッケージAはランダム値を取得できなくなります。大規模なコードベースで実際にこの現象が発生しているのを目撃しました。

振り返ってみると、ここでC標準ライブラリに従ったのは明らかに間違いでした。グローバルジェネレーターを自動的にシードすることで、誰がシードするのかという混乱が解消され、ユーザーは意図しないときに再現性のある出力に驚くことがなくなるでしょう。

スケーラビリティ

グローバルジェネレーターもスケーリングがうまくいきませんでした。rand.Intnのようなトップレベル関数は複数のゴルーチンから同時に呼び出される可能性があるため、実装には共有ジェネレーター状態を保護するロックが必要でした。並列使用では、このロックの取得と解放は実際の生成よりもコストがかかりました。代わりにスレッドごとのジェネレーター状態を持つのが理にかなっていますが、そうすると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+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年に、rand.Randもio.Readerを実装するようにし、合わせてトップレベルのRead関数を追加する提案を受け入れました。当時は妥当に見えましたが、振り返ってみると、この変更のソフトウェアエンジニアリング的側面に十分な注意を払っていませんでした。現在、ランダムデータを読み込む場合、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を非推奨にしました。出力ストリームの再現性に焦点を当てていることを考えると、これは互換性のない変更のように見えるかもしれませんが、私たちは、init時または計算内で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が後から実装され、より高速なアルゴリズムを使用していたためです。Permを完全に削除すると、ユーザーの移行が難しくなる可能性がありました。代わりに、PermをShuffleをベースに実装することで、実装を削除できるようにしました。
Int31、Int63、Intn、Int31n、Int63nを、それぞれInt32、Int64、IntN、Int32N、Int64Nに改名しました。名前に含まれる31と63は不必要に専門的で分かりにくく、大文字の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)))
```
Nを使うと、同等のコードはこうなります。
```
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標準ライブラリを進化させるための原則

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

まず、パッケージの新しい、互換性のないバージョンは、標準ライブラリ外のv2モジュールと同様に、意味的インポートバージョニングに従って、that/package/v2をインポートパスとして使用します。これにより、元のパッケージとv2パッケージの両方を1つのプログラムで共存させることができ、新しい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年上半期結果
ブログインデックス